As it collected basic block and variable information in each scope, it
now can build a state table to find matching variable at the location.

The struct type_state is to keep the type info saved in each register
and stack slot.  The update_var_state() updates the table when it finds
variables in the current address.  It expects die_collect_vars() filled
a list of variables with type info and starting address.

Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/annotate-data.c | 173 ++++++++++++++++++++++++++++++++
 tools/perf/util/dwarf-aux.c     |   4 +
 2 files changed, 177 insertions(+)

diff --git a/tools/perf/util/annotate-data.c b/tools/perf/util/annotate-data.c
index f482ccfdaa91..8eaa06f1cee5 100644
--- a/tools/perf/util/annotate-data.c
+++ b/tools/perf/util/annotate-data.c
@@ -46,6 +46,62 @@ static void pr_debug_type_name(Dwarf_Die *die)
 	free(str);
 }
 
+/* Type information in a register, valid when ok is true */
+struct type_state_reg {
+	Dwarf_Die type;
+	bool ok;
+};
+
+/* Type information in a stack location, dynamically allocated */
+struct type_state_stack {
+	struct list_head list;
+	Dwarf_Die type;
+	int offset;
+	int size;
+	bool compound;
+};
+
+/* FIXME: This should be arch-dependent */
+#define TYPE_STATE_MAX_REGS  16
+
+/*
+ * State table to maintain type info in each register and stack location.
+ * It'll be updated when new variable is allocated or type info is moved
+ * to a new location (register or stack).  As it'd be used with the
+ * shortest path of basic blocks, it only maintains a single table.
+ */
+struct type_state {
+	struct type_state_reg regs[TYPE_STATE_MAX_REGS];
+	struct list_head stack_vars;
+};
+
+static bool has_reg_type(struct type_state *state, int reg)
+{
+	return (unsigned)reg < ARRAY_SIZE(state->regs);
+}
+
+/* These declarations will be remove once they are changed to static */
+void init_type_state(struct type_state *state, struct arch *arch __maybe_unused);
+void exit_type_state(struct type_state *state);
+void update_var_state(struct type_state *state, struct data_loc_info *dloc,
+		      u64 addr, u64 insn_offset, struct die_var_type *var_types);
+
+void init_type_state(struct type_state *state, struct arch *arch __maybe_unused)
+{
+	memset(state, 0, sizeof(*state));
+	INIT_LIST_HEAD(&state->stack_vars);
+}
+
+void exit_type_state(struct type_state *state)
+{
+	struct type_state_stack *stack, *tmp;
+
+	list_for_each_entry_safe(stack, tmp, &state->stack_vars, list) {
+		list_del(&stack->list);
+		free(stack);
+	}
+}
+
 /*
  * Compare type name and size to maintain them in a tree.
  * I'm not sure if DWARF would have information of a single type in many
@@ -262,6 +318,123 @@ static int check_variable(Dwarf_Die *var_die, Dwarf_Die *type_die, int offset,
 	return 0;
 }
 
+static struct type_state_stack *find_stack_state(struct type_state *state,
+						 int offset)
+{
+	struct type_state_stack *stack;
+
+	list_for_each_entry(stack, &state->stack_vars, list) {
+		if (offset == stack->offset)
+			return stack;
+
+		if (stack->compound && stack->offset < offset &&
+		    offset < stack->offset + stack->size)
+			return stack;
+	}
+	return NULL;
+}
+
+static void set_stack_state(struct type_state_stack *stack, int offset,
+			    Dwarf_Die *type_die)
+{
+	int tag;
+	Dwarf_Word size;
+
+	if (dwarf_aggregate_size(type_die, &size) < 0)
+		size = 0;
+
+	tag = dwarf_tag(type_die);
+
+	stack->type = *type_die;
+	stack->size = size;
+	stack->offset = offset;
+
+	switch (tag) {
+	case DW_TAG_structure_type:
+	case DW_TAG_union_type:
+		stack->compound = true;
+		break;
+	default:
+		stack->compound = false;
+		break;
+	}
+}
+
+static struct type_state_stack *findnew_stack_state(struct type_state *state,
+						    int offset, Dwarf_Die *type_die)
+{
+	struct type_state_stack *stack = find_stack_state(state, offset);
+
+	if (stack) {
+		set_stack_state(stack, offset, type_die);
+		return stack;
+	}
+
+	stack = malloc(sizeof(*stack));
+	if (stack) {
+		set_stack_state(stack, offset, type_die);
+		list_add(&stack->list, &state->stack_vars);
+	}
+	return stack;
+}
+
+/**
+ * update_var_state - Update type state using given variables
+ * @state: type state table
+ * @dloc: data location info
+ * @addr: instruction address to match with variable
+ * @insn_offset: instruction offset (for debug)
+ * @var_types: list of variables with type info
+ *
+ * This function fills the @state table using @var_types info.  Each variable
+ * is used only at the given location and updates an entry in the table.
+ */
+void update_var_state(struct type_state *state, struct data_loc_info *dloc,
+		      u64 addr, u64 insn_offset, struct die_var_type *var_types)
+{
+	Dwarf_Die mem_die;
+	struct die_var_type *var;
+	int fbreg = dloc->fbreg;
+	int fb_offset = 0;
+
+	if (dloc->fb_cfa) {
+		if (die_get_cfa(dloc->di->dbg, addr, &fbreg, &fb_offset) < 0)
+			fbreg = -1;
+	}
+
+	for (var = var_types; var != NULL; var = var->next) {
+		if (var->addr != addr)
+			continue;
+		/* Get the type DIE using the offset */
+		if (!dwarf_offdie(dloc->di->dbg, var->die_off, &mem_die))
+			continue;
+
+		if (var->reg == DWARF_REG_FB) {
+			findnew_stack_state(state, var->offset, &mem_die);
+
+			pr_debug_dtp("var [%"PRIx64"] -%#x(stack) type=",
+				     insn_offset, -var->offset);
+			pr_debug_type_name(&mem_die);
+		} else if (var->reg == fbreg) {
+			findnew_stack_state(state, var->offset - fb_offset, &mem_die);
+
+			pr_debug_dtp("var [%"PRIx64"] -%#x(stack) type=",
+				     insn_offset, -var->offset + fb_offset);
+			pr_debug_type_name(&mem_die);
+		} else if (has_reg_type(state, var->reg) && var->offset == 0) {
+			struct type_state_reg *reg;
+
+			reg = &state->regs[var->reg];
+			reg->type = mem_die;
+			reg->ok = true;
+
+			pr_debug_dtp("var [%"PRIx64"] reg%d type=",
+				     insn_offset, var->reg);
+			pr_debug_type_name(&mem_die);
+		}
+	}
+}
+
 /* The result will be saved in @type_die */
 static int find_data_type_die(struct data_loc_info *dloc, Dwarf_Die *type_die)
 {
diff --git a/tools/perf/util/dwarf-aux.c b/tools/perf/util/dwarf-aux.c
index 9080119a258c..41dbbb25b256 100644
--- a/tools/perf/util/dwarf-aux.c
+++ b/tools/perf/util/dwarf-aux.c
@@ -9,6 +9,7 @@
 #include <stdlib.h>
 #include "debug.h"
 #include "dwarf-aux.h"
+#include "dwarf-regs.h"
 #include "strbuf.h"
 #include "string2.h"
 
@@ -1190,6 +1191,8 @@ static int reg_from_dwarf_op(Dwarf_Op *op)
 	case DW_OP_regx:
 	case DW_OP_bregx:
 		return op->number;
+	case DW_OP_fbreg:
+		return DWARF_REG_FB;
 	default:
 		break;
 	}
@@ -1203,6 +1206,7 @@ static int offset_from_dwarf_op(Dwarf_Op *op)
 	case DW_OP_regx:
 		return 0;
 	case DW_OP_breg0 ... DW_OP_breg31:
+	case DW_OP_fbreg:
 		return op->number;
 	case DW_OP_bregx:
 		return op->number2;
-- 
2.44.0.291.gc1ea87d7ee-goog

On Mon, Mar 18, 2024 at 10:51:01PM -0700, Namhyung Kim wrote:
> As it collected basic block and variable information in each scope, it
> now can build a state table to find matching variable at the location.
> 
> The struct type_state is to keep the type info saved in each register
> and stack slot.  The update_var_state() updates the table when it finds
> variables in the current address.  It expects die_collect_vars() filled
> a list of variables with type info and starting address.
> 
> Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> ---
>  tools/perf/util/annotate-data.c | 173 ++++++++++++++++++++++++++++++++
>  tools/perf/util/dwarf-aux.c     |   4 +
>  2 files changed, 177 insertions(+)
> 
> diff --git a/tools/perf/util/annotate-data.c b/tools/perf/util/annotate-data.c
> index f482ccfdaa91..8eaa06f1cee5 100644
> --- a/tools/perf/util/annotate-data.c
> +++ b/tools/perf/util/annotate-data.c
> @@ -46,6 +46,62 @@ static void pr_debug_type_name(Dwarf_Die *die)
>  	free(str);
>  }
>  
> +/* Type information in a register, valid when ok is true */
> +struct type_state_reg {
> +	Dwarf_Die type;
> +	bool ok;
> +};
> +
> +/* Type information in a stack location, dynamically allocated */
> +struct type_state_stack {
> +	struct list_head list;
> +	Dwarf_Die type;
> +	int offset;
> +	int size;
> +	bool compound;
> +};
> +
> +/* FIXME: This should be arch-dependent */
> +#define TYPE_STATE_MAX_REGS  16
> +
> +/*
> + * State table to maintain type info in each register and stack location.
> + * It'll be updated when new variable is allocated or type info is moved
> + * to a new location (register or stack).  As it'd be used with the
> + * shortest path of basic blocks, it only maintains a single table.
> + */
> +struct type_state {
> +	struct type_state_reg regs[TYPE_STATE_MAX_REGS];
> +	struct list_head stack_vars;
> +};
> +
> +static bool has_reg_type(struct type_state *state, int reg)
> +{
> +	return (unsigned)reg < ARRAY_SIZE(state->regs);
> +}
> +
> +/* These declarations will be remove once they are changed to static */
> +void init_type_state(struct type_state *state, struct arch *arch __maybe_unused);
> +void exit_type_state(struct type_state *state);
> +void update_var_state(struct type_state *state, struct data_loc_info *dloc,
> +		      u64 addr, u64 insn_offset, struct die_var_type *var_types);
> +
> +void init_type_state(struct type_state *state, struct arch *arch __maybe_unused)
> +{
> +	memset(state, 0, sizeof(*state));
> +	INIT_LIST_HEAD(&state->stack_vars);
> +}
> +
> +void exit_type_state(struct type_state *state)
> +{
> +	struct type_state_stack *stack, *tmp;
> +
> +	list_for_each_entry_safe(stack, tmp, &state->stack_vars, list) {
> +		list_del(&stack->list);

list_del_init()?

> +		free(stack);
> +	}
> +}
> +
>  /*
>   * Compare type name and size to maintain them in a tree.
>   * I'm not sure if DWARF would have information of a single type in many
> @@ -262,6 +318,123 @@ static int check_variable(Dwarf_Die *var_die, Dwarf_Die *type_die, int offset,
>  	return 0;
>  }
>  
> +static struct type_state_stack *find_stack_state(struct type_state *state,
> +						 int offset)
> +{
> +	struct type_state_stack *stack;
> +
> +	list_for_each_entry(stack, &state->stack_vars, list) {
> +		if (offset == stack->offset)
> +			return stack;
> +
> +		if (stack->compound && stack->offset < offset &&
> +		    offset < stack->offset + stack->size)
> +			return stack;
> +	}
> +	return NULL;
> +}
> +
> +static void set_stack_state(struct type_state_stack *stack, int offset,
> +			    Dwarf_Die *type_die)
> +{
> +	int tag;
> +	Dwarf_Word size;
> +
> +	if (dwarf_aggregate_size(type_die, &size) < 0)
> +		size = 0;
> +
> +	tag = dwarf_tag(type_die);
> +
> +	stack->type = *type_die;
> +	stack->size = size;
> +	stack->offset = offset;
> +
> +	switch (tag) {
> +	case DW_TAG_structure_type:
> +	case DW_TAG_union_type:
> +		stack->compound = true;
> +		break;
> +	default:
> +		stack->compound = false;
> +		break;
> +	}
> +}
> +
> +static struct type_state_stack *findnew_stack_state(struct type_state *state,
> +						    int offset, Dwarf_Die *type_die)
> +{
> +	struct type_state_stack *stack = find_stack_state(state, offset);
> +
> +	if (stack) {
> +		set_stack_state(stack, offset, type_die);
> +		return stack;
> +	}
> +
> +	stack = malloc(sizeof(*stack));
> +	if (stack) {
> +		set_stack_state(stack, offset, type_die);
> +		list_add(&stack->list, &state->stack_vars);
> +	}
> +	return stack;
> +}
> +
> +/**
> + * update_var_state - Update type state using given variables
> + * @state: type state table
> + * @dloc: data location info
> + * @addr: instruction address to match with variable
> + * @insn_offset: instruction offset (for debug)
> + * @var_types: list of variables with type info
> + *
> + * This function fills the @state table using @var_types info.  Each variable
> + * is used only at the given location and updates an entry in the table.
> + */
> +void update_var_state(struct type_state *state, struct data_loc_info *dloc,
> +		      u64 addr, u64 insn_offset, struct die_var_type *var_types)
> +{
> +	Dwarf_Die mem_die;
> +	struct die_var_type *var;
> +	int fbreg = dloc->fbreg;
> +	int fb_offset = 0;
> +
> +	if (dloc->fb_cfa) {
> +		if (die_get_cfa(dloc->di->dbg, addr, &fbreg, &fb_offset) < 0)
> +			fbreg = -1;
> +	}
> +
> +	for (var = var_types; var != NULL; var = var->next) {
> +		if (var->addr != addr)
> +			continue;
> +		/* Get the type DIE using the offset */
> +		if (!dwarf_offdie(dloc->di->dbg, var->die_off, &mem_die))
> +			continue;
> +
> +		if (var->reg == DWARF_REG_FB) {
> +			findnew_stack_state(state, var->offset, &mem_die);
> +
> +			pr_debug_dtp("var [%"PRIx64"] -%#x(stack) type=",
> +				     insn_offset, -var->offset);
> +			pr_debug_type_name(&mem_die);
> +		} else if (var->reg == fbreg) {
> +			findnew_stack_state(state, var->offset - fb_offset, &mem_die);
> +
> +			pr_debug_dtp("var [%"PRIx64"] -%#x(stack) type=",
> +				     insn_offset, -var->offset + fb_offset);
> +			pr_debug_type_name(&mem_die);
> +		} else if (has_reg_type(state, var->reg) && var->offset == 0) {
> +			struct type_state_reg *reg;
> +
> +			reg = &state->regs[var->reg];
> +			reg->type = mem_die;
> +			reg->ok = true;
> +
> +			pr_debug_dtp("var [%"PRIx64"] reg%d type=",
> +				     insn_offset, var->reg);
> +			pr_debug_type_name(&mem_die);
> +		}
> +	}
> +}
> +
>  /* The result will be saved in @type_die */
>  static int find_data_type_die(struct data_loc_info *dloc, Dwarf_Die *type_die)
>  {
> diff --git a/tools/perf/util/dwarf-aux.c b/tools/perf/util/dwarf-aux.c
> index 9080119a258c..41dbbb25b256 100644
> --- a/tools/perf/util/dwarf-aux.c
> +++ b/tools/perf/util/dwarf-aux.c
> @@ -9,6 +9,7 @@
>  #include <stdlib.h>
>  #include "debug.h"
>  #include "dwarf-aux.h"
> +#include "dwarf-regs.h"
>  #include "strbuf.h"
>  #include "string2.h"
>  
> @@ -1190,6 +1191,8 @@ static int reg_from_dwarf_op(Dwarf_Op *op)
>  	case DW_OP_regx:
>  	case DW_OP_bregx:
>  		return op->number;
> +	case DW_OP_fbreg:
> +		return DWARF_REG_FB;
>  	default:
>  		break;
>  	}
> @@ -1203,6 +1206,7 @@ static int offset_from_dwarf_op(Dwarf_Op *op)
>  	case DW_OP_regx:
>  		return 0;
>  	case DW_OP_breg0 ... DW_OP_breg31:
> +	case DW_OP_fbreg:
>  		return op->number;
>  	case DW_OP_bregx:
>  		return op->number2;
> -- 
> 2.44.0.291.gc1ea87d7ee-goog

On Tue, Mar 19, 2024 at 7:07 AM Arnaldo Carvalho de Melo
<acme@kernel.org> wrote:
>
> On Mon, Mar 18, 2024 at 10:51:01PM -0700, Namhyung Kim wrote:
> > As it collected basic block and variable information in each scope, it
> > now can build a state table to find matching variable at the location.
> >
> > The struct type_state is to keep the type info saved in each register
> > and stack slot.  The update_var_state() updates the table when it finds
> > variables in the current address.  It expects die_collect_vars() filled
> > a list of variables with type info and starting address.
> >
> > Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> > ---
> >  tools/perf/util/annotate-data.c | 173 ++++++++++++++++++++++++++++++++
> >  tools/perf/util/dwarf-aux.c     |   4 +
> >  2 files changed, 177 insertions(+)
> >
> > diff --git a/tools/perf/util/annotate-data.c b/tools/perf/util/annotate-data.c
> > index f482ccfdaa91..8eaa06f1cee5 100644
> > --- a/tools/perf/util/annotate-data.c
> > +++ b/tools/perf/util/annotate-data.c
> > @@ -46,6 +46,62 @@ static void pr_debug_type_name(Dwarf_Die *die)
> >       free(str);
> >  }
> >
> > +/* Type information in a register, valid when ok is true */
> > +struct type_state_reg {
> > +     Dwarf_Die type;
> > +     bool ok;
> > +};
> > +
> > +/* Type information in a stack location, dynamically allocated */
> > +struct type_state_stack {
> > +     struct list_head list;
> > +     Dwarf_Die type;
> > +     int offset;
> > +     int size;
> > +     bool compound;
> > +};
> > +
> > +/* FIXME: This should be arch-dependent */
> > +#define TYPE_STATE_MAX_REGS  16
> > +
> > +/*
> > + * State table to maintain type info in each register and stack location.
> > + * It'll be updated when new variable is allocated or type info is moved
> > + * to a new location (register or stack).  As it'd be used with the
> > + * shortest path of basic blocks, it only maintains a single table.
> > + */
> > +struct type_state {
> > +     struct type_state_reg regs[TYPE_STATE_MAX_REGS];
> > +     struct list_head stack_vars;
> > +};
> > +
> > +static bool has_reg_type(struct type_state *state, int reg)
> > +{
> > +     return (unsigned)reg < ARRAY_SIZE(state->regs);
> > +}
> > +
> > +/* These declarations will be remove once they are changed to static */
> > +void init_type_state(struct type_state *state, struct arch *arch __maybe_unused);
> > +void exit_type_state(struct type_state *state);
> > +void update_var_state(struct type_state *state, struct data_loc_info *dloc,
> > +                   u64 addr, u64 insn_offset, struct die_var_type *var_types);
> > +
> > +void init_type_state(struct type_state *state, struct arch *arch __maybe_unused)
> > +{
> > +     memset(state, 0, sizeof(*state));
> > +     INIT_LIST_HEAD(&state->stack_vars);
> > +}
> > +
> > +void exit_type_state(struct type_state *state)
> > +{
> > +     struct type_state_stack *stack, *tmp;
> > +
> > +     list_for_each_entry_safe(stack, tmp, &state->stack_vars, list) {
> > +             list_del(&stack->list);
>
> list_del_init()?

Maybe.. but I'm not sure how much value it'd have as we free it right after.

Thanks,
Namhyung

>
> > +             free(stack);
> > +     }
> > +}
> > +

On Tue, Mar 19, 2024 at 10:44:31AM -0700, Namhyung Kim wrote:
> On Tue, Mar 19, 2024 at 7:07 AM Arnaldo Carvalho de Melo <acme@kernel.org> wrote:
> > > +void exit_type_state(struct type_state *state)
> > > +{
> > > +     struct type_state_stack *stack, *tmp;
> > > +
> > > +     list_for_each_entry_safe(stack, tmp, &state->stack_vars, list) {
> > > +             list_del(&stack->list);

> > list_del_init()?
 
> Maybe.. but I'm not sure how much value it'd have as we free it right after.

Usually the value is in catching use after free more quickly, i.e.
someone may have a pointer to a freed list and then it would be able to
traverse the list of freed elements.

- Arnaldo

On Tue, Mar 19, 2024 at 11:12 AM Arnaldo Carvalho de Melo
<acme@kernel.org> wrote:
>
> On Tue, Mar 19, 2024 at 10:44:31AM -0700, Namhyung Kim wrote:
> > On Tue, Mar 19, 2024 at 7:07 AM Arnaldo Carvalho de Melo <acme@kernel.org> wrote:
> > > > +void exit_type_state(struct type_state *state)
> > > > +{
> > > > +     struct type_state_stack *stack, *tmp;
> > > > +
> > > > +     list_for_each_entry_safe(stack, tmp, &state->stack_vars, list) {
> > > > +             list_del(&stack->list);
>
> > > list_del_init()?
>
> > Maybe.. but I'm not sure how much value it'd have as we free it right after.
>
> Usually the value is in catching use after free more quickly, i.e.
> someone may have a pointer to a freed list and then it would be able to
> traverse the list of freed elements.

Ok, then. :)