/*
   This file is part of odin, a memory profiler with fragmentation analysis.

   Copyright (C) 2007 Chris Wilson <chris@chris-wilson.co.uk>

   odin 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.

   odin 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 odin. If not, see <http://www.gnu.org/licenses/>/

   The GNU General Public License is contained in the file COPYING.
*/

#include "odin.h"
#include "frames.h"
#include "client.h"

#include <string.h>

Frame *
frames_get (Frames *frames, gulong ip)
{
    guint index = (ip ^ 6017773UL) % frames->frames.size;
    Frame *frame = frames->frames.nodes[index];
    while (frame != NULL && frame->ip != ip)
	frame = frame->ht_next;
    return frame;
}

guint
frames_get_unique_count (Frames *frames)
{
    return frames->frames.nnodes;
}

static inline guint
srcloc_hash (const Frame *f)
{
    return (gulong) f->function ^
	   (gulong) f->object ^
	   (gulong) f->file ^
	   f->line ^
	   60119197;
}

static inline gboolean
srcloc_equal (const Frame *a, const Frame *b)
{
    return a->function == b->function &&
	   a->object   == b->object   &&
	   a->file     == b->file     &&
	   a->line     == b->line;
}

void
frames_add (Frames *frames,
	    gulong ip,
	    const gchar *object,
	    const gchar *function,
	    const gchar *file,
	    const gchar *path,
	    gint line)
{
    Frame *f, *node;
    gchar buf[4096];
    int buf_len;
    guint index;

    f = frames_get (frames, ip);
    if (f != NULL)
	return;

    f = client_perm_alloc (frames->client, sizeof (Frame));
    f->ip = ip;

    if (function == NULL && object != NULL)
	sprintf (buf, "(within %s)", object);
    f->function = function ? client_add_string (frames->client, function) :
	                     object ? client_add_string (frames->client, buf) :
			              client_add_string (frames->client, "???");
    f->has_function = function != NULL;

    f->object = object ? client_add_string (frames->client, object) : NULL;
    f->file = file ? client_add_string (frames->client, file) : NULL;
    f->path = path ? client_add_string (frames->client, path) : NULL;
    f->line = line;

    index = srcloc_hash (f) % frames->srcloc.size;
    node = frames->srcloc.nodes[index];
    while (node != NULL && ! srcloc_equal (node, f))
	node = node->ht_srcloc_next;
    if (node == NULL) {
	buf_len = 0;
	if (function) {
	    buf_len = strlen (function);
	    memcpy (buf, function, buf_len);
	    if (file == NULL && object != NULL) {
		buf_len += snprintf (buf + buf_len,
			             sizeof (buf) - buf_len - 1,
				     " (in %s)", object);
	    }
	} else if (file == NULL && object != NULL) {
	    buf_len = sprintf (buf, "(within %s)", object);
	} else {
	    memcpy (buf, "???", 3);
	    buf_len = 3;
	}

	if (file != NULL) {
	    buf_len += snprintf (buf + buf_len,
		                 sizeof (buf) - buf_len - 1,
				 " (%s:%d)", file, line);
	}
	buf[buf_len] = '\0';
	f->function_srcloc = client_add_string (frames->client, buf);

	if (++frames->srcloc.nnodes > 3 * frames->srcloc.size) {
	    Frame **new_nodes;
	    Frame *node, *next;
	    guint n, new_size, hv;

	    new_size = g_spaced_primes_closest (frames->srcloc.nnodes);
	    new_nodes = g_new0 (Frame *, new_size);
	    for (n = 0; n < frames->srcloc.size ; n++) {
		for (node = frames->srcloc.nodes[n];
			node != NULL;
			node = next)
		{
		    next = node->ht_srcloc_next;
		    hv = srcloc_hash (node) % new_size;
		    node->ht_srcloc_next = new_nodes[hv];
		    new_nodes[hv] = node;
		}
	    }
	    g_free (frames->srcloc.nodes);
	    frames->frames.nodes = new_nodes;
	    frames->frames.size = new_size;

	    index = srcloc_hash (f) % frames->srcloc.size;
	}

	f->ht_srcloc_next = frames->srcloc.nodes[index];
	frames->srcloc.nodes[index] = f;
    } else
	f->function_srcloc = node->function_srcloc;

    f->alloc_fns_serial = 0;
    f->is_alloc_fn = FALSE;

    if (++frames->frames.nnodes > 3 * frames->frames.size) {
	Frame **new_nodes;
	Frame *node, *next;
	guint n, new_size, hv;

	new_size = g_spaced_primes_closest (frames->frames.nnodes);
	new_nodes = g_new0 (Frame *, new_size);
	for (n = 0; n < frames->frames.size ; n++) {
	    for (node = frames->frames.nodes[n];
		 node != NULL;
		 node = next)
	    {
		next = node->ht_next;
		hv = (node->ip ^ 6017773UL) % new_size;
		node->ht_next = new_nodes[hv];
		new_nodes[hv] = node;
	    }
	}
	g_free (frames->frames.nodes);
	frames->frames.nodes = new_nodes;
	frames->frames.size = new_size;
    }

    index = (ip ^ 6017773UL) % frames->frames.size;
    f->ht_next = frames->frames.nodes[index];
    frames->frames.nodes[index] = f;
    g_assert (frames_get (frames, ip) == f);
}

gboolean
frames_has_ip (Frames *frames, gulong ip)
{
    return frames_get (frames, ip) != NULL;
}

gboolean
frames_is_alloc_fn (Frames *frames, Frame *f)
{
    GList *l;

    if (! f->has_function)
	return TRUE;

    if (f->alloc_fns_serial == frames->alloc_fns_serial)
	return f->is_alloc_fn;

    for (l = frames->alloc_fns; l != NULL; l = g_list_next (l))
	if (g_regex_match (l->data, f->function, 0, NULL))
	    break;
    f->is_alloc_fn = l != NULL;
    f->alloc_fns_serial = frames->alloc_fns_serial;

    return f->is_alloc_fn;
}

gboolean
frames_add_alloc_fn (Frames *frames, const gchar *pattern, GError **error)
{
    GRegex *regex = g_regex_new (pattern, G_REGEX_OPTIMIZE, 0, error);
    if (regex == NULL)
	return FALSE;

    frames->alloc_fns = g_list_prepend (frames->alloc_fns, regex);

    if (++frames->alloc_fns_serial == 0)
	frames->alloc_fns_serial = 1;

    return TRUE;
}

guint
frames_get_alloc_fns_serial (Frames *frames)
{
    return frames->alloc_fns_serial;
}

static void
_frames_init_alloc_fns (Frames *frames)
{
    const gchar *patterns[] = {
	"[mMcCzZ]alloc",
	"operator new",
	"__builtin_new",
	"__builtin_vec_new",
	"realloc",
	"memalign",

	"vasprintf",

	"g_.*alloc",
	"([sS]trn?|[mM]em)dup",
	"ft_.*alloc", "FT_New_Memory", /* FreeType */
	"_hb_.*alloc", /* HarfBuzz */
	"X.*alloc", /* xorg */

	"^alloc",
	"_(new|create)$",
	"(New|Create)$",
    };
    guint n;

    for (n = 0; n < G_N_ELEMENTS (patterns); n++) {
	GError *error = NULL;
	GRegex *regex = g_regex_new (patterns[n], G_REGEX_OPTIMIZE, 0, &error);
	if (regex != NULL) {
	    frames->alloc_fns = g_list_prepend (frames->alloc_fns, regex);
	} else {
	    g_warning ("Failed to compile builtin regex '%s': %s",
		    patterns[n], error->message);
	    g_error_free (error);
	}
    }

    frames->alloc_fns_serial = 1;
}

void
frames_init (Frames *frames, Client *client)
{
    frames->client = client;
    frames->frames.size = 21089;
    frames->frames.nnodes = 0;
    frames->frames.nodes = g_new0 (Frame *, frames->frames.size);
    frames->alloc_fns = NULL;
    frames->alloc_fns_serial = 0;

    frames->srcloc.nnodes = 0;
    frames->srcloc.size = 21089;
    frames->srcloc.nodes = g_new0 (Frame *, frames->srcloc.size);

    _frames_init_alloc_fns (frames);
}

void
frames_fini (Frames *frames)
{
    g_free (frames->frames.nodes);
    g_free (frames->srcloc.nodes);

    g_list_foreach (frames->alloc_fns, (GFunc) g_regex_unref, NULL);
    g_list_free (frames->alloc_fns);
}