[igt-dev] [PATCH i-g-t v2] tools: Add an intel_dbuf_,map tool
Stanislav Lisovskiy
stanislav.lisovskiy at intel.com
Mon Dec 2 17:29:44 UTC 2019
As in modern platforms more Display buffer
slices/pipes are coming, which have different
pipe affinities and other constraints, so BSpec
contains their connection in form of a Graph.
So we can generate optimal DBuf assignment,
from the graph which we have in BSpec, to avoid
manual calculations prone to human error and
copy-pasting. The generated table is in C form
and can be used in i915 driver rightaway and also
for verification.
v2: Removed unused i, j, made some functions static,
to make CI checkers a bit happier. Also had to
change IGT_LIST to IGT_LIST_HEAD and other stuff,
as functions seem to be renamed in latest master.
Signed-off-by: Stanislav Lisovskiy <stanislav.lisovskiy at intel.com>
Cc: Ville Syrjälä <ville.syrjala at linux.intel.com>
---
tools/intel_dbuf_map.c | 706 +++++++++++++++++++++++++++++++++++++++++
tools/meson.build | 1 +
2 files changed, 707 insertions(+)
create mode 100644 tools/intel_dbuf_map.c
diff --git a/tools/intel_dbuf_map.c b/tools/intel_dbuf_map.c
new file mode 100644
index 00000000..d34ca78a
--- /dev/null
+++ b/tools/intel_dbuf_map.c
@@ -0,0 +1,706 @@
+/*
+ * Copyright © 2019 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Authors:
+ * Stanislav Lisovskiy <stanislav.lisovskiy at intel.com>
+ *
+ */
+
+#include <stdlib.h>
+#include "igt.h"
+#include "igt_list.h"
+
+enum NodeType {
+ DBUF_SLICE,
+ PIPE
+};
+
+const char *node_type_to_str[] = { "DBUF_SLICE", "PIPE" };
+
+#define MAX_CONNECTIONS 10
+#define MAX_NODES 10
+#define MAX_EDGES (MAX_NODES * 2)
+
+struct GraphEdge;
+
+/*
+ * Graph node, which can be DBuf or Pipe
+ */
+struct GraphNode {
+ int id;
+ enum NodeType type;
+ unsigned int use_count;
+ int visited;
+ struct GraphEdge *connections[MAX_CONNECTIONS];
+ int num_connections;
+};
+
+static struct GraphNode *all_nodes[MAX_NODES];
+static struct GraphEdge *all_edges[MAX_EDGES];
+static int num_nodes;
+static int num_edges;
+
+/*
+ * Graph edge, which connects Graph nodes
+ * and has a weight property.
+ */
+struct GraphEdge {
+ struct igt_list_head elem;
+ unsigned int weight;
+ struct GraphNode *node;
+};
+
+static struct GraphNode *create_graph_node(enum NodeType type, int id)
+{
+ struct GraphNode *node = 0;
+
+ if (num_nodes >= MAX_NODES) {
+ igt_info("Too much nodes %d", num_nodes);
+ return NULL;
+ }
+
+ node = malloc(sizeof(struct GraphNode));
+ node->type = type;
+ node->id = id;
+ node->use_count = 0;
+ node->visited = 0;
+ memset(node->connections, 0,
+ MAX_CONNECTIONS * sizeof(struct GraphEdge *));
+ node->num_connections = 0;
+
+ all_nodes[num_nodes] = node;
+ num_nodes++;
+
+ return node;
+}
+
+static struct GraphEdge *create_graph_edge(int weight, struct GraphNode *node)
+{
+ struct GraphEdge *edge = 0;
+
+ if (num_edges >= MAX_EDGES) {
+ igt_info("Too much edges %d", num_edges);
+ return NULL;
+ }
+
+ edge = malloc(sizeof(struct GraphEdge));
+
+ edge->elem.prev = &edge->elem;
+ edge->elem.next = &edge->elem;
+ edge->node = node;
+ edge->weight = weight;
+
+ all_edges[num_edges] = edge;
+ num_edges++;
+
+ return edge;
+}
+
+static void connect_nodes(struct GraphNode *node1, struct GraphNode *node2, int weight)
+{
+ struct GraphEdge *edge1;
+ struct GraphEdge *edge2;
+
+ if (node1->num_connections >= MAX_CONNECTIONS) {
+ igt_info("Node %d has too much connections\n", node1->id);
+ return;
+ }
+
+ if (node2->num_connections >= MAX_CONNECTIONS) {
+ igt_info("Node %d has too much connections\n", node2->id);
+ return;
+ }
+
+ edge1 = create_graph_edge(weight, node1);
+ edge2 = create_graph_edge(weight, node2);
+
+ node1->connections[node1->num_connections] = edge2;
+ node1->num_connections++;
+ node2->connections[node2->num_connections] = edge1;
+ node2->num_connections++;
+}
+
+static void reset_node(struct GraphNode *node)
+{
+ node->use_count = 0;
+ node->visited = 0;
+ memset(node->connections, 0,
+ MAX_CONNECTIONS * sizeof(struct GraphEdge *));
+ node->num_connections = 0;
+}
+
+static void destroy_node(struct GraphNode *node)
+{
+ free(node);
+}
+
+static void destroy_edge(struct GraphEdge *edge)
+{
+ free(edge);
+}
+
+static void destroy_all_edges(void)
+{
+ int i;
+
+ for (i = 0; i < num_edges; i++) {
+ destroy_edge(all_edges[i]);
+ }
+ num_edges = 0;
+}
+
+static void destroy_all_nodes(void)
+{
+ int i;
+
+ for (i = 0; i < num_nodes; i++) {
+ destroy_node(all_nodes[i]);
+ }
+ num_nodes = 0;
+}
+
+static void reset_all_nodes(void)
+{
+ int i;
+
+ destroy_all_edges();
+
+ for (i = 0; i < num_nodes; i++) {
+ reset_node(all_nodes[i]);
+ }
+}
+
+/*
+ * Traverse and try to print graph in a
+ * somewhat graphical form.
+ */
+static void traverse_graph(struct GraphNode *start_node,
+ int depth)
+{
+ int i, space;
+
+ if (!depth)
+ igt_info("Graph: \n");
+
+ for (space = 0; space < depth * 4; space++)
+ igt_info(" ");
+
+ start_node->visited++;
+ igt_info("Type %s id %d\n", node_type_to_str[start_node->type],
+ start_node->id);
+ for (i = 0; i < start_node->num_connections; i++) {
+ if (!start_node->connections[i]->node->visited) {
+ for (space = 0; space < (depth + 1) * 4; space++)
+ igt_info(" ");
+ igt_info("(%d)-> \n", start_node->connections[i]->weight);
+ traverse_graph(start_node->connections[i]->node, depth+2);
+ start_node->connections[i]->node->visited--;
+ }
+ }
+}
+
+/*
+ * This function recursively searches for a free DBuf slice
+ * for correspondent pipe, based on different constraints, like
+ * weight, usage count. This algorithm is "greedy" which means
+ * that it accounts for local optimum only, which means that
+ * total comparison has to be done in the end.
+ */
+static struct GraphNode *find_slice_for_pipe(struct GraphNode *start_node,
+ int acc_weight, int max_use_count,
+ unsigned int *total_weight,
+ int depth,
+ int skip)
+{
+ int i;
+ unsigned int min_weight = ~0, min_use_count = ~0;
+ struct GraphEdge *min_edge = 0;
+ struct GraphNode *node = NULL;
+ IGT_LIST_HEAD(slice_list);
+
+ start_node->visited++;
+
+ for (i = 0; i < start_node->num_connections; i++) {
+ struct GraphEdge *cur_edge = start_node->connections[i];
+
+ /*
+ * DBuf slices to be added first
+ */
+ if (cur_edge->node->type == DBUF_SLICE) {
+ if (cur_edge->node->use_count < min_use_count) {
+ min_use_count = cur_edge->node->use_count;
+ min_weight = acc_weight + cur_edge->weight;
+ min_edge = cur_edge;
+ igt_list_add(&cur_edge->elem, &slice_list);
+ continue;
+ } else if (cur_edge->node->use_count ==
+ min_edge->node->use_count) {
+ if ((acc_weight + cur_edge->weight) < min_weight) {
+ min_weight = acc_weight + cur_edge->weight;
+ min_edge = cur_edge;
+ igt_list_add(&cur_edge->elem, &slice_list);
+ continue;
+ }
+ }
+ }
+ igt_list_add_tail(&cur_edge->elem, &slice_list);
+ }
+
+ if (igt_list_empty(&slice_list))
+ return NULL;
+
+ /*
+ * Iterate through neighbouring slices, checking
+ * if it's use count allows usage and skip if needed,
+ * skips are needed when we use multiple slices for
+ * same pipe to prevent algorithm from returning the
+ * same DBuf.
+ */
+ igt_list_for_each_entry(min_edge, &slice_list, elem) {
+ if (min_edge->node->type == DBUF_SLICE) {
+ if (min_edge->node->use_count < max_use_count) {
+ if (!skip) {
+ min_edge->node->use_count++;
+ *total_weight = acc_weight + min_edge->weight;
+ if (depth == 0)
+ start_node->visited = 0;
+ return min_edge->node;
+ }
+ }
+ if (skip)
+ skip--;
+ }
+ }
+
+ /*
+ * If couldn't find suitable DBuf node from our
+ * neighbours, have to continue further, checking
+ * visited flag, to prevent loops.
+ */
+ igt_list_for_each_entry(min_edge, &slice_list, elem) {
+ if (!min_edge->node->visited) {
+ node = find_slice_for_pipe(min_edge->node,
+ acc_weight + min_edge->weight,
+ max_use_count, total_weight,
+ depth + 1, skip);
+ min_edge->node->visited--;
+ if (node) {
+ if (depth == 0)
+ start_node->visited = 0;
+ return node;
+ }
+ }
+ }
+ if (depth == 0)
+ start_node->visited = 0;
+ return NULL;
+}
+
+static int hweight32(int mask)
+{
+ int i;
+ int count = 0;
+
+ for (i = 0; i < 32; i++)
+ if ((1<<i) & mask)
+ count += 1;
+ return count;
+}
+
+#define I915_MAX_PIPES 4
+#define I915_MAX_SLICES_PER_PIPE 2
+#define I915_MAX_SLICES (I915_MAX_PIPES * I915_MAX_SLICES_PER_PIPE)
+
+const char *pipe_names[] = { "PIPE_A", "PIPE_B", "PIPE_C", "PIPE_D" };
+
+static int factorial(int n)
+{
+ if (n <= 1)
+ return 1;
+ return n * factorial(n - 1);
+}
+
+static void do_swap(struct GraphNode **pipe_nodes, int m, int n)
+{
+ *((unsigned long *)pipe_nodes + m) ^= *((unsigned long *)pipe_nodes + n);
+ *((unsigned long *)pipe_nodes + n) ^= *((unsigned long *)pipe_nodes + m);
+ *((unsigned long *)pipe_nodes + m) ^= *((unsigned long *)pipe_nodes + n);
+}
+
+struct PipeNodesCombination {
+ unsigned int total_weight;
+ struct GraphNode *pipe_nodes[I915_MAX_PIPES];
+ struct GraphNode *slices[I915_MAX_SLICES];
+};
+
+struct IterateContext {
+ struct PipeNodesCombination min_comb;
+ int max_use_count;
+ int num_pipes;
+ int num_slices;
+ int slices_per_pipe;
+ int max_combinations;
+};
+
+struct PipeDBuf {
+ struct GraphNode *pipe;
+ struct GraphNode *dbuf[I915_MAX_SLICES_PER_PIPE];
+};
+
+static void compare_weight(struct IterateContext *ctx,
+ struct PipeNodesCombination *comb)
+{
+ unsigned int weight;
+ int j = 0;
+ int pipe = 0;
+ int skip = 0;
+ int slice_num = 0;
+
+ comb->total_weight = 0;
+
+ /*
+ * Get a free DBuf slice for each pipe, then
+ * calculate total weight, which will be
+ * then compared to minimal weight to find
+ * combination with total minimal weight.
+ */
+ while (pipe < I915_MAX_PIPES) {
+ if (comb->pipe_nodes[pipe]) {
+ comb->slices[j] =
+ find_slice_for_pipe(comb->pipe_nodes[pipe],
+ 0, ctx->max_use_count,
+ &weight, 0, skip);
+ if (comb->slices[j]) {
+ if (slice_num < ctx->slices_per_pipe)
+ skip++;
+ comb->total_weight += weight;
+ } else {
+ igt_info("Could not find slice for pipe %d!\n",
+ comb->pipe_nodes[pipe]->id);
+ }
+ slice_num++;
+
+ if (slice_num >= ctx->slices_per_pipe) {
+ slice_num = 0;
+ pipe++;
+ skip = 0;
+ }
+ j++;
+ } else {
+ pipe++;
+ j += ctx->slices_per_pipe;
+ skip = 0;
+ }
+ }
+
+ for (j = 0; j < I915_MAX_SLICES; j++) {
+ if (comb->slices[j])
+ comb->slices[j]->use_count = 0;
+ }
+
+ if (ctx->min_comb.total_weight > comb->total_weight) {
+ memcpy(&ctx->min_comb, comb,
+ sizeof(struct PipeNodesCombination));
+ }
+}
+
+/*
+ * Generate all possible combinations for elements in
+ * pipe array(total is calculated as n!).
+ */
+static void iterate_all_combinations(struct IterateContext *ctx,
+ struct GraphNode **pipe_nodes,
+ int start, int step,
+ void (*func)(struct IterateContext *ctx,
+ struct PipeNodesCombination *comb))
+{
+ int i, j;
+ struct GraphNode *nodes[I915_MAX_PIPES];
+ struct PipeNodesCombination comb;
+
+ memcpy(comb.pipe_nodes, pipe_nodes,
+ I915_MAX_PIPES * sizeof(struct GraphNode *));
+ memset(comb.slices, 0,
+ I915_MAX_SLICES * sizeof(struct GraphNode *));
+
+ if (func)
+ (*func)(ctx, &comb);
+
+ if ((step == 0) || (ctx->num_pipes == 1))
+ return;
+
+ for (j = step; j > 0; j--) {
+ for (i = start; i < I915_MAX_PIPES - j; i++) {
+ if (!pipe_nodes[i] || !pipe_nodes[i + j])
+ continue;
+ memcpy(nodes, pipe_nodes,
+ I915_MAX_PIPES * sizeof(struct GraphNode *));
+ do_swap(nodes, i, i + j);
+ iterate_all_combinations(ctx, nodes, i + 1,
+ step - 1, func);
+ }
+ }
+}
+
+/*
+ * This function calculates and prints optimal
+ * weight-based DBuf assignment for active pipes.
+ */
+static void
+print_dbuf_mask_for_pipes(int active_pipes,
+ struct GraphNode **pipe_nodes,
+ int num_slices)
+{
+ int i;
+ int num_pipes = hweight32(active_pipes);
+ int max_use_count = num_slices < num_pipes ? 2 : 1;
+ int pipe = 0;
+ int slices_per_pipe = max(num_slices / num_pipes, 1);
+ struct IterateContext ctx;
+ struct PipeDBuf pipe_dbuf[I915_MAX_PIPES];
+
+ memcpy(ctx.min_comb.pipe_nodes, pipe_nodes,
+ sizeof(struct GraphNode *) * I915_MAX_PIPES);
+ memset(ctx.min_comb.slices, 0,
+ I915_MAX_SLICES * sizeof(struct GraphNode *));
+ ctx.min_comb.total_weight = ~0;
+ ctx.max_use_count = max_use_count;
+ ctx.num_pipes = num_pipes;
+ ctx.num_slices = num_slices;
+ ctx.slices_per_pipe = slices_per_pipe;
+ ctx.max_combinations = factorial(num_pipes);
+
+ iterate_all_combinations(&ctx, pipe_nodes,
+ 0, I915_MAX_PIPES - 1, compare_weight);
+
+ igt_info("Combination with least weight %d(total combinations %d):\n",
+ ctx.min_comb.total_weight, ctx.max_combinations);
+
+ memset(pipe_dbuf, 0, sizeof(struct PipeDBuf) * I915_MAX_PIPES);
+
+ for (i = 0; i < I915_MAX_PIPES; i++) {
+ if (ctx.min_comb.pipe_nodes[i]) {
+ int pipe_index = ctx.min_comb.pipe_nodes[i]->id;
+
+ pipe_dbuf[pipe_index].pipe = ctx.min_comb.pipe_nodes[i];
+ memcpy(&pipe_dbuf[pipe_index].dbuf,
+ &ctx.min_comb.slices[i * slices_per_pipe],
+ sizeof(struct GraphNode *) * slices_per_pipe);
+ }
+ }
+
+ igt_info("{ ");
+ pipe = 0;
+ for (i = 0; i < I915_MAX_PIPES; i++) {
+ if (pipe_dbuf[i].pipe) {
+ igt_info("BIT(%s)", pipe_names[pipe_dbuf[i].pipe->id]);
+ if (pipe < (num_pipes - 1))
+ igt_info(" | ");
+ pipe++;
+ }
+ }
+ igt_info(", { ");
+ for (pipe = 0; pipe < I915_MAX_PIPES; pipe++) {
+ if (pipe_dbuf[pipe].pipe) {
+ for (i = 0; i < slices_per_pipe; i++) {
+ int slice_index_converted =
+ pipe_dbuf[pipe].dbuf[i]->id;
+
+ if (i < (slices_per_pipe - 1)) {
+ igt_info("DBUF_S%d_BIT | ",
+ slice_index_converted + 1);
+ } else {
+ igt_info("DBUF_S%d_BIT",
+ slice_index_converted + 1);
+ }
+ }
+ } else {
+ igt_info("0");
+ }
+ if (pipe < (I915_MAX_PIPES - 1))
+ igt_info(", ");
+ else
+ break;
+ }
+ igt_info(" } },\n");
+}
+
+static void print_table(struct GraphNode **pipes, int num_pipes,
+ struct GraphNode **slices, int num_slices)
+{
+ unsigned int i, j;
+ int num_combinations = 1 << num_pipes;
+
+ if (num_pipes > I915_MAX_PIPES) {
+ igt_info("Too many pipes %d\n", num_pipes);
+ return;
+ }
+
+ if (num_slices > I915_MAX_SLICES) {
+ igt_info("Too many slices %d\n", num_slices);
+ return;
+ }
+
+ for (i = 1; i < num_combinations; i++) {
+ struct GraphNode *tmp[I915_MAX_PIPES];
+
+ memcpy(tmp, pipes, I915_MAX_PIPES * sizeof(struct GraphNode *));
+
+ for (j = 0; j < num_slices; j++) {
+ if (slices[j])
+ slices[j]->use_count = 0;
+ }
+
+ for (j = 0; j < num_pipes; j++) {
+ if (!(i & (1 << j))) {
+ tmp[j] = 0;
+ }
+ }
+
+ print_dbuf_mask_for_pipes(i, tmp, I915_MAX_SLICES_PER_PIPE);
+ }
+}
+
+enum opt {
+ OPT_UNKNOWN = '?',
+ OPT_END = -1,
+ OPT_GEN,
+ OPT_USAGE,
+};
+
+static void usage(const char *toolname)
+{
+ fprintf(stderr, "usage: %s", toolname);
+ fprintf(stderr, " --gen=<GEN>"
+ " [--help]\n");
+}
+
+int main(int argc, char **argv)
+{
+ struct GraphNode *pipes[I915_MAX_PIPES];
+ struct GraphNode *slices[I915_MAX_SLICES];
+ struct GraphNode *pipeA, *pipeB, *pipeC, *pipeD;
+ struct GraphNode *slice1, *slice2;
+ int gen = 12, index;
+ enum opt opt;
+ char *endp;
+ const char *toolname = argv[0];
+ static struct option options[] = {
+ { "gen", required_argument, NULL, OPT_GEN },
+ { "help", no_argument, NULL, OPT_USAGE },
+ { 0 }
+ };
+
+ num_edges = 0;
+ num_nodes = 0;
+
+ for (opt = 0; opt != OPT_END; ) {
+ opt = getopt_long(argc, argv, "", options, &index);
+
+ switch (opt) {
+ case OPT_GEN:
+ gen = strtoul(optarg, &endp, 0);
+ break;
+ case OPT_END:
+ break;
+ case OPT_USAGE: /* fall-through */
+ case OPT_UNKNOWN:
+ usage(toolname);
+ return EXIT_FAILURE;
+ }
+ }
+ pipeA = create_graph_node(PIPE, 0);
+ pipeB = create_graph_node(PIPE, 1);
+ pipeC = create_graph_node(PIPE, 2);
+ pipeD = create_graph_node(PIPE, 3);
+ slice1 = create_graph_node(DBUF_SLICE, 0);
+ slice2 = create_graph_node(DBUF_SLICE, 1);
+
+ memset(pipes, 0, I915_MAX_PIPES * sizeof(struct GraphNode *));
+ memset(slices, 0, I915_MAX_SLICES * sizeof(struct GraphNode *));
+
+ if (gen == 11) {
+
+ /*
+ * Prepare to generate assignments for ICL, which
+ * has 3 pipes and 2 DBuf slices.
+ */
+ slices[0] = slice1;
+ slices[1] = slice2;
+ pipes[0] = pipeA;
+ pipes[1] = pipeB;
+ pipes[2] = pipeC;
+
+ /*
+ * BSpec 12716. Generate DBuf Slices table for ICL,
+ * Graph(each edge assumed to have weight 1):
+ * PipeA - DBUF_S1 - PipeB - PipeC - DBUF_S2
+ */
+ connect_nodes(pipeA, slice1, 1);
+ connect_nodes(slice1, pipeB, 1);
+ connect_nodes(pipeB, pipeC, 1);
+ connect_nodes(pipeC, slice2, 1);
+
+ traverse_graph(pipeA, 0);
+
+ print_table(pipes, 3, slices, 2);
+
+ } else if (gen == 12) {
+
+ /*
+ * Prepare to generate assignments for TGL, which
+ * has 4 pipes and 2 DBuf slices.
+ */
+ slices[0] = slice1;
+ slices[1] = slice2;
+ pipes[0] = pipeA;
+ pipes[1] = pipeB;
+ pipes[2] = pipeC;
+ pipes[3] = pipeD;
+
+ /*
+ * BSpec 49255. Generate DBuf Slices table for TGL.
+ * Graph(each edge assumed to have weight 1):
+ * PipeD - DBUF_S2 - PipeC - PipeA - DBUF_S1 - PipeB
+ */
+ connect_nodes(pipeD, slice2, 1);
+ connect_nodes(slice2, pipeC, 1);
+ connect_nodes(pipeC, pipeA, 1);
+ connect_nodes(pipeA, slice1, 1);
+ connect_nodes(slice1, pipeB, 1);
+
+ traverse_graph(pipeA, 0);
+
+ print_table(pipes, 4, slices, 2);
+ }
+
+ reset_all_nodes();
+
+ /*
+ * Further platforms can generate table same way.
+ */
+
+ destroy_all_nodes();
+
+ return 0;
+}
+
diff --git a/tools/meson.build b/tools/meson.build
index eecb122b..2b8df4b4 100644
--- a/tools/meson.build
+++ b/tools/meson.build
@@ -35,6 +35,7 @@ tools_progs = [
'intel_watermark',
'intel_gem_info',
'intel_gvtg_test',
+ 'intel_dbuf_map',
'dpcd_reg',
]
tool_deps = igt_deps
--
2.17.1
More information about the igt-dev
mailing list