cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

call-path.c (2513B)

      1// SPDX-License-Identifier: GPL-2.0-only
      2/*
      3 * call-path.h: Manipulate a tree data structure containing function call paths
      4 * Copyright (c) 2014, Intel Corporation.
      5 */
      6
      7#include <linux/rbtree.h>
      8#include <linux/list.h>
      9#include <linux/zalloc.h>
     10#include <stdlib.h>
     11
     12#include "call-path.h"
     13
     14static void call_path__init(struct call_path *cp, struct call_path *parent,
     15			    struct symbol *sym, u64 ip, bool in_kernel)
     16{
     17	cp->parent = parent;
     18	cp->sym = sym;
     19	cp->ip = sym ? 0 : ip;
     20	cp->db_id = 0;
     21	cp->in_kernel = in_kernel;
     22	RB_CLEAR_NODE(&cp->rb_node);
     23	cp->children = RB_ROOT;
     24}
     25
     26struct call_path_root *call_path_root__new(void)
     27{
     28	struct call_path_root *cpr;
     29
     30	cpr = zalloc(sizeof(struct call_path_root));
     31	if (!cpr)
     32		return NULL;
     33	call_path__init(&cpr->call_path, NULL, NULL, 0, false);
     34	INIT_LIST_HEAD(&cpr->blocks);
     35	return cpr;
     36}
     37
     38void call_path_root__free(struct call_path_root *cpr)
     39{
     40	struct call_path_block *pos, *n;
     41
     42	list_for_each_entry_safe(pos, n, &cpr->blocks, node) {
     43		list_del_init(&pos->node);
     44		free(pos);
     45	}
     46	free(cpr);
     47}
     48
     49static struct call_path *call_path__new(struct call_path_root *cpr,
     50					struct call_path *parent,
     51					struct symbol *sym, u64 ip,
     52					bool in_kernel)
     53{
     54	struct call_path_block *cpb;
     55	struct call_path *cp;
     56	size_t n;
     57
     58	if (cpr->next < cpr->sz) {
     59		cpb = list_last_entry(&cpr->blocks, struct call_path_block,
     60				      node);
     61	} else {
     62		cpb = zalloc(sizeof(struct call_path_block));
     63		if (!cpb)
     64			return NULL;
     65		list_add_tail(&cpb->node, &cpr->blocks);
     66		cpr->sz += CALL_PATH_BLOCK_SIZE;
     67	}
     68
     69	n = cpr->next++ & CALL_PATH_BLOCK_MASK;
     70	cp = &cpb->cp[n];
     71
     72	call_path__init(cp, parent, sym, ip, in_kernel);
     73
     74	return cp;
     75}
     76
     77struct call_path *call_path__findnew(struct call_path_root *cpr,
     78				     struct call_path *parent,
     79				     struct symbol *sym, u64 ip, u64 ks)
     80{
     81	struct rb_node **p;
     82	struct rb_node *node_parent = NULL;
     83	struct call_path *cp;
     84	bool in_kernel = ip >= ks;
     85
     86	if (sym)
     87		ip = 0;
     88
     89	if (!parent)
     90		return call_path__new(cpr, parent, sym, ip, in_kernel);
     91
     92	p = &parent->children.rb_node;
     93	while (*p != NULL) {
     94		node_parent = *p;
     95		cp = rb_entry(node_parent, struct call_path, rb_node);
     96
     97		if (cp->sym == sym && cp->ip == ip)
     98			return cp;
     99
    100		if (sym < cp->sym || (sym == cp->sym && ip < cp->ip))
    101			p = &(*p)->rb_left;
    102		else
    103			p = &(*p)->rb_right;
    104	}
    105
    106	cp = call_path__new(cpr, parent, sym, ip, in_kernel);
    107	if (!cp)
    108		return NULL;
    109
    110	rb_link_node(&cp->rb_node, node_parent, p);
    111	rb_insert_color(&cp->rb_node, &parent->children);
    112
    113	return cp;
    114}