/*
 * 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;
}
4d4e2db4fbc03d5d2203abafc6e188528&amp;showmsg=1'>include</a>/<a href='/cgit.cgi/linux/net-next.git/log/include/net?id=038b9404d4e2db4fbc03d5d2203abafc6e188528&amp;showmsg=1'>net</a>/<a href='/cgit.cgi/linux/net-next.git/log/include/net/sctp?id=038b9404d4e2db4fbc03d5d2203abafc6e188528&amp;showmsg=1'>sctp</a>/<a href='/cgit.cgi/linux/net-next.git/log/include/net/sctp/sctp.h?id=038b9404d4e2db4fbc03d5d2203abafc6e188528&amp;showmsg=1'>sctp.h</a></div><div class='content'><table class='list nowrap'><tr class='nohover'><th class='left'>Age</th><th class='left'>Commit message (<a href='/cgit.cgi/linux/net-next.git/log/include/net/sctp/sctp.h?id=038b9404d4e2db4fbc03d5d2203abafc6e188528'>Collapse</a>)</th><th class='left'>Author</th><th class='left'>Files</th><th class='left'>Lines</th></tr>
<tr class='logheader'><td><span title='2017-02-09 16:57:38 -0500'>2017-02-09</span></td><td class='logsubject'><a href='/cgit.cgi/linux/net-next.git/commit/include/net/sctp/sctp.h?id=242bd2d519d7194633e309286ba7ba29a1ad63e8'>sctp: implement sender-side procedures for Add Incoming/Outgoing Streams ↵</a></td><td>Xin Long</td><td>1</td><td><span class='deletions'>-0</span>/<span class='insertions'>+2</span></td></tr>
<tr class='nohover-highlight'><td/><td colspan='5' class='logmsg'>
Request Parameter

This patch is to implement Sender-Side Procedures for the Add
Outgoing and Incoming Streams Request Parameter described in
rfc6525 section 5.1.5-5.1.6.

It is also to add sockopt SCTP_ADD_STREAMS in rfc6525 section
6.3.4 for users.

Signed-off-by: Xin Long &lt;lucien.xin@gmail.com&gt;
Acked-by: Marcelo Ricardo Leitner &lt;marcelo.leitner@gmail.com&gt;
Signed-off-by: David S. Miller &lt;davem@davemloft.net&gt;


</td></tr>
<tr class='logheader'><td><span title='2017-02-09 16:57:38 -0500'>2017-02-09</span></td><td class='logsubject'><a href='/cgit.cgi/linux/net-next.git/commit/include/net/sctp/sctp.h?id=a92ce1a42dde1caaee4afae67531e3e7acecf6e4'>sctp: implement sender-side procedures for SSN/TSN Reset Request Parameter</a></td><td>Xin Long</td><td>1</td><td><span class='deletions'>-0</span>/<span class='insertions'>+1</span></td></tr>
<tr class='nohover-highlight'><td/><td colspan='5' class='logmsg'>
This patch is to implement Sender-Side Procedures for the SSN/TSN
Reset Request Parameter descibed in rfc6525 section 5.1.4.

It is also to add sockopt SCTP_RESET_ASSOC in rfc6525 section 6.3.3
for users.

Signed-off-by: Xin Long &lt;lucien.xin@gmail.com&gt;
Acked-by: Marcelo Ricardo Leitner &lt;marcelo.leitner@gmail.com&gt;
Signed-off-by: David S. Miller &lt;davem@davemloft.net&gt;


</td></tr>
<tr class='logheader'><td><span title='2017-02-07 13:07:46 -0500'>2017-02-07</span></td><td class='logsubject'><a href='/cgit.cgi/linux/net-next.git/commit/include/net/sctp/sctp.h?id=c86a773c78025f5b825bacd7b846f4fa60dc0317'>sctp: add dst_pending_confirm flag</a></td><td>Julian Anastasov</td><td>1</td><td><span class='deletions'>-4</span>/<span class='insertions'>+2</span></td></tr>
<tr class='nohover-highlight'><td/><td colspan='5' class='logmsg'>
Add new transport flag to allow sockets to confirm neighbour.
When same struct dst_entry can be used for many different
neighbours we can not use it for pending confirmations.
The flag is propagated from transport to every packet.
It is reset when cached dst is reset.

Reported-by: YueHaibing &lt;yuehaibing@huawei.com&gt;
Fixes: 5110effee8fd ("net: Do delayed neigh confirmation.")
Fixes: f2bb4bedf35d ("ipv4: Cache output routes in fib_info nexthops.")
Signed-off-by: Julian Anastasov &lt;ja@ssi.bg&gt;
Acked-by: Eric Dumazet &lt;edumazet@google.com&gt;
Acked-by: Neil Horman &lt;nhorman@tuxdriver.com&gt;
Signed-off-by: David S. Miller &lt;davem@davemloft.net&gt;


</td></tr>