/*
 * 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;
}
52e7e195f55b27cde15d2a8f43342a8b'>xfrm</a>/<a href='/cgit.cgi/linux/net-next.git/commit/net/xfrm/xfrm_user.c?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>xfrm_user.c</a></div><div class='content'><div class='cgit-panel'><b>diff options</b><form method='get'><input type='hidden' name='id' value='1930b60352e7e195f55b27cde15d2a8f43342a8b'/><table><tr><td colspan='2'/></tr><tr><td class='label'>context:</td><td class='ctrl'><select name='context' onchange='this.form.submit();'><option value='1'>1</option><option value='2'>2</option><option value='3' selected='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>David S. Miller &lt;davem@davemloft.net&gt;</td><td class='right'>2017-01-30 15:55:48 -0500</td></tr>
<tr><th>committer</th><td>David S. Miller &lt;davem@davemloft.net&gt;</td><td class='right'>2017-01-30 15:56:40 -0500</td></tr>
<tr><th>commit</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/xfrm/xfrm_user.c?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>1930b60352e7e195f55b27cde15d2a8f43342a8b</a> (<a href='/cgit.cgi/linux/net-next.git/patch/net/xfrm/xfrm_user.c?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>patch</a>)</td></tr>
<tr><th>tree</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/tree/?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>ec3f66cd8d8110bf7b4f61e0446bdea505915db9</a> /<a href='/cgit.cgi/linux/net-next.git/tree/net/xfrm/xfrm_user.c?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>net/xfrm/xfrm_user.c</a></td></tr>
<tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/xfrm/xfrm_user.c?id=4be9993493bc7ee3fdf950a83bc050a3e6cf2a45'>4be9993493bc7ee3fdf950a83bc050a3e6cf2a45</a> (<a href='/cgit.cgi/linux/net-next.git/diff/net/xfrm/xfrm_user.c?id=1930b60352e7e195f55b27cde15d2a8f43342a8b&amp;id2=4be9993493bc7ee3fdf950a83bc050a3e6cf2a45'>diff</a>)</td></tr><tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/xfrm/xfrm_user.c?id=ec960de61503ef349588dccfa3ae02efabcc2762'>ec960de61503ef349588dccfa3ae02efabcc2762</a> (<a href='/cgit.cgi/linux/net-next.git/diff/net/xfrm/xfrm_user.c?id=1930b60352e7e195f55b27cde15d2a8f43342a8b&amp;id2=ec960de61503ef349588dccfa3ae02efabcc2762'>diff</a>)</td></tr></table>
<div class='commit-subject'>Merge branch 'dsa-port-mirroring'</div><div class='commit-msg'>Florian Fainelli says:

====================
net: dsa: Port mirroring support

This patch series adds support for port mirroring in the two
Broadcom switch drivers. The major part of the functional are actually with
the plumbing between tc and the drivers.

Changes in v5:

- Added Jiri's Reviewed-by tag to first patch
- rebase against latest net-next/master after bcm_sf2 CFP series

Changes in v4:

- rebased against latest net-next/master after Vivien's changes

Changes in v3:

- removed multiline comments from added structures
- simplify error handling in dsa_slave_add_cls_matchall

Changes in v2:

- fixed filter removal logic to disable the ingress or egress mirroring
  when there are no longer ports being monitored in ingress or egress

- removed a stray list_head in dsa_port structure that is not used

Tested using the two iproute2 examples:

      tc qdisc  add dev eth1 handle ffff: ingress
      tc filter add dev eth1 parent ffff:           \
               matchall skip_sw                      \
               action mirred egress mirror           \
               dev eth2
      tc qdisc add dev eth1 handle 1: root prio
      tc filter add dev eth1 parent 1:               \
               matchall skip_sw                       \
               action mirred egress mirror            \
               dev eth2
====================

Signed-off-by: David S. Miller &lt;davem@davemloft.net&gt;
</div><div class='diffstat-header'><a href='/cgit.cgi/linux/net-next.git/diff/?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>Diffstat</a> (limited to 'net/xfrm/xfrm_user.c')</div><table summary='diffstat' class='diffstat'>