[sysprof] memprof: add memory profiling using LD_PRELOAD
- From: Christian Hergert <chergert src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [sysprof] memprof: add memory profiling using LD_PRELOAD
- Date: Sat, 8 Feb 2020 03:01:10 +0000 (UTC)
commit 33c81a3a9ca4a2a40f5aeb35ae80d46751abffab
Author: Christian Hergert <chergert redhat com>
Date: Thu Jan 30 18:24:04 2020 -0800
memprof: add memory profiling using LD_PRELOAD
This brings over some of the techniques from the old memprof design.
Sysprof and memprof shared a lot of code, so it is pretty natural to
bring back the same callgraph view based on memory allocations.
This reuses the StackStash just like it did in memprof. While it
would be nice to reuse some existing tools out there, the fit of
memprof with sysprof is so naturally aligned, it's not really a
big deal to bring back the LD_PRELOAD. The value really comes
from seeing all this stuff together instead of multiple apps.
There are plenty of things we can implement on top of this that
we are not doing yet such as temporary allocations, cross-thread
frees, graphing the heap, and graphing differences between the
heap at to points in time. I'd like all of these things, given
enough time to make them useful.
This is still a bit slow though due to the global lock we take
to access the writer. To improve the speed here we need to get
rid of that lock and head towards a design that allows a thread
to request a new writer from Sysprof and save it in TLS (to be
destroyed when the thread exits).
meson.build | 21 +-
src/libsysprof-capture/sysprof-capture-cursor.c | 4 +
src/libsysprof-capture/sysprof-capture-reader.c | 49 +
src/libsysprof-capture/sysprof-capture-reader.h | 96 +-
src/libsysprof-capture/sysprof-capture-types.h | 42 +-
.../sysprof-capture-writer-cat.c | 18 +
src/libsysprof-capture/sysprof-capture-writer.c | 99 +
src/libsysprof-capture/sysprof-capture-writer.h | 324 ++--
src/libsysprof-ui/libsysprof-ui.gresource.xml | 1 +
src/libsysprof-ui/meson.build | 3 +
src/libsysprof-ui/sysprof-display.c | 4 +
src/libsysprof-ui/sysprof-memory-aid.c | 11 +-
src/libsysprof-ui/sysprof-memprof-aid.c | 226 +++
src/libsysprof-ui/sysprof-memprof-aid.h | 33 +
src/libsysprof-ui/sysprof-memprof-page.c | 1319 +++++++++++++
src/libsysprof-ui/sysprof-memprof-page.h | 51 +
src/libsysprof-ui/sysprof-memprof-page.ui | 232 +++
src/libsysprof-ui/sysprof-memprof-visualizer.c | 614 ++++++
src/libsysprof-ui/sysprof-memprof-visualizer.h | 33 +
src/libsysprof-ui/sysprof-profiler-assistant.c | 2 +
src/libsysprof-ui/sysprof-profiler-assistant.ui | 9 +
src/libsysprof-ui/sysprof-ui-private.h | 3 +
src/libsysprof/meson.build | 19 +
src/libsysprof/preload/meson.build | 16 +
src/libsysprof/preload/sysprof-memory-collector.c | 295 +++
src/libsysprof/rax.c | 1947 ++++++++++++++++++++
src/libsysprof/rax.h | 216 +++
src/libsysprof/rax_malloc.h | 43 +
src/libsysprof/sysprof-memprof-profile.c | 489 +++++
src/libsysprof/sysprof-memprof-profile.h | 53 +
src/libsysprof/sysprof-memprof-source.c | 77 +
src/libsysprof/sysprof-memprof-source.h | 35 +
src/libsysprof/sysprof.h | 2 +
src/tests/allocs-by-size.c | 147 ++
src/tests/cross-thread-frees.c | 137 ++
src/tests/memory-stack-stash.c | 90 +
src/tests/meson.build | 24 +
src/tests/show-page-usage.c | 196 ++
src/tests/test-capture.c | 62 +
src/tools/sysprof-cli.c | 9 +
src/tools/sysprof-dump.c | 13 +
41 files changed, 6844 insertions(+), 220 deletions(-)
---
diff --git a/meson.build b/meson.build
index 2d97c0a..13ef5a4 100644
--- a/meson.build
+++ b/meson.build
@@ -27,10 +27,12 @@ cc = meson.get_compiler('c')
cxx = meson.get_compiler('cpp')
config_h = configuration_data()
+config_h.set_quoted('API_VERSION_S', '@0@'.format(libsysprof_api_version))
config_h.set_quoted('PACKAGE_NAME', 'sysprof')
config_h.set_quoted('PACKAGE_VERSION', meson.project_version())
config_h.set_quoted('PACKAGE_STRING', 'sysprof-' + meson.project_version())
config_h.set_quoted('PACKAGE_BUGREPORT', 'https://bugzilla.gnome.org/enter_bug.cgi?product=sysprof')
+config_h.set_quoted('PACKAGE_LIBEXECDIR', join_paths(get_option('prefix'), get_option('libexecdir')))
config_h.set('PACKAGE_TARNAME', 'PACKAGE_STRING')
config_h.set('PACKAGE', 'PACKAGE_NAME')
config_h.set('VERSION', 'PACKAGE_VERSION')
@@ -83,6 +85,15 @@ config_h.set10('ENABLE_NLS', true)
config_h.set_quoted('PACKAGE_LOCALE_DIR', join_paths(get_option('prefix'), get_option('datadir'), 'locale'))
config_h.set('LOCALEDIR', 'PACKAGE_LOCALE_DIR')
+if cc.has_header('execinfo.h')
+ config_h.set10('HAVE_EXECINFO_H', true)
+endif
+
+libunwind_dep = dependency('libunwind-generic', required: false)
+if libunwind_dep.found()
+ config_h.set10('ENABLE_LIBUNWIND', libunwind_dep.found())
+endif
+
# Development build setup
config_h.set('DEVELOPMENT_BUILD', version_split[1].to_int().is_odd())
@@ -179,17 +190,17 @@ int main(void) {
error('Sysprof requires a C compiler with stdatomic support such as GCC 4.9 or newer')
endif
-configure_file(
- output: 'config.h',
- configuration: config_h
-)
-
subdir('src')
subdir('data')
subdir('examples')
subdir('help')
subdir('po')
+configure_file(
+ output: 'config.h',
+ configuration: config_h
+)
+
if get_option('enable_gtk')
meson.add_install_script('build-aux/meson/post_install.sh')
endif
diff --git a/src/libsysprof-capture/sysprof-capture-cursor.c b/src/libsysprof-capture/sysprof-capture-cursor.c
index d94569f..d2d014f 100644
--- a/src/libsysprof-capture/sysprof-capture-cursor.c
+++ b/src/libsysprof-capture/sysprof-capture-cursor.c
@@ -207,6 +207,10 @@ sysprof_capture_cursor_foreach (SysprofCaptureCursor *self,
delegate = READ_DELEGATE (sysprof_capture_reader_read_file);
break;
+ case SYSPROF_CAPTURE_FRAME_ALLOCATION:
+ delegate = READ_DELEGATE (sysprof_capture_reader_read_allocation);
+ break;
+
default:
if (!sysprof_capture_reader_skip (self->reader))
return;
diff --git a/src/libsysprof-capture/sysprof-capture-reader.c b/src/libsysprof-capture/sysprof-capture-reader.c
index 5bf03a1..4774e3f 100644
--- a/src/libsysprof-capture/sysprof-capture-reader.c
+++ b/src/libsysprof-capture/sysprof-capture-reader.c
@@ -1352,3 +1352,52 @@ sysprof_capture_reader_find_file (SysprofCaptureReader *self,
return NULL;
}
+
+const SysprofCaptureAllocation *
+sysprof_capture_reader_read_allocation (SysprofCaptureReader *self)
+{
+ SysprofCaptureAllocation *ma;
+
+ g_assert (self != NULL);
+ g_assert ((self->pos % SYSPROF_CAPTURE_ALIGN) == 0);
+ g_assert (self->pos <= self->bufsz);
+
+ if (!sysprof_capture_reader_ensure_space_for (self, sizeof *ma))
+ return NULL;
+
+ ma = (SysprofCaptureAllocation *)(gpointer)&self->buf[self->pos];
+
+ sysprof_capture_reader_bswap_frame (self, &ma->frame);
+
+ if (ma->frame.type != SYSPROF_CAPTURE_FRAME_ALLOCATION)
+ return NULL;
+
+ if (ma->frame.len < sizeof *ma)
+ return NULL;
+
+ if (self->endian != G_BYTE_ORDER)
+ {
+ ma->n_addrs = GUINT16_SWAP_LE_BE (ma->n_addrs);
+ ma->alloc_size = GUINT64_SWAP_LE_BE (ma->alloc_size);
+ ma->alloc_addr = GUINT64_SWAP_LE_BE (ma->alloc_addr);
+ ma->tid = GUINT32_SWAP_LE_BE (ma->tid);
+ }
+
+ if (ma->frame.len < (sizeof *ma + (sizeof(SysprofCaptureAddress) * ma->n_addrs)))
+ return NULL;
+
+ if (!sysprof_capture_reader_ensure_space_for (self, ma->frame.len))
+ return NULL;
+
+ ma = (SysprofCaptureAllocation *)(gpointer)&self->buf[self->pos];
+
+ if (G_UNLIKELY (self->endian != G_BYTE_ORDER))
+ {
+ for (guint i = 0; i < ma->n_addrs; i++)
+ ma->addrs[i] = GUINT64_SWAP_LE_BE (ma->addrs[i]);
+ }
+
+ self->pos += ma->frame.len;
+
+ return ma;
+}
diff --git a/src/libsysprof-capture/sysprof-capture-reader.h b/src/libsysprof-capture/sysprof-capture-reader.h
index 8467540..3c58524 100644
--- a/src/libsysprof-capture/sysprof-capture-reader.h
+++ b/src/libsysprof-capture/sysprof-capture-reader.h
@@ -64,86 +64,88 @@ G_BEGIN_DECLS
typedef struct _SysprofCaptureReader SysprofCaptureReader;
SYSPROF_AVAILABLE_IN_ALL
-SysprofCaptureReader *sysprof_capture_reader_new (const gchar
*filename,
- GError
**error);
+SysprofCaptureReader *sysprof_capture_reader_new (const gchar
*filename,
+ GError
**error);
SYSPROF_AVAILABLE_IN_ALL
-SysprofCaptureReader *sysprof_capture_reader_new_from_fd (int
fd,
- GError
**error);
+SysprofCaptureReader *sysprof_capture_reader_new_from_fd (int
fd,
+ GError
**error);
SYSPROF_AVAILABLE_IN_ALL
-SysprofCaptureReader *sysprof_capture_reader_copy (SysprofCaptureReader
*self);
+SysprofCaptureReader *sysprof_capture_reader_copy (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-SysprofCaptureReader *sysprof_capture_reader_ref (SysprofCaptureReader
*self);
+SysprofCaptureReader *sysprof_capture_reader_ref (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-void sysprof_capture_reader_unref (SysprofCaptureReader
*self);
+void sysprof_capture_reader_unref (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-gint sysprof_capture_reader_get_byte_order (SysprofCaptureReader
*self);
+gint sysprof_capture_reader_get_byte_order (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-const gchar *sysprof_capture_reader_get_filename (SysprofCaptureReader
*self);
+const gchar *sysprof_capture_reader_get_filename (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-const gchar *sysprof_capture_reader_get_time (SysprofCaptureReader
*self);
+const gchar *sysprof_capture_reader_get_time (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-gint64 sysprof_capture_reader_get_start_time (SysprofCaptureReader
*self);
+gint64 sysprof_capture_reader_get_start_time (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-gint64 sysprof_capture_reader_get_end_time (SysprofCaptureReader
*self);
+gint64 sysprof_capture_reader_get_end_time (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_reader_skip (SysprofCaptureReader
*self);
+gboolean sysprof_capture_reader_skip (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_reader_peek_type (SysprofCaptureReader
*self,
- SysprofCaptureFrameType
*type);
+gboolean sysprof_capture_reader_peek_type (SysprofCaptureReader
*self,
+ SysprofCaptureFrameType
*type);
SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_reader_peek_frame (SysprofCaptureReader
*self,
- SysprofCaptureFrame
*frame);
+gboolean sysprof_capture_reader_peek_frame (SysprofCaptureReader
*self,
+ SysprofCaptureFrame
*frame);
SYSPROF_AVAILABLE_IN_ALL
-const SysprofCaptureLog *sysprof_capture_reader_read_log (SysprofCaptureReader
*self);
+const SysprofCaptureLog *sysprof_capture_reader_read_log (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-const SysprofCaptureMap *sysprof_capture_reader_read_map (SysprofCaptureReader
*self);
+const SysprofCaptureMap *sysprof_capture_reader_read_map (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-const SysprofCaptureMark *sysprof_capture_reader_read_mark (SysprofCaptureReader
*self);
+const SysprofCaptureMark *sysprof_capture_reader_read_mark (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-const SysprofCaptureMetadata *sysprof_capture_reader_read_metadata (SysprofCaptureReader
*self);
+const SysprofCaptureMetadata *sysprof_capture_reader_read_metadata (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-const SysprofCaptureExit *sysprof_capture_reader_read_exit (SysprofCaptureReader
*self);
+const SysprofCaptureExit *sysprof_capture_reader_read_exit (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-const SysprofCaptureFork *sysprof_capture_reader_read_fork (SysprofCaptureReader
*self);
+const SysprofCaptureFork *sysprof_capture_reader_read_fork (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-const SysprofCaptureTimestamp *sysprof_capture_reader_read_timestamp (SysprofCaptureReader
*self);
+const SysprofCaptureTimestamp *sysprof_capture_reader_read_timestamp (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-const SysprofCaptureProcess *sysprof_capture_reader_read_process (SysprofCaptureReader
*self);
+const SysprofCaptureProcess *sysprof_capture_reader_read_process (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-const SysprofCaptureSample *sysprof_capture_reader_read_sample (SysprofCaptureReader
*self);
+const SysprofCaptureSample *sysprof_capture_reader_read_sample (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-GHashTable *sysprof_capture_reader_read_jitmap (SysprofCaptureReader
*self);
+GHashTable *sysprof_capture_reader_read_jitmap (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-const SysprofCaptureCounterDefine *sysprof_capture_reader_read_counter_define (SysprofCaptureReader
*self);
+const SysprofCaptureCounterDefine *sysprof_capture_reader_read_counter_define (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-const SysprofCaptureCounterSet *sysprof_capture_reader_read_counter_set (SysprofCaptureReader
*self);
+const SysprofCaptureCounterSet *sysprof_capture_reader_read_counter_set (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-const SysprofCaptureFileChunk *sysprof_capture_reader_read_file (SysprofCaptureReader
*self);
+const SysprofCaptureFileChunk *sysprof_capture_reader_read_file (SysprofCaptureReader
*self);
+SYSPROF_AVAILABLE_IN_3_36
+const SysprofCaptureAllocation *sysprof_capture_reader_read_allocation (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_reader_reset (SysprofCaptureReader
*self);
+gboolean sysprof_capture_reader_reset (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_reader_splice (SysprofCaptureReader
*self,
- SysprofCaptureWriter
*dest,
- GError
**error);
+gboolean sysprof_capture_reader_splice (SysprofCaptureReader
*self,
+ SysprofCaptureWriter
*dest,
+ GError
**error);
SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_reader_save_as (SysprofCaptureReader
*self,
- const gchar
*filename,
- GError
**error);
+gboolean sysprof_capture_reader_save_as (SysprofCaptureReader
*self,
+ const gchar
*filename,
+ GError
**error);
SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_reader_get_stat (SysprofCaptureReader
*self,
- SysprofCaptureStat
*st_buf);
+gboolean sysprof_capture_reader_get_stat (SysprofCaptureReader
*self,
+ SysprofCaptureStat
*st_buf);
SYSPROF_AVAILABLE_IN_ALL
-void sysprof_capture_reader_set_stat (SysprofCaptureReader
*self,
- const SysprofCaptureStat
*st_buf);
+void sysprof_capture_reader_set_stat (SysprofCaptureReader
*self,
+ const SysprofCaptureStat
*st_buf);
SYSPROF_AVAILABLE_IN_ALL
-const SysprofCaptureFileChunk *sysprof_capture_reader_find_file (SysprofCaptureReader
*self,
- const gchar
*path);
+const SysprofCaptureFileChunk *sysprof_capture_reader_find_file (SysprofCaptureReader
*self,
+ const gchar
*path);
SYSPROF_AVAILABLE_IN_ALL
-gchar **sysprof_capture_reader_list_files (SysprofCaptureReader
*self);
+gchar **sysprof_capture_reader_list_files (SysprofCaptureReader
*self);
SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_reader_read_file_fd (SysprofCaptureReader
*self,
- const gchar
*path,
- gint
fd);
+gboolean sysprof_capture_reader_read_file_fd (SysprofCaptureReader
*self,
+ const gchar
*path,
+ gint
fd);
G_DEFINE_AUTOPTR_CLEANUP_FUNC (SysprofCaptureReader, sysprof_capture_reader_unref)
diff --git a/src/libsysprof-capture/sysprof-capture-types.h b/src/libsysprof-capture/sysprof-capture-types.h
index d95d6b3..11e3d19 100644
--- a/src/libsysprof-capture/sysprof-capture-types.h
+++ b/src/libsysprof-capture/sysprof-capture-types.h
@@ -115,19 +115,20 @@ typedef union
typedef enum
{
- SYSPROF_CAPTURE_FRAME_TIMESTAMP = 1,
- SYSPROF_CAPTURE_FRAME_SAMPLE = 2,
- SYSPROF_CAPTURE_FRAME_MAP = 3,
- SYSPROF_CAPTURE_FRAME_PROCESS = 4,
- SYSPROF_CAPTURE_FRAME_FORK = 5,
- SYSPROF_CAPTURE_FRAME_EXIT = 6,
- SYSPROF_CAPTURE_FRAME_JITMAP = 7,
- SYSPROF_CAPTURE_FRAME_CTRDEF = 8,
- SYSPROF_CAPTURE_FRAME_CTRSET = 9,
- SYSPROF_CAPTURE_FRAME_MARK = 10,
- SYSPROF_CAPTURE_FRAME_METADATA = 11,
- SYSPROF_CAPTURE_FRAME_LOG = 12,
- SYSPROF_CAPTURE_FRAME_FILE_CHUNK = 13,
+ SYSPROF_CAPTURE_FRAME_TIMESTAMP = 1,
+ SYSPROF_CAPTURE_FRAME_SAMPLE = 2,
+ SYSPROF_CAPTURE_FRAME_MAP = 3,
+ SYSPROF_CAPTURE_FRAME_PROCESS = 4,
+ SYSPROF_CAPTURE_FRAME_FORK = 5,
+ SYSPROF_CAPTURE_FRAME_EXIT = 6,
+ SYSPROF_CAPTURE_FRAME_JITMAP = 7,
+ SYSPROF_CAPTURE_FRAME_CTRDEF = 8,
+ SYSPROF_CAPTURE_FRAME_CTRSET = 9,
+ SYSPROF_CAPTURE_FRAME_MARK = 10,
+ SYSPROF_CAPTURE_FRAME_METADATA = 11,
+ SYSPROF_CAPTURE_FRAME_LOG = 12,
+ SYSPROF_CAPTURE_FRAME_FILE_CHUNK = 13,
+ SYSPROF_CAPTURE_FRAME_ALLOCATION = 14,
} SysprofCaptureFrameType;
SYSPROF_ALIGNED_BEGIN(1)
@@ -311,6 +312,19 @@ typedef struct
} SysprofCaptureFileChunk
SYSPROF_ALIGNED_END(1);
+SYSPROF_ALIGNED_BEGIN(1)
+typedef struct
+{
+ SysprofCaptureFrame frame;
+ SysprofCaptureAddress alloc_addr;
+ gint64 alloc_size;
+ gint32 tid;
+ guint32 n_addrs : 16;
+ guint32 padding1 : 16;
+ SysprofCaptureAddress addrs[0];
+} SysprofCaptureAllocation
+SYSPROF_ALIGNED_END(1);
+
G_STATIC_ASSERT (sizeof (SysprofCaptureFileHeader) == 256);
G_STATIC_ASSERT (sizeof (SysprofCaptureFrame) == 24);
G_STATIC_ASSERT (sizeof (SysprofCaptureMap) == 56);
@@ -328,6 +342,8 @@ G_STATIC_ASSERT (sizeof (SysprofCaptureMark) == 96);
G_STATIC_ASSERT (sizeof (SysprofCaptureMetadata) == 64);
G_STATIC_ASSERT (sizeof (SysprofCaptureLog) == 64);
G_STATIC_ASSERT (sizeof (SysprofCaptureFileChunk) == 284);
+G_STATIC_ASSERT (sizeof (SysprofCaptureAllocation) == 48);
+G_STATIC_ASSERT ((G_STRUCT_OFFSET (SysprofCaptureAllocation, addrs) % 8) == 0);
static inline gint
sysprof_capture_address_compare (SysprofCaptureAddress a,
diff --git a/src/libsysprof-capture/sysprof-capture-writer-cat.c
b/src/libsysprof-capture/sysprof-capture-writer-cat.c
index 6dc2fce..0e473f4 100644
--- a/src/libsysprof-capture/sysprof-capture-writer-cat.c
+++ b/src/libsysprof-capture/sysprof-capture-writer-cat.c
@@ -477,6 +477,24 @@ sysprof_capture_writer_cat (SysprofCaptureWriter *self,
goto panic;
break;
+ case SYSPROF_CAPTURE_FRAME_ALLOCATION: {
+ const SysprofCaptureAllocation *frame;
+
+ if (!(frame = sysprof_capture_reader_read_allocation (reader)))
+ goto panic;
+
+ sysprof_capture_writer_add_allocation_copy (self,
+ frame->frame.time,
+ frame->frame.cpu,
+ frame->frame.pid,
+ frame->tid,
+ frame->alloc_addr,
+ frame->alloc_size,
+ frame->addrs,
+ frame->n_addrs);
+ break;
+ }
+
default:
/* Silently drop, which is better than looping. We could potentially
* copy this over using the raw bytes at some point.
diff --git a/src/libsysprof-capture/sysprof-capture-writer.c b/src/libsysprof-capture/sysprof-capture-writer.c
index 956340e..5e206af 100644
--- a/src/libsysprof-capture/sysprof-capture-writer.c
+++ b/src/libsysprof-capture/sysprof-capture-writer.c
@@ -78,6 +78,7 @@
#define DEFAULT_BUFFER_SIZE (_sysprof_getpagesize() * 64L)
#define INVALID_ADDRESS (G_GUINT64_CONSTANT(0))
#define MAX_COUNTERS ((1 << 24) - 1)
+#define MAX_UNWIND_DEPTH 128
typedef struct
{
@@ -1510,3 +1511,101 @@ sysprof_capture_writer_set_flush_delay (SysprofCaptureWriter *self,
g_source_attach (self->periodic_flush, main_context);
}
+
+gboolean
+sysprof_capture_writer_add_allocation (SysprofCaptureWriter *self,
+ gint64 time,
+ gint cpu,
+ gint32 pid,
+ gint32 tid,
+ SysprofCaptureAddress alloc_addr,
+ gint64 alloc_size,
+ SysprofBacktraceFunc backtrace_func,
+ gpointer backtrace_data)
+{
+ SysprofCaptureAllocation *ev;
+ gsize len;
+ guint n_addrs;
+
+ g_assert (self != NULL);
+ g_assert (backtrace_func != NULL);
+
+ len = sizeof *ev + (MAX_UNWIND_DEPTH * sizeof (SysprofCaptureAddress));
+ ev = (SysprofCaptureAllocation *)sysprof_capture_writer_allocate (self, &len);
+ if (!ev)
+ return FALSE;
+
+ sysprof_capture_writer_frame_init (&ev->frame,
+ len,
+ cpu,
+ pid,
+ time,
+ SYSPROF_CAPTURE_FRAME_ALLOCATION);
+
+ ev->alloc_size = alloc_size;
+ ev->alloc_addr = alloc_addr;
+ ev->padding1 = 0;
+ ev->tid = tid;
+ ev->n_addrs = 0;
+
+ n_addrs = backtrace_func (ev->addrs, MAX_UNWIND_DEPTH, backtrace_data);
+
+ if (n_addrs <= MAX_UNWIND_DEPTH)
+ ev->n_addrs = n_addrs;
+
+ if (ev->n_addrs < MAX_UNWIND_DEPTH)
+ {
+ gsize diff = (sizeof (SysprofCaptureAddress) * (MAX_UNWIND_DEPTH - ev->n_addrs));
+
+ ev->frame.len -= diff;
+ self->pos -= diff;
+ }
+
+ self->stat.frame_count[SYSPROF_CAPTURE_FRAME_ALLOCATION]++;
+
+ return TRUE;
+}
+
+gboolean
+sysprof_capture_writer_add_allocation_copy (SysprofCaptureWriter *self,
+ gint64 time,
+ gint cpu,
+ gint32 pid,
+ gint32 tid,
+ SysprofCaptureAddress alloc_addr,
+ gint64 alloc_size,
+ const SysprofCaptureAddress *addrs,
+ guint n_addrs)
+{
+ SysprofCaptureAllocation *ev;
+ gsize len;
+
+ g_assert (self != NULL);
+
+ if (n_addrs > 0xFFF)
+ n_addrs = 0xFFF;
+
+ len = sizeof *ev + (n_addrs * sizeof (SysprofCaptureAddress));
+ ev = (SysprofCaptureAllocation *)sysprof_capture_writer_allocate (self, &len);
+ if (!ev)
+ return FALSE;
+
+ sysprof_capture_writer_frame_init (&ev->frame,
+ len,
+ cpu,
+ pid,
+ time,
+ SYSPROF_CAPTURE_FRAME_ALLOCATION);
+
+ ev->alloc_size = alloc_size;
+ ev->alloc_addr = alloc_addr;
+ ev->padding1 = 0;
+ ev->tid = tid;
+ ev->n_addrs = n_addrs;
+
+ memcpy (ev->addrs, addrs, sizeof (SysprofCaptureAddress) * n_addrs);
+
+ self->stat.frame_count[SYSPROF_CAPTURE_FRAME_ALLOCATION]++;
+
+ return TRUE;
+}
diff --git a/src/libsysprof-capture/sysprof-capture-writer.h b/src/libsysprof-capture/sysprof-capture-writer.h
index 8d9859a..657e726 100644
--- a/src/libsysprof-capture/sysprof-capture-writer.h
+++ b/src/libsysprof-capture/sysprof-capture-writer.h
@@ -63,154 +63,188 @@ G_BEGIN_DECLS
typedef struct _SysprofCaptureWriter SysprofCaptureWriter;
+/**
+ * SysprofBacktraceFunc:
+ * @addrs: (inout) (array length=n_addrs): an array to place addresses
+ * into the capture frame
+ * @n_addrs: the length of @addrs
+ * @user_data: (scope call): closure data for the callback
+ *
+ * Returns: the number of addresses filled in @addrs
+ */
+typedef guint (*SysprofBacktraceFunc) (SysprofCaptureAddress *addrs,
+ guint n_addrs,
+ gpointer user_data);
+
SYSPROF_AVAILABLE_IN_ALL
-SysprofCaptureWriter *sysprof_capture_writer_new_from_env (gsize
buffer_size);
-SYSPROF_AVAILABLE_IN_ALL
-SysprofCaptureWriter *sysprof_capture_writer_new (const gchar *filename,
- gsize
buffer_size);
-SYSPROF_AVAILABLE_IN_ALL
-SysprofCaptureWriter *sysprof_capture_writer_new_from_fd (int fd,
- gsize
buffer_size);
-SYSPROF_AVAILABLE_IN_ALL
-gsize sysprof_capture_writer_get_buffer_size (SysprofCaptureWriter *self);
-SYSPROF_AVAILABLE_IN_ALL
-SysprofCaptureWriter *sysprof_capture_writer_ref (SysprofCaptureWriter *self);
-SYSPROF_AVAILABLE_IN_ALL
-void sysprof_capture_writer_unref (SysprofCaptureWriter *self);
-SYSPROF_AVAILABLE_IN_ALL
-void sysprof_capture_writer_stat (SysprofCaptureWriter *self,
- SysprofCaptureStat *stat);
-SYSPROF_AVAILABLE_IN_ALL
-void sysprof_capture_writer_set_flush_delay (SysprofCaptureWriter *self,
- GMainContext
*main_context,
- guint
timeout_seconds);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_add_file (SysprofCaptureWriter *self,
- gint64 time,
- gint cpu,
- gint32 pid,
- const gchar *path,
- gboolean is_last,
- const guint8 *data,
- gsize data_len);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_add_file_fd (SysprofCaptureWriter *self,
- gint64 time,
- gint cpu,
- gint32 pid,
- const gchar *path,
- gint fd);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_add_map (SysprofCaptureWriter *self,
- gint64 time,
- gint cpu,
- gint32 pid,
- guint64 start,
- guint64 end,
- guint64 offset,
- guint64 inode,
- const gchar *filename);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_add_mark (SysprofCaptureWriter *self,
- gint64 time,
- gint cpu,
- gint32 pid,
- guint64 duration,
- const gchar *group,
- const gchar *name,
- const gchar *message);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_add_metadata (SysprofCaptureWriter *self,
- gint64 time,
- gint cpu,
- gint32 pid,
- const gchar *id,
- const gchar *metadata,
- gssize
metadata_len);
-SYSPROF_AVAILABLE_IN_ALL
-guint64 sysprof_capture_writer_add_jitmap (SysprofCaptureWriter *self,
- const gchar *name);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_add_process (SysprofCaptureWriter *self,
- gint64 time,
- gint cpu,
- gint32 pid,
- const gchar *cmdline);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_add_sample (SysprofCaptureWriter *self,
- gint64 time,
- gint cpu,
- gint32 pid,
- gint32 tid,
- const SysprofCaptureAddress *addrs,
- guint n_addrs);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_add_fork (SysprofCaptureWriter *self,
- gint64 time,
- gint cpu,
- gint32 pid,
- gint32 child_pid);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_add_exit (SysprofCaptureWriter *self,
- gint64 time,
- gint cpu,
- gint32 pid);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_add_timestamp (SysprofCaptureWriter *self,
- gint64 time,
- gint cpu,
- gint32 pid);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_define_counters (SysprofCaptureWriter *self,
- gint64 time,
- gint cpu,
- gint32 pid,
- const SysprofCaptureCounter *counters,
- guint n_counters);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_set_counters (SysprofCaptureWriter *self,
- gint64 time,
- gint cpu,
- gint32 pid,
- const guint
*counters_ids,
- const SysprofCaptureCounterValue *values,
- guint n_counters);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_add_log (SysprofCaptureWriter *self,
- gint64 time,
- gint cpu,
- gint32 pid,
- GLogLevelFlags severity,
- const gchar *domain,
- const gchar *message);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_flush (SysprofCaptureWriter *self);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_save_as (SysprofCaptureWriter *self,
- const gchar *filename,
- GError **error);
-SYSPROF_AVAILABLE_IN_ALL
-guint sysprof_capture_writer_request_counter (SysprofCaptureWriter *self,
- guint n_counters);
-SYSPROF_AVAILABLE_IN_ALL
-SysprofCaptureReader *sysprof_capture_writer_create_reader (SysprofCaptureWriter *self,
- GError **error);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_splice (SysprofCaptureWriter *self,
- SysprofCaptureWriter *dest,
- GError **error);
-SYSPROF_AVAILABLE_IN_ALL
-gboolean sysprof_capture_writer_cat (SysprofCaptureWriter *self,
- SysprofCaptureReader *reader,
- GError **error);
+SysprofCaptureWriter *sysprof_capture_writer_new_from_env (gsize
buffer_size);
+SYSPROF_AVAILABLE_IN_ALL
+SysprofCaptureWriter *sysprof_capture_writer_new (const gchar
*filename,
+ gsize
buffer_size);
+SYSPROF_AVAILABLE_IN_ALL
+SysprofCaptureWriter *sysprof_capture_writer_new_from_fd (int
fd,
+ gsize
buffer_size);
+SYSPROF_AVAILABLE_IN_ALL
+gsize sysprof_capture_writer_get_buffer_size (SysprofCaptureWriter
*self);
+SYSPROF_AVAILABLE_IN_ALL
+SysprofCaptureWriter *sysprof_capture_writer_ref (SysprofCaptureWriter
*self);
+SYSPROF_AVAILABLE_IN_ALL
+void sysprof_capture_writer_unref (SysprofCaptureWriter
*self);
+SYSPROF_AVAILABLE_IN_ALL
+void sysprof_capture_writer_stat (SysprofCaptureWriter
*self,
+ SysprofCaptureStat
*stat);
+SYSPROF_AVAILABLE_IN_ALL
+void sysprof_capture_writer_set_flush_delay (SysprofCaptureWriter
*self,
+ GMainContext
*main_context,
+ guint
timeout_seconds);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_add_file (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid,
+ const gchar
*path,
+ gboolean
is_last,
+ const guint8
*data,
+ gsize
data_len);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_add_file_fd (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid,
+ const gchar
*path,
+ gint
fd);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_add_map (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid,
+ guint64
start,
+ guint64
end,
+ guint64
offset,
+ guint64
inode,
+ const gchar
*filename);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_add_mark (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid,
+ guint64
duration,
+ const gchar
*group,
+ const gchar
*name,
+ const gchar
*message);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_add_metadata (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid,
+ const gchar
*id,
+ const gchar
*metadata,
+ gssize
metadata_len);
+SYSPROF_AVAILABLE_IN_ALL
+guint64 sysprof_capture_writer_add_jitmap (SysprofCaptureWriter
*self,
+ const gchar
*name);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_add_process (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid,
+ const gchar
*cmdline);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_add_sample (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid,
+ gint32
tid,
+ const SysprofCaptureAddress
*addrs,
+ guint
n_addrs);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_add_fork (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid,
+ gint32
child_pid);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_add_exit (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_add_timestamp (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_define_counters (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid,
+ const SysprofCaptureCounter
*counters,
+ guint
n_counters);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_set_counters (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid,
+ const guint
*counters_ids,
+ const
SysprofCaptureCounterValue *values,
+ guint
n_counters);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_add_log (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid,
+ GLogLevelFlags
severity,
+ const gchar
*domain,
+ const gchar
*message);
+SYSPROF_AVAILABLE_IN_3_36
+gboolean sysprof_capture_writer_add_allocation (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid,
+ gint32
tid,
+ SysprofCaptureAddress
alloc_addr,
+ gint64
alloc_size,
+ SysprofBacktraceFunc
backtrace_func,
+ gpointer
backtrace_data);
+SYSPROF_AVAILABLE_IN_3_36
+gboolean sysprof_capture_writer_add_allocation_copy (SysprofCaptureWriter
*self,
+ gint64
time,
+ gint
cpu,
+ gint32
pid,
+ gint32
tid,
+ SysprofCaptureAddress
alloc_addr,
+ gint64
alloc_size,
+ const SysprofCaptureAddress
*addrs,
+ guint
n_addrs);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_flush (SysprofCaptureWriter
*self);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_save_as (SysprofCaptureWriter
*self,
+ const gchar
*filename,
+ GError
**error);
+SYSPROF_AVAILABLE_IN_ALL
+guint sysprof_capture_writer_request_counter (SysprofCaptureWriter
*self,
+ guint
n_counters);
+SYSPROF_AVAILABLE_IN_ALL
+SysprofCaptureReader *sysprof_capture_writer_create_reader (SysprofCaptureWriter
*self,
+ GError
**error);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_splice (SysprofCaptureWriter
*self,
+ SysprofCaptureWriter
*dest,
+ GError
**error);
+SYSPROF_AVAILABLE_IN_ALL
+gboolean sysprof_capture_writer_cat (SysprofCaptureWriter
*self,
+ SysprofCaptureReader
*reader,
+ GError
**error);
G_GNUC_INTERNAL
-gboolean _sysprof_capture_writer_splice_from_fd (SysprofCaptureWriter *self,
- int fd,
- GError **error)
G_GNUC_INTERNAL;
+gboolean _sysprof_capture_writer_splice_from_fd (SysprofCaptureWriter
*self,
+ int
fd,
+ GError
**error) G_GNUC_INTERNAL;
G_GNUC_INTERNAL
-gboolean _sysprof_capture_writer_set_time_range (SysprofCaptureWriter *self,
- gint64 start_time,
- gint64 end_time)
G_GNUC_INTERNAL;
+gboolean _sysprof_capture_writer_set_time_range (SysprofCaptureWriter
*self,
+ gint64
start_time,
+ gint64
end_time) G_GNUC_INTERNAL;
+
G_DEFINE_AUTOPTR_CLEANUP_FUNC (SysprofCaptureWriter, sysprof_capture_writer_unref)
diff --git a/src/libsysprof-ui/libsysprof-ui.gresource.xml b/src/libsysprof-ui/libsysprof-ui.gresource.xml
index fd6a597..c6ca3ef 100644
--- a/src/libsysprof-ui/libsysprof-ui.gresource.xml
+++ b/src/libsysprof-ui/libsysprof-ui.gresource.xml
@@ -19,6 +19,7 @@
<file preprocess="xml-stripblanks">sysprof-failed-state-view.ui</file>
<file preprocess="xml-stripblanks">sysprof-logs-page.ui</file>
<file preprocess="xml-stripblanks">sysprof-marks-page.ui</file>
+ <file preprocess="xml-stripblanks">sysprof-memprof-page.ui</file>
<file preprocess="xml-stripblanks">sysprof-process-model-row.ui</file>
<file preprocess="xml-stripblanks">sysprof-profiler-assistant.ui</file>
<file preprocess="xml-stripblanks">sysprof-recording-state-view.ui</file>
diff --git a/src/libsysprof-ui/meson.build b/src/libsysprof-ui/meson.build
index 52c9121..1151f39 100644
--- a/src/libsysprof-ui/meson.build
+++ b/src/libsysprof-ui/meson.build
@@ -45,6 +45,9 @@ libsysprof_ui_private_sources = [
'sysprof-marks-page.c',
'sysprof-mark-visualizer.c',
'sysprof-memory-aid.c',
+ 'sysprof-memprof-aid.c',
+ 'sysprof-memprof-page.c',
+ 'sysprof-memprof-visualizer.c',
'sysprof-netdev-aid.c',
'sysprof-procs-visualizer.c',
'sysprof-profiler-assistant.c',
diff --git a/src/libsysprof-ui/sysprof-display.c b/src/libsysprof-ui/sysprof-display.c
index e7ea00f..7bd8f89 100644
--- a/src/libsysprof-ui/sysprof-display.c
+++ b/src/libsysprof-ui/sysprof-display.c
@@ -42,6 +42,8 @@
#include "sysprof-diskstat-aid.h"
#include "sysprof-logs-aid.h"
#include "sysprof-marks-aid.h"
+#include "sysprof-memory-aid.h"
+#include "sysprof-memprof-aid.h"
#include "sysprof-netdev-aid.h"
#include "sysprof-rapl-aid.h"
@@ -654,6 +656,8 @@ sysprof_display_present_async (SysprofDisplay *self,
g_ptr_array_add (aids, sysprof_diskstat_aid_new ());
g_ptr_array_add (aids, sysprof_logs_aid_new ());
g_ptr_array_add (aids, sysprof_marks_aid_new ());
+ g_ptr_array_add (aids, sysprof_memory_aid_new ());
+ g_ptr_array_add (aids, sysprof_memprof_aid_new ());
g_ptr_array_add (aids, sysprof_netdev_aid_new ());
g_ptr_array_add (aids, sysprof_rapl_aid_new ());
diff --git a/src/libsysprof-ui/sysprof-memory-aid.c b/src/libsysprof-ui/sysprof-memory-aid.c
index 7280dc3..67341ac 100644
--- a/src/libsysprof-ui/sysprof-memory-aid.c
+++ b/src/libsysprof-ui/sysprof-memory-aid.c
@@ -33,15 +33,6 @@ struct _SysprofMemoryAid
G_DEFINE_TYPE (SysprofMemoryAid, sysprof_memory_aid, SYSPROF_TYPE_AID)
-/**
- * sysprof_memory_aid_new:
- *
- * Create a new #SysprofMemoryAid.
- *
- * Returns: (transfer full): a newly created #SysprofMemoryAid
- *
- * Since: 3.34
- */
SysprofAid *
sysprof_memory_aid_new (void)
{
@@ -50,7 +41,7 @@ sysprof_memory_aid_new (void)
static void
sysprof_memory_aid_prepare (SysprofAid *self,
- SysprofProfiler *profiler)
+ SysprofProfiler *profiler)
{
#ifdef __linux__
g_autoptr(SysprofSource) source = NULL;
diff --git a/src/libsysprof-ui/sysprof-memprof-aid.c b/src/libsysprof-ui/sysprof-memprof-aid.c
new file mode 100644
index 0000000..6299b54
--- /dev/null
+++ b/src/libsysprof-ui/sysprof-memprof-aid.c
@@ -0,0 +1,226 @@
+/* sysprof-memprof-aid.c
+ *
+ * Copyright 2019 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#define G_LOG_DOMAIN "sysprof-memprof-aid"
+
+#include "config.h"
+
+#include <glib/gi18n.h>
+
+#include "sysprof-memprof-aid.h"
+#include "sysprof-memprof-page.h"
+#include "sysprof-memprof-source.h"
+#include "sysprof-memprof-visualizer.h"
+
+struct _SysprofMemprofAid
+{
+ SysprofAid parent_instance;
+};
+
+G_DEFINE_TYPE (SysprofMemprofAid, sysprof_memprof_aid, SYSPROF_TYPE_AID)
+
+typedef struct
+{
+ SysprofCaptureCursor *cursor;
+ SysprofDisplay *display;
+ guint has_allocs : 1;
+} Present;
+
+static void
+present_free (gpointer data)
+{
+ Present *p = data;
+
+ g_clear_pointer (&p->cursor, sysprof_capture_cursor_unref);
+ g_clear_object (&p->display);
+ g_slice_free (Present, p);
+}
+
+static void
+on_group_activated_cb (SysprofVisualizerGroup *group,
+ SysprofPage *page)
+{
+ SysprofDisplay *display;
+
+ g_assert (SYSPROF_IS_VISUALIZER_GROUP (group));
+ g_assert (SYSPROF_IS_PAGE (page));
+
+ display = SYSPROF_DISPLAY (gtk_widget_get_ancestor (GTK_WIDGET (page), SYSPROF_TYPE_DISPLAY));
+ sysprof_display_set_visible_page (display, page);
+}
+
+SysprofAid *
+sysprof_memprof_aid_new (void)
+{
+ return g_object_new (SYSPROF_TYPE_MEMPROF_AID, NULL);
+}
+
+static void
+sysprof_memprof_aid_prepare (SysprofAid *self,
+ SysprofProfiler *profiler)
+{
+#ifdef __linux__
+ g_autoptr(SysprofSource) source = NULL;
+
+ g_assert (SYSPROF_IS_MEMPROF_AID (self));
+ g_assert (SYSPROF_IS_PROFILER (profiler));
+
+ source = sysprof_memprof_source_new ();
+ sysprof_profiler_add_source (profiler, source);
+#endif
+}
+
+static gboolean
+discover_samples_cb (const SysprofCaptureFrame *frame,
+ gpointer user_data)
+{
+ Present *p = user_data;
+
+ g_assert (frame != NULL);
+ g_assert (p != NULL);
+
+ if (frame->type == SYSPROF_CAPTURE_FRAME_ALLOCATION)
+ {
+ p->has_allocs = TRUE;
+ return FALSE;
+ }
+
+ return TRUE;
+}
+
+static void
+sysprof_memprof_aid_present_worker (GTask *task,
+ gpointer source_object,
+ gpointer task_data,
+ GCancellable *cancellable)
+{
+ Present *p = task_data;
+
+ g_assert (G_IS_TASK (task));
+ g_assert (SYSPROF_IS_MEMPROF_AID (source_object));
+ g_assert (p != NULL);
+ g_assert (p->cursor != NULL);
+ g_assert (!cancellable || G_IS_CANCELLABLE (cancellable));
+
+ sysprof_capture_cursor_foreach (p->cursor, discover_samples_cb, p);
+ g_task_return_boolean (task, TRUE);
+}
+
+static void
+sysprof_memprof_aid_present_async (SysprofAid *aid,
+ SysprofCaptureReader *reader,
+ SysprofDisplay *display,
+ GCancellable *cancellable,
+ GAsyncReadyCallback callback,
+ gpointer user_data)
+{
+ static const SysprofCaptureFrameType types[] = { SYSPROF_CAPTURE_FRAME_ALLOCATION };
+ g_autoptr(SysprofCaptureCondition) condition = NULL;
+ g_autoptr(SysprofCaptureCursor) cursor = NULL;
+ g_autoptr(GTask) task = NULL;
+ Present present;
+
+ g_assert (SYSPROF_IS_MEMPROF_AID (aid));
+ g_assert (reader != NULL);
+ g_assert (SYSPROF_IS_DISPLAY (display));
+ g_assert (!cancellable || G_IS_CANCELLABLE (cancellable));
+
+ condition = sysprof_capture_condition_new_where_type_in (1, types);
+ cursor = sysprof_capture_cursor_new (reader);
+ sysprof_capture_cursor_add_condition (cursor, g_steal_pointer (&condition));
+
+ present.cursor = g_steal_pointer (&cursor);
+ present.display = g_object_ref (display);
+
+ task = g_task_new (aid, cancellable, callback, user_data);
+ g_task_set_source_tag (task, sysprof_memprof_aid_present_async);
+ g_task_set_task_data (task,
+ g_slice_dup (Present, &present),
+ present_free);
+ g_task_run_in_thread (task, sysprof_memprof_aid_present_worker);
+}
+
+static gboolean
+sysprof_memprof_aid_present_finish (SysprofAid *aid,
+ GAsyncResult *result,
+ GError **error)
+{
+ Present *p;
+
+ g_assert (SYSPROF_IS_MEMPROF_AID (aid));
+ g_assert (G_IS_TASK (result));
+
+ p = g_task_get_task_data (G_TASK (result));
+
+ if (p->has_allocs)
+ {
+ SysprofVisualizerGroup *group;
+ SysprofVisualizer *row;
+ SysprofPage *page;
+
+ group = g_object_new (SYSPROF_TYPE_VISUALIZER_GROUP,
+ "can-focus", TRUE,
+ "has-page", TRUE,
+ "priority", -300,
+ "title", _("Memory"),
+ "visible", TRUE,
+ NULL);
+
+ row = sysprof_memprof_visualizer_new (FALSE);
+ sysprof_visualizer_group_insert (group, row, 0, FALSE);
+
+ row = sysprof_memprof_visualizer_new (TRUE);
+ sysprof_visualizer_group_insert (group, row, 1, FALSE);
+
+ page = g_object_new (SYSPROF_TYPE_MEMPROF_PAGE,
+ "title", _("Memory Allocations"),
+ "vexpand", TRUE,
+ "visible", TRUE,
+ NULL);
+ sysprof_display_add_page (p->display, page);
+
+ g_signal_connect_object (group,
+ "group-activated",
+ G_CALLBACK (on_group_activated_cb),
+ page,
+ 0);
+
+ sysprof_display_add_group (p->display, group);
+ }
+
+ return g_task_propagate_boolean (G_TASK (result), error);
+}
+
+static void
+sysprof_memprof_aid_class_init (SysprofMemprofAidClass *klass)
+{
+ SysprofAidClass *aid_class = SYSPROF_AID_CLASS (klass);
+
+ aid_class->prepare = sysprof_memprof_aid_prepare;
+ aid_class->present_async = sysprof_memprof_aid_present_async;
+ aid_class->present_finish = sysprof_memprof_aid_present_finish;
+}
+
+static void
+sysprof_memprof_aid_init (SysprofMemprofAid *self)
+{
+ sysprof_aid_set_display_name (SYSPROF_AID (self), _("Track Allocations"));
+ sysprof_aid_set_icon_name (SYSPROF_AID (self), "org.gnome.Sysprof-symbolic");
+}
diff --git a/src/libsysprof-ui/sysprof-memprof-aid.h b/src/libsysprof-ui/sysprof-memprof-aid.h
new file mode 100644
index 0000000..b5294d5
--- /dev/null
+++ b/src/libsysprof-ui/sysprof-memprof-aid.h
@@ -0,0 +1,33 @@
+/* sysprof-memprof-aid.h
+ *
+ * Copyright 2019 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#pragma once
+
+#include "sysprof-aid.h"
+
+G_BEGIN_DECLS
+
+#define SYSPROF_TYPE_MEMPROF_AID (sysprof_memprof_aid_get_type())
+
+G_DECLARE_FINAL_TYPE (SysprofMemprofAid, sysprof_memprof_aid, SYSPROF, MEMPROF_AID, SysprofAid)
+
+SysprofAid *sysprof_memprof_aid_new (void);
+
+G_END_DECLS
diff --git a/src/libsysprof-ui/sysprof-memprof-page.c b/src/libsysprof-ui/sysprof-memprof-page.c
new file mode 100644
index 0000000..6ffb5df
--- /dev/null
+++ b/src/libsysprof-ui/sysprof-memprof-page.c
@@ -0,0 +1,1319 @@
+/* sysprof-memprof-page.c
+ *
+ * Copyright 2016-2019 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+/* Sysprof -- Sampling, systemwide CPU profiler
+ * Copyright 2004, Red Hat, Inc.
+ * Copyright 2004, 2005, 2006, Soeren Sandmann
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+
+#include "config.h"
+
+#include <dazzle.h>
+#include <glib/gi18n.h>
+
+#include "../stackstash.h"
+
+#include "sysprof-cell-renderer-percent.h"
+#include "sysprof-memprof-page.h"
+#include "sysprof-profile.h"
+
+typedef struct
+{
+ SysprofMemprofProfile *profile;
+
+ GtkTreeView *callers_view;
+ GtkTreeView *functions_view;
+ GtkTreeView *descendants_view;
+ GtkTreeViewColumn *descendants_name_column;
+ GtkTreeViewColumn *function_size_column;
+ GtkCellRendererText *function_size_cell;
+ GtkStack *stack;
+
+ GQueue *history;
+
+ guint profile_size;
+ guint loading;
+} SysprofMemprofPagePrivate;
+
+G_DEFINE_TYPE_WITH_PRIVATE (SysprofMemprofPage, sysprof_memprof_page, SYSPROF_TYPE_PAGE)
+
+enum {
+ PROP_0,
+ PROP_PROFILE,
+ N_PROPS
+};
+
+enum {
+ GO_PREVIOUS,
+ N_SIGNALS
+};
+
+enum {
+ COLUMN_NAME,
+ COLUMN_SELF,
+ COLUMN_TOTAL,
+ COLUMN_POINTER,
+ COLUMN_SIZE,
+};
+
+static void sysprof_memprof_page_update_descendants (SysprofMemprofPage *self,
+ StackNode *node);
+
+static GParamSpec *properties [N_PROPS];
+static guint signals [N_SIGNALS];
+
+static guint
+sysprof_memprof_page_get_profile_size (SysprofMemprofPage *self)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+ StackStash *stash;
+ StackNode *node;
+ guint size = 0;
+
+ g_assert (SYSPROF_IS_MEMPROF_PAGE (self));
+
+ if (priv->profile_size != 0)
+ return priv->profile_size;
+
+ if (priv->profile == NULL)
+ return 0;
+
+ if (NULL == (stash = sysprof_memprof_profile_get_stash (priv->profile)))
+ return 0;
+
+ for (node = stack_stash_get_root (stash); node != NULL; node = node->siblings)
+ size += node->total;
+
+ priv->profile_size = size;
+
+ return size;
+}
+
+static void
+build_functions_store (StackNode *node,
+ gpointer user_data)
+{
+ struct {
+ GtkListStore *store;
+ gdouble profile_size;
+ } *state = user_data;
+ GtkTreeIter iter;
+ const StackNode *n;
+ guint size = 0;
+ guint total = 0;
+
+ g_assert (state != NULL);
+ g_assert (GTK_IS_LIST_STORE (state->store));
+
+ for (n = node; n != NULL; n = n->next)
+ {
+ size += n->size;
+ if (n->toplevel)
+ total += n->total;
+ }
+
+ gtk_list_store_append (state->store, &iter);
+ gtk_list_store_set (state->store, &iter,
+ COLUMN_NAME, U64_TO_POINTER(node->data),
+ COLUMN_SELF, 100.0 * size / state->profile_size,
+ COLUMN_TOTAL, 100.0 * total / state->profile_size,
+ COLUMN_POINTER, node,
+ -1);
+
+}
+
+static void
+sysprof_memprof_page_load (SysprofMemprofPage *self,
+ SysprofMemprofProfile *profile)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+ GtkListStore *functions;
+ StackStash *stash;
+ StackNode *n;
+ GtkTreeIter iter;
+ struct {
+ GtkListStore *store;
+ gdouble profile_size;
+ } state = { 0 };
+
+ g_assert (SYSPROF_IS_MEMPROF_PAGE (self));
+ g_assert (SYSPROF_IS_MEMPROF_PROFILE (profile));
+
+ /*
+ * TODO: This is probably the type of thing we want to do off the main
+ * thread. We should be able to build the tree models off thread
+ * and then simply apply them on the main thread.
+ *
+ * In the mean time, we should set the state of the widget to
+ * insensitive and give some indication of loading progress.
+ */
+
+ if (!g_set_object (&priv->profile, profile))
+ return;
+
+ if (sysprof_memprof_profile_is_empty (profile))
+ return;
+
+ stash = sysprof_memprof_profile_get_stash (profile);
+
+ for (n = stack_stash_get_root (stash); n; n = n->siblings)
+ state.profile_size += n->total;
+
+ functions = gtk_list_store_new (4, G_TYPE_STRING, G_TYPE_DOUBLE, G_TYPE_DOUBLE, G_TYPE_POINTER);
+
+ state.store = functions;
+ stack_stash_foreach_by_address (stash, build_functions_store, &state);
+
+ gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (functions),
+ COLUMN_TOTAL,
+ GTK_SORT_DESCENDING);
+
+ gtk_tree_view_set_model (priv->functions_view, GTK_TREE_MODEL (functions));
+ gtk_tree_view_set_model (priv->callers_view, NULL);
+ gtk_tree_view_set_model (priv->descendants_view, NULL);
+
+ if (gtk_tree_model_get_iter_first (GTK_TREE_MODEL (functions), &iter))
+ {
+ GtkTreeSelection *selection;
+
+ selection = gtk_tree_view_get_selection (priv->functions_view);
+ gtk_tree_selection_select_iter (selection, &iter);
+ }
+
+ gtk_stack_set_visible_child_name (priv->stack, "callgraph");
+
+ g_clear_object (&functions);
+}
+
+void
+_sysprof_memprof_page_set_failed (SysprofMemprofPage *self)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+
+ g_return_if_fail (SYSPROF_IS_MEMPROF_PAGE (self));
+
+ gtk_stack_set_visible_child_name (priv->stack, "empty-state");
+}
+
+static void
+sysprof_memprof_page_unload (SysprofMemprofPage *self)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+
+ g_assert (SYSPROF_IS_MEMPROF_PAGE (self));
+ g_assert (SYSPROF_IS_MEMPROF_PROFILE (priv->profile));
+
+ g_queue_clear (priv->history);
+ g_clear_object (&priv->profile);
+ priv->profile_size = 0;
+
+ gtk_tree_view_set_model (priv->callers_view, NULL);
+ gtk_tree_view_set_model (priv->functions_view, NULL);
+ gtk_tree_view_set_model (priv->descendants_view, NULL);
+
+ gtk_stack_set_visible_child_name (priv->stack, "empty-state");
+}
+
+/**
+ * sysprof_memprof_page_get_profile:
+ *
+ * Returns: (transfer none): An #SysprofMemprofProfile.
+ */
+SysprofMemprofProfile *
+sysprof_memprof_page_get_profile (SysprofMemprofPage *self)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+
+ g_return_val_if_fail (SYSPROF_IS_MEMPROF_PAGE (self), NULL);
+
+ return priv->profile;
+}
+
+void
+sysprof_memprof_page_set_profile (SysprofMemprofPage *self,
+ SysprofMemprofProfile *profile)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+
+ g_return_if_fail (SYSPROF_IS_MEMPROF_PAGE (self));
+ g_return_if_fail (!profile || SYSPROF_IS_MEMPROF_PROFILE (profile));
+
+ if (profile != priv->profile)
+ {
+ if (priv->profile)
+ sysprof_memprof_page_unload (self);
+
+ if (profile)
+ sysprof_memprof_page_load (self, profile);
+
+ g_object_notify_by_pspec (G_OBJECT (self), properties [PROP_PROFILE]);
+ }
+}
+
+static void
+sysprof_memprof_page_expand_descendants (SysprofMemprofPage *self)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+ GtkTreeModel *model;
+ GList *all_paths = NULL;
+ GtkTreePath *first_path;
+ GtkTreeIter iter;
+ gdouble top_value = 0;
+ gint max_rows = 40; /* FIXME */
+ gint n_rows;
+
+ g_assert (SYSPROF_IS_MEMPROF_PAGE (self));
+
+ model = gtk_tree_view_get_model (priv->descendants_view);
+ first_path = gtk_tree_path_new_first ();
+ all_paths = g_list_prepend (all_paths, first_path);
+ n_rows = 1;
+
+ gtk_tree_model_get_iter (model, &iter, first_path);
+ gtk_tree_model_get (model, &iter,
+ COLUMN_TOTAL, &top_value,
+ -1);
+
+ while ((all_paths != NULL) && (n_rows < max_rows))
+ {
+ GtkTreeIter best_iter;
+ GtkTreePath *best_path = NULL;
+ GList *list;
+ gdouble best_value = 0.0;
+ gint n_children;
+ gint i;
+
+ for (list = all_paths; list != NULL; list = list->next)
+ {
+ GtkTreePath *path = list->data;
+
+ g_assert (path != NULL);
+
+ if (gtk_tree_model_get_iter (model, &iter, path))
+ {
+ gdouble value;
+
+ gtk_tree_model_get (model, &iter,
+ COLUMN_TOTAL, &value,
+ -1);
+
+ if (value >= best_value)
+ {
+ best_value = value;
+ best_path = path;
+ best_iter = iter;
+ }
+ }
+ }
+
+ n_children = gtk_tree_model_iter_n_children (model, &best_iter);
+
+ if ((n_children > 0) &&
+ ((best_value / top_value) > 0.04) &&
+ ((n_children + gtk_tree_path_get_depth (best_path)) / (gdouble)max_rows) < (best_value /
top_value))
+ {
+ gtk_tree_view_expand_row (priv->descendants_view, best_path, FALSE);
+ n_rows += n_children;
+
+ if (gtk_tree_path_get_depth (best_path) < 4)
+ {
+ GtkTreePath *path;
+
+ path = gtk_tree_path_copy (best_path);
+ gtk_tree_path_down (path);
+
+ for (i = 0; i < n_children; i++)
+ {
+ all_paths = g_list_prepend (all_paths, path);
+
+ path = gtk_tree_path_copy (path);
+ gtk_tree_path_next (path);
+ }
+
+ gtk_tree_path_free (path);
+ }
+ }
+
+ all_paths = g_list_remove (all_paths, best_path);
+
+ /* Always expand at least once */
+ if ((all_paths == NULL) && (n_rows == 1))
+ gtk_tree_view_expand_row (priv->descendants_view, best_path, FALSE);
+
+ gtk_tree_path_free (best_path);
+ }
+
+ g_list_free_full (all_paths, (GDestroyNotify)gtk_tree_path_free);
+}
+
+typedef struct
+{
+ StackNode *node;
+ const gchar *name;
+ guint self;
+ guint total;
+} Caller;
+
+static Caller *
+caller_new (StackNode *node)
+{
+ Caller *c;
+
+ c = g_slice_new (Caller);
+ c->name = U64_TO_POINTER (node->data);
+ c->self = 0;
+ c->total = 0;
+ c->node = node;
+
+ return c;
+}
+
+static void
+caller_free (gpointer data)
+{
+ Caller *c = data;
+ g_slice_free (Caller, c);
+}
+
+static void
+sysprof_memprof_page_function_selection_changed (SysprofMemprofPage *self,
+ GtkTreeSelection *selection)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+ GtkTreeModel *model = NULL;
+ GtkTreeIter iter;
+ GtkListStore *callers_store;
+ g_autoptr(GHashTable) callers = NULL;
+ g_autoptr(GHashTable) processed = NULL;
+ StackNode *callees = NULL;
+ StackNode *node;
+
+ g_assert (SYSPROF_IS_MEMPROF_PAGE (self));
+ g_assert (GTK_IS_TREE_SELECTION (selection));
+
+ if (!gtk_tree_selection_get_selected (selection, &model, &iter))
+ {
+ gtk_tree_view_set_model (priv->callers_view, NULL);
+ gtk_tree_view_set_model (priv->descendants_view, NULL);
+ return;
+ }
+
+ gtk_tree_model_get (model, &iter,
+ COLUMN_POINTER, &callees,
+ -1);
+
+ sysprof_memprof_page_update_descendants (self, callees);
+
+ callers_store = gtk_list_store_new (4,
+ G_TYPE_STRING,
+ G_TYPE_DOUBLE,
+ G_TYPE_DOUBLE,
+ G_TYPE_POINTER);
+
+ callers = g_hash_table_new_full (NULL, NULL, NULL, caller_free);
+ processed = g_hash_table_new (NULL, NULL);
+
+ for (node = callees; node != NULL; node = node->next)
+ {
+ Caller *c;
+
+ if (!node->parent)
+ continue;
+
+ c = g_hash_table_lookup (callers, U64_TO_POINTER (node->parent->data));
+
+ if (c == NULL)
+ {
+ c = caller_new (node->parent);
+ g_hash_table_insert (callers, (gpointer)c->name, c);
+ }
+ }
+
+ for (node = callees; node != NULL; node = node->next)
+ {
+ StackNode *top_caller = node->parent;
+ StackNode *top_callee = node;
+ StackNode *n;
+ Caller *c;
+
+ if (!node->parent)
+ continue;
+
+ /*
+ * We could have a situation where the function was called in a
+ * reentrant fashion, so we want to take the top-most match in the
+ * stack.
+ */
+ for (n = node; n && n->parent; n = n->parent)
+ {
+ if (n->data == node->data && n->parent->data == node->parent->data)
+ {
+ top_caller = n->parent;
+ top_callee = n;
+ }
+ }
+
+ c = g_hash_table_lookup (callers, U64_TO_POINTER (node->parent->data));
+
+ g_assert (c != NULL);
+
+ if (!g_hash_table_lookup (processed, top_caller))
+ {
+ c->total += top_callee->total;
+ g_hash_table_insert (processed, top_caller, top_caller);
+ }
+
+ c->self += node->size;
+ }
+
+ {
+ GHashTableIter hiter;
+ gpointer key, value;
+ guint size = 0;
+
+ size = MAX (1, sysprof_memprof_page_get_profile_size (self));
+
+ g_hash_table_iter_init (&hiter, callers);
+
+ while (g_hash_table_iter_next (&hiter, &key, &value))
+ {
+ Caller *c = value;
+
+ gtk_list_store_append (callers_store, &iter);
+ gtk_list_store_set (callers_store, &iter,
+ COLUMN_NAME, c->name,
+ COLUMN_SELF, c->self * 100.0 / size,
+ COLUMN_TOTAL, c->total * 100.0 / size,
+ COLUMN_POINTER, c->node,
+ -1);
+ }
+ }
+
+ gtk_tree_view_set_model (priv->callers_view, GTK_TREE_MODEL (callers_store));
+ gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (callers_store),
+ COLUMN_TOTAL,
+ GTK_SORT_DESCENDING);
+
+ g_clear_object (&callers_store);
+}
+
+static void
+sysprof_memprof_page_set_node (SysprofMemprofPage *self,
+ StackNode *node)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+ GtkTreeModel *model;
+ GtkTreeIter iter;
+
+ g_assert (SYSPROF_IS_MEMPROF_PAGE (self));
+ g_assert (node != NULL);
+
+ if (priv->profile == NULL)
+ return;
+
+ model = gtk_tree_view_get_model (priv->functions_view);
+
+ if (gtk_tree_model_get_iter_first (model, &iter))
+ {
+ do
+ {
+ StackNode *item = NULL;
+
+ gtk_tree_model_get (model, &iter,
+ COLUMN_POINTER, &item,
+ -1);
+
+ if (item != NULL && item->data == node->data)
+ {
+ GtkTreeSelection *selection;
+
+ selection = gtk_tree_view_get_selection (priv->functions_view);
+ gtk_tree_selection_select_iter (selection, &iter);
+
+ break;
+ }
+ }
+ while (gtk_tree_model_iter_next (model, &iter));
+ }
+}
+
+static void
+sysprof_memprof_page_descendant_activated (SysprofMemprofPage *self,
+ GtkTreePath *path,
+ GtkTreeViewColumn *column,
+ GtkTreeView *tree_view)
+{
+ GtkTreeModel *model;
+ StackNode *node = NULL;
+ GtkTreeIter iter;
+
+ g_assert (SYSPROF_IS_MEMPROF_PAGE (self));
+ g_assert (GTK_IS_TREE_VIEW (tree_view));
+ g_assert (path != NULL);
+ g_assert (GTK_IS_TREE_VIEW_COLUMN (column));
+
+ model = gtk_tree_view_get_model (tree_view);
+
+ if (!gtk_tree_model_get_iter (model, &iter, path))
+ return;
+
+ gtk_tree_model_get (model, &iter,
+ COLUMN_POINTER, &node,
+ -1);
+
+ if (node != NULL)
+ sysprof_memprof_page_set_node (self, node);
+}
+
+static void
+sysprof_memprof_page_caller_activated (SysprofMemprofPage *self,
+ GtkTreePath *path,
+ GtkTreeViewColumn *column,
+ GtkTreeView *tree_view)
+{
+ GtkTreeModel *model;
+ StackNode *node = NULL;
+ GtkTreeIter iter;
+
+ g_assert (SYSPROF_IS_MEMPROF_PAGE (self));
+ g_assert (GTK_IS_TREE_VIEW (tree_view));
+ g_assert (path != NULL);
+ g_assert (GTK_IS_TREE_VIEW_COLUMN (column));
+
+ model = gtk_tree_view_get_model (tree_view);
+
+ if (!gtk_tree_model_get_iter (model, &iter, path))
+ return;
+
+ gtk_tree_model_get (model, &iter,
+ COLUMN_POINTER, &node,
+ -1);
+
+ if (node != NULL)
+ sysprof_memprof_page_set_node (self, node);
+}
+
+static void
+sysprof_memprof_page_size_data_func (GtkTreeViewColumn *column,
+ GtkCellRenderer *cell,
+ GtkTreeModel *model,
+ GtkTreeIter *iter,
+ gpointer data)
+{
+ g_autofree gchar *size_str = NULL;
+ guint64 size;
+
+ gtk_tree_model_get (model, iter, COLUMN_SIZE, &size, -1);
+ if (size)
+ size_str = g_format_size_full (size, G_FORMAT_SIZE_IEC_UNITS);
+ g_object_set (cell, "text", size_str, NULL);
+}
+
+static void
+sysprof_memprof_page_tag_data_func (GtkTreeViewColumn *column,
+ GtkCellRenderer *cell,
+ GtkTreeModel *model,
+ GtkTreeIter *iter,
+ gpointer data)
+{
+ SysprofMemprofPage *self = data;
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+ StackNode *node = NULL;
+ const gchar *str = NULL;
+
+ if (priv->profile == NULL)
+ return;
+
+ gtk_tree_model_get (model, iter, COLUMN_POINTER, &node, -1);
+
+ if (node && node->data)
+ {
+ GQuark tag;
+
+ tag = sysprof_memprof_profile_get_tag (priv->profile, GSIZE_TO_POINTER (node->data));
+ if (tag != 0)
+ str = g_quark_to_string (tag);
+ }
+
+ g_object_set (cell, "text", str, NULL);
+}
+
+static void
+sysprof_memprof_page_real_go_previous (SysprofMemprofPage *self)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+ StackNode *node;
+
+ g_assert (SYSPROF_IS_MEMPROF_PAGE (self));
+
+ node = g_queue_pop_head (priv->history);
+
+ if (NULL != (node = g_queue_peek_head (priv->history)))
+ sysprof_memprof_page_set_node (self, node);
+}
+
+static void
+descendants_view_move_cursor_cb (GtkTreeView *descendants_view,
+ GtkMovementStep step,
+ int direction,
+ gpointer user_data)
+{
+ if (step == GTK_MOVEMENT_VISUAL_POSITIONS)
+ {
+ GtkTreePath *path;
+
+ gtk_tree_view_get_cursor (descendants_view, &path, NULL);
+
+ if (direction == 1)
+ {
+ gtk_tree_view_expand_row (descendants_view, path, FALSE);
+ g_signal_stop_emission_by_name (descendants_view, "move-cursor");
+ }
+ else if (direction == -1)
+ {
+ gtk_tree_view_collapse_row (descendants_view, path);
+ g_signal_stop_emission_by_name (descendants_view, "move-cursor");
+ }
+
+ gtk_tree_path_free (path);
+ }
+}
+
+static void
+copy_tree_view_selection_cb (GtkTreeModel *model,
+ GtkTreePath *path,
+ GtkTreeIter *iter,
+ gpointer data)
+{
+ g_autofree gchar *name = NULL;
+ gchar sstr[16];
+ gchar tstr[16];
+ GString *str = data;
+ gdouble self;
+ gdouble total;
+ gint depth;
+
+ g_assert (GTK_IS_TREE_MODEL (model));
+ g_assert (path != NULL);
+ g_assert (iter != NULL);
+ g_assert (str != NULL);
+
+ depth = gtk_tree_path_get_depth (path);
+ gtk_tree_model_get (model, iter,
+ COLUMN_NAME, &name,
+ COLUMN_SELF, &self,
+ COLUMN_TOTAL, &total,
+ -1);
+
+ g_snprintf (sstr, sizeof sstr, "%.2lf%%", self);
+ g_snprintf (tstr, sizeof tstr, "%.2lf%%", total);
+
+ g_string_append_printf (str, "[%8s] [%8s] ", sstr, tstr);
+
+ for (gint i = 1; i < depth; i++)
+ g_string_append (str, " ");
+ g_string_append (str, name);
+ g_string_append_c (str, '\n');
+}
+
+static void
+copy_tree_view_selection (GtkTreeView *tree_view)
+{
+ g_autoptr(GString) str = NULL;
+ GtkClipboard *clipboard;
+
+ g_assert (GTK_IS_TREE_VIEW (tree_view));
+
+ str = g_string_new (" SELF TOTAL FUNCTION\n");
+ gtk_tree_selection_selected_foreach (gtk_tree_view_get_selection (tree_view),
+ copy_tree_view_selection_cb,
+ str);
+
+ clipboard = gtk_widget_get_clipboard (GTK_WIDGET (tree_view), GDK_SELECTION_CLIPBOARD);
+ gtk_clipboard_set_text (clipboard, str->str, str->len);
+}
+
+static void
+sysprof_memprof_page_copy_cb (GtkWidget *widget,
+ SysprofMemprofPage *self)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+ GtkWidget *toplevel;
+ GtkWidget *focus;
+
+ g_assert (GTK_IS_WIDGET (widget));
+ g_assert (SYSPROF_IS_MEMPROF_PAGE (self));
+
+ if (!(toplevel = gtk_widget_get_toplevel (widget)) ||
+ !GTK_IS_WINDOW (toplevel) ||
+ !(focus = gtk_window_get_focus (GTK_WINDOW (toplevel))))
+ return;
+
+ if (focus == GTK_WIDGET (priv->descendants_view))
+ copy_tree_view_selection (priv->descendants_view);
+ else if (focus == GTK_WIDGET (priv->callers_view))
+ copy_tree_view_selection (priv->callers_view);
+ else if (focus == GTK_WIDGET (priv->functions_view))
+ copy_tree_view_selection (priv->functions_view);
+}
+
+static void
+sysprof_memprof_page_generate_cb (GObject *object,
+ GAsyncResult *result,
+ gpointer user_data)
+{
+ SysprofProfile *profile = (SysprofProfile *)object;
+ SysprofMemprofPage *self;
+ g_autoptr(GTask) task = user_data;
+ g_autoptr(GError) error = NULL;
+
+ g_assert (SYSPROF_IS_PROFILE (profile));
+ g_assert (G_IS_ASYNC_RESULT (result));
+ g_assert (G_IS_TASK (task));
+
+ self = g_task_get_source_object (task);
+
+ if (!sysprof_profile_generate_finish (profile, result, &error))
+ g_task_return_error (task, g_steal_pointer (&error));
+ else
+ sysprof_memprof_page_set_profile (self, SYSPROF_MEMPROF_PROFILE (profile));
+}
+
+static void
+sysprof_memprof_page_load_async (SysprofPage *page,
+ SysprofCaptureReader *reader,
+ SysprofSelection *selection,
+ SysprofCaptureCondition *filter,
+ GCancellable *cancellable,
+ GAsyncReadyCallback callback,
+ gpointer user_data)
+{
+ SysprofMemprofPage *self = (SysprofMemprofPage *)page;
+ g_autoptr(SysprofCaptureReader) copy = NULL;
+ g_autoptr(SysprofProfile) profile = NULL;
+ g_autoptr(GTask) task = NULL;
+
+ g_assert (SYSPROF_IS_MEMPROF_PAGE (self));
+ g_assert (reader != NULL);
+ g_assert (SYSPROF_IS_SELECTION (selection));
+ g_assert (!cancellable || G_IS_CANCELLABLE (cancellable));
+
+ task = g_task_new (self, cancellable, callback, user_data);
+ g_task_set_source_tag (task, sysprof_memprof_page_load_async);
+
+ copy = sysprof_capture_reader_copy (reader);
+
+ profile = sysprof_memprof_profile_new_with_selection (selection);
+ sysprof_profile_set_reader (profile, reader);
+ sysprof_profile_generate (profile,
+ cancellable,
+ sysprof_memprof_page_generate_cb,
+ g_steal_pointer (&task));
+}
+
+static gboolean
+sysprof_memprof_page_load_finish (SysprofPage *page,
+ GAsyncResult *result,
+ GError **error)
+{
+ g_return_val_if_fail (SYSPROF_IS_MEMPROF_PAGE (page), FALSE);
+ g_return_val_if_fail (G_IS_TASK (result), FALSE);
+
+ return g_task_propagate_boolean (G_TASK (result), error);
+}
+
+static void
+sysprof_memprof_page_finalize (GObject *object)
+{
+ SysprofMemprofPage *self = (SysprofMemprofPage *)object;
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+
+ g_clear_pointer (&priv->history, g_queue_free);
+ g_clear_object (&priv->profile);
+
+ G_OBJECT_CLASS (sysprof_memprof_page_parent_class)->finalize (object);
+}
+
+static void
+sysprof_memprof_page_get_property (GObject *object,
+ guint prop_id,
+ GValue *value,
+ GParamSpec *pspec)
+{
+ SysprofMemprofPage *self = SYSPROF_MEMPROF_PAGE (object);
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+
+ switch (prop_id)
+ {
+ case PROP_PROFILE:
+ g_value_set_object (value, priv->profile);
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
+ }
+}
+
+static void
+sysprof_memprof_page_set_property (GObject *object,
+ guint prop_id,
+ const GValue *value,
+ GParamSpec *pspec)
+{
+ SysprofMemprofPage *self = SYSPROF_MEMPROF_PAGE (object);
+
+ switch (prop_id)
+ {
+ case PROP_PROFILE:
+ sysprof_memprof_page_set_profile (self, g_value_get_object (value));
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
+ }
+}
+
+static void
+sysprof_memprof_page_class_init (SysprofMemprofPageClass *klass)
+{
+ GObjectClass *object_class = G_OBJECT_CLASS (klass);
+ GtkWidgetClass *widget_class = GTK_WIDGET_CLASS (klass);
+ SysprofPageClass *page_class = SYSPROF_PAGE_CLASS (klass);
+ GtkBindingSet *bindings;
+
+ object_class->finalize = sysprof_memprof_page_finalize;
+ object_class->get_property = sysprof_memprof_page_get_property;
+ object_class->set_property = sysprof_memprof_page_set_property;
+
+ page_class->load_async = sysprof_memprof_page_load_async;
+ page_class->load_finish = sysprof_memprof_page_load_finish;
+
+ klass->go_previous = sysprof_memprof_page_real_go_previous;
+
+ properties [PROP_PROFILE] =
+ g_param_spec_object ("profile",
+ "Profile",
+ "The callgraph profile to view",
+ SYSPROF_TYPE_MEMPROF_PROFILE,
+ (G_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY | G_PARAM_STATIC_STRINGS));
+
+ g_object_class_install_properties (object_class, N_PROPS, properties);
+
+ signals [GO_PREVIOUS] =
+ g_signal_new ("go-previous",
+ G_TYPE_FROM_CLASS (klass),
+ G_SIGNAL_RUN_LAST | G_SIGNAL_ACTION,
+ G_STRUCT_OFFSET (SysprofMemprofPageClass, go_previous),
+ NULL, NULL, NULL, G_TYPE_NONE, 0);
+
+ gtk_widget_class_set_template_from_resource (widget_class,
+ "/org/gnome/sysprof/ui/sysprof-memprof-page.ui");
+
+ gtk_widget_class_bind_template_child_private (widget_class, SysprofMemprofPage, callers_view);
+ gtk_widget_class_bind_template_child_private (widget_class, SysprofMemprofPage, function_size_cell);
+ gtk_widget_class_bind_template_child_private (widget_class, SysprofMemprofPage, function_size_column);
+ gtk_widget_class_bind_template_child_private (widget_class, SysprofMemprofPage, functions_view);
+ gtk_widget_class_bind_template_child_private (widget_class, SysprofMemprofPage, descendants_view);
+ gtk_widget_class_bind_template_child_private (widget_class, SysprofMemprofPage, descendants_name_column);
+ gtk_widget_class_bind_template_child_private (widget_class, SysprofMemprofPage, stack);
+
+ bindings = gtk_binding_set_by_class (klass);
+ gtk_binding_entry_add_signal (bindings, GDK_KEY_Left, GDK_MOD1_MASK, "go-previous", 0);
+
+ g_type_ensure (SYSPROF_TYPE_CELL_RENDERER_PERCENT);
+}
+
+static void
+sysprof_memprof_page_init (SysprofMemprofPage *self)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+ DzlShortcutController *controller;
+ GtkTreeSelection *selection;
+ GtkCellRenderer *cell;
+
+ priv->history = g_queue_new ();
+
+ gtk_widget_init_template (GTK_WIDGET (self));
+
+ gtk_stack_set_visible_child_name (priv->stack, "empty-state");
+
+ selection = gtk_tree_view_get_selection (priv->functions_view);
+
+ g_signal_connect_object (selection,
+ "changed",
+ G_CALLBACK (sysprof_memprof_page_function_selection_changed),
+ self,
+ G_CONNECT_SWAPPED);
+
+ g_signal_connect_object (priv->descendants_view,
+ "row-activated",
+ G_CALLBACK (sysprof_memprof_page_descendant_activated),
+ self,
+ G_CONNECT_SWAPPED);
+
+ g_signal_connect_object (priv->callers_view,
+ "row-activated",
+ G_CALLBACK (sysprof_memprof_page_caller_activated),
+ self,
+ G_CONNECT_SWAPPED);
+
+ g_signal_connect (priv->descendants_view,
+ "move-cursor",
+ G_CALLBACK (descendants_view_move_cursor_cb),
+ NULL);
+
+ cell = g_object_new (GTK_TYPE_CELL_RENDERER_TEXT,
+ "ellipsize", PANGO_ELLIPSIZE_MIDDLE,
+ "xalign", 0.0f,
+ NULL);
+ gtk_tree_view_column_pack_start (priv->descendants_name_column, cell, TRUE);
+ gtk_tree_view_column_add_attribute (priv->descendants_name_column, cell, "text", 0);
+
+ cell = g_object_new (GTK_TYPE_CELL_RENDERER_TEXT,
+ "foreground", "#666666",
+ "scale", PANGO_SCALE_SMALL,
+ "xalign", 1.0f,
+ NULL);
+ gtk_tree_view_column_pack_start (priv->descendants_name_column, cell, FALSE);
+ gtk_tree_view_column_set_cell_data_func (priv->descendants_name_column, cell,
+ sysprof_memprof_page_tag_data_func,
+ self, NULL);
+
+ gtk_tree_view_column_set_cell_data_func (priv->function_size_column,
+ GTK_CELL_RENDERER (priv->function_size_cell),
+ sysprof_memprof_page_size_data_func,
+ self, NULL);
+
+ gtk_tree_selection_set_mode (gtk_tree_view_get_selection (priv->descendants_view),
+ GTK_SELECTION_MULTIPLE);
+
+ controller = dzl_shortcut_controller_find (GTK_WIDGET (self));
+
+ dzl_shortcut_controller_add_command_callback (controller,
+ "org.gnome.sysprof3.capture.copy",
+ "<Control>c",
+ DZL_SHORTCUT_PHASE_BUBBLE,
+ (GtkCallback) sysprof_memprof_page_copy_cb,
+ self,
+ NULL);
+}
+
+typedef struct _Descendant Descendant;
+
+struct _Descendant
+{
+ const gchar *name;
+ guint self;
+ guint cumulative;
+ Descendant *parent;
+ Descendant *siblings;
+ Descendant *children;
+};
+
+static void
+build_tree_cb (StackLink *trace,
+ gint size,
+ gpointer user_data)
+{
+ Descendant **tree = user_data;
+ Descendant *parent = NULL;
+ StackLink *link;
+
+ g_assert (trace != NULL);
+ g_assert (tree != NULL);
+
+ /* Get last item */
+ link = trace;
+ while (link->next)
+ link = link->next;
+
+ for (; link != NULL; link = link->prev)
+ {
+ const gchar *address = U64_TO_POINTER (link->data);
+ Descendant *prev = NULL;
+ Descendant *match = NULL;
+
+ for (match = *tree; match != NULL; match = match->siblings)
+ {
+ if (match->name == address)
+ {
+ if (prev != NULL)
+ {
+ /* Move to front */
+ prev->siblings = match->siblings;
+ match->siblings = *tree;
+ *tree = match;
+ }
+ break;
+ }
+ }
+
+ if (match == NULL)
+ {
+ /* Have we seen this object further up the tree? */
+ for (match = parent; match != NULL; match = match->parent)
+ {
+ if (match->name == address)
+ break;
+ }
+ }
+
+ if (match == NULL)
+ {
+ match = g_slice_new (Descendant);
+ match->name = address;
+ match->cumulative = 0;
+ match->self = 0;
+ match->children = NULL;
+ match->parent = parent;
+ match->siblings = *tree;
+ *tree = match;
+ }
+
+ tree = &match->children;
+ parent = match;
+ }
+
+ parent->self += size;
+
+ for (; parent != NULL; parent = parent->parent)
+ parent->cumulative += size;
+}
+
+static Descendant *
+build_tree (StackNode *node)
+{
+ Descendant *tree = NULL;
+
+ for (; node != NULL; node = node->next)
+ {
+ if (node->toplevel)
+ stack_node_foreach_trace (node, build_tree_cb, &tree);
+ }
+
+ return tree;
+}
+
+static void
+append_to_tree_and_free (SysprofMemprofPage *self,
+ StackStash *stash,
+ GtkTreeStore *store,
+ Descendant *item,
+ GtkTreeIter *parent)
+{
+ StackNode *node = NULL;
+ GtkTreeIter iter;
+ guint profile_size;
+
+ g_assert (GTK_IS_TREE_STORE (store));
+ g_assert (item != NULL);
+
+ profile_size = MAX (1, sysprof_memprof_page_get_profile_size (self));
+
+ gtk_tree_store_append (store, &iter, parent);
+
+ node = stack_stash_find_node (stash, (gpointer)item->name);
+
+ gtk_tree_store_set (store, &iter,
+ COLUMN_NAME, item->name,
+ COLUMN_SELF, item->self * 100.0 / (gdouble)profile_size,
+ COLUMN_TOTAL, item->cumulative * 100.0 / (gdouble)profile_size,
+ COLUMN_POINTER, node,
+ COLUMN_SIZE, item->cumulative,
+ -1);
+
+ if (item->siblings != NULL)
+ append_to_tree_and_free (self, stash, store, item->siblings, parent);
+
+ if (item->children != NULL)
+ append_to_tree_and_free (self, stash, store, item->children, &iter);
+
+ g_slice_free (Descendant, item);
+}
+
+static void
+sysprof_memprof_page_update_descendants (SysprofMemprofPage *self,
+ StackNode *node)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+ GtkTreeStore *store;
+
+ g_assert (SYSPROF_IS_MEMPROF_PAGE (self));
+
+ if (g_queue_peek_head (priv->history) != node)
+ g_queue_push_head (priv->history, node);
+
+ store = gtk_tree_store_new (5,
+ G_TYPE_STRING,
+ G_TYPE_DOUBLE,
+ G_TYPE_DOUBLE,
+ G_TYPE_POINTER,
+ G_TYPE_UINT64);
+
+ if (priv->profile != NULL)
+ {
+ StackStash *stash;
+
+ stash = sysprof_memprof_profile_get_stash (priv->profile);
+ if (stash != NULL)
+ {
+ Descendant *tree;
+
+ tree = build_tree (node);
+ if (tree != NULL)
+ append_to_tree_and_free (self, stash, store, tree, NULL);
+ }
+ }
+
+ gtk_tree_view_set_model (priv->descendants_view, GTK_TREE_MODEL (store));
+ gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (store),
+ COLUMN_TOTAL, GTK_SORT_DESCENDING);
+ sysprof_memprof_page_expand_descendants (self);
+
+ g_clear_object (&store);
+}
+
+/**
+ * sysprof_memprof_page_screenshot:
+ * @self: A #SysprofMemprofPage.
+ *
+ * This function will generate a text representation of the descendants tree.
+ * This is useful if you want to include various profiling information in a
+ * commit message or email.
+ *
+ * The text generated will match the current row expansion in the tree view.
+ *
+ * Returns: (nullable) (transfer full): A newly allocated string that should be freed
+ * with g_free().
+ */
+gchar *
+sysprof_memprof_page_screenshot (SysprofMemprofPage *self)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+ GtkTreeView *tree_view;
+ GtkTreeModel *model;
+ GtkTreePath *tree_path;
+ GString *str;
+ GtkTreeIter iter;
+
+ g_return_val_if_fail (SYSPROF_IS_MEMPROF_PAGE (self), NULL);
+
+ tree_view = priv->descendants_view;
+
+ if (NULL == (model = gtk_tree_view_get_model (tree_view)))
+ return NULL;
+
+ /*
+ * To avoid having to precalculate the deepest visible row, we
+ * put the timing information at the beginning of the line.
+ */
+
+ str = g_string_new (" SELF CUMULATIVE FUNCTION\n");
+ tree_path = gtk_tree_path_new_first ();
+
+ for (;;)
+ {
+ if (gtk_tree_model_get_iter (model, &iter, tree_path))
+ {
+ guint depth = gtk_tree_path_get_depth (tree_path);
+ StackNode *node;
+ gdouble in_self;
+ gdouble total;
+ guint i;
+
+ gtk_tree_model_get (model, &iter,
+ COLUMN_SELF, &in_self,
+ COLUMN_TOTAL, &total,
+ COLUMN_POINTER, &node,
+ -1);
+
+ g_string_append_printf (str, "[% 7.2lf%%] [% 7.2lf%%] ", in_self, total);
+
+ for (i = 0; i < depth; i++)
+ g_string_append (str, " ");
+ g_string_append (str, GSIZE_TO_POINTER (node->data));
+ g_string_append_c (str, '\n');
+
+ if (gtk_tree_view_row_expanded (tree_view, tree_path))
+ gtk_tree_path_down (tree_path);
+ else
+ gtk_tree_path_next (tree_path);
+
+ continue;
+ }
+
+ if (!gtk_tree_path_up (tree_path) || !gtk_tree_path_get_depth (tree_path))
+ break;
+
+ gtk_tree_path_next (tree_path);
+ }
+
+ gtk_tree_path_free (tree_path);
+
+ return g_string_free (str, FALSE);
+}
+
+guint
+sysprof_memprof_page_get_n_functions (SysprofMemprofPage *self)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+ GtkTreeModel *model;
+ guint ret = 0;
+
+ g_return_val_if_fail (SYSPROF_IS_MEMPROF_PAGE (self), 0);
+
+ if (NULL != (model = gtk_tree_view_get_model (priv->functions_view)))
+ ret = gtk_tree_model_iter_n_children (model, NULL);
+
+ return ret;
+}
+
+void
+_sysprof_memprof_page_set_loading (SysprofMemprofPage *self,
+ gboolean loading)
+{
+ SysprofMemprofPagePrivate *priv = sysprof_memprof_page_get_instance_private (self);
+
+ g_return_if_fail (SYSPROF_IS_MEMPROF_PAGE (self));
+
+ if (loading)
+ priv->loading++;
+ else
+ priv->loading--;
+
+ if (priv->loading)
+ gtk_stack_set_visible_child_name (priv->stack, "loading");
+ else
+ gtk_stack_set_visible_child_name (priv->stack, "callgraph");
+}
diff --git a/src/libsysprof-ui/sysprof-memprof-page.h b/src/libsysprof-ui/sysprof-memprof-page.h
new file mode 100644
index 0000000..1b3f7af
--- /dev/null
+++ b/src/libsysprof-ui/sysprof-memprof-page.h
@@ -0,0 +1,51 @@
+/* sysprof-memprof-page.h
+ *
+ * Copyright 2016-2019 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#pragma once
+
+#include <gtk/gtk.h>
+#include <sysprof.h>
+
+#include "sysprof-page.h"
+
+G_BEGIN_DECLS
+
+#define SYSPROF_TYPE_MEMPROF_PAGE (sysprof_memprof_page_get_type())
+
+G_DECLARE_DERIVABLE_TYPE (SysprofMemprofPage, sysprof_memprof_page, SYSPROF, MEMPROF_PAGE, SysprofPage)
+
+struct _SysprofMemprofPageClass
+{
+ SysprofPageClass parent_class;
+
+ void (*go_previous) (SysprofMemprofPage *self);
+
+ /*< private >*/
+ gpointer _reserved[16];
+};
+
+GtkWidget *sysprof_memprof_page_new (void);
+SysprofMemprofProfile *sysprof_memprof_page_get_profile (SysprofMemprofPage *self);
+void sysprof_memprof_page_set_profile (SysprofMemprofPage *self,
+ SysprofMemprofProfile *profile);
+gchar *sysprof_memprof_page_screenshot (SysprofMemprofPage *self);
+guint sysprof_memprof_page_get_n_functions (SysprofMemprofPage *self);
+
+G_END_DECLS
diff --git a/src/libsysprof-ui/sysprof-memprof-page.ui b/src/libsysprof-ui/sysprof-memprof-page.ui
new file mode 100644
index 0000000..66899bb
--- /dev/null
+++ b/src/libsysprof-ui/sysprof-memprof-page.ui
@@ -0,0 +1,232 @@
+<interface>
+ <template class="SysprofMemprofPage" parent="SysprofPage">
+ <child>
+ <object class="GtkStack" id="stack">
+ <property name="visible">true</property>
+ <child>
+ <object class="GtkPaned">
+ <property name="orientation">horizontal</property>
+ <property name="position">450</property>
+ <property name="visible">true</property>
+ <child>
+ <object class="GtkPaned">
+ <property name="orientation">vertical</property>
+ <property name="visible">true</property>
+ <child>
+ <object class="GtkScrolledWindow">
+ <property name="visible">true</property>
+ <child>
+ <object class="GtkTreeView" id="functions_view">
+ <property name="fixed-height-mode">true</property>
+ <property name="visible">true</property>
+ <child>
+ <object class="GtkTreeViewColumn" id="function_name_column">
+ <property name="expand">true</property>
+ <property name="sizing">fixed</property>
+ <property name="sort-column-id">0</property>
+ <property name="title" translatable="yes">Functions</property>
+ <child>
+ <object class="GtkCellRendererText">
+ <property name="ellipsize">middle</property>
+ </object>
+ <attributes>
+ <attribute name="text">0</attribute>
+ </attributes>
+ </child>
+ </object>
+ </child>
+ <child>
+ <object class="GtkTreeViewColumn" id="function_self_column">
+ <property name="expand">false</property>
+ <property name="sizing">fixed</property>
+ <property name="sort-column-id">1</property>
+ <property name="title" translatable="yes">Self</property>
+ <child>
+ <object class="SysprofCellRendererPercent">
+ <property name="width">65</property>
+ </object>
+ <attributes>
+ <attribute name="percent">1</attribute>
+ </attributes>
+ </child>
+ </object>
+ </child>
+ <child>
+ <object class="GtkTreeViewColumn" id="function_total_column">
+ <property name="expand">false</property>
+ <property name="sizing">fixed</property>
+ <property name="sort-column-id">2</property>
+ <property name="title" translatable="yes">Total</property>
+ <child>
+ <object class="SysprofCellRendererPercent">
+ <property name="width">65</property>
+ </object>
+ <attributes>
+ <attribute name="percent">2</attribute>
+ </attributes>
+ </child>
+ </object>
+ </child>
+ </object>
+ </child>
+ </object>
+ <packing>
+ <property name="resize">true</property>
+ </packing>
+ </child>
+ <child>
+ <object class="GtkScrolledWindow">
+ <property name="visible">true</property>
+ <child>
+ <object class="GtkTreeView" id="callers_view">
+ <property name="visible">true</property>
+ <child>
+ <object class="GtkTreeViewColumn" id="callers_name_column">
+ <property name="expand">true</property>
+ <property name="sizing">fixed</property>
+ <property name="sort-column-id">0</property>
+ <property name="title" translatable="yes">Callers</property>
+ <child>
+ <object class="GtkCellRendererText">
+ <property name="ellipsize">middle</property>
+ </object>
+ <attributes>
+ <attribute name="text">0</attribute>
+ </attributes>
+ </child>
+ </object>
+ </child>
+ <child>
+ <object class="GtkTreeViewColumn" id="callers_self_column">
+ <property name="expand">false</property>
+ <property name="sizing">fixed</property>
+ <property name="sort-column-id">1</property>
+ <property name="title" translatable="yes">Self</property>
+ <child>
+ <object class="SysprofCellRendererPercent">
+ <property name="width">65</property>
+ </object>
+ <attributes>
+ <attribute name="percent">1</attribute>
+ </attributes>
+ </child>
+ </object>
+ </child>
+ <child>
+ <object class="GtkTreeViewColumn" id="callers_total_column">
+ <property name="expand">false</property>
+ <property name="sizing">fixed</property>
+ <property name="sort-column-id">2</property>
+ <property name="title" translatable="yes">Total</property>
+ <child>
+ <object class="SysprofCellRendererPercent">
+ <property name="width">65</property>
+ </object>
+ <attributes>
+ <attribute name="percent">2</attribute>
+ </attributes>
+ </child>
+ </object>
+ </child>
+ </object>
+ </child>
+ </object>
+ <packing>
+ <property name="resize">true</property>
+ </packing>
+ </child>
+ </object>
+ </child>
+ <child>
+ <object class="GtkScrolledWindow">
+ <property name="visible">true</property>
+ <child>
+ <object class="GtkTreeView" id="descendants_view">
+ <property name="visible">true</property>
+ <child>
+ <object class="GtkTreeViewColumn" id="descendants_name_column">
+ <property name="expand">true</property>
+ <property name="sizing">autosize</property>
+ <property name="sort-column-id">0</property>
+ <property name="title" translatable="yes">Descendants</property>
+ </object>
+ </child>
+ <child>
+ <object class="GtkTreeViewColumn" id="descendants_self_column">
+ <property name="expand">false</property>
+ <property name="sizing">fixed</property>
+ <property name="sort-column-id">1</property>
+ <property name="title" translatable="yes">Self</property>
+ <child>
+ <object class="SysprofCellRendererPercent">
+ <property name="width">65</property>
+ </object>
+ <attributes>
+ <attribute name="percent">1</attribute>
+ </attributes>
+ </child>
+ </object>
+ </child>
+ <child>
+ <object class="GtkTreeViewColumn" id="descendants_total_column">
+ <property name="expand">false</property>
+ <property name="sizing">fixed</property>
+ <property name="sort-column-id">2</property>
+ <property name="title" translatable="yes">Total</property>
+ <child>
+ <object class="SysprofCellRendererPercent">
+ <property name="width">65</property>
+ </object>
+ <attributes>
+ <attribute name="percent">2</attribute>
+ </attributes>
+ </child>
+ </object>
+ </child>
+ <child>
+ <object class="GtkTreeViewColumn" id="function_size_column">
+ <property name="expand">false</property>
+ <property name="sizing">fixed</property>
+ <property name="title" translatable="yes">Size</property>
+ <child>
+ <object class="GtkCellRendererText" id="function_size_cell">
+ <property name="xalign">1.0</property>
+ </object>
+ </child>
+ </object>
+ </child>
+ </object>
+ </child>
+ </object>
+ </child>
+ </object>
+ <packing>
+ <property name="name">callgraph</property>
+ </packing>
+ </child>
+ <child>
+ <object class="DzlEmptyState">
+ <property name="icon-name">content-loading-symbolic</property>
+ <property name="title" translatable="yes">Generating Callgraph</property>
+ <property name="subtitle" translatable="yes">Sysprof is busy creating the selected
callgraph.</property>
+ <property name="visible">true</property>
+ </object>
+ <packing>
+ <property name="name">loading</property>
+ </packing>
+ </child>
+ <child>
+ <object class="DzlEmptyState">
+ <property name="icon-name">computer-fail-symbolic</property>
+ <property name="title" translatable="yes">Not Enough Samples</property>
+ <property name="subtitle" translatable="yes">More samples are necessary to display a
callgraph.</property>
+ <property name="visible">false</property>
+ </object>
+ <packing>
+ <property name="name">empty-state</property>
+ </packing>
+ </child>
+ </object>
+ </child>
+ </template>
+</interface>
diff --git a/src/libsysprof-ui/sysprof-memprof-visualizer.c b/src/libsysprof-ui/sysprof-memprof-visualizer.c
new file mode 100644
index 0000000..d2f47ea
--- /dev/null
+++ b/src/libsysprof-ui/sysprof-memprof-visualizer.c
@@ -0,0 +1,614 @@
+/* sysprof-memprof-visualizer.c
+ *
+ * Copyright 2020 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include "config.h"
+
+#define G_LOG_DOMAIN "sysprof-memprof-visualizer"
+
+#include <glib/gi18n.h>
+#include <math.h>
+#include <stddef.h>
+
+#include "rax.h"
+
+#include "sysprof-memprof-visualizer.h"
+
+typedef struct
+{
+ cairo_surface_t *surface;
+ SysprofCaptureReader *reader;
+ rax *rax;
+ GtkAllocation alloc;
+ gint64 begin_time;
+ gint64 duration;
+ gint64 total_alloc;
+ gint64 max_alloc;
+ GdkRGBA fg;
+ GdkRGBA fg2;
+ guint scale;
+} DrawContext;
+
+struct _SysprofMemprofVisualizer
+{
+ SysprofVisualizer parent_instance;
+
+ SysprofCaptureReader *reader;
+ GCancellable *cancellable;
+
+ cairo_surface_t *surface;
+ gint surface_w;
+ gint surface_h;
+
+ guint queued_draw;
+
+ gint64 begin_time;
+ gint64 duration;
+
+ gint64 cached_total_alloc;
+ gint64 cached_max_alloc;
+
+ guint mode : 1;
+};
+
+enum {
+ MODE_ALLOCS,
+ MODE_TOTAL,
+};
+
+G_DEFINE_TYPE (SysprofMemprofVisualizer, sysprof_memprof_visualizer, SYSPROF_TYPE_VISUALIZER)
+
+static void
+draw_context_free (DrawContext *draw)
+{
+ g_clear_pointer (&draw->reader, sysprof_capture_reader_unref);
+ g_clear_pointer (&draw->surface, cairo_surface_destroy);
+ g_clear_pointer (&draw->rax, raxFree);
+ g_slice_free (DrawContext, draw);
+}
+
+static void
+sysprof_memprof_visualizer_set_reader (SysprofVisualizer *visualizer,
+ SysprofCaptureReader *reader)
+{
+ SysprofMemprofVisualizer *self = (SysprofMemprofVisualizer *)visualizer;
+
+ g_assert (SYSPROF_IS_MEMPROF_VISUALIZER (self));
+
+ if (reader == self->reader)
+ return;
+
+ g_clear_pointer (&self->reader, sysprof_capture_reader_unref);
+
+ self->reader = sysprof_capture_reader_ref (reader);
+ self->begin_time = sysprof_capture_reader_get_start_time (reader);
+ self->duration = sysprof_capture_reader_get_end_time (reader)
+ - sysprof_capture_reader_get_start_time (reader);
+
+ gtk_widget_queue_draw (GTK_WIDGET (self));
+}
+
+SysprofVisualizer *
+sysprof_memprof_visualizer_new (gboolean total_allocs)
+{
+ SysprofMemprofVisualizer *self;
+
+ self = g_object_new (SYSPROF_TYPE_MEMPROF_VISUALIZER,
+ "title", total_allocs ? _("Memory Used") : _("Memory Allocations"),
+ "height-request", 35,
+ "visible", TRUE,
+ NULL);
+
+ if (total_allocs)
+ self->mode = MODE_TOTAL;
+ else
+ self->mode = MODE_ALLOCS;
+
+ return SYSPROF_VISUALIZER (self);
+}
+
+static guint64
+get_max_alloc (SysprofCaptureReader *reader)
+{
+ SysprofCaptureFrameType type;
+ gint64 ret = 0;
+
+ while (sysprof_capture_reader_peek_type (reader, &type))
+ {
+ const SysprofCaptureAllocation *ev;
+
+ if (type == SYSPROF_CAPTURE_FRAME_ALLOCATION)
+ {
+ if (!(ev = sysprof_capture_reader_read_allocation (reader)))
+ break;
+
+ if (ev->alloc_size > ret)
+ ret = ev->alloc_size;
+ }
+ else
+ {
+ if (!sysprof_capture_reader_skip (reader))
+ break;
+ continue;
+ }
+ }
+
+ sysprof_capture_reader_reset (reader);
+
+ return ret;
+}
+
+static guint64
+get_total_alloc (SysprofCaptureReader *reader)
+{
+ SysprofCaptureFrameType type;
+ guint64 total = 0;
+ guint64 max = 0;
+ rax *r;
+
+ r = raxNew ();
+
+ while (sysprof_capture_reader_peek_type (reader, &type))
+ {
+ const SysprofCaptureAllocation *ev;
+
+ if (type == SYSPROF_CAPTURE_FRAME_ALLOCATION)
+ {
+ if (!(ev = sysprof_capture_reader_read_allocation (reader)))
+ break;
+
+ if (ev->alloc_size > 0)
+ {
+ raxInsert (r,
+ (guint8 *)&ev->alloc_addr,
+ sizeof ev->alloc_addr,
+ GSIZE_TO_POINTER (ev->alloc_size),
+ NULL);
+
+ total += ev->alloc_size;
+
+ if (total > max)
+ max = total;
+ }
+ else
+ {
+ gpointer res = raxFind (r, (guint8 *)&ev->alloc_addr, sizeof ev->alloc_addr);
+
+ if (res != raxNotFound)
+ {
+ total -= GPOINTER_TO_SIZE (res);
+ raxRemove (r,
+ (guint8 *)&ev->alloc_addr,
+ sizeof ev->alloc_addr,
+ NULL);
+ }
+ }
+ }
+ else
+ {
+ if (!sysprof_capture_reader_skip (reader))
+ break;
+ continue;
+ }
+ }
+
+ sysprof_capture_reader_reset (reader);
+ raxFree (r);
+
+ return max;
+}
+
+static void
+draw_total_worker (GTask *task,
+ gpointer source_object,
+ gpointer task_data,
+ GCancellable *cancellable)
+{
+ SysprofCaptureFrameType type;
+ DrawContext *draw = task_data;
+ gint64 total = 0;
+ cairo_t *cr;
+ rax *r;
+ gint x = 0;
+
+ g_assert (G_IS_TASK (task));
+ g_assert (draw != NULL);
+ g_assert (draw->surface != NULL);
+ g_assert (draw->reader != NULL);
+ g_assert (!cancellable || G_IS_CANCELLABLE (cancellable));
+
+ if (draw->total_alloc == 0)
+ draw->total_alloc = get_total_alloc (draw->reader);
+
+ r = raxNew ();
+
+ /* To avoid sorting, this code assums that all allocation information
+ * is sorted and in order. Generally this is the case, but a crafted
+ * syscap file could break it on purpose if they tried.
+ */
+
+ cr = cairo_create (draw->surface);
+ cairo_set_antialias (cr, CAIRO_ANTIALIAS_NONE);
+ cairo_set_source_rgb (cr, 0, 0, 0);
+
+ while (sysprof_capture_reader_peek_type (draw->reader, &type))
+ {
+ const SysprofCaptureAllocation *ev;
+ gint y;
+
+ if (type == SYSPROF_CAPTURE_FRAME_ALLOCATION)
+ {
+ if (!(ev = sysprof_capture_reader_read_allocation (draw->reader)))
+ break;
+
+ if (ev->alloc_size > 0)
+ {
+ raxInsert (r,
+ (guint8 *)&ev->alloc_addr,
+ sizeof ev->alloc_addr,
+ GSIZE_TO_POINTER (ev->alloc_size),
+ NULL);
+
+ total += ev->alloc_size;
+ }
+ else
+ {
+ gpointer res = raxFind (r, (guint8 *)&ev->alloc_addr, sizeof ev->alloc_addr);
+
+ if (res != raxNotFound)
+ {
+ total -= GPOINTER_TO_SIZE (res);
+ raxRemove (r,
+ (guint8 *)&ev->alloc_addr,
+ sizeof ev->alloc_addr,
+ NULL);
+ }
+ }
+ }
+ else
+ {
+ if (!sysprof_capture_reader_skip (draw->reader))
+ break;
+ continue;
+ }
+
+ x = (ev->frame.time - draw->begin_time) / (gdouble)draw->duration * draw->alloc.width;
+ y = draw->alloc.height - ((gdouble)total / (gdouble)draw->total_alloc * (gdouble)draw->alloc.height);
+
+ cairo_rectangle (cr, x, y, 1, 1);
+ cairo_fill (cr);
+ }
+
+ cairo_destroy (cr);
+
+ g_task_return_boolean (task, TRUE);
+
+ raxFree (r);
+}
+
+static void
+draw_alloc_worker (GTask *task,
+ gpointer source_object,
+ gpointer task_data,
+ GCancellable *cancellable)
+{
+ static const gdouble dashes[] = { 1.0, 2.0 };
+ DrawContext *draw = task_data;
+ SysprofCaptureFrameType type;
+ GdkRGBA *last;
+ GdkRGBA mid;
+ cairo_t *cr;
+ guint counter = 0;
+ gint midpt;
+ gdouble log_max;
+
+ g_assert (G_IS_TASK (task));
+ g_assert (draw != NULL);
+ g_assert (draw->surface != NULL);
+ g_assert (draw->reader != NULL);
+ g_assert (!cancellable || G_IS_CANCELLABLE (cancellable));
+
+ if (draw->max_alloc == 0)
+ draw->max_alloc = get_max_alloc (draw->reader);
+
+ log_max = log10 (draw->max_alloc);
+ midpt = draw->alloc.height / 2;
+
+ cr = cairo_create (draw->surface);
+
+ /* Draw mid-point line */
+ mid = draw->fg;
+ mid.alpha *= 0.4;
+ cairo_set_line_width (cr, 1.0);
+ gdk_cairo_set_source_rgba (cr, &mid);
+ cairo_move_to (cr, 0, midpt);
+ cairo_line_to (cr, draw->alloc.width, midpt);
+ cairo_set_dash (cr, dashes, G_N_ELEMENTS (dashes), 0);
+ cairo_stroke (cr);
+
+ cairo_set_antialias (cr, CAIRO_ANTIALIAS_NONE);
+ gdk_cairo_set_source_rgba (cr, &draw->fg);
+ last = &draw->fg;
+
+ /* Now draw data points */
+ while (sysprof_capture_reader_peek_type (draw->reader, &type))
+ {
+ const SysprofCaptureAllocation *ev;
+ gint64 size;
+ gdouble l;
+ gint x;
+ gint y;
+
+ /* Cancellation check every 1000 frames */
+ if G_UNLIKELY (++counter == 1000)
+ {
+ if (g_task_return_error_if_cancelled (task))
+ {
+ cairo_destroy (cr);
+ return;
+ }
+
+ counter = 0;
+ }
+
+ /* We only care about memory frames here */
+ if (type != SYSPROF_CAPTURE_FRAME_ALLOCATION)
+ {
+ if (!sysprof_capture_reader_skip (draw->reader))
+ break;
+ continue;
+ }
+
+ if (!(ev = sysprof_capture_reader_read_allocation (draw->reader)))
+ break;
+
+ if (ev->alloc_size > 0)
+ {
+ size = ev->alloc_size;
+ raxInsert (draw->rax, (guint8 *)&ev->alloc_addr, sizeof ev->alloc_addr, GSIZE_TO_POINTER (size),
NULL);
+
+ if (last != &draw->fg)
+ {
+ gdk_cairo_set_source_rgba (cr, &draw->fg);
+ last = &draw->fg;
+ }
+ }
+ else
+ {
+ size = GPOINTER_TO_SIZE (raxFind (draw->rax, (guint8 *)&ev->alloc_addr, sizeof ev->alloc_addr));
+ if (size)
+ raxRemove (draw->rax, (guint8 *)&ev->alloc_addr, sizeof ev->alloc_addr, NULL);
+
+ if (last != &draw->fg2)
+ {
+ gdk_cairo_set_source_rgba (cr, &draw->fg2);
+ last = &draw->fg2;
+ }
+ }
+
+ l = log10 (size);
+
+ x = (ev->frame.time - draw->begin_time) / (gdouble)draw->duration * draw->alloc.width;
+
+ if (ev->alloc_size > 0)
+ y = midpt - ((l / log_max) * midpt);
+ else
+ y = midpt + ((l / log_max) * midpt);
+
+ /* Fill immediately instead of batching draws so that
+ * we don't take a lot of memory to hold on to the
+ * path while drawing.
+ */
+ cairo_rectangle (cr, x, y, 1, 1);
+ cairo_fill (cr);
+ }
+
+ cairo_destroy (cr);
+
+ g_task_return_boolean (task, TRUE);
+}
+
+static void
+draw_finished (GObject *object,
+ GAsyncResult *result,
+ gpointer user_data)
+{
+ g_autoptr(SysprofMemprofVisualizer) self = user_data;
+ g_autoptr(GError) error = NULL;
+
+ g_assert (object == NULL);
+ g_assert (G_IS_TASK (result));
+ g_assert (SYSPROF_IS_MEMPROF_VISUALIZER (self));
+
+ if (g_task_propagate_boolean (G_TASK (result), &error))
+ {
+ DrawContext *draw = g_task_get_task_data (G_TASK (result));
+
+ g_clear_pointer (&self->surface, cairo_surface_destroy);
+
+ self->surface = g_steal_pointer (&draw->surface);
+ self->surface_w = draw->alloc.width;
+ self->surface_h = draw->alloc.height;
+ self->cached_max_alloc = draw->max_alloc;
+ self->cached_total_alloc = draw->total_alloc;
+
+ gtk_widget_queue_draw (GTK_WIDGET (self));
+ }
+}
+
+static gboolean
+sysprof_memprof_visualizer_begin_draw (SysprofMemprofVisualizer *self)
+{
+ g_autoptr(GTask) task = NULL;
+ GtkAllocation alloc;
+ DrawContext *draw;
+
+ g_assert (SYSPROF_IS_MEMPROF_VISUALIZER (self));
+
+ self->queued_draw = 0;
+
+ /* Make sure we even need to draw */
+ gtk_widget_get_allocation (GTK_WIDGET (self), &alloc);
+ if (self->reader == NULL ||
+ !gtk_widget_get_visible (GTK_WIDGET (self)) ||
+ !gtk_widget_get_mapped (GTK_WIDGET (self)) ||
+ alloc.width == 0 || alloc.height == 0)
+ return G_SOURCE_REMOVE;
+
+ /* Some GPUs (Intel) cannot deal with graphics textures larger than
+ * 8000x8000. So here we are going to cheat a bit and just use that as our
+ * max, and scale when drawing. The biggest issue here is that long term we
+ * need a tiling solution that lets us render lots of tiles and then draw
+ * them as necessary.
+ */
+ if (alloc.width > 8000)
+ alloc.width = 8000;
+
+ draw = g_slice_new0 (DrawContext);
+ draw->rax = raxNew ();
+ draw->alloc.width = alloc.width;
+ draw->alloc.height = alloc.height;
+ draw->reader = sysprof_capture_reader_copy (self->reader);
+ draw->begin_time = self->begin_time;
+ draw->duration = self->duration;
+ draw->scale = gtk_widget_get_scale_factor (GTK_WIDGET (self));
+ draw->max_alloc = self->cached_max_alloc;
+ draw->total_alloc = self->cached_total_alloc;
+
+ gdk_rgba_parse (&draw->fg, "rgba(246,97,81,1)");
+ gdk_rgba_parse (&draw->fg2, "rgba(245,194,17,1)");
+
+ draw->surface = cairo_image_surface_create (CAIRO_FORMAT_ARGB32,
+ alloc.width * draw->scale,
+ alloc.height * draw->scale);
+ cairo_surface_set_device_scale (draw->surface, draw->scale, draw->scale);
+
+ g_cancellable_cancel (self->cancellable);
+ g_clear_object (&self->cancellable);
+ self->cancellable = g_cancellable_new ();
+
+ task = g_task_new (NULL, self->cancellable, draw_finished, g_object_ref (self));
+ g_task_set_source_tag (task, sysprof_memprof_visualizer_begin_draw);
+ g_task_set_task_data (task, g_steal_pointer (&draw), (GDestroyNotify)draw_context_free);
+
+ if (self->mode == MODE_ALLOCS)
+ g_task_run_in_thread (task, draw_alloc_worker);
+ else
+ g_task_run_in_thread (task, draw_total_worker);
+
+ return G_SOURCE_REMOVE;
+}
+
+static void
+sysprof_memprof_visualizer_queue_redraw (SysprofMemprofVisualizer *self)
+{
+ g_assert (SYSPROF_IS_MEMPROF_VISUALIZER (self));
+
+ if (self->queued_draw == 0)
+ self->queued_draw = g_idle_add_full (G_PRIORITY_HIGH_IDLE,
+ (GSourceFunc) sysprof_memprof_visualizer_begin_draw,
+ g_object_ref (self),
+ g_object_unref);
+}
+
+static void
+sysprof_memprof_visualizer_size_allocate (GtkWidget *widget,
+ GtkAllocation *alloc)
+{
+ SysprofMemprofVisualizer *self = (SysprofMemprofVisualizer *)widget;
+
+ g_assert (GTK_IS_WIDGET (widget));
+ g_assert (alloc != NULL);
+
+ GTK_WIDGET_CLASS (sysprof_memprof_visualizer_parent_class)->size_allocate (widget, alloc);
+
+ sysprof_memprof_visualizer_queue_redraw (self);
+}
+
+static void
+sysprof_memprof_visualizer_destroy (GtkWidget *widget)
+{
+ SysprofMemprofVisualizer *self = (SysprofMemprofVisualizer *)widget;
+
+ g_clear_pointer (&self->reader, sysprof_capture_reader_unref);
+ g_clear_pointer (&self->surface, cairo_surface_destroy);
+ g_clear_handle_id (&self->queued_draw, g_source_remove);
+
+ GTK_WIDGET_CLASS (sysprof_memprof_visualizer_parent_class)->destroy (widget);
+}
+
+static gboolean
+sysprof_memprof_visualizer_draw (GtkWidget *widget,
+ cairo_t *cr)
+{
+ SysprofMemprofVisualizer *self = (SysprofMemprofVisualizer *)widget;
+ gboolean ret;
+
+ g_assert (SYSPROF_IS_MEMPROF_VISUALIZER (self));
+ g_assert (cr != NULL);
+
+ ret = GTK_WIDGET_CLASS (sysprof_memprof_visualizer_parent_class)->draw (widget, cr);
+
+ if (self->surface != NULL)
+ {
+ GtkAllocation alloc;
+
+ gtk_widget_get_allocation (widget, &alloc);
+
+ cairo_save (cr);
+ cairo_rectangle (cr, 0, 0, alloc.width, alloc.height);
+
+ /* We might be drawing an updated image in the background, and this
+ * will take our current surface (which is the wrong size) and draw
+ * it stretched to fit the allocation. That gives us *something* that
+ * represents the end result even if it is a bit blurry in the mean
+ * time. Allocators take a while to render anyway.
+ */
+ if (self->surface_w != alloc.width || self->surface_h != alloc.height)
+ {
+ cairo_scale (cr,
+ (gdouble)alloc.width / (gdouble)self->surface_w,
+ (gdouble)alloc.height / (gdouble)self->surface_h);
+ }
+
+ cairo_set_source_surface (cr, self->surface, 0, 0);
+ cairo_paint (cr);
+ cairo_restore (cr);
+ }
+
+ return ret;
+}
+
+static void
+sysprof_memprof_visualizer_class_init (SysprofMemprofVisualizerClass *klass)
+{
+ GtkWidgetClass *widget_class = GTK_WIDGET_CLASS (klass);
+ SysprofVisualizerClass *visualizer_class = SYSPROF_VISUALIZER_CLASS (klass);
+
+ widget_class->destroy = sysprof_memprof_visualizer_destroy;
+ widget_class->draw = sysprof_memprof_visualizer_draw;
+ widget_class->size_allocate = sysprof_memprof_visualizer_size_allocate;
+
+ visualizer_class->set_reader = sysprof_memprof_visualizer_set_reader;
+}
+
+static void
+sysprof_memprof_visualizer_init (SysprofMemprofVisualizer *self)
+{
+}
diff --git a/src/libsysprof-ui/sysprof-memprof-visualizer.h b/src/libsysprof-ui/sysprof-memprof-visualizer.h
new file mode 100644
index 0000000..04f078c
--- /dev/null
+++ b/src/libsysprof-ui/sysprof-memprof-visualizer.h
@@ -0,0 +1,33 @@
+/* sysprof-memprof-visualizer.h
+ *
+ * Copyright 2020 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#pragma once
+
+#include "sysprof-visualizer.h"
+
+G_BEGIN_DECLS
+
+#define SYSPROF_TYPE_MEMPROF_VISUALIZER (sysprof_memprof_visualizer_get_type())
+
+G_DECLARE_FINAL_TYPE (SysprofMemprofVisualizer, sysprof_memprof_visualizer, SYSPROF, MEMPROF_VISUALIZER,
SysprofVisualizer)
+
+SysprofVisualizer *sysprof_memprof_visualizer_new (gboolean total_allocs);
+
+G_END_DECLS
diff --git a/src/libsysprof-ui/sysprof-profiler-assistant.c b/src/libsysprof-ui/sysprof-profiler-assistant.c
index 9ab76bc..dc22da2 100644
--- a/src/libsysprof-ui/sysprof-profiler-assistant.c
+++ b/src/libsysprof-ui/sysprof-profiler-assistant.c
@@ -41,6 +41,7 @@
#include "sysprof-callgraph-aid.h"
#include "sysprof-cpu-aid.h"
#include "sysprof-memory-aid.h"
+#include "sysprof-memprof-aid.h"
#include "sysprof-netdev-aid.h"
#include "sysprof-proxy-aid.h"
#include "sysprof-rapl-aid.h"
@@ -397,6 +398,7 @@ sysprof_profiler_assistant_class_init (SysprofProfilerAssistantClass *klass)
g_type_ensure (SYSPROF_TYPE_DISKSTAT_SOURCE);
g_type_ensure (SYSPROF_TYPE_ENVIRON_EDITOR);
g_type_ensure (SYSPROF_TYPE_MEMORY_AID);
+ g_type_ensure (SYSPROF_TYPE_MEMPROF_AID);
g_type_ensure (SYSPROF_TYPE_NETDEV_AID);
g_type_ensure (SYSPROF_TYPE_PROXY_AID);
g_type_ensure (SYSPROF_TYPE_RAPL_AID);
diff --git a/src/libsysprof-ui/sysprof-profiler-assistant.ui b/src/libsysprof-ui/sysprof-profiler-assistant.ui
index f7737ec..b6a7010 100644
--- a/src/libsysprof-ui/sysprof-profiler-assistant.ui
+++ b/src/libsysprof-ui/sysprof-profiler-assistant.ui
@@ -3,6 +3,7 @@
<requires lib="gtk+" version="3.22"/>
<object class="SysprofCpuAid" id="cpu_aid"/>
<object class="SysprofMemoryAid" id="memory_aid"/>
+ <object class="SysprofMemprofAid" id="memprof_aid"/>
<object class="SysprofCallgraphAid" id="callgraph_aid"/>
<object class="SysprofNetdevAid" id="network_aid"/>
<object class="SysprofRaplAid" id="rapl_aid"/>
@@ -178,6 +179,14 @@
<property name="visible">true</property>
</object>
</child>
+ <child>
+ <object class="SysprofAidIcon">
+ <property name="tooltip-text" translatable="yes">Track application memory
allocations (Sysprof must launch target application)</property>
+ <property name="aid">memprof_aid</property>
+ <property name="selected">false</property>
+ <property name="visible">true</property>
+ </object>
+ </child>
</object>
</child>
</object>
diff --git a/src/libsysprof-ui/sysprof-ui-private.h b/src/libsysprof-ui/sysprof-ui-private.h
index aef6e8a..a0a08fd 100644
--- a/src/libsysprof-ui/sysprof-ui-private.h
+++ b/src/libsysprof-ui/sysprof-ui-private.h
@@ -29,6 +29,9 @@ G_BEGIN_DECLS
void _sysprof_callgraph_page_set_failed (SysprofCallgraphPage *self);
void _sysprof_callgraph_page_set_loading (SysprofCallgraphPage *self,
gboolean loading);
+void _sysprof_memory_page_set_failed (SysprofCallgraphPage *self);
+void _sysprof_memory_page_set_loading (SysprofCallgraphPage *self,
+ gboolean loading);
void _sysprof_display_focus_record (SysprofDisplay *self);
void _sysprof_profiler_assistant_focus_record (SysprofProfilerAssistant *self);
gchar *_sysprof_format_duration (gint64 duration);
diff --git a/src/libsysprof/meson.build b/src/libsysprof/meson.build
index 2b40744..a7c52bd 100644
--- a/src/libsysprof/meson.build
+++ b/src/libsysprof/meson.build
@@ -16,6 +16,8 @@ libsysprof_public_sources = [
'sysprof-kernel-symbol.c',
'sysprof-kernel-symbol-resolver.c',
'sysprof-local-profiler.c',
+ 'sysprof-memprof-profile.c',
+ 'sysprof-memprof-source.c',
'sysprof-netdev-source.c',
'sysprof-process-model.c',
'sysprof-process-model-item.c',
@@ -45,6 +47,8 @@ libsysprof_public_headers = [
'sysprof-kernel-symbol.h',
'sysprof-kernel-symbol-resolver.h',
'sysprof-local-profiler.h',
+ 'sysprof-memprof-profile.h',
+ 'sysprof-memprof-source.h',
'sysprof-process-model.h',
'sysprof-process-model-item.h',
'sysprof-profile.h',
@@ -79,10 +83,23 @@ libsysprof_private_sources = [
libsysprof_public_sources += libsysprof_capture_sources
+librax = static_library('rax', ['rax.c'],
+ c_args: [ '-Wno-declaration-after-statement',
+ '-Wno-format-nonliteral',
+ '-Wno-shadow' ],
+)
+
+librax_dep = declare_dependency(
+ link_whole: librax,
+ include_directories: include_directories('.'),
+)
+
libsysprof_deps = [
+ libsysprof_capture_deps,
gio_dep,
gio_unix_dep,
polkit_dep,
+ librax_dep,
]
if host_machine.system() == 'linux'
@@ -146,4 +163,6 @@ pkgconfig.generate(
install_headers(libsysprof_public_headers, subdir: sysprof_header_subdir)
+subdir('preload')
+
endif
diff --git a/src/libsysprof/preload/meson.build b/src/libsysprof/preload/meson.build
new file mode 100644
index 0000000..596fc79
--- /dev/null
+++ b/src/libsysprof/preload/meson.build
@@ -0,0 +1,16 @@
+libsysprof_memory_preload_deps = [
+ cc.find_library('dl', required: false),
+ libsysprof_capture_dep,
+ libunwind_dep,
+]
+
+libsysprof_memory_preload_sources = [
+ 'sysprof-memory-collector.c',
+]
+
+libsysprof_memory_preload = shared_library('sysprof-memory-@0@'.format(libsysprof_api_version),
+ libsysprof_memory_preload_sources,
+ dependencies: libsysprof_memory_preload_deps,
+ install: true,
+ install_dir: get_option('libexecdir'),
+)
diff --git a/src/libsysprof/preload/sysprof-memory-collector.c
b/src/libsysprof/preload/sysprof-memory-collector.c
new file mode 100644
index 0000000..1e6b240
--- /dev/null
+++ b/src/libsysprof/preload/sysprof-memory-collector.c
@@ -0,0 +1,295 @@
+#define _GNU_SOURCE
+
+#include "config.h"
+
+#include <dlfcn.h>
+#ifdef HAVE_EXECINFO_H
+# include <execinfo.h>
+#endif
+#ifdef ENABLE_LIBUNWIND
+# include <libunwind.h>
+#endif
+#include <sched.h>
+#include <stdlib.h>
+#include <sys/syscall.h>
+#include <sys/types.h>
+#include <sysprof-capture.h>
+#include <unistd.h>
+
+typedef void *(* RealMalloc) (size_t);
+typedef void (* RealFree) (void *);
+typedef void *(* RealCalloc) (size_t, size_t);
+typedef void *(* RealRealloc) (void *, size_t);
+typedef void *(* RealAlignedAlloc) (size_t, size_t);
+typedef int (* RealPosixMemalign) (void **, size_t, size_t);
+typedef void *(* RealMemalign) (size_t, size_t);
+
+typedef struct
+{
+ char buf[4092];
+ int off;
+} ScratchAlloc;
+
+static void hook_memtable (void);
+static void *scratch_malloc (size_t);
+static void *scratch_realloc (void *, size_t);
+static void *scratch_calloc (size_t, size_t);
+static void scratch_free (void *);
+
+static G_LOCK_DEFINE (writer);
+static SysprofCaptureWriter *writer;
+static int hooked;
+static int pid;
+static ScratchAlloc scratch;
+static RealCalloc real_calloc = scratch_calloc;
+static RealFree real_free = scratch_free;
+static RealMalloc real_malloc = scratch_malloc;
+static RealRealloc real_realloc = scratch_realloc;
+static RealAlignedAlloc real_aligned_alloc;
+static RealPosixMemalign real_posix_memalign;
+static RealMemalign real_memalign;
+
+static guint
+backtrace_func (SysprofCaptureAddress *addrs,
+ guint n_addrs,
+ gpointer user_data)
+{
+#if defined(ENABLE_LIBUNWIND)
+ unw_context_t uc;
+ unw_cursor_t cursor;
+ unw_word_t ip;
+
+ unw_getcontext (&uc);
+ unw_init_local (&cursor, &uc);
+
+ /* Skip past caller frames */
+ if (unw_step (&cursor) > 0 && unw_step (&cursor) > 0)
+ {
+ guint n = 0;
+
+ /* Now walk the stack frames back */
+ while (n < n_addrs && unw_step (&cursor) > 0)
+ {
+ unw_get_reg (&cursor, UNW_REG_IP, &ip);
+ addrs[n++] = ip;
+ }
+
+ return n;
+ }
+
+ return 0;
+#elif defined(HAVE_EXECINFO_H)
+# if GLIB_SIZEOF_VOID_P == 8
+ return backtrace ((void **)addrs, n_addrs);
+# else /* GLIB_SIZEOF_VOID_P != 8 */
+ void **stack = alloca (n_addrs * sizeof (gpointer));
+ guint n = backtrace (stack, n_addrs);
+ for (guint i = 0; i < n; i++)
+ addrs[i] = GPOINTER_TO_SIZE (stack[i]);
+ return n;
+# endif /* GLIB_SIZEOF_VOID_P */
+#else
+ return 0;
+#endif
+}
+
+static void *
+scratch_malloc (size_t size)
+{
+ hook_memtable ();
+ return real_malloc (size);
+}
+
+static void *
+scratch_realloc (void *ptr,
+ size_t size)
+{
+ hook_memtable ();
+ return real_realloc (ptr, size);
+}
+
+static void *
+scratch_calloc (size_t nmemb,
+ size_t size)
+{
+ void *ret;
+
+ /* re-entrant, but forces early hook in case calloc is
+ * called before any of our other hooks.
+ */
+ if (!hooked)
+ hook_memtable ();
+
+ size *= nmemb;
+ ret = &scratch.buf[scratch.off];
+ scratch.off += size;
+
+ return ret;
+}
+
+static void
+scratch_free (void *ptr)
+{
+ if ((char *)ptr >= scratch.buf && (char *)ptr < scratch.buf + scratch.off)
+ return;
+}
+
+static void
+flush_writer (void)
+{
+ G_LOCK (writer);
+ sysprof_capture_writer_flush (writer);
+ G_UNLOCK (writer);
+}
+
+static void
+hook_memtable (void)
+{
+ const gchar *env;
+
+ if (hooked)
+ return;
+
+ hooked = 1;
+
+ real_calloc = dlsym (RTLD_NEXT, "calloc");
+ real_free = dlsym (RTLD_NEXT, "free");
+ real_malloc = dlsym (RTLD_NEXT, "malloc");
+ real_realloc = dlsym (RTLD_NEXT, "realloc");
+ real_aligned_alloc = dlsym (RTLD_NEXT, "aligned_alloc");
+ real_posix_memalign = dlsym (RTLD_NEXT, "posix_memalign");
+ real_memalign = dlsym (RTLD_NEXT, "memalign");
+
+ unsetenv ("LD_PRELOAD");
+
+ pid = getpid ();
+
+ /* TODO: We want an API that let's us create a new writer
+ * per-thread instead of something like this (or using an
+ * environment variable). That will require a control channel
+ * to sysprof to request new writer/muxed APIs.
+ */
+
+ env = getenv ("MEMPROF_TRACE_FD");
+
+ if (env != NULL)
+ {
+ int fd = atoi (env);
+
+ if (fd > 0)
+ writer = sysprof_capture_writer_new_from_fd (fd, 0);
+ }
+
+ if (writer == NULL)
+ writer = sysprof_capture_writer_new ("memory.syscap", 0);
+
+ atexit (flush_writer);
+}
+
+#define gettid() syscall(__NR_gettid, 0)
+
+static inline void
+track_malloc (void *ptr,
+ size_t size)
+{
+ if G_UNLIKELY (!writer)
+ return;
+
+ G_LOCK (writer);
+ sysprof_capture_writer_add_allocation (writer,
+ SYSPROF_CAPTURE_CURRENT_TIME,
+ sched_getcpu (),
+ pid,
+ gettid(),
+ GPOINTER_TO_SIZE (ptr),
+ size,
+ backtrace_func,
+ NULL);
+ G_UNLOCK (writer);
+}
+
+static inline void
+track_free (void *ptr)
+{
+ if G_UNLIKELY (!writer)
+ return;
+
+ G_LOCK (writer);
+ sysprof_capture_writer_add_allocation (writer,
+ SYSPROF_CAPTURE_CURRENT_TIME,
+ sched_getcpu (),
+ pid,
+ gettid(),
+ GPOINTER_TO_SIZE (ptr),
+ 0,
+ backtrace_func,
+ 0);
+ G_UNLOCK (writer);
+}
+
+void *
+malloc (size_t size)
+{
+ void *ret = real_malloc (size);
+ track_malloc (ret, size);
+ return ret;
+}
+
+void *
+calloc (size_t nmemb,
+ size_t size)
+{
+ void *ret = real_calloc (nmemb, size);
+ track_malloc (ret, size);
+ return ret;
+}
+
+void *
+realloc (void *ptr,
+ size_t size)
+{
+ void *ret = real_realloc (ptr, size);
+
+ if (ret != ptr)
+ {
+ track_free (ptr);
+ track_malloc (ret, size);
+ }
+
+ return ret;
+}
+
+void
+free (void *ptr)
+{
+ real_free (ptr);
+ track_free (ptr);
+}
+
+void *
+aligned_alloc (size_t alignment,
+ size_t size)
+{
+ void *ret = real_aligned_alloc (alignment, size);
+ track_malloc (ret, size);
+ return ret;
+}
+
+int
+posix_memalign (void **memptr,
+ size_t alignment,
+ size_t size)
+{
+ int ret = real_posix_memalign (memptr, alignment, size);
+ track_malloc (*memptr, size);
+ return ret;
+}
+
+void *
+memalign (size_t alignment,
+ size_t size)
+{
+ void *ret = real_memalign (alignment, size);
+ track_malloc (ret, size);
+ return ret;
+}
diff --git a/src/libsysprof/rax.c b/src/libsysprof/rax.c
new file mode 100644
index 0000000..7172f21
--- /dev/null
+++ b/src/libsysprof/rax.c
@@ -0,0 +1,1947 @@
+/* Rax -- A radix tree implementation.
+ *
+ * Version 1.1 -- 3 December 2019
+ *
+ * Copyright (c) 2017-2019, Salvatore Sanfilippo <antirez at gmail dot com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * * Neither the name of Redis nor the names of its contributors may be used
+ * to endorse or promote products derived from this software without
+ * specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <stdio.h>
+#include <errno.h>
+#include <math.h>
+#include "rax.h"
+
+#ifndef RAX_MALLOC_INCLUDE
+#define RAX_MALLOC_INCLUDE "rax_malloc.h"
+#endif
+
+#include RAX_MALLOC_INCLUDE
+
+/* This is a special pointer that is guaranteed to never have the same value
+ * of a radix tree node. It's used in order to report "not found" error without
+ * requiring the function to have multiple return values. */
+void *raxNotFound = (void*)"rax-not-found-pointer";
+
+/* -------------------------------- Debugging ------------------------------ */
+
+void raxDebugShowNode(const char *msg, raxNode *n);
+
+/* Turn debugging messages on/off by compiling with RAX_DEBUG_MSG macro on.
+ * When RAX_DEBUG_MSG is defined by default Rax operations will emit a lot
+ * of debugging info to the standard output, however you can still turn
+ * debugging on/off in order to enable it only when you suspect there is an
+ * operation causing a bug using the function raxSetDebugMsg(). */
+#ifdef RAX_DEBUG_MSG
+#define debugf(...) \
+ if (raxDebugMsg) { \
+ printf("%s:%s:%d:\t", __FILE__, __FUNCTION__, __LINE__); \
+ printf(__VA_ARGS__); \
+ fflush(stdout); \
+ }
+
+#define debugnode(msg,n) raxDebugShowNode(msg,n)
+#else
+#define debugf(...)
+#define debugnode(msg,n)
+#endif
+
+/* By default log debug info if RAX_DEBUG_MSG is defined. */
+static int raxDebugMsg = 1;
+
+/* When debug messages are enabled, turn them on/off dynamically. By
+ * default they are enabled. Set the state to 0 to disable, and 1 to
+ * re-enable. */
+void raxSetDebugMsg(int onoff) {
+ raxDebugMsg = onoff;
+}
+
+/* ------------------------- raxStack functions --------------------------
+ * The raxStack is a simple stack of pointers that is capable of switching
+ * from using a stack-allocated array to dynamic heap once a given number of
+ * items are reached. It is used in order to retain the list of parent nodes
+ * while walking the radix tree in order to implement certain operations that
+ * need to navigate the tree upward.
+ * ------------------------------------------------------------------------- */
+
+/* Initialize the stack. */
+static inline void raxStackInit(raxStack *ts) {
+ ts->stack = ts->static_items;
+ ts->items = 0;
+ ts->maxitems = RAX_STACK_STATIC_ITEMS;
+ ts->oom = 0;
+}
+
+/* Push an item into the stack, returns 1 on success, 0 on out of memory. */
+static inline int raxStackPush(raxStack *ts, void *ptr) {
+ if (ts->items == ts->maxitems) {
+ if (ts->stack == ts->static_items) {
+ ts->stack = rax_malloc(sizeof(void*)*ts->maxitems*2);
+ if (ts->stack == NULL) {
+ ts->stack = ts->static_items;
+ ts->oom = 1;
+ errno = ENOMEM;
+ return 0;
+ }
+ memcpy(ts->stack,ts->static_items,sizeof(void*)*ts->maxitems);
+ } else {
+ void **newalloc = rax_realloc(ts->stack,sizeof(void*)*ts->maxitems*2);
+ if (newalloc == NULL) {
+ ts->oom = 1;
+ errno = ENOMEM;
+ return 0;
+ }
+ ts->stack = newalloc;
+ }
+ ts->maxitems *= 2;
+ }
+ ts->stack[ts->items] = ptr;
+ ts->items++;
+ return 1;
+}
+
+/* Pop an item from the stack, the function returns NULL if there are no
+ * items to pop. */
+static inline void *raxStackPop(raxStack *ts) {
+ if (ts->items == 0) return NULL;
+ ts->items--;
+ return ts->stack[ts->items];
+}
+
+/* Return the stack item at the top of the stack without actually consuming
+ * it. */
+static inline void *raxStackPeek(raxStack *ts) {
+ if (ts->items == 0) return NULL;
+ return ts->stack[ts->items-1];
+}
+
+/* Free the stack in case we used heap allocation. */
+static inline void raxStackFree(raxStack *ts) {
+ if (ts->stack != ts->static_items) rax_free(ts->stack);
+}
+
+/* ----------------------------------------------------------------------------
+ * Radix tree implementation
+ * --------------------------------------------------------------------------*/
+
+/* Return the padding needed in the characters section of a node having size
+ * 'nodesize'. The padding is needed to store the child pointers to aligned
+ * addresses. Note that we add 4 to the node size because the node has a four
+ * bytes header. */
+#define raxPadding(nodesize) ((sizeof(void*)-((nodesize+4) % sizeof(void*))) & (sizeof(void*)-1))
+
+/* Return the pointer to the last child pointer in a node. For the compressed
+ * nodes this is the only child pointer. */
+#define raxNodeLastChildPtr(n) ((raxNode**) ( \
+ ((char*)(n)) + \
+ raxNodeCurrentLength(n) - \
+ sizeof(raxNode*) - \
+ (((n)->iskey && !(n)->isnull) ? sizeof(void*) : 0) \
+))
+
+/* Return the pointer to the first child pointer. */
+#define raxNodeFirstChildPtr(n) ((raxNode**) ( \
+ (n)->data + \
+ (n)->size + \
+ raxPadding((n)->size)))
+
+/* Return the current total size of the node. Note that the second line
+ * computes the padding after the string of characters, needed in order to
+ * save pointers to aligned addresses. */
+#define raxNodeCurrentLength(n) ( \
+ sizeof(raxNode)+(n)->size+ \
+ raxPadding((n)->size)+ \
+ ((n)->iscompr ? sizeof(raxNode*) : sizeof(raxNode*)*(n)->size)+ \
+ (((n)->iskey && !(n)->isnull)*sizeof(void*)) \
+)
+
+/* Allocate a new non compressed node with the specified number of children.
+ * If datafiled is true, the allocation is made large enough to hold the
+ * associated data pointer.
+ * Returns the new node pointer. On out of memory NULL is returned. */
+raxNode *raxNewNode(size_t children, int datafield) {
+ size_t nodesize = sizeof(raxNode)+children+raxPadding(children)+
+ sizeof(raxNode*)*children;
+ if (datafield) nodesize += sizeof(void*);
+ raxNode *node = rax_malloc(nodesize);
+ if (node == NULL) return NULL;
+ node->iskey = 0;
+ node->isnull = 0;
+ node->iscompr = 0;
+ node->size = children;
+ return node;
+}
+
+/* Allocate a new rax and return its pointer. On out of memory the function
+ * returns NULL. */
+rax *raxNew(void) {
+ rax *rax = rax_malloc(sizeof(*rax));
+ if (rax == NULL) return NULL;
+ rax->numele = 0;
+ rax->numnodes = 1;
+ rax->head = raxNewNode(0,0);
+ if (rax->head == NULL) {
+ rax_free(rax);
+ return NULL;
+ } else {
+ return rax;
+ }
+}
+
+/* realloc the node to make room for auxiliary data in order
+ * to store an item in that node. On out of memory NULL is returned. */
+raxNode *raxReallocForData(raxNode *n, void *data) {
+ if (data == NULL) return n; /* No reallocation needed, setting isnull=1 */
+ size_t curlen = raxNodeCurrentLength(n);
+ return rax_realloc(n,curlen+sizeof(void*));
+}
+
+/* Set the node auxiliary data to the specified pointer. */
+void raxSetData(raxNode *n, void *data) {
+ n->iskey = 1;
+ if (data != NULL) {
+ n->isnull = 0;
+ void **ndata = (void**)
+ ((char*)n+raxNodeCurrentLength(n)-sizeof(void*));
+ memcpy(ndata,&data,sizeof(data));
+ } else {
+ n->isnull = 1;
+ }
+}
+
+/* Get the node auxiliary data. */
+void *raxGetData(raxNode *n) {
+ if (n->isnull) return NULL;
+ void **ndata =(void**)((char*)n+raxNodeCurrentLength(n)-sizeof(void*));
+ void *data;
+ memcpy(&data,ndata,sizeof(data));
+ return data;
+}
+
+/* Add a new child to the node 'n' representing the character 'c' and return
+ * its new pointer, as well as the child pointer by reference. Additionally
+ * '***parentlink' is populated with the raxNode pointer-to-pointer of where
+ * the new child was stored, which is useful for the caller to replace the
+ * child pointer if it gets reallocated.
+ *
+ * On success the new parent node pointer is returned (it may change because
+ * of the realloc, so the caller should discard 'n' and use the new value).
+ * On out of memory NULL is returned, and the old node is still valid. */
+raxNode *raxAddChild(raxNode *n, unsigned char c, raxNode **childptr, raxNode ***parentlink) {
+ assert(n->iscompr == 0);
+
+ size_t curlen = raxNodeCurrentLength(n);
+ n->size++;
+ size_t newlen = raxNodeCurrentLength(n);
+ n->size--; /* For now restore the orignal size. We'll update it only on
+ success at the end. */
+
+ /* Alloc the new child we will link to 'n'. */
+ raxNode *child = raxNewNode(0,0);
+ if (child == NULL) return NULL;
+
+ /* Make space in the original node. */
+ raxNode *newn = rax_realloc(n,newlen);
+ if (newn == NULL) {
+ rax_free(child);
+ return NULL;
+ }
+ n = newn;
+
+ /* After the reallocation, we have up to 8/16 (depending on the system
+ * pointer size, and the required node padding) bytes at the end, that is,
+ * the additional char in the 'data' section, plus one pointer to the new
+ * child, plus the padding needed in order to store addresses into aligned
+ * locations.
+ *
+ * So if we start with the following node, having "abde" edges.
+ *
+ * Note:
+ * - We assume 4 bytes pointer for simplicity.
+ * - Each space below corresponds to one byte
+ *
+ * [HDR*][abde][Aptr][Bptr][Dptr][Eptr]|AUXP|
+ *
+ * After the reallocation we need: 1 byte for the new edge character
+ * plus 4 bytes for a new child pointer (assuming 32 bit machine).
+ * However after adding 1 byte to the edge char, the header + the edge
+ * characters are no longer aligned, so we also need 3 bytes of padding.
+ * In total the reallocation will add 1+4+3 bytes = 8 bytes:
+ *
+ * (Blank bytes are represented by ".")
+ *
+ * [HDR*][abde][Aptr][Bptr][Dptr][Eptr]|AUXP|[....][....]
+ *
+ * Let's find where to insert the new child in order to make sure
+ * it is inserted in-place lexicographically. Assuming we are adding
+ * a child "c" in our case pos will be = 2 after the end of the following
+ * loop. */
+ int pos;
+ for (pos = 0; pos < n->size; pos++) {
+ if (n->data[pos] > c) break;
+ }
+
+ /* Now, if present, move auxiliary data pointer at the end
+ * so that we can mess with the other data without overwriting it.
+ * We will obtain something like that:
+ *
+ * [HDR*][abde][Aptr][Bptr][Dptr][Eptr][....][....]|AUXP|
+ */
+ unsigned char *src, *dst;
+ if (n->iskey && !n->isnull) {
+ src = ((unsigned char*)n+curlen-sizeof(void*));
+ dst = ((unsigned char*)n+newlen-sizeof(void*));
+ memmove(dst,src,sizeof(void*));
+ }
+
+ /* Compute the "shift", that is, how many bytes we need to move the
+ * pointers section forward because of the addition of the new child
+ * byte in the string section. Note that if we had no padding, that
+ * would be always "1", since we are adding a single byte in the string
+ * section of the node (where now there is "abde" basically).
+ *
+ * However we have padding, so it could be zero, or up to 8.
+ *
+ * Another way to think at the shift is, how many bytes we need to
+ * move child pointers forward *other than* the obvious sizeof(void*)
+ * needed for the additional pointer itself. */
+ size_t shift = newlen - curlen - sizeof(void*);
+
+ /* We said we are adding a node with edge 'c'. The insertion
+ * point is between 'b' and 'd', so the 'pos' variable value is
+ * the index of the first child pointer that we need to move forward
+ * to make space for our new pointer.
+ *
+ * To start, move all the child pointers after the insertion point
+ * of shift+sizeof(pointer) bytes on the right, to obtain:
+ *
+ * [HDR*][abde][Aptr][Bptr][....][....][Dptr][Eptr]|AUXP|
+ */
+ src = n->data+n->size+
+ raxPadding(n->size)+
+ sizeof(raxNode*)*pos;
+ memmove(src+shift+sizeof(raxNode*),src,sizeof(raxNode*)*(n->size-pos));
+
+ /* Move the pointers to the left of the insertion position as well. Often
+ * we don't need to do anything if there was already some padding to use. In
+ * that case the final destination of the pointers will be the same, however
+ * in our example there was no pre-existing padding, so we added one byte
+ * plus thre bytes of padding. After the next memmove() things will look
+ * like thata:
+ *
+ * [HDR*][abde][....][Aptr][Bptr][....][Dptr][Eptr]|AUXP|
+ */
+ if (shift) {
+ src = (unsigned char*) raxNodeFirstChildPtr(n);
+ memmove(src+shift,src,sizeof(raxNode*)*pos);
+ }
+
+ /* Now make the space for the additional char in the data section,
+ * but also move the pointers before the insertion point to the right
+ * by shift bytes, in order to obtain the following:
+ *
+ * [HDR*][ab.d][e...][Aptr][Bptr][....][Dptr][Eptr]|AUXP|
+ */
+ src = n->data+pos;
+ memmove(src+1,src,n->size-pos);
+
+ /* We can now set the character and its child node pointer to get:
+ *
+ * [HDR*][abcd][e...][Aptr][Bptr][....][Dptr][Eptr]|AUXP|
+ * [HDR*][abcd][e...][Aptr][Bptr][Cptr][Dptr][Eptr]|AUXP|
+ */
+ n->data[pos] = c;
+ n->size++;
+ src = (unsigned char*) raxNodeFirstChildPtr(n);
+ raxNode **childfield = (raxNode**)(src+sizeof(raxNode*)*pos);
+ memcpy(childfield,&child,sizeof(child));
+ *childptr = child;
+ *parentlink = childfield;
+ return n;
+}
+
+/* Turn the node 'n', that must be a node without any children, into a
+ * compressed node representing a set of nodes linked one after the other
+ * and having exactly one child each. The node can be a key or not: this
+ * property and the associated value if any will be preserved.
+ *
+ * The function also returns a child node, since the last node of the
+ * compressed chain cannot be part of the chain: it has zero children while
+ * we can only compress inner nodes with exactly one child each. */
+raxNode *raxCompressNode(raxNode *n, unsigned char *s, size_t len, raxNode **child) {
+ assert(n->size == 0 && n->iscompr == 0);
+ void *data = NULL; /* Initialized only to avoid warnings. */
+ size_t newsize;
+
+ debugf("Compress node: %.*s\n", (int)len,s);
+
+ /* Allocate the child to link to this node. */
+ *child = raxNewNode(0,0);
+ if (*child == NULL) return NULL;
+
+ /* Make space in the parent node. */
+ newsize = sizeof(raxNode)+len+raxPadding(len)+sizeof(raxNode*);
+ if (n->iskey) {
+ data = raxGetData(n); /* To restore it later. */
+ if (!n->isnull) newsize += sizeof(void*);
+ }
+ raxNode *newn = rax_realloc(n,newsize);
+ if (newn == NULL) {
+ rax_free(*child);
+ return NULL;
+ }
+ n = newn;
+
+ n->iscompr = 1;
+ n->size = len;
+ memcpy(n->data,s,len);
+ if (n->iskey) raxSetData(n,data);
+ raxNode **childfield = raxNodeLastChildPtr(n);
+ memcpy(childfield,child,sizeof(*child));
+ return n;
+}
+
+/* Low level function that walks the tree looking for the string
+ * 's' of 'len' bytes. The function returns the number of characters
+ * of the key that was possible to process: if the returned integer
+ * is the same as 'len', then it means that the node corresponding to the
+ * string was found (however it may not be a key in case the node->iskey is
+ * zero or if simply we stopped in the middle of a compressed node, so that
+ * 'splitpos' is non zero).
+ *
+ * Otherwise if the returned integer is not the same as 'len', there was an
+ * early stop during the tree walk because of a character mismatch.
+ *
+ * The node where the search ended (because the full string was processed
+ * or because there was an early stop) is returned by reference as
+ * '*stopnode' if the passed pointer is not NULL. This node link in the
+ * parent's node is returned as '*plink' if not NULL. Finally, if the
+ * search stopped in a compressed node, '*splitpos' returns the index
+ * inside the compressed node where the search ended. This is useful to
+ * know where to split the node for insertion.
+ *
+ * Note that when we stop in the middle of a compressed node with
+ * a perfect match, this function will return a length equal to the
+ * 'len' argument (all the key matched), and will return a *splitpos which is
+ * always positive (that will represent the index of the character immediately
+ * *after* the last match in the current compressed node).
+ *
+ * When instead we stop at a compressed node and *splitpos is zero, it
+ * means that the current node represents the key (that is, none of the
+ * compressed node characters are needed to represent the key, just all
+ * its parents nodes). */
+static inline size_t raxLowWalk(rax *rax, unsigned char *s, size_t len, raxNode **stopnode, raxNode
***plink, int *splitpos, raxStack *ts) {
+ raxNode *h = rax->head;
+ raxNode **parentlink = &rax->head;
+
+ size_t i = 0; /* Position in the string. */
+ size_t j = 0; /* Position in the node children (or bytes if compressed).*/
+ while(h->size && i < len) {
+ debugnode("Lookup current node",h);
+ unsigned char *v = h->data;
+
+ if (h->iscompr) {
+ for (j = 0; j < h->size && i < len; j++, i++) {
+ if (v[j] != s[i]) break;
+ }
+ if (j != h->size) break;
+ } else {
+ /* Even when h->size is large, linear scan provides good
+ * performances compared to other approaches that are in theory
+ * more sounding, like performing a binary search. */
+ for (j = 0; j < h->size; j++) {
+ if (v[j] == s[i]) break;
+ }
+ if (j == h->size) break;
+ i++;
+ }
+
+ if (ts) raxStackPush(ts,h); /* Save stack of parent nodes. */
+ raxNode **children = raxNodeFirstChildPtr(h);
+ if (h->iscompr) j = 0; /* Compressed node only child is at index 0. */
+ memcpy(&h,children+j,sizeof(h));
+ parentlink = children+j;
+ j = 0; /* If the new node is compressed and we do not
+ iterate again (since i == l) set the split
+ position to 0 to signal this node represents
+ the searched key. */
+ }
+ debugnode("Lookup stop node is",h);
+ if (stopnode) *stopnode = h;
+ if (plink) *plink = parentlink;
+ if (splitpos && h->iscompr) *splitpos = j;
+ return i;
+}
+
+/* Insert the element 's' of size 'len', setting as auxiliary data
+ * the pointer 'data'. If the element is already present, the associated
+ * data is updated (only if 'overwrite' is set to 1), and 0 is returned,
+ * otherwise the element is inserted and 1 is returned. On out of memory the
+ * function returns 0 as well but sets errno to ENOMEM, otherwise errno will
+ * be set to 0.
+ */
+int raxGenericInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old, int overwrite) {
+ size_t i;
+ int j = 0; /* Split position. If raxLowWalk() stops in a compressed
+ node, the index 'j' represents the char we stopped within the
+ compressed node, that is, the position where to split the
+ node for insertion. */
+ raxNode *h, **parentlink;
+
+ debugf("### Insert %.*s with value %p\n", (int)len, s, data);
+ i = raxLowWalk(rax,s,len,&h,&parentlink,&j,NULL);
+
+ /* If i == len we walked following the whole string. If we are not
+ * in the middle of a compressed node, the string is either already
+ * inserted or this middle node is currently not a key, but can represent
+ * our key. We have just to reallocate the node and make space for the
+ * data pointer. */
+ if (i == len && (!h->iscompr || j == 0 /* not in the middle if j is 0 */)) {
+ debugf("### Insert: node representing key exists\n");
+ /* Make space for the value pointer if needed. */
+ if (!h->iskey || (h->isnull && overwrite)) {
+ h = raxReallocForData(h,data);
+ if (h) memcpy(parentlink,&h,sizeof(h));
+ }
+ if (h == NULL) {
+ errno = ENOMEM;
+ return 0;
+ }
+
+ /* Update the existing key if there is already one. */
+ if (h->iskey) {
+ if (old) *old = raxGetData(h);
+ if (overwrite) raxSetData(h,data);
+ errno = 0;
+ return 0; /* Element already exists. */
+ }
+
+ /* Otherwise set the node as a key. Note that raxSetData()
+ * will set h->iskey. */
+ raxSetData(h,data);
+ rax->numele++;
+ return 1; /* Element inserted. */
+ }
+
+ /* If the node we stopped at is a compressed node, we need to
+ * split it before to continue.
+ *
+ * Splitting a compressed node have a few possible cases.
+ * Imagine that the node 'h' we are currently at is a compressed
+ * node contaning the string "ANNIBALE" (it means that it represents
+ * nodes A -> N -> N -> I -> B -> A -> L -> E with the only child
+ * pointer of this node pointing at the 'E' node, because remember that
+ * we have characters at the edges of the graph, not inside the nodes
+ * themselves.
+ *
+ * In order to show a real case imagine our node to also point to
+ * another compressed node, that finally points at the node without
+ * children, representing 'O':
+ *
+ * "ANNIBALE" -> "SCO" -> []
+ *
+ * When inserting we may face the following cases. Note that all the cases
+ * require the insertion of a non compressed node with exactly two
+ * children, except for the last case which just requires splitting a
+ * compressed node.
+ *
+ * 1) Inserting "ANNIENTARE"
+ *
+ * |B| -> "ALE" -> "SCO" -> []
+ * "ANNI" -> |-|
+ * |E| -> (... continue algo ...) "NTARE" -> []
+ *
+ * 2) Inserting "ANNIBALI"
+ *
+ * |E| -> "SCO" -> []
+ * "ANNIBAL" -> |-|
+ * |I| -> (... continue algo ...) []
+ *
+ * 3) Inserting "AGO" (Like case 1, but set iscompr = 0 into original node)
+ *
+ * |N| -> "NIBALE" -> "SCO" -> []
+ * |A| -> |-|
+ * |G| -> (... continue algo ...) |O| -> []
+ *
+ * 4) Inserting "CIAO"
+ *
+ * |A| -> "NNIBALE" -> "SCO" -> []
+ * |-|
+ * |C| -> (... continue algo ...) "IAO" -> []
+ *
+ * 5) Inserting "ANNI"
+ *
+ * "ANNI" -> "BALE" -> "SCO" -> []
+ *
+ * The final algorithm for insertion covering all the above cases is as
+ * follows.
+ *
+ * ============================= ALGO 1 =============================
+ *
+ * For the above cases 1 to 4, that is, all cases where we stopped in
+ * the middle of a compressed node for a character mismatch, do:
+ *
+ * Let $SPLITPOS be the zero-based index at which, in the
+ * compressed node array of characters, we found the mismatching
+ * character. For example if the node contains "ANNIBALE" and we add
+ * "ANNIENTARE" the $SPLITPOS is 4, that is, the index at which the
+ * mismatching character is found.
+ *
+ * 1. Save the current compressed node $NEXT pointer (the pointer to the
+ * child element, that is always present in compressed nodes).
+ *
+ * 2. Create "split node" having as child the non common letter
+ * at the compressed node. The other non common letter (at the key)
+ * will be added later as we continue the normal insertion algorithm
+ * at step "6".
+ *
+ * 3a. IF $SPLITPOS == 0:
+ * Replace the old node with the split node, by copying the auxiliary
+ * data if any. Fix parent's reference. Free old node eventually
+ * (we still need its data for the next steps of the algorithm).
+ *
+ * 3b. IF $SPLITPOS != 0:
+ * Trim the compressed node (reallocating it as well) in order to
+ * contain $splitpos characters. Change chilid pointer in order to link
+ * to the split node. If new compressed node len is just 1, set
+ * iscompr to 0 (layout is the same). Fix parent's reference.
+ *
+ * 4a. IF the postfix len (the length of the remaining string of the
+ * original compressed node after the split character) is non zero,
+ * create a "postfix node". If the postfix node has just one character
+ * set iscompr to 0, otherwise iscompr to 1. Set the postfix node
+ * child pointer to $NEXT.
+ *
+ * 4b. IF the postfix len is zero, just use $NEXT as postfix pointer.
+ *
+ * 5. Set child[0] of split node to postfix node.
+ *
+ * 6. Set the split node as the current node, set current index at child[1]
+ * and continue insertion algorithm as usually.
+ *
+ * ============================= ALGO 2 =============================
+ *
+ * For case 5, that is, if we stopped in the middle of a compressed
+ * node but no mismatch was found, do:
+ *
+ * Let $SPLITPOS be the zero-based index at which, in the
+ * compressed node array of characters, we stopped iterating because
+ * there were no more keys character to match. So in the example of
+ * the node "ANNIBALE", addig the string "ANNI", the $SPLITPOS is 4.
+ *
+ * 1. Save the current compressed node $NEXT pointer (the pointer to the
+ * child element, that is always present in compressed nodes).
+ *
+ * 2. Create a "postfix node" containing all the characters from $SPLITPOS
+ * to the end. Use $NEXT as the postfix node child pointer.
+ * If the postfix node length is 1, set iscompr to 0.
+ * Set the node as a key with the associated value of the new
+ * inserted key.
+ *
+ * 3. Trim the current node to contain the first $SPLITPOS characters.
+ * As usually if the new node length is just 1, set iscompr to 0.
+ * Take the iskey / associated value as it was in the orignal node.
+ * Fix the parent's reference.
+ *
+ * 4. Set the postfix node as the only child pointer of the trimmed
+ * node created at step 1.
+ */
+
+ /* ------------------------- ALGORITHM 1 --------------------------- */
+ if (h->iscompr && i != len) {
+ debugf("ALGO 1: Stopped at compressed node %.*s (%p)\n",
+ h->size, h->data, (void*)h);
+ debugf("Still to insert: %.*s\n", (int)(len-i), s+i);
+ debugf("Splitting at %d: '%c'\n", j, ((char*)h->data)[j]);
+ debugf("Other (key) letter is '%c'\n", s[i]);
+
+ /* 1: Save next pointer. */
+ raxNode **childfield = raxNodeLastChildPtr(h);
+ raxNode *next;
+ memcpy(&next,childfield,sizeof(next));
+ debugf("Next is %p\n", (void*)next);
+ debugf("iskey %d\n", h->iskey);
+ if (h->iskey) {
+ debugf("key value is %p\n", raxGetData(h));
+ }
+
+ /* Set the length of the additional nodes we will need. */
+ size_t trimmedlen = j;
+ size_t postfixlen = h->size - j - 1;
+ int split_node_is_key = !trimmedlen && h->iskey && !h->isnull;
+ size_t nodesize;
+
+ /* 2: Create the split node. Also allocate the other nodes we'll need
+ * ASAP, so that it will be simpler to handle OOM. */
+ raxNode *splitnode = raxNewNode(1, split_node_is_key);
+ raxNode *trimmed = NULL;
+ raxNode *postfix = NULL;
+
+ if (trimmedlen) {
+ nodesize = sizeof(raxNode)+trimmedlen+raxPadding(trimmedlen)+
+ sizeof(raxNode*);
+ if (h->iskey && !h->isnull) nodesize += sizeof(void*);
+ trimmed = rax_malloc(nodesize);
+ }
+
+ if (postfixlen) {
+ nodesize = sizeof(raxNode)+postfixlen+raxPadding(postfixlen)+
+ sizeof(raxNode*);
+ postfix = rax_malloc(nodesize);
+ }
+
+ /* OOM? Abort now that the tree is untouched. */
+ if (splitnode == NULL ||
+ (trimmedlen && trimmed == NULL) ||
+ (postfixlen && postfix == NULL))
+ {
+ rax_free(splitnode);
+ rax_free(trimmed);
+ rax_free(postfix);
+ errno = ENOMEM;
+ return 0;
+ }
+ splitnode->data[0] = h->data[j];
+
+ if (j == 0) {
+ /* 3a: Replace the old node with the split node. */
+ if (h->iskey) {
+ void *ndata = raxGetData(h);
+ raxSetData(splitnode,ndata);
+ }
+ memcpy(parentlink,&splitnode,sizeof(splitnode));
+ } else {
+ /* 3b: Trim the compressed node. */
+ trimmed->size = j;
+ memcpy(trimmed->data,h->data,j);
+ trimmed->iscompr = j > 1 ? 1 : 0;
+ trimmed->iskey = h->iskey;
+ trimmed->isnull = h->isnull;
+ if (h->iskey && !h->isnull) {
+ void *ndata = raxGetData(h);
+ raxSetData(trimmed,ndata);
+ }
+ raxNode **cp = raxNodeLastChildPtr(trimmed);
+ memcpy(cp,&splitnode,sizeof(splitnode));
+ memcpy(parentlink,&trimmed,sizeof(trimmed));
+ parentlink = cp; /* Set parentlink to splitnode parent. */
+ rax->numnodes++;
+ }
+
+ /* 4: Create the postfix node: what remains of the original
+ * compressed node after the split. */
+ if (postfixlen) {
+ /* 4a: create a postfix node. */
+ postfix->iskey = 0;
+ postfix->isnull = 0;
+ postfix->size = postfixlen;
+ postfix->iscompr = postfixlen > 1;
+ memcpy(postfix->data,h->data+j+1,postfixlen);
+ raxNode **cp = raxNodeLastChildPtr(postfix);
+ memcpy(cp,&next,sizeof(next));
+ rax->numnodes++;
+ } else {
+ /* 4b: just use next as postfix node. */
+ postfix = next;
+ }
+
+ /* 5: Set splitnode first child as the postfix node. */
+ raxNode **splitchild = raxNodeLastChildPtr(splitnode);
+ memcpy(splitchild,&postfix,sizeof(postfix));
+
+ /* 6. Continue insertion: this will cause the splitnode to
+ * get a new child (the non common character at the currently
+ * inserted key). */
+ rax_free(h);
+ h = splitnode;
+ } else if (h->iscompr && i == len) {
+ /* ------------------------- ALGORITHM 2 --------------------------- */
+ debugf("ALGO 2: Stopped at compressed node %.*s (%p) j = %d\n",
+ h->size, h->data, (void*)h, j);
+
+ /* Allocate postfix & trimmed nodes ASAP to fail for OOM gracefully. */
+ size_t postfixlen = h->size - j;
+ size_t nodesize = sizeof(raxNode)+postfixlen+raxPadding(postfixlen)+
+ sizeof(raxNode*);
+ if (data != NULL) nodesize += sizeof(void*);
+ raxNode *postfix = rax_malloc(nodesize);
+
+ nodesize = sizeof(raxNode)+j+raxPadding(j)+sizeof(raxNode*);
+ if (h->iskey && !h->isnull) nodesize += sizeof(void*);
+ raxNode *trimmed = rax_malloc(nodesize);
+
+ if (postfix == NULL || trimmed == NULL) {
+ rax_free(postfix);
+ rax_free(trimmed);
+ errno = ENOMEM;
+ return 0;
+ }
+
+ /* 1: Save next pointer. */
+ raxNode **childfield = raxNodeLastChildPtr(h);
+ raxNode *next;
+ memcpy(&next,childfield,sizeof(next));
+
+ /* 2: Create the postfix node. */
+ postfix->size = postfixlen;
+ postfix->iscompr = postfixlen > 1;
+ postfix->iskey = 1;
+ postfix->isnull = 0;
+ memcpy(postfix->data,h->data+j,postfixlen);
+ raxSetData(postfix,data);
+ raxNode **cp = raxNodeLastChildPtr(postfix);
+ memcpy(cp,&next,sizeof(next));
+ rax->numnodes++;
+
+ /* 3: Trim the compressed node. */
+ trimmed->size = j;
+ trimmed->iscompr = j > 1;
+ trimmed->iskey = 0;
+ trimmed->isnull = 0;
+ memcpy(trimmed->data,h->data,j);
+ memcpy(parentlink,&trimmed,sizeof(trimmed));
+ if (h->iskey) {
+ void *aux = raxGetData(h);
+ raxSetData(trimmed,aux);
+ }
+
+ /* Fix the trimmed node child pointer to point to
+ * the postfix node. */
+ cp = raxNodeLastChildPtr(trimmed);
+ memcpy(cp,&postfix,sizeof(postfix));
+
+ /* Finish! We don't need to continue with the insertion
+ * algorithm for ALGO 2. The key is already inserted. */
+ rax->numele++;
+ rax_free(h);
+ return 1; /* Key inserted. */
+ }
+
+ /* We walked the radix tree as far as we could, but still there are left
+ * chars in our string. We need to insert the missing nodes. */
+ while(i < len) {
+ raxNode *child;
+
+ /* If this node is going to have a single child, and there
+ * are other characters, so that that would result in a chain
+ * of single-childed nodes, turn it into a compressed node. */
+ if (h->size == 0 && len-i > 1) {
+ debugf("Inserting compressed node\n");
+ size_t comprsize = len-i;
+ if (comprsize > RAX_NODE_MAX_SIZE)
+ comprsize = RAX_NODE_MAX_SIZE;
+ raxNode *newh = raxCompressNode(h,s+i,comprsize,&child);
+ if (newh == NULL) goto oom;
+ h = newh;
+ memcpy(parentlink,&h,sizeof(h));
+ parentlink = raxNodeLastChildPtr(h);
+ i += comprsize;
+ } else {
+ debugf("Inserting normal node\n");
+ raxNode **new_parentlink;
+ raxNode *newh = raxAddChild(h,s[i],&child,&new_parentlink);
+ if (newh == NULL) goto oom;
+ h = newh;
+ memcpy(parentlink,&h,sizeof(h));
+ parentlink = new_parentlink;
+ i++;
+ }
+ rax->numnodes++;
+ h = child;
+ }
+ raxNode *newh = raxReallocForData(h,data);
+ if (newh == NULL) goto oom;
+ h = newh;
+ if (!h->iskey) rax->numele++;
+ raxSetData(h,data);
+ memcpy(parentlink,&h,sizeof(h));
+ return 1; /* Element inserted. */
+
+oom:
+ /* This code path handles out of memory after part of the sub-tree was
+ * already modified. Set the node as a key, and then remove it. However we
+ * do that only if the node is a terminal node, otherwise if the OOM
+ * happened reallocating a node in the middle, we don't need to free
+ * anything. */
+ if (h->size == 0) {
+ h->isnull = 1;
+ h->iskey = 1;
+ rax->numele++; /* Compensate the next remove. */
+ assert(raxRemove(rax,s,i,NULL) != 0);
+ }
+ errno = ENOMEM;
+ return 0;
+}
+
+/* Overwriting insert. Just a wrapper for raxGenericInsert() that will
+ * update the element if there is already one for the same key. */
+int raxInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old) {
+ return raxGenericInsert(rax,s,len,data,old,1);
+}
+
+/* Non overwriting insert function: this if an element with the same key
+ * exists, the value is not updated and the function returns 0.
+ * This is a just a wrapper for raxGenericInsert(). */
+int raxTryInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old) {
+ return raxGenericInsert(rax,s,len,data,old,0);
+}
+
+/* Find a key in the rax, returns raxNotFound special void pointer value
+ * if the item was not found, otherwise the value associated with the
+ * item is returned. */
+void *raxFind(rax *rax, unsigned char *s, size_t len) {
+ raxNode *h;
+
+ debugf("### Lookup: %.*s\n", (int)len, s);
+ int splitpos = 0;
+ size_t i = raxLowWalk(rax,s,len,&h,NULL,&splitpos,NULL);
+ if (i != len || (h->iscompr && splitpos != 0) || !h->iskey)
+ return raxNotFound;
+ return raxGetData(h);
+}
+
+/* Return the memory address where the 'parent' node stores the specified
+ * 'child' pointer, so that the caller can update the pointer with another
+ * one if needed. The function assumes it will find a match, otherwise the
+ * operation is an undefined behavior (it will continue scanning the
+ * memory without any bound checking). */
+raxNode **raxFindParentLink(raxNode *parent, raxNode *child) {
+ raxNode **cp = raxNodeFirstChildPtr(parent);
+ raxNode *c;
+ while(1) {
+ memcpy(&c,cp,sizeof(c));
+ if (c == child) break;
+ cp++;
+ }
+ return cp;
+}
+
+/* Low level child removal from node. The new node pointer (after the child
+ * removal) is returned. Note that this function does not fix the pointer
+ * of the parent node in its parent, so this task is up to the caller.
+ * The function never fails for out of memory. */
+raxNode *raxRemoveChild(raxNode *parent, raxNode *child) {
+ debugnode("raxRemoveChild before", parent);
+ /* If parent is a compressed node (having a single child, as for definition
+ * of the data structure), the removal of the child consists into turning
+ * it into a normal node without children. */
+ if (parent->iscompr) {
+ void *data = NULL;
+ if (parent->iskey) data = raxGetData(parent);
+ parent->isnull = 0;
+ parent->iscompr = 0;
+ parent->size = 0;
+ if (parent->iskey) raxSetData(parent,data);
+ debugnode("raxRemoveChild after", parent);
+ return parent;
+ }
+
+ /* Otherwise we need to scan for the child pointer and memmove()
+ * accordingly.
+ *
+ * 1. To start we seek the first element in both the children
+ * pointers and edge bytes in the node. */
+ raxNode **cp = raxNodeFirstChildPtr(parent);
+ raxNode **c = cp;
+ unsigned char *e = parent->data;
+
+ /* 2. Search the child pointer to remove inside the array of children
+ * pointers. */
+ while(1) {
+ raxNode *aux;
+ memcpy(&aux,c,sizeof(aux));
+ if (aux == child) break;
+ c++;
+ e++;
+ }
+
+ /* 3. Remove the edge and the pointer by memmoving the remaining children
+ * pointer and edge bytes one position before. */
+ int taillen = parent->size - (e - parent->data) - 1;
+ debugf("raxRemoveChild tail len: %d\n", taillen);
+ memmove(e,e+1,taillen);
+
+ /* Compute the shift, that is the amount of bytes we should move our
+ * child pointers to the left, since the removal of one edge character
+ * and the corresponding padding change, may change the layout.
+ * We just check if in the old version of the node there was at the
+ * end just a single byte and all padding: in that case removing one char
+ * will remove a whole sizeof(void*) word. */
+ size_t shift = ((parent->size+4) % sizeof(void*)) == 1 ? sizeof(void*) : 0;
+
+ /* Move the children pointers before the deletion point. */
+ if (shift)
+ memmove(((char*)cp)-shift,cp,(parent->size-taillen-1)*sizeof(raxNode**));
+
+ /* Move the remaining "tail" pointers at the right position as well. */
+ size_t valuelen = (parent->iskey && !parent->isnull) ? sizeof(void*) : 0;
+ memmove(((char*)c)-shift,c+1,taillen*sizeof(raxNode**)+valuelen);
+
+ /* 4. Update size. */
+ parent->size--;
+
+ /* realloc the node according to the theoretical memory usage, to free
+ * data if we are over-allocating right now. */
+ raxNode *newnode = rax_realloc(parent,raxNodeCurrentLength(parent));
+ if (newnode) {
+ debugnode("raxRemoveChild after", newnode);
+ }
+ /* Note: if rax_realloc() fails we just return the old address, which
+ * is valid. */
+ return newnode ? newnode : parent;
+}
+
+/* Remove the specified item. Returns 1 if the item was found and
+ * deleted, 0 otherwise. */
+int raxRemove(rax *rax, unsigned char *s, size_t len, void **old) {
+ raxNode *h;
+ raxStack ts;
+
+ debugf("### Delete: %.*s\n", (int)len, s);
+ raxStackInit(&ts);
+ int splitpos = 0;
+ size_t i = raxLowWalk(rax,s,len,&h,NULL,&splitpos,&ts);
+ if (i != len || (h->iscompr && splitpos != 0) || !h->iskey) {
+ raxStackFree(&ts);
+ return 0;
+ }
+ if (old) *old = raxGetData(h);
+ h->iskey = 0;
+ rax->numele--;
+
+ /* If this node has no children, the deletion needs to reclaim the
+ * no longer used nodes. This is an iterative process that needs to
+ * walk the three upward, deleting all the nodes with just one child
+ * that are not keys, until the head of the rax is reached or the first
+ * node with more than one child is found. */
+
+ int trycompress = 0; /* Will be set to 1 if we should try to optimize the
+ tree resulting from the deletion. */
+
+ if (h->size == 0) {
+ debugf("Key deleted in node without children. Cleanup needed.\n");
+ raxNode *child = NULL;
+ while(h != rax->head) {
+ child = h;
+ debugf("Freeing child %p [%.*s] key:%d\n", (void*)child,
+ (int)child->size, (char*)child->data, child->iskey);
+ rax_free(child);
+ rax->numnodes--;
+ h = raxStackPop(&ts);
+ /* If this node has more then one child, or actually holds
+ * a key, stop here. */
+ if (h->iskey || (!h->iscompr && h->size != 1)) break;
+ }
+ if (child) {
+ debugf("Unlinking child %p from parent %p\n",
+ (void*)child, (void*)h);
+ raxNode *new = raxRemoveChild(h,child);
+ if (new != h) {
+ raxNode *parent = raxStackPeek(&ts);
+ raxNode **parentlink;
+ if (parent == NULL) {
+ parentlink = &rax->head;
+ } else {
+ parentlink = raxFindParentLink(parent,h);
+ }
+ memcpy(parentlink,&new,sizeof(new));
+ }
+
+ /* If after the removal the node has just a single child
+ * and is not a key, we need to try to compress it. */
+ if (new->size == 1 && new->iskey == 0) {
+ trycompress = 1;
+ h = new;
+ }
+ }
+ } else if (h->size == 1) {
+ /* If the node had just one child, after the removal of the key
+ * further compression with adjacent nodes is pontentially possible. */
+ trycompress = 1;
+ }
+
+ /* Don't try node compression if our nodes pointers stack is not
+ * complete because of OOM while executing raxLowWalk() */
+ if (trycompress && ts.oom) trycompress = 0;
+
+ /* Recompression: if trycompress is true, 'h' points to a radix tree node
+ * that changed in a way that could allow to compress nodes in this
+ * sub-branch. Compressed nodes represent chains of nodes that are not
+ * keys and have a single child, so there are two deletion events that
+ * may alter the tree so that further compression is needed:
+ *
+ * 1) A node with a single child was a key and now no longer is a key.
+ * 2) A node with two children now has just one child.
+ *
+ * We try to navigate upward till there are other nodes that can be
+ * compressed, when we reach the upper node which is not a key and has
+ * a single child, we scan the chain of children to collect the
+ * compressable part of the tree, and replace the current node with the
+ * new one, fixing the child pointer to reference the first non
+ * compressable node.
+ *
+ * Example of case "1". A tree stores the keys "FOO" = 1 and
+ * "FOOBAR" = 2:
+ *
+ *
+ * "FOO" -> "BAR" -> [] (2)
+ * (1)
+ *
+ * After the removal of "FOO" the tree can be compressed as:
+ *
+ * "FOOBAR" -> [] (2)
+ *
+ *
+ * Example of case "2". A tree stores the keys "FOOBAR" = 1 and
+ * "FOOTER" = 2:
+ *
+ * |B| -> "AR" -> [] (1)
+ * "FOO" -> |-|
+ * |T| -> "ER" -> [] (2)
+ *
+ * After the removal of "FOOTER" the resulting tree is:
+ *
+ * "FOO" -> |B| -> "AR" -> [] (1)
+ *
+ * That can be compressed into:
+ *
+ * "FOOBAR" -> [] (1)
+ */
+ if (trycompress) {
+ debugf("After removing %.*s:\n", (int)len, s);
+ debugnode("Compression may be needed",h);
+ debugf("Seek start node\n");
+
+ /* Try to reach the upper node that is compressible.
+ * At the end of the loop 'h' will point to the first node we
+ * can try to compress and 'parent' to its parent. */
+ raxNode *parent;
+ while(1) {
+ parent = raxStackPop(&ts);
+ if (!parent || parent->iskey ||
+ (!parent->iscompr && parent->size != 1)) break;
+ h = parent;
+ debugnode("Going up to",h);
+ }
+ raxNode *start = h; /* Compression starting node. */
+
+ /* Scan chain of nodes we can compress. */
+ size_t comprsize = h->size;
+ int nodes = 1;
+ while(h->size != 0) {
+ raxNode **cp = raxNodeLastChildPtr(h);
+ memcpy(&h,cp,sizeof(h));
+ if (h->iskey || (!h->iscompr && h->size != 1)) break;
+ /* Stop here if going to the next node would result into
+ * a compressed node larger than h->size can hold. */
+ if (comprsize + h->size > RAX_NODE_MAX_SIZE) break;
+ nodes++;
+ comprsize += h->size;
+ }
+ if (nodes > 1) {
+ /* If we can compress, create the new node and populate it. */
+ size_t nodesize =
+ sizeof(raxNode)+comprsize+raxPadding(comprsize)+sizeof(raxNode*);
+ raxNode *new = rax_malloc(nodesize);
+ /* An out of memory here just means we cannot optimize this
+ * node, but the tree is left in a consistent state. */
+ if (new == NULL) {
+ raxStackFree(&ts);
+ return 1;
+ }
+ new->iskey = 0;
+ new->isnull = 0;
+ new->iscompr = 1;
+ new->size = comprsize;
+ rax->numnodes++;
+
+ /* Scan again, this time to populate the new node content and
+ * to fix the new node child pointer. At the same time we free
+ * all the nodes that we'll no longer use. */
+ comprsize = 0;
+ h = start;
+ while(h->size != 0) {
+ memcpy(new->data+comprsize,h->data,h->size);
+ comprsize += h->size;
+ raxNode **cp = raxNodeLastChildPtr(h);
+ raxNode *tofree = h;
+ memcpy(&h,cp,sizeof(h));
+ rax_free(tofree); rax->numnodes--;
+ if (h->iskey || (!h->iscompr && h->size != 1)) break;
+ }
+ debugnode("New node",new);
+
+ /* Now 'h' points to the first node that we still need to use,
+ * so our new node child pointer will point to it. */
+ raxNode **cp = raxNodeLastChildPtr(new);
+ memcpy(cp,&h,sizeof(h));
+
+ /* Fix parent link. */
+ if (parent) {
+ raxNode **parentlink = raxFindParentLink(parent,start);
+ memcpy(parentlink,&new,sizeof(new));
+ } else {
+ rax->head = new;
+ }
+
+ debugf("Compressed %d nodes, %d total bytes\n",
+ nodes, (int)comprsize);
+ }
+ }
+ raxStackFree(&ts);
+ return 1;
+}
+
+/* This is the core of raxFree(): performs a depth-first scan of the
+ * tree and releases all the nodes found. */
+void raxRecursiveFree(rax *rax, raxNode *n, void (*free_callback)(void*)) {
+ debugnode("free traversing",n);
+ int numchildren = n->iscompr ? 1 : n->size;
+ raxNode **cp = raxNodeLastChildPtr(n);
+ while(numchildren--) {
+ raxNode *child;
+ memcpy(&child,cp,sizeof(child));
+ raxRecursiveFree(rax,child,free_callback);
+ cp--;
+ }
+ debugnode("free depth-first",n);
+ if (free_callback && n->iskey && !n->isnull)
+ free_callback(raxGetData(n));
+ rax_free(n);
+ rax->numnodes--;
+}
+
+/* Free a whole radix tree, calling the specified callback in order to
+ * free the auxiliary data. */
+void raxFreeWithCallback(rax *rax, void (*free_callback)(void*)) {
+ raxRecursiveFree(rax,rax->head,free_callback);
+ assert(rax->numnodes == 0);
+ rax_free(rax);
+}
+
+/* Free a whole radix tree. */
+void raxFree(rax *rax) {
+ raxFreeWithCallback(rax,NULL);
+}
+
+/* ------------------------------- Iterator --------------------------------- */
+
+/* Initialize a Rax iterator. This call should be performed a single time
+ * to initialize the iterator, and must be followed by a raxSeek() call,
+ * otherwise the raxPrev()/raxNext() functions will just return EOF. */
+void raxStart(raxIterator *it, rax *rt) {
+ it->flags = RAX_ITER_EOF; /* No crash if the iterator is not seeked. */
+ it->rt = rt;
+ it->key_len = 0;
+ it->key = it->key_static_string;
+ it->key_max = RAX_ITER_STATIC_LEN;
+ it->data = NULL;
+ it->node_cb = NULL;
+ raxStackInit(&it->stack);
+}
+
+/* Append characters at the current key string of the iterator 'it'. This
+ * is a low level function used to implement the iterator, not callable by
+ * the user. Returns 0 on out of memory, otherwise 1 is returned. */
+int raxIteratorAddChars(raxIterator *it, unsigned char *s, size_t len) {
+ if (it->key_max < it->key_len+len) {
+ unsigned char *old = (it->key == it->key_static_string) ? NULL :
+ it->key;
+ size_t new_max = (it->key_len+len)*2;
+ it->key = rax_realloc(old,new_max);
+ if (it->key == NULL) {
+ it->key = (!old) ? it->key_static_string : old;
+ errno = ENOMEM;
+ return 0;
+ }
+ if (old == NULL) memcpy(it->key,it->key_static_string,it->key_len);
+ it->key_max = new_max;
+ }
+ /* Use memmove since there could be an overlap between 's' and
+ * it->key when we use the current key in order to re-seek. */
+ memmove(it->key+it->key_len,s,len);
+ it->key_len += len;
+ return 1;
+}
+
+/* Remove the specified number of chars from the right of the current
+ * iterator key. */
+void raxIteratorDelChars(raxIterator *it, size_t count) {
+ it->key_len -= count;
+}
+
+/* Do an iteration step towards the next element. At the end of the step the
+ * iterator key will represent the (new) current key. If it is not possible
+ * to step in the specified direction since there are no longer elements, the
+ * iterator is flagged with RAX_ITER_EOF.
+ *
+ * If 'noup' is true the function starts directly scanning for the next
+ * lexicographically smaller children, and the current node is already assumed
+ * to be the parent of the last key node, so the first operation to go back to
+ * the parent will be skipped. This option is used by raxSeek() when
+ * implementing seeking a non existing element with the ">" or "<" options:
+ * the starting node is not a key in that particular case, so we start the scan
+ * from a node that does not represent the key set.
+ *
+ * The function returns 1 on success or 0 on out of memory. */
+int raxIteratorNextStep(raxIterator *it, int noup) {
+ if (it->flags & RAX_ITER_EOF) {
+ return 1;
+ } else if (it->flags & RAX_ITER_JUST_SEEKED) {
+ it->flags &= ~RAX_ITER_JUST_SEEKED;
+ return 1;
+ }
+
+ /* Save key len, stack items and the node where we are currently
+ * so that on iterator EOF we can restore the current key and state. */
+ size_t orig_key_len = it->key_len;
+ size_t orig_stack_items = it->stack.items;
+ raxNode *orig_node = it->node;
+
+ while(1) {
+ int children = it->node->iscompr ? 1 : it->node->size;
+ if (!noup && children) {
+ debugf("GO DEEPER\n");
+ /* Seek the lexicographically smaller key in this subtree, which
+ * is the first one found always going torwards the first child
+ * of every successive node. */
+ if (!raxStackPush(&it->stack,it->node)) return 0;
+ raxNode **cp = raxNodeFirstChildPtr(it->node);
+ if (!raxIteratorAddChars(it,it->node->data,
+ it->node->iscompr ? it->node->size : 1)) return 0;
+ memcpy(&it->node,cp,sizeof(it->node));
+ /* Call the node callback if any, and replace the node pointer
+ * if the callback returns true. */
+ if (it->node_cb && it->node_cb(&it->node))
+ memcpy(cp,&it->node,sizeof(it->node));
+ /* For "next" step, stop every time we find a key along the
+ * way, since the key is lexicograhically smaller compared to
+ * what follows in the sub-children. */
+ if (it->node->iskey) {
+ it->data = raxGetData(it->node);
+ return 1;
+ }
+ } else {
+ /* If we finished exporing the previous sub-tree, switch to the
+ * new one: go upper until a node is found where there are
+ * children representing keys lexicographically greater than the
+ * current key. */
+ while(1) {
+ int old_noup = noup;
+
+ /* Already on head? Can't go up, iteration finished. */
+ if (!noup && it->node == it->rt->head) {
+ it->flags |= RAX_ITER_EOF;
+ it->stack.items = orig_stack_items;
+ it->key_len = orig_key_len;
+ it->node = orig_node;
+ return 1;
+ }
+ /* If there are no children at the current node, try parent's
+ * next child. */
+ unsigned char prevchild = it->key[it->key_len-1];
+ if (!noup) {
+ it->node = raxStackPop(&it->stack);
+ } else {
+ noup = 0;
+ }
+ /* Adjust the current key to represent the node we are
+ * at. */
+ int todel = it->node->iscompr ? it->node->size : 1;
+ raxIteratorDelChars(it,todel);
+
+ /* Try visiting the next child if there was at least one
+ * additional child. */
+ if (!it->node->iscompr && it->node->size > (old_noup ? 0 : 1)) {
+ raxNode **cp = raxNodeFirstChildPtr(it->node);
+ int i = 0;
+ while (i < it->node->size) {
+ debugf("SCAN NEXT %c\n", it->node->data[i]);
+ if (it->node->data[i] > prevchild) break;
+ i++;
+ cp++;
+ }
+ if (i != it->node->size) {
+ debugf("SCAN found a new node\n");
+ raxIteratorAddChars(it,it->node->data+i,1);
+ if (!raxStackPush(&it->stack,it->node)) return 0;
+ memcpy(&it->node,cp,sizeof(it->node));
+ /* Call the node callback if any, and replace the node
+ * pointer if the callback returns true. */
+ if (it->node_cb && it->node_cb(&it->node))
+ memcpy(cp,&it->node,sizeof(it->node));
+ if (it->node->iskey) {
+ it->data = raxGetData(it->node);
+ return 1;
+ }
+ break;
+ }
+ }
+ }
+ }
+ }
+}
+
+/* Seek the greatest key in the subtree at the current node. Return 0 on
+ * out of memory, otherwise 1. This is an helper function for different
+ * iteration functions below. */
+int raxSeekGreatest(raxIterator *it) {
+ while(it->node->size) {
+ if (it->node->iscompr) {
+ if (!raxIteratorAddChars(it,it->node->data,
+ it->node->size)) return 0;
+ } else {
+ if (!raxIteratorAddChars(it,it->node->data+it->node->size-1,1))
+ return 0;
+ }
+ raxNode **cp = raxNodeLastChildPtr(it->node);
+ if (!raxStackPush(&it->stack,it->node)) return 0;
+ memcpy(&it->node,cp,sizeof(it->node));
+ }
+ return 1;
+}
+
+/* Like raxIteratorNextStep() but implements an iteration step moving
+ * to the lexicographically previous element. The 'noup' option has a similar
+ * effect to the one of raxIteratorNextStep(). */
+int raxIteratorPrevStep(raxIterator *it, int noup) {
+ if (it->flags & RAX_ITER_EOF) {
+ return 1;
+ } else if (it->flags & RAX_ITER_JUST_SEEKED) {
+ it->flags &= ~RAX_ITER_JUST_SEEKED;
+ return 1;
+ }
+
+ /* Save key len, stack items and the node where we are currently
+ * so that on iterator EOF we can restore the current key and state. */
+ size_t orig_key_len = it->key_len;
+ size_t orig_stack_items = it->stack.items;
+ raxNode *orig_node = it->node;
+
+ while(1) {
+ int old_noup = noup;
+
+ /* Already on head? Can't go up, iteration finished. */
+ if (!noup && it->node == it->rt->head) {
+ it->flags |= RAX_ITER_EOF;
+ it->stack.items = orig_stack_items;
+ it->key_len = orig_key_len;
+ it->node = orig_node;
+ return 1;
+ }
+
+ unsigned char prevchild = it->key[it->key_len-1];
+ if (!noup) {
+ it->node = raxStackPop(&it->stack);
+ } else {
+ noup = 0;
+ }
+
+ /* Adjust the current key to represent the node we are
+ * at. */
+ int todel = it->node->iscompr ? it->node->size : 1;
+ raxIteratorDelChars(it,todel);
+
+ /* Try visiting the prev child if there is at least one
+ * child. */
+ if (!it->node->iscompr && it->node->size > (old_noup ? 0 : 1)) {
+ raxNode **cp = raxNodeLastChildPtr(it->node);
+ int i = it->node->size-1;
+ while (i >= 0) {
+ debugf("SCAN PREV %c\n", it->node->data[i]);
+ if (it->node->data[i] < prevchild) break;
+ i--;
+ cp--;
+ }
+ /* If we found a new subtree to explore in this node,
+ * go deeper following all the last children in order to
+ * find the key lexicographically greater. */
+ if (i != -1) {
+ debugf("SCAN found a new node\n");
+ /* Enter the node we just found. */
+ if (!raxIteratorAddChars(it,it->node->data+i,1)) return 0;
+ if (!raxStackPush(&it->stack,it->node)) return 0;
+ memcpy(&it->node,cp,sizeof(it->node));
+ /* Seek sub-tree max. */
+ if (!raxSeekGreatest(it)) return 0;
+ }
+ }
+
+ /* Return the key: this could be the key we found scanning a new
+ * subtree, or if we did not find a new subtree to explore here,
+ * before giving up with this node, check if it's a key itself. */
+ if (it->node->iskey) {
+ it->data = raxGetData(it->node);
+ return 1;
+ }
+ }
+}
+
+/* Seek an iterator at the specified element.
+ * Return 0 if the seek failed for syntax error or out of memory. Otherwise
+ * 1 is returned. When 0 is returned for out of memory, errno is set to
+ * the ENOMEM value. */
+int raxSeek(raxIterator *it, const char *op, unsigned char *ele, size_t len) {
+ int eq = 0, lt = 0, gt = 0, first = 0, last = 0;
+
+ it->stack.items = 0; /* Just resetting. Intialized by raxStart(). */
+ it->flags |= RAX_ITER_JUST_SEEKED;
+ it->flags &= ~RAX_ITER_EOF;
+ it->key_len = 0;
+ it->node = NULL;
+
+ /* Set flags according to the operator used to perform the seek. */
+ if (op[0] == '>') {
+ gt = 1;
+ if (op[1] == '=') eq = 1;
+ } else if (op[0] == '<') {
+ lt = 1;
+ if (op[1] == '=') eq = 1;
+ } else if (op[0] == '=') {
+ eq = 1;
+ } else if (op[0] == '^') {
+ first = 1;
+ } else if (op[0] == '$') {
+ last = 1;
+ } else {
+ errno = 0;
+ return 0; /* Error. */
+ }
+
+ /* If there are no elements, set the EOF condition immediately and
+ * return. */
+ if (it->rt->numele == 0) {
+ it->flags |= RAX_ITER_EOF;
+ return 1;
+ }
+
+ if (first) {
+ /* Seeking the first key greater or equal to the empty string
+ * is equivalent to seeking the smaller key available. */
+ return raxSeek(it,">=",NULL,0);
+ }
+
+ if (last) {
+ /* Find the greatest key taking always the last child till a
+ * final node is found. */
+ it->node = it->rt->head;
+ if (!raxSeekGreatest(it)) return 0;
+ assert(it->node->iskey);
+ it->data = raxGetData(it->node);
+ return 1;
+ }
+
+ /* We need to seek the specified key. What we do here is to actually
+ * perform a lookup, and later invoke the prev/next key code that
+ * we already use for iteration. */
+ int splitpos = 0;
+ size_t i = raxLowWalk(it->rt,ele,len,&it->node,NULL,&splitpos,&it->stack);
+
+ /* Return OOM on incomplete stack info. */
+ if (it->stack.oom) return 0;
+
+ if (eq && i == len && (!it->node->iscompr || splitpos == 0) &&
+ it->node->iskey)
+ {
+ /* We found our node, since the key matches and we have an
+ * "equal" condition. */
+ if (!raxIteratorAddChars(it,ele,len)) return 0; /* OOM. */
+ it->data = raxGetData(it->node);
+ } else if (lt || gt) {
+ /* Exact key not found or eq flag not set. We have to set as current
+ * key the one represented by the node we stopped at, and perform
+ * a next/prev operation to seek. To reconstruct the key at this node
+ * we start from the parent and go to the current node, accumulating
+ * the characters found along the way. */
+ if (!raxStackPush(&it->stack,it->node)) return 0;
+ for (size_t j = 1; j < it->stack.items; j++) {
+ raxNode *parent = it->stack.stack[j-1];
+ raxNode *child = it->stack.stack[j];
+ if (parent->iscompr) {
+ if (!raxIteratorAddChars(it,parent->data,parent->size))
+ return 0;
+ } else {
+ raxNode **cp = raxNodeFirstChildPtr(parent);
+ unsigned char *p = parent->data;
+ while(1) {
+ raxNode *aux;
+ memcpy(&aux,cp,sizeof(aux));
+ if (aux == child) break;
+ cp++;
+ p++;
+ }
+ if (!raxIteratorAddChars(it,p,1)) return 0;
+ }
+ }
+ raxStackPop(&it->stack);
+
+ /* We need to set the iterator in the correct state to call next/prev
+ * step in order to seek the desired element. */
+ debugf("After initial seek: i=%d len=%d key=%.*s\n",
+ (int)i, (int)len, (int)it->key_len, it->key);
+ if (i != len && !it->node->iscompr) {
+ /* If we stopped in the middle of a normal node because of a
+ * mismatch, add the mismatching character to the current key
+ * and call the iterator with the 'noup' flag so that it will try
+ * to seek the next/prev child in the current node directly based
+ * on the mismatching character. */
+ if (!raxIteratorAddChars(it,ele+i,1)) return 0;
+ debugf("Seek normal node on mismatch: %.*s\n",
+ (int)it->key_len, (char*)it->key);
+
+ it->flags &= ~RAX_ITER_JUST_SEEKED;
+ if (lt && !raxIteratorPrevStep(it,1)) return 0;
+ if (gt && !raxIteratorNextStep(it,1)) return 0;
+ it->flags |= RAX_ITER_JUST_SEEKED; /* Ignore next call. */
+ } else if (i != len && it->node->iscompr) {
+ debugf("Compressed mismatch: %.*s\n",
+ (int)it->key_len, (char*)it->key);
+ /* In case of a mismatch within a compressed node. */
+ int nodechar = it->node->data[splitpos];
+ int keychar = ele[i];
+ it->flags &= ~RAX_ITER_JUST_SEEKED;
+ if (gt) {
+ /* If the key the compressed node represents is greater
+ * than our seek element, continue forward, otherwise set the
+ * state in order to go back to the next sub-tree. */
+ if (nodechar > keychar) {
+ if (!raxIteratorNextStep(it,0)) return 0;
+ } else {
+ if (!raxIteratorAddChars(it,it->node->data,it->node->size))
+ return 0;
+ if (!raxIteratorNextStep(it,1)) return 0;
+ }
+ }
+ if (lt) {
+ /* If the key the compressed node represents is smaller
+ * than our seek element, seek the greater key in this
+ * subtree, otherwise set the state in order to go back to
+ * the previous sub-tree. */
+ if (nodechar < keychar) {
+ if (!raxSeekGreatest(it)) return 0;
+ it->data = raxGetData(it->node);
+ } else {
+ if (!raxIteratorAddChars(it,it->node->data,it->node->size))
+ return 0;
+ if (!raxIteratorPrevStep(it,1)) return 0;
+ }
+ }
+ it->flags |= RAX_ITER_JUST_SEEKED; /* Ignore next call. */
+ } else {
+ debugf("No mismatch: %.*s\n",
+ (int)it->key_len, (char*)it->key);
+ /* If there was no mismatch we are into a node representing the
+ * key, (but which is not a key or the seek operator does not
+ * include 'eq'), or we stopped in the middle of a compressed node
+ * after processing all the key. Continue iterating as this was
+ * a legitimate key we stopped at. */
+ it->flags &= ~RAX_ITER_JUST_SEEKED;
+ if (it->node->iscompr && it->node->iskey && splitpos && lt) {
+ /* If we stopped in the middle of a compressed node with
+ * perfect match, and the condition is to seek a key "<" than
+ * the specified one, then if this node is a key it already
+ * represents our match. For instance we may have nodes:
+ *
+ * "f" -> "oobar" = 1 -> "" = 2
+ *
+ * Representing keys "f" = 1, "foobar" = 2. A seek for
+ * the key < "foo" will stop in the middle of the "oobar"
+ * node, but will be our match, representing the key "f".
+ *
+ * So in that case, we don't seek backward. */
+ it->data = raxGetData(it->node);
+ } else {
+ if (gt && !raxIteratorNextStep(it,0)) return 0;
+ if (lt && !raxIteratorPrevStep(it,0)) return 0;
+ }
+ it->flags |= RAX_ITER_JUST_SEEKED; /* Ignore next call. */
+ }
+ } else {
+ /* If we are here just eq was set but no match was found. */
+ it->flags |= RAX_ITER_EOF;
+ return 1;
+ }
+ return 1;
+}
+
+/* Go to the next element in the scope of the iterator 'it'.
+ * If EOF (or out of memory) is reached, 0 is returned, otherwise 1 is
+ * returned. In case 0 is returned because of OOM, errno is set to ENOMEM. */
+int raxNext(raxIterator *it) {
+ if (!raxIteratorNextStep(it,0)) {
+ errno = ENOMEM;
+ return 0;
+ }
+ if (it->flags & RAX_ITER_EOF) {
+ errno = 0;
+ return 0;
+ }
+ return 1;
+}
+
+/* Go to the previous element in the scope of the iterator 'it'.
+ * If EOF (or out of memory) is reached, 0 is returned, otherwise 1 is
+ * returned. In case 0 is returned because of OOM, errno is set to ENOMEM. */
+int raxPrev(raxIterator *it) {
+ if (!raxIteratorPrevStep(it,0)) {
+ errno = ENOMEM;
+ return 0;
+ }
+ if (it->flags & RAX_ITER_EOF) {
+ errno = 0;
+ return 0;
+ }
+ return 1;
+}
+
+/* Perform a random walk starting in the current position of the iterator.
+ * Return 0 if the tree is empty or on out of memory. Otherwise 1 is returned
+ * and the iterator is set to the node reached after doing a random walk
+ * of 'steps' steps. If the 'steps' argument is 0, the random walk is performed
+ * using a random number of steps between 1 and two times the logarithm of
+ * the number of elements.
+ *
+ * NOTE: if you use this function to generate random elements from the radix
+ * tree, expect a disappointing distribution. A random walk produces good
+ * random elements if the tree is not sparse, however in the case of a radix
+ * tree certain keys will be reported much more often than others. At least
+ * this function should be able to expore every possible element eventually. */
+int raxRandomWalk(raxIterator *it, size_t steps) {
+ if (it->rt->numele == 0) {
+ it->flags |= RAX_ITER_EOF;
+ return 0;
+ }
+
+ if (steps == 0) {
+ size_t fle = 1+floor(log(it->rt->numele));
+ fle *= 2;
+ steps = 1 + rand() % fle;
+ }
+
+ raxNode *n = it->node;
+ while(steps > 0 || !n->iskey) {
+ int numchildren = n->iscompr ? 1 : n->size;
+ int r = rand() % (numchildren+(n != it->rt->head));
+
+ if (r == numchildren) {
+ /* Go up to parent. */
+ n = raxStackPop(&it->stack);
+ int todel = n->iscompr ? n->size : 1;
+ raxIteratorDelChars(it,todel);
+ } else {
+ /* Select a random child. */
+ if (n->iscompr) {
+ if (!raxIteratorAddChars(it,n->data,n->size)) return 0;
+ } else {
+ if (!raxIteratorAddChars(it,n->data+r,1)) return 0;
+ }
+ raxNode **cp = raxNodeFirstChildPtr(n)+r;
+ if (!raxStackPush(&it->stack,n)) return 0;
+ memcpy(&n,cp,sizeof(n));
+ }
+ if (n->iskey) steps--;
+ }
+ it->node = n;
+ return 1;
+}
+
+/* Compare the key currently pointed by the iterator to the specified
+ * key according to the specified operator. Returns 1 if the comparison is
+ * true, otherwise 0 is returned. */
+int raxCompare(raxIterator *iter, const char *op, unsigned char *key, size_t key_len) {
+ int eq = 0, lt = 0, gt = 0;
+
+ if (op[0] == '=' || op[1] == '=') eq = 1;
+ if (op[0] == '>') gt = 1;
+ else if (op[0] == '<') lt = 1;
+ else if (op[1] != '=') return 0; /* Syntax error. */
+
+ size_t minlen = key_len < iter->key_len ? key_len : iter->key_len;
+ int cmp = memcmp(iter->key,key,minlen);
+
+ /* Handle == */
+ if (lt == 0 && gt == 0) return cmp == 0 && key_len == iter->key_len;
+
+ /* Handle >, >=, <, <= */
+ if (cmp == 0) {
+ /* Same prefix: longer wins. */
+ if (eq && key_len == iter->key_len) return 1;
+ else if (lt) return iter->key_len < key_len;
+ else if (gt) return iter->key_len > key_len;
+ else return 0; /* Avoid warning, just 'eq' is handled before. */
+ } else if (cmp > 0) {
+ return gt ? 1 : 0;
+ } else /* (cmp < 0) */ {
+ return lt ? 1 : 0;
+ }
+}
+
+/* Free the iterator. */
+void raxStop(raxIterator *it) {
+ if (it->key != it->key_static_string) rax_free(it->key);
+ raxStackFree(&it->stack);
+}
+
+/* Return if the iterator is in an EOF state. This happens when raxSeek()
+ * failed to seek an appropriate element, so that raxNext() or raxPrev()
+ * will return zero, or when an EOF condition was reached while iterating
+ * with raxNext() and raxPrev(). */
+int raxEOF(raxIterator *it) {
+ return it->flags & RAX_ITER_EOF;
+}
+
+/* Return the number of elements inside the radix tree. */
+uint64_t raxSize(rax *rax) {
+ return rax->numele;
+}
+
+/* ----------------------------- Introspection ------------------------------ */
+
+/* This function is mostly used for debugging and learning purposes.
+ * It shows an ASCII representation of a tree on standard output, outling
+ * all the nodes and the contained keys.
+ *
+ * The representation is as follow:
+ *
+ * "foobar" (compressed node)
+ * [abc] (normal node with three children)
+ * [abc]=0x12345678 (node is a key, pointing to value 0x12345678)
+ * [] (a normal empty node)
+ *
+ * Children are represented in new idented lines, each children prefixed by
+ * the "`-(x)" string, where "x" is the edge byte.
+ *
+ * [abc]
+ * `-(a) "ladin"
+ * `-(b) [kj]
+ * `-(c) []
+ *
+ * However when a node has a single child the following representation
+ * is used instead:
+ *
+ * [abc] -> "ladin" -> []
+ */
+
+/* The actual implementation of raxShow(). */
+void raxRecursiveShow(int level, int lpad, raxNode *n) {
+ char s = n->iscompr ? '"' : '[';
+ char e = n->iscompr ? '"' : ']';
+
+ int numchars = printf("%c%.*s%c", s, n->size, n->data, e);
+ if (n->iskey) {
+ numchars += printf("=%p",raxGetData(n));
+ }
+
+ int numchildren = n->iscompr ? 1 : n->size;
+ /* Note that 7 and 4 magic constants are the string length
+ * of " `-(x) " and " -> " respectively. */
+ if (level) {
+ lpad += (numchildren > 1) ? 7 : 4;
+ if (numchildren == 1) lpad += numchars;
+ }
+ raxNode **cp = raxNodeFirstChildPtr(n);
+ for (int i = 0; i < numchildren; i++) {
+ char *branch = " `-(%c) ";
+ if (numchildren > 1) {
+ printf("\n");
+ for (int j = 0; j < lpad; j++) putchar(' ');
+ printf(branch,n->data[i]);
+ } else {
+ printf(" -> ");
+ }
+ raxNode *child;
+ memcpy(&child,cp,sizeof(child));
+ raxRecursiveShow(level+1,lpad,child);
+ cp++;
+ }
+}
+
+/* Show a tree, as outlined in the comment above. */
+void raxShow(rax *rax) {
+ raxRecursiveShow(0,0,rax->head);
+ putchar('\n');
+}
+
+/* Used by debugnode() macro to show info about a given node. */
+void raxDebugShowNode(const char *msg, raxNode *n) {
+ if (raxDebugMsg == 0) return;
+ printf("%s: %p [%.*s] key:%d size:%d children:",
+ msg, (void*)n, (int)n->size, (char*)n->data, n->iskey, n->size);
+ int numcld = n->iscompr ? 1 : n->size;
+ raxNode **cldptr = raxNodeLastChildPtr(n) - (numcld-1);
+ while(numcld--) {
+ raxNode *child;
+ memcpy(&child,cldptr,sizeof(child));
+ cldptr++;
+ printf("%p ", (void*)child);
+ }
+ printf("\n");
+ fflush(stdout);
+}
+
+/* Touch all the nodes of a tree returning a check sum. This is useful
+ * in order to make Valgrind detect if there is something wrong while
+ * reading the data structure.
+ *
+ * This function was used in order to identify Rax bugs after a big refactoring
+ * using this technique:
+ *
+ * 1. The rax-test is executed using Valgrind, adding a printf() so that for
+ * the fuzz tester we see what iteration in the loop we are in.
+ * 2. After every modification of the radix tree made by the fuzz tester
+ * in rax-test.c, we add a call to raxTouch().
+ * 3. Now as soon as an operation will corrupt the tree, raxTouch() will
+ * detect it (via Valgrind) immediately. We can add more calls to narrow
+ * the state.
+ * 4. At this point a good idea is to enable Rax debugging messages immediately
+ * before the moment the tree is corrupted, to see what happens.
+ */
+unsigned long raxTouch(raxNode *n) {
+ debugf("Touching %p\n", (void*)n);
+ unsigned long sum = 0;
+ if (n->iskey) {
+ sum += (unsigned long)raxGetData(n);
+ }
+
+ int numchildren = n->iscompr ? 1 : n->size;
+ raxNode **cp = raxNodeFirstChildPtr(n);
+ int count = 0;
+ for (int i = 0; i < numchildren; i++) {
+ if (numchildren > 1) {
+ sum += (long)n->data[i];
+ }
+ raxNode *child;
+ memcpy(&child,cp,sizeof(child));
+ if (child == (void*)0x65d1760) count++;
+ if (count > 1) exit(1);
+ sum += raxTouch(child);
+ cp++;
+ }
+ return sum;
+}
diff --git a/src/libsysprof/rax.h b/src/libsysprof/rax.h
new file mode 100644
index 0000000..f2521d1
--- /dev/null
+++ b/src/libsysprof/rax.h
@@ -0,0 +1,216 @@
+/* Rax -- A radix tree implementation.
+ *
+ * Copyright (c) 2017-2018, Salvatore Sanfilippo <antirez at gmail dot com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * * Neither the name of Redis nor the names of its contributors may be used
+ * to endorse or promote products derived from this software without
+ * specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef RAX_H
+#define RAX_H
+
+#include <stdint.h>
+
+/* Representation of a radix tree as implemented in this file, that contains
+ * the strings "foo", "foobar" and "footer" after the insertion of each
+ * word. When the node represents a key inside the radix tree, we write it
+ * between [], otherwise it is written between ().
+ *
+ * This is the vanilla representation:
+ *
+ * (f) ""
+ * \
+ * (o) "f"
+ * \
+ * (o) "fo"
+ * \
+ * [t b] "foo"
+ * / \
+ * "foot" (e) (a) "foob"
+ * / \
+ * "foote" (r) (r) "fooba"
+ * / \
+ * "footer" [] [] "foobar"
+ *
+ * However, this implementation implements a very common optimization where
+ * successive nodes having a single child are "compressed" into the node
+ * itself as a string of characters, each representing a next-level child,
+ * and only the link to the node representing the last character node is
+ * provided inside the representation. So the above representation is turend
+ * into:
+ *
+ * ["foo"] ""
+ * |
+ * [t b] "foo"
+ * / \
+ * "foot" ("er") ("ar") "foob"
+ * / \
+ * "footer" [] [] "foobar"
+ *
+ * However this optimization makes the implementation a bit more complex.
+ * For instance if a key "first" is added in the above radix tree, a
+ * "node splitting" operation is needed, since the "foo" prefix is no longer
+ * composed of nodes having a single child one after the other. This is the
+ * above tree and the resulting node splitting after this event happens:
+ *
+ *
+ * (f) ""
+ * /
+ * (i o) "f"
+ * / \
+ * "firs" ("rst") (o) "fo"
+ * / \
+ * "first" [] [t b] "foo"
+ * / \
+ * "foot" ("er") ("ar") "foob"
+ * / \
+ * "footer" [] [] "foobar"
+ *
+ * Similarly after deletion, if a new chain of nodes having a single child
+ * is created (the chain must also not include nodes that represent keys),
+ * it must be compressed back into a single node.
+ *
+ */
+
+#define RAX_NODE_MAX_SIZE ((1<<29)-1)
+typedef struct raxNode {
+ uint32_t iskey:1; /* Does this node contain a key? */
+ uint32_t isnull:1; /* Associated value is NULL (don't store it). */
+ uint32_t iscompr:1; /* Node is compressed. */
+ uint32_t size:29; /* Number of children, or compressed string len. */
+ /* Data layout is as follows:
+ *
+ * If node is not compressed we have 'size' bytes, one for each children
+ * character, and 'size' raxNode pointers, point to each child node.
+ * Note how the character is not stored in the children but in the
+ * edge of the parents:
+ *
+ * [header iscompr=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)
+ *
+ * if node is compressed (iscompr bit is 1) the node has 1 children.
+ * In that case the 'size' bytes of the string stored immediately at
+ * the start of the data section, represent a sequence of successive
+ * nodes linked one after the other, for which only the last one in
+ * the sequence is actually represented as a node, and pointed to by
+ * the current compressed node.
+ *
+ * [header iscompr=1][xyz][z-ptr](value-ptr?)
+ *
+ * Both compressed and not compressed nodes can represent a key
+ * with associated data in the radix tree at any level (not just terminal
+ * nodes).
+ *
+ * If the node has an associated key (iskey=1) and is not NULL
+ * (isnull=0), then after the raxNode pointers poiting to the
+ * children, an additional value pointer is present (as you can see
+ * in the representation above as "value-ptr" field).
+ */
+ unsigned char data[];
+} raxNode;
+
+typedef struct rax {
+ raxNode *head;
+ uint64_t numele;
+ uint64_t numnodes;
+} rax;
+
+/* Stack data structure used by raxLowWalk() in order to, optionally, return
+ * a list of parent nodes to the caller. The nodes do not have a "parent"
+ * field for space concerns, so we use the auxiliary stack when needed. */
+#define RAX_STACK_STATIC_ITEMS 32
+typedef struct raxStack {
+ void **stack; /* Points to static_items or an heap allocated array. */
+ size_t items, maxitems; /* Number of items contained and total space. */
+ /* Up to RAXSTACK_STACK_ITEMS items we avoid to allocate on the heap
+ * and use this static array of pointers instead. */
+ void *static_items[RAX_STACK_STATIC_ITEMS];
+ int oom; /* True if pushing into this stack failed for OOM at some point. */
+} raxStack;
+
+/* Optional callback used for iterators and be notified on each rax node,
+ * including nodes not representing keys. If the callback returns true
+ * the callback changed the node pointer in the iterator structure, and the
+ * iterator implementation will have to replace the pointer in the radix tree
+ * internals. This allows the callback to reallocate the node to perform
+ * very special operations, normally not needed by normal applications.
+ *
+ * This callback is used to perform very low level analysis of the radix tree
+ * structure, scanning each possible node (but the root node), or in order to
+ * reallocate the nodes to reduce the allocation fragmentation (this is the
+ * Redis application for this callback).
+ *
+ * This is currently only supported in forward iterations (raxNext) */
+typedef int (*raxNodeCallback)(raxNode **noderef);
+
+/* Radix tree iterator state is encapsulated into this data structure. */
+#define RAX_ITER_STATIC_LEN 128
+#define RAX_ITER_JUST_SEEKED (1<<0) /* Iterator was just seeked. Return current
+ element for the first iteration and
+ clear the flag. */
+#define RAX_ITER_EOF (1<<1) /* End of iteration reached. */
+#define RAX_ITER_SAFE (1<<2) /* Safe iterator, allows operations while
+ iterating. But it is slower. */
+typedef struct raxIterator {
+ int flags;
+ rax *rt; /* Radix tree we are iterating. */
+ unsigned char *key; /* The current string. */
+ void *data; /* Data associated to this key. */
+ size_t key_len; /* Current key length. */
+ size_t key_max; /* Max key len the current key buffer can hold. */
+ unsigned char key_static_string[RAX_ITER_STATIC_LEN];
+ raxNode *node; /* Current node. Only for unsafe iteration. */
+ raxStack stack; /* Stack used for unsafe iteration. */
+ raxNodeCallback node_cb; /* Optional node callback. Normally set to NULL. */
+} raxIterator;
+
+/* A special pointer returned for not found items. */
+extern void *raxNotFound;
+
+/* Exported API. */
+rax *raxNew(void);
+int raxInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old);
+int raxTryInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old);
+int raxRemove(rax *rax, unsigned char *s, size_t len, void **old);
+void *raxFind(rax *rax, unsigned char *s, size_t len);
+void raxFree(rax *rax);
+void raxFreeWithCallback(rax *rax, void (*free_callback)(void*));
+void raxStart(raxIterator *it, rax *rt);
+int raxSeek(raxIterator *it, const char *op, unsigned char *ele, size_t len);
+int raxNext(raxIterator *it);
+int raxPrev(raxIterator *it);
+int raxRandomWalk(raxIterator *it, size_t steps);
+int raxCompare(raxIterator *iter, const char *op, unsigned char *key, size_t key_len);
+void raxStop(raxIterator *it);
+int raxEOF(raxIterator *it);
+void raxShow(rax *rax);
+uint64_t raxSize(rax *rax);
+unsigned long raxTouch(raxNode *n);
+void raxSetDebugMsg(int onoff);
+
+/* Internal API. May be used by the node callback in order to access rax nodes
+ * in a low level way, so this function is exported as well. */
+void raxSetData(raxNode *n, void *data);
+
+#endif
diff --git a/src/libsysprof/rax_malloc.h b/src/libsysprof/rax_malloc.h
new file mode 100644
index 0000000..e9d5d5d
--- /dev/null
+++ b/src/libsysprof/rax_malloc.h
@@ -0,0 +1,43 @@
+/* Rax -- A radix tree implementation.
+ *
+ * Copyright (c) 2017, Salvatore Sanfilippo <antirez at gmail dot com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * * Neither the name of Redis nor the names of its contributors may be used
+ * to endorse or promote products derived from this software without
+ * specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/* Allocator selection.
+ *
+ * This file is used in order to change the Rax allocator at compile time.
+ * Just define the following defines to what you want to use. Also add
+ * the include of your alternate allocator if needed (not needed in order
+ * to use the default libc allocator). */
+
+#ifndef RAX_ALLOC_H
+#define RAX_ALLOC_H
+#define rax_malloc malloc
+#define rax_realloc realloc
+#define rax_free free
+#endif
diff --git a/src/libsysprof/sysprof-memprof-profile.c b/src/libsysprof/sysprof-memprof-profile.c
new file mode 100644
index 0000000..7f9b0c5
--- /dev/null
+++ b/src/libsysprof/sysprof-memprof-profile.c
@@ -0,0 +1,489 @@
+/* sysprof-memprof-profile.c
+ *
+ * Copyright 2020 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#define G_LOG_DOMAIN "sysprof-memprof-profile"
+
+#include "config.h"
+
+#include <sysprof-capture.h>
+
+#include "sysprof-capture-symbol-resolver.h"
+#include "sysprof-elf-symbol-resolver.h"
+#include "sysprof-kernel-symbol-resolver.h"
+#include "sysprof-memprof-profile.h"
+#include "sysprof-symbol-resolver.h"
+
+#include "rax.h"
+#include "../stackstash.h"
+
+typedef struct
+{
+ SysprofSelection *selection;
+ SysprofCaptureReader *reader;
+ GPtrArray *resolvers;
+ GStringChunk *symbols;
+ GHashTable *tags;
+ GHashTable *cmdlines;
+ StackStash *stash;
+ StackStash *building;
+ rax *rax;
+ GArray *resolved;
+} Generate;
+
+struct _SysprofMemprofProfile
+{
+ GObject parent_instance;
+ SysprofSelection *selection;
+ SysprofCaptureReader *reader;
+ Generate *g;
+};
+
+static void profile_iface_init (SysprofProfileInterface *iface);
+
+G_DEFINE_TYPE_WITH_CODE (SysprofMemprofProfile, sysprof_memprof_profile, G_TYPE_OBJECT,
+ G_IMPLEMENT_INTERFACE (SYSPROF_TYPE_PROFILE, profile_iface_init))
+
+enum {
+ PROP_0,
+ PROP_SELECTION,
+ N_PROPS
+};
+
+static GParamSpec *properties[N_PROPS];
+
+static void
+generate_free (Generate *g)
+{
+ g_clear_pointer (&g->reader, sysprof_capture_reader_unref);
+ g_clear_pointer (&g->rax, raxFree);
+ g_clear_pointer (&g->stash, stack_stash_unref);
+ g_clear_pointer (&g->building, stack_stash_unref);
+ g_clear_pointer (&g->resolvers, g_ptr_array_unref);
+ g_clear_pointer (&g->symbols, g_string_chunk_free);
+ g_clear_pointer (&g->tags, g_hash_table_unref);
+ g_clear_pointer (&g->resolved, g_array_unref);
+ g_clear_pointer (&g->cmdlines, g_hash_table_unref);
+ g_clear_object (&g->selection);
+}
+
+static Generate *
+generate_ref (Generate *g)
+{
+ return g_atomic_rc_box_acquire (g);
+}
+
+static void
+generate_unref (Generate *g)
+{
+ g_atomic_rc_box_release_full (g, (GDestroyNotify)generate_free);
+}
+
+static void
+sysprof_memprof_profile_finalize (GObject *object)
+{
+ SysprofMemprofProfile *self = (SysprofMemprofProfile *)object;
+
+ g_clear_pointer (&self->g, generate_unref);
+ g_clear_pointer (&self->reader, sysprof_capture_reader_unref);
+ g_clear_object (&self->selection);
+
+ G_OBJECT_CLASS (sysprof_memprof_profile_parent_class)->finalize (object);
+}
+
+static void
+sysprof_memprof_profile_get_property (GObject *object,
+ guint prop_id,
+ GValue *value,
+ GParamSpec *pspec)
+{
+ SysprofMemprofProfile *self = SYSPROF_MEMPROF_PROFILE (object);
+
+ switch (prop_id)
+ {
+ case PROP_SELECTION:
+ g_value_set_object (value, self->selection);
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
+ }
+}
+
+static void
+sysprof_memprof_profile_set_property (GObject *object,
+ guint prop_id,
+ const GValue *value,
+ GParamSpec *pspec)
+{
+ SysprofMemprofProfile *self = SYSPROF_MEMPROF_PROFILE (object);
+
+ switch (prop_id)
+ {
+ case PROP_SELECTION:
+ self->selection = g_value_dup_object (value);
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
+ }
+}
+
+static void
+sysprof_memprof_profile_class_init (SysprofMemprofProfileClass *klass)
+{
+ GObjectClass *object_class = G_OBJECT_CLASS (klass);
+
+ object_class->finalize = sysprof_memprof_profile_finalize;
+ object_class->get_property = sysprof_memprof_profile_get_property;
+ object_class->set_property = sysprof_memprof_profile_set_property;
+
+ properties [PROP_SELECTION] =
+ g_param_spec_object ("selection",
+ "Selection",
+ "The selection for filtering the callgraph",
+ SYSPROF_TYPE_SELECTION,
+ (G_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY | G_PARAM_STATIC_STRINGS));
+
+ g_object_class_install_properties (object_class, N_PROPS, properties);
+}
+
+static void
+sysprof_memprof_profile_init (SysprofMemprofProfile *self)
+{
+}
+
+SysprofProfile *
+sysprof_memprof_profile_new (void)
+{
+ return g_object_new (SYSPROF_TYPE_MEMPROF_PROFILE, NULL);
+}
+
+static void
+sysprof_memprof_profile_set_reader (SysprofProfile *profile,
+ SysprofCaptureReader *reader)
+{
+ SysprofMemprofProfile *self = (SysprofMemprofProfile *)profile;
+
+ g_assert (SYSPROF_IS_MEMPROF_PROFILE (self));
+ g_assert (reader != NULL);
+
+ if (reader != self->reader)
+ {
+ g_clear_pointer (&self->reader, sysprof_capture_reader_unref);
+ self->reader = sysprof_capture_reader_ref (reader);
+ }
+}
+
+static SysprofCaptureCursor *
+create_cursor (SysprofCaptureReader *reader)
+{
+ static SysprofCaptureFrameType types[] = {
+ SYSPROF_CAPTURE_FRAME_ALLOCATION,
+ SYSPROF_CAPTURE_FRAME_PROCESS,
+ };
+ SysprofCaptureCursor *cursor;
+ SysprofCaptureCondition *cond;
+
+ cond = sysprof_capture_condition_new_where_type_in (G_N_ELEMENTS (types), types);
+ cursor = sysprof_capture_cursor_new (reader);
+ sysprof_capture_cursor_add_condition (cursor, cond);
+
+ return cursor;
+}
+
+static gboolean
+cursor_foreach_cb (const SysprofCaptureFrame *frame,
+ gpointer user_data)
+{
+ Generate *g = user_data;
+
+ g_assert (frame != NULL);
+ g_assert (frame->type == SYSPROF_CAPTURE_FRAME_ALLOCATION ||
+ frame->type == SYSPROF_CAPTURE_FRAME_PROCESS);
+
+ /* Short-circuit if we don't care about this frame */
+ if (!sysprof_selection_contains (g->selection, frame->time))
+ return TRUE;
+
+ if (frame->type == SYSPROF_CAPTURE_FRAME_PROCESS)
+ {
+ const SysprofCaptureProcess *pr = (const SysprofCaptureProcess *)frame;
+ g_autofree gchar *cmdline = g_strdup_printf ("[%s]", pr->cmdline);
+
+ g_hash_table_insert (g->cmdlines,
+ GINT_TO_POINTER (frame->pid),
+ (gchar *)g_string_chunk_insert_const (g->symbols, cmdline));
+
+ return TRUE;
+ }
+
+ if (frame->type == SYSPROF_CAPTURE_FRAME_ALLOCATION)
+ {
+ const SysprofCaptureAllocation *ev = (const SysprofCaptureAllocation *)frame;
+
+ /* Handle memory allocations */
+ if (ev->alloc_size > 0)
+ {
+ SysprofAddressContext last_context = SYSPROF_ADDRESS_CONTEXT_NONE;
+ const gchar *cmdline;
+ StackNode *node;
+ guint len = 5;
+
+ node = stack_stash_add_trace (g->building, ev->addrs, ev->n_addrs, ev->alloc_size);
+
+ for (const StackNode *iter = node; iter != NULL; iter = iter->parent)
+ len++;
+
+ if (G_UNLIKELY (g->resolved->len < len))
+ g_array_set_size (g->resolved, len);
+
+ len = 0;
+
+ for (const StackNode *iter = node; iter != NULL; iter = iter->parent)
+ {
+ SysprofAddressContext context = SYSPROF_ADDRESS_CONTEXT_NONE;
+ SysprofAddress address = iter->data;
+ const gchar *symbol = NULL;
+
+ if (sysprof_address_is_context_switch (address, &context))
+ {
+ if (last_context)
+ symbol = sysprof_address_context_to_string (last_context);
+ else
+ symbol = NULL;
+
+ last_context = context;
+ }
+ else
+ {
+ for (guint i = 0; i < g->resolvers->len; i++)
+ {
+ SysprofSymbolResolver *resolver = g_ptr_array_index (g->resolvers, i);
+ GQuark tag = 0;
+ gchar *str;
+
+ str = sysprof_symbol_resolver_resolve_with_context (resolver,
+ frame->time,
+ frame->pid,
+ last_context,
+ address,
+ &tag);
+
+ if (str != NULL)
+ {
+ symbol = g_string_chunk_insert_const (g->symbols, str);
+ g_free (str);
+
+ if (tag != 0 && !g_hash_table_contains (g->tags, symbol))
+ g_hash_table_insert (g->tags, (gchar *)symbol, GSIZE_TO_POINTER (tag));
+
+ break;
+ }
+ }
+ }
+
+ if (symbol != NULL)
+ g_array_index (g->resolved, SysprofAddress, len++) = POINTER_TO_U64 (symbol);
+ }
+
+ if ((cmdline = g_hash_table_lookup (g->cmdlines, GINT_TO_POINTER (frame->pid))))
+ g_array_index (g->resolved, guint64, len++) = POINTER_TO_U64 (cmdline);
+
+ g_array_index (g->resolved, guint64, len++) = POINTER_TO_U64 ("[Everything]");
+
+ stack_stash_add_trace (g->stash,
+ (gpointer)g->resolved->data,
+ len,
+ ev->alloc_size);
+ }
+ }
+
+ return TRUE;
+}
+
+static void
+sysprof_memprof_profile_generate_worker (GTask *task,
+ gpointer source_object,
+ gpointer task_data,
+ GCancellable *cancellable)
+{
+ SysprofCaptureCursor *cursor;
+ Generate *g = task_data;
+
+ g_assert (G_IS_TASK (task));
+ g_assert (g != NULL);
+ g_assert (g->reader != NULL);
+ g_assert (!cancellable || G_IS_CANCELLABLE (cancellable));
+
+ /* Make sure the capture is at the beginning */
+ sysprof_capture_reader_reset (g->reader);
+
+ /* Load all our symbol resolvers */
+ for (guint i = 0; i < g->resolvers->len; i++)
+ {
+ SysprofSymbolResolver *resolver = g_ptr_array_index (g->resolvers, i);
+
+ sysprof_symbol_resolver_load (resolver, g->reader);
+ sysprof_capture_reader_reset (g->reader);
+ }
+
+ cursor = create_cursor (g->reader);
+ sysprof_capture_cursor_foreach (cursor, cursor_foreach_cb, g);
+
+ /* Release some data we don't need anymore */
+ g_clear_pointer (&g->resolved, g_array_unref);
+ g_clear_pointer (&g->resolvers, g_ptr_array_unref);
+ g_clear_pointer (&g->reader, sysprof_capture_reader_unref);
+ g_clear_pointer (&g->building, stack_stash_unref);
+ g_clear_pointer (&g->cmdlines, g_hash_table_unref);
+ g_clear_object (&g->selection);
+
+ g_task_return_boolean (task, TRUE);
+}
+
+static void
+sysprof_memprof_profile_generate (SysprofProfile *profile,
+ GCancellable *cancellable,
+ GAsyncReadyCallback callback,
+ gpointer user_data)
+{
+ SysprofMemprofProfile *self = (SysprofMemprofProfile *)profile;
+ g_autoptr(GTask) task = NULL;
+ Generate *g;
+
+ g_assert (SYSPROF_IS_MEMPROF_PROFILE (self));
+ g_assert (!cancellable || G_IS_CANCELLABLE (cancellable));
+
+ task = g_task_new (self, cancellable, callback, user_data);
+ g_task_set_source_tag (task, sysprof_memprof_profile_generate);
+
+ if (self->reader == NULL)
+ {
+ g_task_return_new_error (task,
+ G_IO_ERROR,
+ G_IO_ERROR_NOT_INITIALIZED,
+ "No capture reader has been set");
+ return;
+ }
+
+ g = g_atomic_rc_box_new0 (Generate);
+ g->reader = sysprof_capture_reader_copy (self->reader);
+ g->selection = sysprof_selection_copy (self->selection);
+ g->cmdlines = g_hash_table_new (NULL, NULL);
+ g->rax = raxNew ();
+ g->stash = stack_stash_new (NULL);
+ g->building = stack_stash_new (NULL);
+ g->resolvers = g_ptr_array_new_with_free_func (g_object_unref);
+ g->symbols = g_string_chunk_new (4096*4);
+ g->tags = g_hash_table_new (g_str_hash, g_str_equal);
+ g->resolved = g_array_new (FALSE, TRUE, sizeof (guint64));
+
+ g_ptr_array_add (g->resolvers, sysprof_capture_symbol_resolver_new ());
+ g_ptr_array_add (g->resolvers, sysprof_kernel_symbol_resolver_new ());
+ g_ptr_array_add (g->resolvers, sysprof_elf_symbol_resolver_new ());
+
+ g_task_set_task_data (task, g, (GDestroyNotify) generate_unref);
+ g_task_run_in_thread (task, sysprof_memprof_profile_generate_worker);
+}
+
+static gboolean
+sysprof_memprof_profile_generate_finish (SysprofProfile *profile,
+ GAsyncResult *result,
+ GError **error)
+{
+ SysprofMemprofProfile *self = (SysprofMemprofProfile *)profile;
+
+ g_assert (SYSPROF_IS_MEMPROF_PROFILE (self));
+ g_assert (G_IS_TASK (result));
+
+ g_clear_pointer (&self->g, generate_unref);
+
+ if (g_task_propagate_boolean (G_TASK (result), error))
+ {
+ Generate *g = g_task_get_task_data (G_TASK (result));
+ self->g = generate_ref (g);
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+static void
+profile_iface_init (SysprofProfileInterface *iface)
+{
+ iface->set_reader = sysprof_memprof_profile_set_reader;
+ iface->generate = sysprof_memprof_profile_generate;
+ iface->generate_finish = sysprof_memprof_profile_generate_finish;
+}
+
+gpointer
+sysprof_memprof_profile_get_native (SysprofMemprofProfile *self)
+{
+ g_return_val_if_fail (SYSPROF_IS_MEMPROF_PROFILE (self), NULL);
+
+ if (self->g != NULL)
+ return self->g->rax;
+
+ return NULL;
+}
+
+gpointer
+sysprof_memprof_profile_get_stash (SysprofMemprofProfile *self)
+{
+ g_return_val_if_fail (SYSPROF_IS_MEMPROF_PROFILE (self), NULL);
+
+ if (self->g != NULL)
+ return self->g->stash;
+
+ return NULL;
+}
+
+gboolean
+sysprof_memprof_profile_is_empty (SysprofMemprofProfile *self)
+{
+ StackNode *root;
+
+ g_return_val_if_fail (SYSPROF_IS_MEMPROF_PROFILE (self), FALSE);
+
+ return (self->g == NULL ||
+ self->g->stash == NULL ||
+ !(root = stack_stash_get_root (self->g->stash)) ||
+ !root->total);
+}
+
+GQuark
+sysprof_memprof_profile_get_tag (SysprofMemprofProfile *self,
+ const gchar *symbol)
+{
+ g_return_val_if_fail (SYSPROF_IS_MEMPROF_PROFILE (self), 0);
+
+ if (self->g != NULL)
+ return GPOINTER_TO_SIZE (g_hash_table_lookup (self->g->tags, symbol));
+
+ return 0;
+}
+
+SysprofProfile *
+sysprof_memprof_profile_new_with_selection (SysprofSelection *selection)
+{
+ return g_object_new (SYSPROF_TYPE_MEMPROF_PROFILE,
+ "selection", selection,
+ NULL);
+}
diff --git a/src/libsysprof/sysprof-memprof-profile.h b/src/libsysprof/sysprof-memprof-profile.h
new file mode 100644
index 0000000..aaae18c
--- /dev/null
+++ b/src/libsysprof/sysprof-memprof-profile.h
@@ -0,0 +1,53 @@
+/* sysprof-memprof-profile.h
+ *
+ * Copyright 2020 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#pragma once
+
+#if !defined (SYSPROF_INSIDE) && !defined (SYSPROF_COMPILATION)
+# error "Only <sysprof.h> can be included directly."
+#endif
+
+#include "sysprof-version-macros.h"
+
+#include "sysprof-profile.h"
+#include "sysprof-selection.h"
+
+G_BEGIN_DECLS
+
+#define SYSPROF_TYPE_MEMPROF_PROFILE (sysprof_memprof_profile_get_type())
+
+SYSPROF_AVAILABLE_IN_ALL
+G_DECLARE_FINAL_TYPE (SysprofMemprofProfile, sysprof_memprof_profile, SYSPROF, MEMPROF_PROFILE, GObject)
+
+SYSPROF_AVAILABLE_IN_3_36
+SysprofProfile *sysprof_memprof_profile_new (void);
+SYSPROF_AVAILABLE_IN_3_36
+SysprofProfile *sysprof_memprof_profile_new_with_selection (SysprofSelection *selection);
+SYSPROF_AVAILABLE_IN_3_36
+gpointer sysprof_memprof_profile_get_native (SysprofMemprofProfile *self);
+SYSPROF_AVAILABLE_IN_3_36
+gpointer sysprof_memprof_profile_get_stash (SysprofMemprofProfile *self);
+SYSPROF_AVAILABLE_IN_3_36
+gboolean sysprof_memprof_profile_is_empty (SysprofMemprofProfile *self);
+SYSPROF_AVAILABLE_IN_3_36
+GQuark sysprof_memprof_profile_get_tag (SysprofMemprofProfile *self,
+ const gchar *symbol);
+
+G_END_DECLS
diff --git a/src/libsysprof/sysprof-memprof-source.c b/src/libsysprof/sysprof-memprof-source.c
new file mode 100644
index 0000000..4856ba7
--- /dev/null
+++ b/src/libsysprof/sysprof-memprof-source.c
@@ -0,0 +1,77 @@
+/* sysprof-memprof-source.c
+ *
+ * Copyright 2020 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#define G_LOG_DOMAIN "sysprof-memprof-source"
+
+#include "config.h"
+
+#include "sysprof-memprof-source.h"
+
+struct _SysprofMemprofSource
+{
+ SysprofTracefdSource parent_instance;
+};
+
+static SysprofSourceInterface *parent_iface;
+
+static void
+sysprof_memprof_source_modify_spawn (SysprofSource *source,
+ SysprofSpawnable *spawnable)
+{
+ g_assert (SYSPROF_IS_SOURCE (source));
+ g_assert (SYSPROF_IS_SPAWNABLE (spawnable));
+
+ parent_iface->modify_spawn (source, spawnable);
+
+#ifdef __linux__
+ sysprof_spawnable_setenv (spawnable, "G_SLICE", "always-malloc");
+ sysprof_spawnable_setenv (spawnable,
+ "LD_PRELOAD",
+ PACKAGE_LIBEXECDIR"/libsysprof-memory-"API_VERSION_S".so");
+#endif
+}
+
+static void
+source_iface_init (SysprofSourceInterface *iface)
+{
+ parent_iface = g_type_interface_peek_parent (iface);
+
+ iface->modify_spawn = sysprof_memprof_source_modify_spawn;
+}
+
+G_DEFINE_TYPE_WITH_CODE (SysprofMemprofSource, sysprof_memprof_source, SYSPROF_TYPE_TRACEFD_SOURCE,
+ G_IMPLEMENT_INTERFACE (SYSPROF_TYPE_SOURCE, source_iface_init))
+
+static void
+sysprof_memprof_source_class_init (SysprofMemprofSourceClass *klass)
+{
+}
+
+static void
+sysprof_memprof_source_init (SysprofMemprofSource *self)
+{
+ sysprof_tracefd_source_set_envvar (SYSPROF_TRACEFD_SOURCE (self), "MEMPROF_TRACE_FD");
+}
+
+SysprofSource *
+sysprof_memprof_source_new (void)
+{
+ return g_object_new (SYSPROF_TYPE_MEMPROF_SOURCE, NULL);
+}
diff --git a/src/libsysprof/sysprof-memprof-source.h b/src/libsysprof/sysprof-memprof-source.h
new file mode 100644
index 0000000..9188a89
--- /dev/null
+++ b/src/libsysprof/sysprof-memprof-source.h
@@ -0,0 +1,35 @@
+/* sysprof-memprof-source.h
+ *
+ * Copyright 2020 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#pragma once
+
+#include "sysprof-tracefd-source.h"
+
+G_BEGIN_DECLS
+
+#define SYSPROF_TYPE_MEMPROF_SOURCE (sysprof_memprof_source_get_type())
+
+SYSPROF_AVAILABLE_IN_3_36
+G_DECLARE_FINAL_TYPE (SysprofMemprofSource, sysprof_memprof_source, SYSPROF, MEMPROF_SOURCE,
SysprofTracefdSource)
+
+SYSPROF_AVAILABLE_IN_3_36
+SysprofSource *sysprof_memprof_source_new (void);
+
+G_END_DECLS
diff --git a/src/libsysprof/sysprof.h b/src/libsysprof/sysprof.h
index da4b524..bd81a83 100644
--- a/src/libsysprof/sysprof.h
+++ b/src/libsysprof/sysprof.h
@@ -36,6 +36,8 @@ G_BEGIN_DECLS
# include "sysprof-kernel-symbol-resolver.h"
# include "sysprof-kernel-symbol.h"
# include "sysprof-local-profiler.h"
+# include "sysprof-memprof-profile.h"
+# include "sysprof-memprof-source.h"
# include "sysprof-netdev-source.h"
# include "sysprof-process-model-item.h"
# include "sysprof-process-model.h"
diff --git a/src/tests/allocs-by-size.c b/src/tests/allocs-by-size.c
new file mode 100644
index 0000000..f0d3f24
--- /dev/null
+++ b/src/tests/allocs-by-size.c
@@ -0,0 +1,147 @@
+/* allocs-by-size.c
+ *
+ * Copyright 2020 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include "config.h"
+
+#include <glib/gi18n.h>
+#include <stddef.h>
+#include <rax.h>
+#include <sysprof.h>
+
+typedef struct
+{
+ gsize size;
+ gsize count;
+ gsize cmp;
+} Item;
+
+static gint
+item_compare (gconstpointer a,
+ gconstpointer b)
+{
+ const Item *item_a = a;
+ const Item *item_b = b;
+
+ if (item_a->cmp < item_b->cmp)
+ return -1;
+ else if (item_a->cmp > item_b->cmp)
+ return 1;
+ else
+ return 0;
+}
+
+static void
+allocs_by_size (SysprofCaptureReader *reader)
+{
+ SysprofCaptureFrameType type;
+ g_autoptr(GHashTable) allocs = NULL;
+ g_autoptr(GArray) ar = NULL;
+ GHashTableIter iter;
+ gpointer k,v;
+ gsize *count;
+
+ allocs = g_hash_table_new_full (NULL, NULL, NULL, g_free);
+ ar = g_array_new (FALSE, FALSE, sizeof (Item));
+
+ while (sysprof_capture_reader_peek_type (reader, &type))
+ {
+ if (type == SYSPROF_CAPTURE_FRAME_ALLOCATION)
+ {
+ const SysprofCaptureAllocation *ev = sysprof_capture_reader_read_allocation (reader);
+
+ if (ev == NULL)
+ break;
+
+ /* Ignore frees */
+ if (ev->alloc_size <= 0)
+ continue;
+
+ if (!(count = g_hash_table_lookup (allocs, GSIZE_TO_POINTER (ev->alloc_size))))
+ {
+ count = g_new0 (gsize, 1);
+ g_hash_table_insert (allocs, GSIZE_TO_POINTER (ev->alloc_size), count);
+ }
+
+ (*count)++;
+ }
+ else
+ {
+ if (!sysprof_capture_reader_skip (reader))
+ break;
+ }
+ }
+
+ g_hash_table_iter_init (&iter, allocs);
+ while (g_hash_table_iter_next (&iter, &k, &v))
+ {
+ const Item item = {
+ .size = GPOINTER_TO_SIZE (k),
+ .count = *(gsize *)v,
+ .cmp = *(gsize *)v * GPOINTER_TO_SIZE (k),
+ };
+
+ g_array_append_val (ar, item);
+ }
+
+ g_array_sort (ar, item_compare);
+
+ g_print ("alloc_size,total_alloc,n_allocs\n");
+
+ for (guint i = 0; i < ar->len; i++)
+ {
+ const Item *item = &g_array_index (ar, Item, i);
+
+ g_print ("%"G_GUINT64_FORMAT",%"G_GUINT64_FORMAT",%"G_GUINT64_FORMAT"\n",
+ item->size, item->cmp, item->count);
+ }
+}
+
+gint
+main (gint argc,
+ gchar *argv[])
+{
+ SysprofCaptureReader *reader;
+ const gchar *filename = argv[1];
+ g_autoptr(GError) error = NULL;
+
+ if (argc < 2)
+ {
+ g_printerr ("usage: %s FILENAME\n", argv[0]);
+ return EXIT_FAILURE;
+ }
+
+ /* Set up gettext translations */
+ setlocale (LC_ALL, "");
+ bindtextdomain (GETTEXT_PACKAGE, LOCALEDIR);
+ bind_textdomain_codeset (GETTEXT_PACKAGE, "UTF-8");
+ textdomain (GETTEXT_PACKAGE);
+
+ if (!(reader = sysprof_capture_reader_new (filename, &error)))
+ {
+ g_printerr ("%s\n", error->message);
+ return EXIT_FAILURE;
+ }
+
+ allocs_by_size (reader);
+
+ sysprof_capture_reader_unref (reader);
+
+ return EXIT_SUCCESS;
+}
diff --git a/src/tests/cross-thread-frees.c b/src/tests/cross-thread-frees.c
new file mode 100644
index 0000000..cd973b7
--- /dev/null
+++ b/src/tests/cross-thread-frees.c
@@ -0,0 +1,137 @@
+/* cross-thread-frees.c
+ *
+ * Copyright 2020 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include "config.h"
+
+#include <stddef.h>
+#include <rax.h>
+#include <sysprof.h>
+
+typedef struct
+{
+ gint tid;
+ guint n_addrs;
+ gint64 size;
+ SysprofCaptureAddress addrs[0];
+} Stack;
+
+static void
+stack_free (gpointer ptr)
+{
+ Stack *stack = ptr;
+ gsize size = sizeof *stack + (stack->n_addrs * sizeof (SysprofCaptureAddress));
+ g_slice_free1 (size, stack);
+}
+
+static Stack *
+stack_new (gint tid,
+ gint64 size,
+ guint n_addrs,
+ const SysprofCaptureAddress *addrs)
+{
+ Stack *stack;
+
+ stack = g_slice_alloc (sizeof *stack + (n_addrs * sizeof (SysprofCaptureAddress)));
+ stack->tid = tid;
+ stack->size = size;
+ stack->n_addrs = n_addrs;
+ for (guint i = 0; i < n_addrs; i++)
+ stack->addrs[i] = addrs[i];
+
+ return stack;
+}
+
+static void
+cross_thread_frees (SysprofCaptureReader *reader)
+{
+ SysprofCaptureFrameType type;
+ g_autoptr(GHashTable) stacks = NULL;
+
+ stacks = g_hash_table_new_full (NULL, NULL, NULL, stack_free);
+
+ while (sysprof_capture_reader_peek_type (reader, &type))
+ {
+ if (type == SYSPROF_CAPTURE_FRAME_ALLOCATION)
+ {
+ const SysprofCaptureAllocation *ev = sysprof_capture_reader_read_allocation (reader);
+ gpointer key;
+
+ if (ev == NULL)
+ break;
+
+ key = GINT_TO_POINTER (ev->alloc_addr);
+
+ if (ev->alloc_size > 0)
+ {
+ g_hash_table_insert (stacks,
+ key,
+ stack_new (ev->tid, ev->alloc_size, ev->n_addrs, ev->addrs));
+ }
+ else
+ {
+ Stack *stack;
+
+ stack = g_hash_table_lookup (stacks, key);
+ if (stack == NULL)
+ continue;
+
+ if (ev->tid != stack->tid)
+ {
+ g_print ("Alloc-Thread=%d Free-Thread=%d Size=%"G_GUINT64_FORMAT"\n",
+ stack->tid, ev->tid, stack->size);
+ }
+
+ g_hash_table_remove (stacks, key);
+ }
+ }
+ else
+ {
+ if (!sysprof_capture_reader_skip (reader))
+ break;
+ }
+ }
+}
+
+gint
+main (gint argc,
+ gchar *argv[])
+{
+ SysprofCaptureReader *reader;
+ const gchar *filename = argv[1];
+ g_autoptr(GError) error = NULL;
+
+ if (argc < 2)
+ {
+ g_printerr ("usage: %s FILENAME\n", argv[0]);
+ return EXIT_FAILURE;
+ }
+
+ if (!(reader = sysprof_capture_reader_new (filename, &error)))
+ {
+ g_printerr ("%s\n", error->message);
+ return EXIT_FAILURE;
+ }
+
+ cross_thread_frees (reader);
+
+ sysprof_capture_reader_unref (reader);
+
+ return EXIT_SUCCESS;
+}
diff --git a/src/tests/memory-stack-stash.c b/src/tests/memory-stack-stash.c
new file mode 100644
index 0000000..9d6859d
--- /dev/null
+++ b/src/tests/memory-stack-stash.c
@@ -0,0 +1,90 @@
+/* memory-stack-stash.c
+ *
+ * Copyright 2020 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include "config.h"
+
+#include <glib/gi18n.h>
+#include <stddef.h>
+#include <rax.h>
+#include <sysprof.h>
+
+#include "../stackstash.h"
+#include "../stackstash.c"
+
+static void
+memory_stack_stash (SysprofCaptureReader *reader)
+{
+ SysprofCaptureFrameType type;
+ StackStash *stash = stack_stash_new (NULL);
+
+ while (sysprof_capture_reader_peek_type (reader, &type))
+ {
+ if (type == SYSPROF_CAPTURE_FRAME_ALLOCATION)
+ {
+ const SysprofCaptureAllocation *ev = sysprof_capture_reader_read_allocation (reader);
+
+ if (ev == NULL)
+ break;
+
+ if (ev->alloc_size > 0)
+ stack_stash_add_trace (stash, ev->addrs, ev->n_addrs, ev->alloc_size);
+ }
+ else
+ {
+ if (!sysprof_capture_reader_skip (reader))
+ break;
+ }
+ }
+
+ stack_stash_unref (stash);
+}
+
+gint
+main (gint argc,
+ gchar *argv[])
+{
+ SysprofCaptureReader *reader;
+ const gchar *filename = argv[1];
+ g_autoptr(GError) error = NULL;
+
+ if (argc < 2)
+ {
+ g_printerr ("usage: %s FILENAME\n", argv[0]);
+ return EXIT_FAILURE;
+ }
+
+ /* Set up gettext translations */
+ setlocale (LC_ALL, "");
+ bindtextdomain (GETTEXT_PACKAGE, LOCALEDIR);
+ bind_textdomain_codeset (GETTEXT_PACKAGE, "UTF-8");
+ textdomain (GETTEXT_PACKAGE);
+
+ if (!(reader = sysprof_capture_reader_new (filename, &error)))
+ {
+ g_printerr ("%s\n", error->message);
+ return EXIT_FAILURE;
+ }
+
+ memory_stack_stash (reader);
+
+ sysprof_capture_reader_unref (reader);
+
+ return EXIT_SUCCESS;
+}
diff --git a/src/tests/meson.build b/src/tests/meson.build
index c506d19..7c41280 100644
--- a/src/tests/meson.build
+++ b/src/tests/meson.build
@@ -64,6 +64,30 @@ test_resolvers = executable('test-resolvers',
dependencies: test_deps,
)
+allocs_by_size = executable('allocs-by-size',
+ ['allocs-by-size.c'],
+ c_args: test_cflags,
+ dependencies: test_deps,
+)
+
+cross_thread_frees = executable('cross-thread-frees',
+ ['cross-thread-frees.c'],
+ c_args: test_cflags,
+ dependencies: test_deps,
+)
+
+memory_stack_stash = executable('memory-stack-stash',
+ ['memory-stack-stash.c'],
+ c_args: test_cflags,
+ dependencies: test_deps,
+)
+
+show_page_usage = executable('show-page-usage',
+ [ 'show-page-usage.c' ],
+ c_args: test_cflags,
+ dependencies: test_deps + [ librax_dep,
+ dependency('cairo') ],
+)
if get_option('enable_gtk')
diff --git a/src/tests/show-page-usage.c b/src/tests/show-page-usage.c
new file mode 100644
index 0000000..536f7bc
--- /dev/null
+++ b/src/tests/show-page-usage.c
@@ -0,0 +1,196 @@
+/* show-page-usage.c
+ *
+ * Copyright 2020 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include "config.h"
+
+#include <cairo.h>
+#include <stddef.h>
+#include <rax.h>
+#include <sysprof.h>
+
+static GMainLoop *main_loop;
+
+static gint
+u64_compare (gconstpointer a,
+ gconstpointer b)
+{
+ const guint64 *aptr = a;
+ const guint64 *bptr = b;
+
+ if (*aptr < *bptr)
+ return -1;
+ else if (*aptr > *bptr)
+ return 1;
+ else
+ return 0;
+}
+
+static void
+generate_cb (GObject *object,
+ GAsyncResult *result,
+ gpointer user_data)
+{
+ SysprofProfile *profile = (SysprofProfile *)object;
+ g_autoptr(GError) error = NULL;
+ GHashTable *seen;
+ GHashTableIter iter;
+ cairo_t *cr;
+ cairo_surface_t *surface;
+ GArray *ar;
+ raxIterator it;
+ rax *r;
+ gpointer k,v;
+
+ g_assert (SYSPROF_IS_MEMPROF_PROFILE (profile));
+ g_assert (G_IS_ASYNC_RESULT (result));
+
+ if (!sysprof_profile_generate_finish (profile, result, &error))
+ {
+ g_printerr ("%s\n", error->message);
+ exit (EXIT_FAILURE);
+ }
+
+ r = sysprof_memprof_profile_get_native (SYSPROF_MEMPROF_PROFILE (profile));
+ seen = g_hash_table_new (NULL, NULL);
+
+ raxStart (&it, r);
+ raxSeek (&it, "^", NULL, 0);
+ while (raxNext (&it))
+ {
+ guint64 page;
+ guint64 addr;
+
+ memcpy (&addr, it.key, sizeof addr);
+ page = addr / 4096;
+
+ if (g_hash_table_contains (seen, GSIZE_TO_POINTER (page)))
+ continue;
+
+ g_hash_table_insert (seen, GSIZE_TO_POINTER (page), NULL);
+ }
+ raxStop (&it);
+
+ ar = g_array_sized_new (FALSE, FALSE, sizeof (guint64), g_hash_table_size (seen));
+
+ g_hash_table_iter_init (&iter, seen);
+ while (g_hash_table_iter_next (&iter, &k, &v))
+ {
+ guint64 key = GPOINTER_TO_SIZE (k);
+
+ g_array_append_val (ar, key);
+ }
+
+ g_array_sort (ar, u64_compare);
+
+ for (guint i = 0; i < ar->len; i++)
+ {
+ guint64 key = g_array_index (ar, guint64, i);
+
+ g_hash_table_insert (seen, GSIZE_TO_POINTER (key), GSIZE_TO_POINTER (i));
+ }
+
+ g_printerr ("We have %u pages to graph\n", ar->len);
+
+ surface = cairo_image_surface_create (CAIRO_FORMAT_RGB24, ar->len, (4096/16));
+ cr = cairo_create (surface);
+
+ cairo_set_line_width (cr, 1.0);
+ cairo_set_antialias (cr, CAIRO_ANTIALIAS_NONE);
+
+ cairo_set_source_rgb (cr, 1, 1, 1);
+ cairo_rectangle (cr, 0, 0, ar->len, (4096/16));
+ cairo_fill (cr);
+
+ cairo_set_source_rgb (cr, 0, 0, 0);
+
+ cairo_scale (cr, 1.0, 1.0/16.0);
+ cairo_translate (cr, .5, .5);
+
+ raxStart (&it, r);
+ raxSeek (&it, "^", NULL, 0);
+ while (raxNext (&it))
+ {
+ guint64 page;
+ guint64 addr;
+ guint64 size;
+ guint x;
+ guint y;
+
+ memcpy (&addr, it.key, sizeof addr);
+ page = addr / 4096;
+ size = GPOINTER_TO_SIZE (it.data);
+
+ x = GPOINTER_TO_UINT (g_hash_table_lookup (seen, GSIZE_TO_POINTER (page)));
+ y = addr % 4096;
+
+ /* TODO: Need size */
+
+ cairo_move_to (cr, x, y);
+ cairo_line_to (cr, x, y+size);
+ }
+ raxStop (&it);
+
+ cairo_stroke (cr);
+
+ cairo_surface_write_to_png (surface, "memory.png");
+
+ cairo_destroy (cr);
+ cairo_surface_destroy (surface);
+
+ g_array_unref (ar);
+ g_hash_table_unref (seen);
+
+ g_main_loop_quit (main_loop);
+}
+
+gint
+main (gint argc,
+ gchar *argv[])
+{
+ SysprofCaptureReader *reader;
+ const gchar *filename = argv[1];
+ g_autoptr(SysprofProfile) memprof = NULL;
+ g_autoptr(GError) error = NULL;
+
+ if (argc < 2)
+ {
+ g_printerr ("usage: %s FILENAME\n", argv[0]);
+ return EXIT_FAILURE;
+ }
+
+ main_loop = g_main_loop_new (NULL, FALSE);
+
+ if (!(reader = sysprof_capture_reader_new (filename, &error)))
+ {
+ g_printerr ("%s\n", error->message);
+ return EXIT_FAILURE;
+ }
+
+ memprof = sysprof_memprof_profile_new ();
+ sysprof_profile_set_reader (memprof, reader);
+ sysprof_profile_generate (memprof, NULL, generate_cb, NULL);
+
+ g_main_loop_run (main_loop);
+ g_main_loop_unref (main_loop);
+
+ sysprof_capture_reader_unref (reader);
+
+ return EXIT_SUCCESS;
+}
diff --git a/src/tests/test-capture.c b/src/tests/test-capture.c
index 5f8eb3d..64d6f2c 100644
--- a/src/tests/test-capture.c
+++ b/src/tests/test-capture.c
@@ -900,6 +900,67 @@ test_reader_writer_cat_jitmap (void)
g_unlink ("jitmap-joined.syscap");
}
+static void
+test_writer_memory_alloc_free (void)
+{
+ SysprofCaptureWriter *writer;
+ SysprofCaptureReader *reader;
+ GError *error = NULL;
+ SysprofCaptureAddress addrs[20] = {
+ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
+ 11, 12, 13, 14, 15, 16, 17, 18, 19,
+ };
+ gboolean r;
+
+ writer = sysprof_capture_writer_new ("memory.syscap", 0);
+
+ for (guint i = 0; i < 20; i++)
+ {
+ r = sysprof_capture_writer_add_allocation_copy (writer,
+ SYSPROF_CAPTURE_CURRENT_TIME,
+ i % 4,
+ i % 3,
+ i % 7,
+ i,
+ i * 2,
+ addrs,
+ i);
+ g_assert_true (r);
+ }
+
+ sysprof_capture_writer_flush (writer);
+
+ reader = sysprof_capture_writer_create_reader (writer, &error);
+ g_assert_no_error (error);
+ g_assert_nonnull (reader);
+
+ for (guint i = 0; i < 20; i++)
+ {
+ const SysprofCaptureAllocation *ev;
+
+ ev = sysprof_capture_reader_read_allocation (reader);
+ g_assert_nonnull (ev);
+ g_assert_cmpint (ev->frame.type, ==, SYSPROF_CAPTURE_FRAME_ALLOCATION);
+
+ g_assert_cmpint (ev->frame.cpu, ==, i % 4);
+ g_assert_cmpint (ev->frame.pid, ==, i % 3);
+ g_assert_cmpint (ev->tid, ==, i % 7);
+ g_assert_cmpint (ev->alloc_addr, ==, i);
+ g_assert_cmpint (ev->alloc_size, ==, i * 2);
+ g_assert_cmpint (ev->n_addrs, ==, i);
+
+ for (guint j = 0; j < i; j++)
+ {
+ g_assert_cmpint (ev->addrs[j], ==, j);
+ }
+ }
+
+ sysprof_capture_writer_unref (writer);
+ sysprof_capture_reader_unref (reader);
+
+ g_unlink ("memory.syscap");
+}
+
int
main (int argc,
char *argv[])
@@ -907,6 +968,7 @@ main (int argc,
sysprof_clock_init ();
g_test_init (&argc, &argv, NULL);
g_test_add_func ("/SysprofCapture/ReaderWriter", test_reader_basic);
+ g_test_add_func ("/SysprofCapture/ReaderWriter/alloc_free", test_writer_memory_alloc_free);
g_test_add_func ("/SysprofCapture/Writer/splice", test_writer_splice);
g_test_add_func ("/SysprofCapture/Reader/splice", test_reader_splice);
g_test_add_func ("/SysprofCapture/ReaderWriter/log", test_reader_writer_log);
diff --git a/src/tools/sysprof-cli.c b/src/tools/sysprof-cli.c
index 78ff2b0..72b94e7 100644
--- a/src/tools/sysprof-cli.c
+++ b/src/tools/sysprof-cli.c
@@ -189,6 +189,7 @@ main (gint argc,
gboolean use_trace_fd = FALSE;
gboolean gnome_shell = FALSE;
gboolean rapl = FALSE;
+ gboolean memprof = FALSE;
gboolean merge = FALSE;
int pid = -1;
int fd;
@@ -208,6 +209,7 @@ main (gint argc,
{ "gjs", 0, 0, G_OPTION_ARG_NONE, &gjs, N_("Set GJS_TRACE_FD environment to trace GJS processes") },
{ "gtk", 0, 0, G_OPTION_ARG_NONE, >k, N_("Set GTK_TRACE_FD environment to trace a GTK application") },
{ "rapl", 0, 0, G_OPTION_ARG_NONE, &rapl, N_("Include RAPL energy statistics") },
+ { "memprof", 0, 0, G_OPTION_ARG_NONE, &memprof, N_("Profile memory allocations and frees") },
{ "gnome-shell", 0, 0, G_OPTION_ARG_NONE, &gnome_shell, N_("Connect to org.gnome.Shell for profiler
statistics") },
{ "merge", 0, 0, G_OPTION_ARG_NONE, &merge, N_("Merge all provided *.syscap files and write to stdout")
},
{ "version", 0, 0, G_OPTION_ARG_NONE, &version, N_("Print the sysprof-cli version and exit") },
@@ -471,6 +473,13 @@ Examples:\n\
g_object_unref (source);
}
+ if (memprof)
+ {
+ source = sysprof_memprof_source_new ();
+ sysprof_profiler_add_source (profiler, source);
+ g_object_unref (source);
+ }
+
if (pid != -1)
{
sysprof_profiler_set_whole_system (profiler, FALSE);
diff --git a/src/tools/sysprof-dump.c b/src/tools/sysprof-dump.c
index f93a177..8b50f54 100644
--- a/src/tools/sysprof-dump.c
+++ b/src/tools/sysprof-dump.c
@@ -299,6 +299,19 @@ main (gint argc,
}
break;
+ case SYSPROF_CAPTURE_FRAME_ALLOCATION:
+ {
+ const SysprofCaptureAllocation *ev = sysprof_capture_reader_read_allocation (reader);
+ gdouble ptime = (ev->frame.time - begin_time) / (gdouble)SYSPROF_NSEC_PER_SEC;
+
+ g_print ("%s: pid=%d tid=%d addr=0x%"G_GINT64_MODIFIER"x size=%"G_GINT64_FORMAT"
time=%"G_GINT64_FORMAT" (%lf)\n",
+ ev->alloc_size > 0 ? "ALLOC" : "FREE",
+ ev->frame.pid, ev->tid,
+ ev->alloc_addr, ev->alloc_size,
+ ev->frame.time, ptime);
+ }
+ break;
+
default:
g_print ("Skipping unknown frame type: (%d): ", type);
if (!sysprof_capture_reader_skip (reader))
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
