// SPDX-License-Identifier: GPL-2.0
/*
 * Infrastructure to took into function calls and returns.
 * Copyright (c) 2008-2009 Frederic Weisbecker <fweisbec@gmail.com>
 * Mostly borrowed from function tracer which
 * is Copyright (c) Steven Rostedt <srostedt@redhat.com>
 *
 * Highly modified by Steven Rostedt (VMware).
 */
#include <linux/bits.h>
#include <linux/jump_label.h>
#include <linux/suspend.h>
#include <linux/ftrace.h>
#include <linux/static_call.h>
#include <linux/slab.h>

#include <trace/events/sched.h>

#include "ftrace_internal.h"
#include "trace.h"

/*
 * FGRAPH_FRAME_SIZE:	Size in bytes of the meta data on the shadow stack
 * FGRAPH_FRAME_OFFSET:	Size in long words of the meta data frame
 */
#define FGRAPH_FRAME_SIZE	sizeof(struct ftrace_ret_stack)
#define FGRAPH_FRAME_OFFSET	DIV_ROUND_UP(FGRAPH_FRAME_SIZE, sizeof(long))

/*
 * On entry to a function (via function_graph_enter()), a new fgraph frame
 * (ftrace_ret_stack) is pushed onto the stack as well as a word that
 * holds a bitmask and a type (called "bitmap"). The bitmap is defined as:
 *
 * bits:  0 -  9	offset in words from the previous ftrace_ret_stack
 *
 * bits: 10 - 11	Type of storage
 *			  0 - reserved
 *			  1 - bitmap of fgraph_array index
 *			  2 - reserved data
 *
 * For type with "bitmap of fgraph_array index" (FGRAPH_TYPE_BITMAP):
 *  bits: 12 - 27	The bitmap of fgraph_ops fgraph_array index
 *			That is, it's a bitmask of 0-15 (16 bits)
 *			where if a corresponding ops in the fgraph_array[]
 *			expects a callback from the return of the function
 *			it's corresponding bit will be set.
 *
 *
 * The top of the ret_stack (when not empty) will always have a reference
 * word that points to the last fgraph frame that was saved.
 *
 * For reserved data:
 *  bits: 12 - 17	The size in words that is stored
 *  bits: 18 - 23	The index of fgraph_array, which shows who is stored
 *
 * That is, at the end of function_graph_enter, if the first and forth
 * fgraph_ops on the fgraph_array[] (index 0 and 3) needs their retfunc called
 * on the return of the function being traced, and the forth fgraph_ops
 * stored two words of data, this is what will be on the task's shadow
 * ret_stack: (the stack grows upward)
 *
 *  ret_stack[SHADOW_STACK_OFFSET]
 * | SHADOW_STACK_TASK_VARS(ret_stack)[15]      |
 * ...
 * | SHADOW_STACK_TASK_VARS(ret_stack)[0]       |
 *  ret_stack[SHADOW_STACK_MAX_OFFSET]
 * ...
 * |                                            | <- task->curr_ret_stack
 * +--------------------------------------------+
 * | (3 << 12) | (3 << 10) | FGRAPH_FRAME_OFFSET|
 * |         *or put another way*               |
 * | (3 << FGRAPH_DATA_INDEX_SHIFT)| \          | This is for fgraph_ops[3].
 * | ((2 - 1) << FGRAPH_DATA_SHIFT)| \          | The data size is 2 words.
 * | (FGRAPH_TYPE_DATA << FGRAPH_TYPE_SHIFT)| \ |
 * | (offset2:FGRAPH_FRAME_OFFSET+3)            | <- the offset2 is from here
 * +--------------------------------------------+ ( It is 4 words from the ret_stack)
 * |            STORED DATA WORD 2              |
 * |            STORED DATA WORD 1              |
 * +--------------------------------------------+
 * | (9 << 12) | (1 << 10) | FGRAPH_FRAME_OFFSET|
 * |         *or put another way*               |
 * | (BIT(3)|BIT(0)) << FGRAPH_INDEX_SHIFT | \  |
 * | FGRAPH_TYPE_BITMAP << FGRAPH_TYPE_SHIFT| \ |
 * | (offset1:FGRAPH_FRAME_OFFSET)              | <- the offset1 is from here
 * +--------------------------------------------+
 * | struct ftrace_ret_stack                    |
 * |   (stores the saved ret pointer)           | <- the offset points here
 * +--------------------------------------------+
 * |                 (X) | (N)                  | ( N words away from
 * |                                            |   previous ret_stack)
 * ...
 * ret_stack[0]
 *
 * If a backtrace is required, and the real return pointer needs to be
 * fetched, then it looks at the task's curr_ret_stack offset, if it
 * is greater than zero (reserved, or right before popped), it would mask
 * the value by FGRAPH_FRAME_OFFSET_MASK to get the offset of the
 * ftrace_ret_stack structure stored on the shadow stack.
 */

/*
 * The following is for the top word on the stack:
 *
 *   FGRAPH_FRAME_OFFSET (0-9) holds the offset delta to the fgraph frame
 *   FGRAPH_TYPE (10-11) holds the type of word this is.
 *     (RESERVED or BITMAP)
 */
#define FGRAPH_FRAME_OFFSET_BITS	10
#define FGRAPH_FRAME_OFFSET_MASK	GENMASK(FGRAPH_FRAME_OFFSET_BITS - 1, 0)

#define FGRAPH_TYPE_BITS	2
#define FGRAPH_TYPE_MASK	GENMASK(FGRAPH_TYPE_BITS - 1, 0)
#define FGRAPH_TYPE_SHIFT	FGRAPH_FRAME_OFFSET_BITS

enum {
	FGRAPH_TYPE_RESERVED	= 0,
	FGRAPH_TYPE_BITMAP	= 1,
	FGRAPH_TYPE_DATA	= 2,
};

/*
 * For BITMAP type:
 *   FGRAPH_INDEX (12-27) bits holding the gops index wanting return callback called
 */
#define FGRAPH_INDEX_BITS	16
#define FGRAPH_INDEX_MASK	GENMASK(FGRAPH_INDEX_BITS - 1, 0)
#define FGRAPH_INDEX_SHIFT	(FGRAPH_TYPE_SHIFT + FGRAPH_TYPE_BITS)

/*
 * For DATA type:
 *  FGRAPH_DATA (12-17) bits hold the size of data (in words)
 *  FGRAPH_INDEX (18-23) bits hold the index for which gops->idx the data is for
 *
 * Note:
 *  data_size == 0 means 1 word, and 31 (=2^5 - 1) means 32 words.
 */
#define FGRAPH_DATA_BITS	5
#define FGRAPH_DATA_MASK	GENMASK(FGRAPH_DATA_BITS - 1, 0)
#define FGRAPH_DATA_SHIFT	(FGRAPH_TYPE_SHIFT + FGRAPH_TYPE_BITS)
#define FGRAPH_MAX_DATA_SIZE (sizeof(long) * (1 << FGRAPH_DATA_BITS))

#define FGRAPH_DATA_INDEX_BITS	4
#define FGRAPH_DATA_INDEX_MASK	GENMASK(FGRAPH_DATA_INDEX_BITS - 1, 0)
#define FGRAPH_DATA_INDEX_SHIFT	(FGRAPH_DATA_SHIFT + FGRAPH_DATA_BITS)

#define FGRAPH_MAX_INDEX	\
	((FGRAPH_INDEX_SIZE << FGRAPH_DATA_BITS) + FGRAPH_RET_IN