/*
 * call-path.h: Manipulate a tree data structure containing function call paths
 * Copyright (c) 2014, Intel Corporation.
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms and conditions of the GNU General Public License,
 * version 2, as published by the Free Software Foundation.
 *
 * This program is distributed in the hope 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.
 *
 */

#include <linux/rbtree.h>
#include <linux/list.h>

#include "util.h"
#include "call-path.h"

static void call_path__init(struct call_path *cp, struct call_path *parent,
			    struct symbol *sym, u64 ip, bool in_kernel)
{
	cp->parent = parent;
	cp->sym = sym;
	cp->ip = sym ? 0 : ip;
	cp->db_id = 0;
	cp->in_kernel = in_kernel;
	RB_CLEAR_NODE(&cp->rb_node);
	cp->children = RB_ROOT;
}

struct call_path_root *call_path_root__new(void)
{
	struct call_path_root *cpr;

	cpr = zalloc(sizeof(struct call_path_root));
	if (!cpr)
		return NULL;
	call_path__init(&cpr->call_path, NULL, NULL, 0, false);
	INIT_LIST_HEAD(&cpr->blocks);
	return cpr;
}

void call_path_root__free(struct call_path_root *cpr)
{
	struct call_path_block *pos, *n;

	list_for_each_entry_safe(pos, n, &cpr->blocks, node) {
		list_del(&pos->node);
		free(pos);
	}
	free(cpr);
}

static struct call_path *call_path__new(struct call_path_root *cpr,
					struct call_path *parent,
					struct symbol *sym, u64 ip,
					bool in_kernel)
{
	struct call_path_block *cpb;
	struct call_path *cp;
	size_t n;

	if (cpr->next < cpr->sz) {
		cpb = list_last_entry(&cpr->blocks, struct call_path_block,
				      node);
	} else {
		cpb = zalloc(sizeof(struct call_path_block));
		if (!cpb)
			return NULL;
		list_add_tail(&cpb->node, &cpr->blocks);
		cpr->sz += CALL_PATH_BLOCK_SIZE;
	}

	n = cpr->next++ & CALL_PATH_BLOCK_MASK;
	cp = &cpb->cp[n];

	call_path__init(cp, parent, sym, ip, in_kernel);

	return cp;
}

struct call_path *call_path__findnew(struct call_path_root *cpr,
				     struct call_path *parent,
				     struct symbol *sym, u64 ip, u64 ks)
{
	struct rb_node **p;
	struct rb_node *node_parent = NULL;
	struct call_path *cp;
	bool in_kernel = ip >= ks;

	if (sym)
		ip = 0;

	if (!parent)
		return call_path__new(cpr, parent, sym, ip, in_kernel);

	p = &parent->children.rb_node;
	while (*p != NULL) {
		node_parent = *p;
		cp = rb_entry(node_parent, struct call_path, rb_node);

		if (cp->sym == sym && cp->ip == ip)
			return cp;

		if (sym < cp->sym || (sym == cp->sym && ip < cp->ip))
			p = &(*p)->rb_left;
		else
			p = &(*p)->rb_right;
	}

	cp = call_path__new(cpr, parent, sym, ip, in_kernel);
	if (!cp)
		return NULL;

	rb_link_node(&cp->rb_node, node_parent, p);
	rb_insert_color(&cp->rb_node, &parent->children);

	return cp;
}
selected'>3</option><option value='4'>4</option><option value='5'>5</option><option value='6'>6</option><option value='7'>7</option><option value='8'>8</option><option value='9'>9</option><option value='10'>10</option><option value='15'>15</option><option value='20'>20</option><option value='25'>25</option><option value='30'>30</option><option value='35'>35</option><option value='40'>40</option></select></td></tr><tr><td class='label'>space:</td><td class='ctrl'><select name='ignorews' onchange='this.form.submit();'><option value='0' selected='selected'>include</option><option value='1'>ignore</option></select></td></tr><tr><td class='label'>mode:</td><td class='ctrl'><select name='dt' onchange='this.form.submit();'><option value='0' selected='selected'>unified</option><option value='1'>ssdiff</option><option value='2'>stat only</option></select></td></tr><tr><td/><td class='ctrl'><noscript><input type='submit' value='reload'/></noscript></td></tr></table></form></div><table summary='commit info' class='commit-info'>
<tr><th>author</th><td>Kan Liang &lt;kan.liang@intel.com&gt;</td><td class='right'>2016-08-16 16:09:50 -0400</td></tr>
<tr><th>committer</th><td>Ingo Molnar &lt;mingo@kernel.org&gt;</td><td class='right'>2016-09-10 11:18:52 +0200</td></tr>
<tr><th>commit</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/?id=cd34cd97b7b4336aa2c623c37daffab264c7c6ce'>cd34cd97b7b4336aa2c623c37daffab264c7c6ce</a> (<a href='/cgit.cgi/linux/net-next.git/patch/?id=cd34cd97b7b4336aa2c623c37daffab264c7c6ce'>patch</a>)</td></tr>
<tr><th>tree</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/tree/?id=cd34cd97b7b4336aa2c623c37daffab264c7c6ce'>15ae623fa3d2a89b98bdea61485ff6d9402380fb</a></td></tr>
<tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/?id=2668c6195685f4b6f281767d10b4f4f2e32c2305'>2668c6195685f4b6f281767d10b4f4f2e32c2305</a> (<a href='/cgit.cgi/linux/net-next.git/diff/?id=cd34cd97b7b4336aa2c623c37daffab264c7c6ce&amp;id2=2668c6195685f4b6f281767d10b4f4f2e32c2305'>diff</a>)</td></tr></table>
<div class='commit-subject'>perf/x86/intel/uncore: Add Skylake server uncore support</div><div class='commit-msg'>This patch implements the uncore monitoring driver for Skylake server.
The uncore subsystem in Skylake server is similar to previous
server. There are some differences in config register encoding and pci
device IDs. Besides, Skylake introduces many new boxes to reflect the
MESH architecture changes.

The control registers for IIO and UPI have been extended to 64 bit. This
patch also introduces event_mask_ext to handle the high 32 bit mask.

The CHA box number could vary for different machines. This patch gets
the CHA box number by counting the CHA register space during
initialization at runtime.

Signed-off-by: Kan Liang &lt;kan.liang@intel.com&gt;
Signed-off-by: Peter Zijlstra (Intel) &lt;peterz@infradead.org&gt;
Cc: Alexander Shishkin &lt;alexander.shishkin@linux.intel.com&gt;
Cc: Arnaldo Carvalho de Melo &lt;acme@redhat.com&gt;
Cc: Jiri Olsa &lt;jolsa@redhat.com&gt;
Cc: Linus Torvalds &lt;torvalds@linux-foundation.org&gt;
Cc: Peter Zijlstra &lt;peterz@infradead.org&gt;
Cc: Stephane Eranian &lt;eranian@google.com&gt;
Cc: Thomas Gleixner &lt;tglx@linutronix.de&gt;
Cc: Vince Weaver &lt;vincent.weaver@maine.edu&gt;
Link: http://lkml.kernel.org/r/1471378190-17276-3-git-send-email-kan.liang@intel.com
Signed-off-by: Ingo Molnar &lt;mingo@kernel.org&gt;
</div><div class='diffstat-header'><a href='/cgit.cgi/linux/net-next.git/diff/?id=cd34cd97b7b4336aa2c623c37daffab264c7c6ce'>Diffstat</a></div><table summary='diffstat' class='diffstat'>