[igt-dev] [PATCH i-g-t v3 0/5] Implement the BST allocator

[igt-dev] [PATCH i-g-t v3 0/5] Implement the BST allocator

[Andrzej Turko]

This patch series implements an allocator
with best-fit strategy. This implementation
is based on a balanced search tree which
allows for fast lookup of free blocks.

Cc: Zbigniew Kempczyński <zbigniew.kempczynski@intel.com>


Andrzej Turko (5):
  lib/intel_allocator: Fix argument names in declarations
  lib/igt_bst: Add a BST interface and an AVL implementation
  lib/intel_allocator_bst: Implement the allocator with a BST
  tests/i915_api_intel_allocator: Add the BST allocator
  benchmarks/intel_allocator: Test the allocator performance

 benchmarks/intel_allocator.c     | 756 +++++++++++++++++++++++++++++++
 benchmarks/meson.build           |   1 +
 lib/igt_bst.c                    | 157 +++++++
 lib/igt_bst.h                    |  69 +++
 lib/igt_bst_avl.c                | 651 ++++++++++++++++++++++++++
 lib/intel_allocator.c            |   7 +
 lib/intel_allocator.h            |   9 +-
 lib/intel_allocator_bst.c        | 672 +++++++++++++++++++++++++++
 lib/meson.build                  |   3 +
 tests/i915/api_intel_allocator.c |  55 ++-
 10 files changed, 2356 insertions(+), 24 deletions(-)
 create mode 100644 benchmarks/intel_allocator.c
 create mode 100644 lib/igt_bst.c
 create mode 100644 lib/igt_bst.h
 create mode 100644 lib/igt_bst_avl.c
 create mode 100644 lib/intel_allocator_bst.c

-- 
2.25.1

_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev

[igt-dev] [PATCH i-g-t 1/5] lib/intel_allocator: Fix argument names in declarations

[Andrzej Turko]

Unify the argument names to avoid confusion.

Signed-off-by: Andrzej Turko <andrzej.turko@linux.intel.com>
Cc: Zbigniew Kempczyński <zbigniew.kempczynski@intel.com>
---
 lib/intel_allocator.h | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/lib/intel_allocator.h b/lib/intel_allocator.h
index c14f57b4d..7d9d01123 100644
--- a/lib/intel_allocator.h
+++ b/lib/intel_allocator.h
@@ -144,13 +144,13 @@ struct intel_allocator {
 			  uint64_t size, uint64_t alignment,
 			  enum allocator_strategy strategy);
 	bool (*is_allocated)(struct intel_allocator *ial, uint32_t handle,
-			     uint64_t size, uint64_t alignment);
+			     uint64_t size, uint64_t offset);
 	bool (*reserve)(struct intel_allocator *ial,
-			uint32_t handle, uint64_t start, uint64_t size);
+			uint32_t handle, uint64_t start, uint64_t end);
 	bool (*unreserve)(struct intel_allocator *ial,
-			  uint32_t handle, uint64_t start, uint64_t size);
+			  uint32_t handle, uint64_t start, uint64_t end);
 	bool (*is_reserved)(struct intel_allocator *ial,
-			    uint64_t start, uint64_t size);
+			    uint64_t start, uint64_t end);
 	bool (*free)(struct intel_allocator *ial, uint32_t handle);
 
 	void (*destroy)(struct intel_allocator *ial);
-- 
2.25.1

_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev

[igt-dev] [PATCH i-g-t 2/5] lib/igt_bst: Add a BST interface and an AVL implementation

[Andrzej Turko]

This adds an efficient binary search tree implementation
in order to support an allocator with best-fit strategy.

Signed-off-by: Andrzej Turko <andrzej.turko@linux.intel.com>
Cc: Zbigniew Kempczyński <zbigniew.kempczynski@intel.com>
---
 lib/igt_bst.c     | 157 +++++++++++
 lib/igt_bst.h     |  69 +++++
 lib/igt_bst_avl.c | 651 ++++++++++++++++++++++++++++++++++++++++++++++
 lib/meson.build   |   2 +
 4 files changed, 879 insertions(+)
 create mode 100644 lib/igt_bst.c
 create mode 100644 lib/igt_bst.h
 create mode 100644 lib/igt_bst_avl.c

diff --git a/lib/igt_bst.c b/lib/igt_bst.c
new file mode 100644
index 000000000..a24859213
--- /dev/null
+++ b/lib/igt_bst.c
@@ -0,0 +1,157 @@
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright © 2021 Intel Corporation
+ */
+
+#include "igt_bst.h"
+
+
+/**
+ * igt_bst_insert
+ * @bst: igt_bst pointer
+ * @value: a pointer value being inserted
+ * @key: the key under which the value should be stored
+ *
+ * Inserts a new value to the bst.
+ *
+ * Returns: a pointer to the newly created node.
+ */
+void *igt_bst_insert(struct igt_bst *bst, void *value, uint64_t key)
+{
+	return bst->insert(bst, value, key);
+}
+
+/**
+ * igt_bst_erase
+ * @bst: igt_bst pointer
+ * @nodeptr: a pointer to a node in the bst
+ *
+ * Erases the indicated node.
+ *
+ * Returns: the value associated with the
+ * erased node.
+ */
+void *igt_bst_erase(struct igt_bst *bst, void *nodeptr)
+{
+	return bst->erase(bst, nodeptr);
+}
+
+/**
+ * igt_bst_query_successor
+ * @bst: igt_bst pointer
+ * @key: an arbitrary key
+ *
+ * Among the elements currently present in the bst,
+ * finds the one with the smallest key not smaller than
+ * the given key.
+ *
+ * Returns: a value associated with the found element,
+ * NULL if all keys in the tree are smaller than the key
+ * parameter.
+ */
+void *igt_bst_query_successor(struct igt_bst *bst, uint64_t key)
+{
+	return bst->query_successor(bst, key);
+}
+
+/**
+ * igt_bst_query_successor
+ * Similar to igt_bst_query_predecessor, but looks for an
+ * element with the greatest key not exceeding the parameter.
+ */
+void *igt_bst_query_predecessor(struct igt_bst *bst, uint64_t key)
+{
+	return bst->query_predecessor(bst, key);
+}
+
+/**
+ * igt_bst_pop_successor
+ * Like igt_bst_query_successor, but also removes the
+ * found element from the bst.
+ */
+void *igt_bst_pop_successor(struct igt_bst *bst, uint64_t key)
+{
+	return bst->pop_successor(bst, key);
+}
+
+/**
+ * igt_bst_pop_predecessor
+ * Like igt_bst_query_predecessor, but also removes the
+ * found element from the bst.
+ */
+void *igt_bst_pop_predecessor(struct igt_bst *bst, uint64_t key)
+{
+	return bst->pop_predecessor(bst, key);
+}
+
+/* check whether the bst contains any elements */
+bool igt_bst_empty(struct igt_bst *bst)
+{
+	return bst->bst_empty(bst);
+}
+
+/* retrieve the value from the element in the bst given by the pointer to its node */
+void *igt_bst_get_value(struct igt_bst *bst, void *nodeptr)
+{
+	return bst->get_value(nodeptr);
+}
+
+/* retrieve the key from the element the bst given by the pointer to its node */
+uint64_t igt_bst_get_key(struct igt_bst *bst, void *nodeptr)
+{
+	return bst->get_key(nodeptr);
+}
+
+/**
+ * igt_bst_leftmost_entry
+ * @bst: igt_bst pointer
+ *
+ * Finds an element in the bst with the smallest key.
+ *
+ * Returns: a pointer to the found node,
+ * NULL if the bst is empty.
+ */
+void *igt_bst_leftmost_entry(struct igt_bst *bst)
+{
+	return bst->leftmost_entry(bst);
+}
+
+/**
+ * igt_bst_rightmost_entry
+ * See igt_bst_leftmost_entry.
+ */
+void *igt_bst_rightmost_entry(struct igt_bst *bst)
+{
+	return bst->rightmost_entry(bst);
+}
+
+/**
+ * igt_bst_next_entry
+ * @bst: igt_bst pointer
+ * @nodeptr: a pointer to a node in the bst
+ *
+ * Finds the next element in the bst in the
+ * nondecreasing order of keys.
+ * Can be used to iterate over all elements.
+ *
+ * Retuns: a pointer to the next node in the bst,
+ * NULL if nodeptr points to the last node.
+ */
+void *igt_bst_next_entry(struct igt_bst *bst, void *nodeptr)
+{
+	return bst->next_entry(nodeptr);
+}
+
+/**
+ * igt_bst_prev_entry
+ * Like igt_bst_next_entry, but returns the previous node.
+ */
+void *igt_bst_prev_entry(struct igt_bst *bst, void *nodeptr)
+{
+	return bst->prev_entry(nodeptr);
+}
+
+void igt_bst_free(struct igt_bst *bst)
+{
+	bst->bst_free(bst);
+}
diff --git a/lib/igt_bst.h b/lib/igt_bst.h
new file mode 100644
index 000000000..f54fca50c
--- /dev/null
+++ b/lib/igt_bst.h
@@ -0,0 +1,69 @@
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright © 2021 Intel Corporation
+ */
+
+#ifndef __IGT_BST_H
+#define __IGT_BST_H
+
+#include <stdint.h>
+#include <stdbool.h>
+
+/**
+ * SECTION: igt_bst
+ * @short_description: a binary search tree interface
+ * @title: IGT Bst
+ * @include: igt_bst.h
+ *
+ * This interface operates on binary rearch trees
+ * which store void pointers ordered by uint64_t keys.
+ */
+
+struct igt_bst {
+
+	/* private structure of the BST */
+	void *priv;
+
+	void* (*insert)(struct igt_bst *bst, void *value, uint64_t key);
+	void* (*erase)(struct igt_bst *bst, void *nodeptr);
+	void* (*pop_successor)(struct igt_bst *bst, uint64_t key);
+	void* (*pop_predecessor)(struct igt_bst *bst, uint64_t key);
+	void* (*query_successor)(struct igt_bst *bst, uint64_t key);
+	void* (*query_predecessor)(struct igt_bst *bst, uint64_t key);
+	bool (*bst_empty)(struct igt_bst *bst);
+	void* (*get_value)(void *nodeptr);
+	uint64_t (*get_key)(void *nodeptr);
+	void* (*leftmost_entry)(struct igt_bst *bst);
+	void* (*rightmost_entry)(struct igt_bst *bst);
+	void* (*next_entry)(void *nodeptr);
+	void* (*prev_entry)(void *nodeptr);
+	void (*bst_free)(struct igt_bst *bst);
+	int (*validate)(struct igt_bst *bst);
+};
+
+/* contructors */
+struct igt_bst *igt_bst_avl_create(void);
+
+#define igt_bst_for_each_node(bst, nodeptr) \
+	for ((nodeptr) = (bst)->leftmost_entry(bst); (nodeptr); (nodeptr) = (bst)->next_entry(nodeptr))
+
+#define igt_bst_for_each_node_rev(bst, nodeptr) \
+	for ((nodeptr) = (bst)->rightmost_entry(bst); (nodeptr); (nodeptr) = (bst)->prev_entry(nodeptr))
+
+
+void *igt_bst_insert(struct igt_bst *bst, void *value, uint64_t key);
+void *igt_bst_erase(struct igt_bst *bst, void *nodeptr);
+void *igt_bst_query_successor(struct igt_bst *bst, uint64_t key);
+void *igt_bst_query_predecessor(struct igt_bst *bst, uint64_t key);
+void *igt_bst_pop_successor(struct igt_bst *bst, uint64_t key);
+void *igt_bst_pop_predecessor(struct igt_bst *bst, uint64_t key);
+bool igt_bst_empty(struct igt_bst *bst);
+void *igt_bst_get_value(struct igt_bst *bst, void *nodeptr);
+uint64_t igt_bst_get_key(struct igt_bst *bst, void *nodeptr);
+void *igt_bst_leftmost_entry(struct igt_bst *bst);
+void *igt_bst_rightmost_entry(struct igt_bst *bst);
+void *igt_bst_next_entry(struct igt_bst *bst, void *nodeptr);
+void *igt_bst_prev_entry(struct igt_bst *bst, void *nodeptr);
+void igt_bst_free(struct igt_bst *bst);
+
+#endif /* IGT_BST_H */
diff --git a/lib/igt_bst_avl.c b/lib/igt_bst_avl.c
new file mode 100644
index 000000000..7245a798d
--- /dev/null
+++ b/lib/igt_bst_avl.c
@@ -0,0 +1,651 @@
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright © 2021 Intel Corporation
+ */
+
+#include "igt.h"
+#include "igt_bst.h"
+
+//#define AVLDBG
+#ifdef AVLDBG
+#define avl_debug(...) fprintf(stderr, __VA_ARGS__)
+#define avl_assert igt_assert
+#define avl_assert_f igt_assert_f
+#else
+#define avl_debug(...) {}
+#define avl_assert(...) {}
+#define avl_assert_f(...) {}
+#endif
+
+struct igt_avl_node {
+	uint64_t key;
+
+	struct igt_avl_node *left;
+	struct igt_avl_node *right;
+	struct igt_avl_node *parent;
+
+	int32_t height;
+
+	void *value;
+};
+
+struct igt_avl {
+	struct igt_avl_node *root;
+};
+
+static int __traverse_validate(struct igt_avl_node *node)
+{
+	int32_t node_balance, left_h, right_h;
+	int n = 1;
+
+	igt_assert(node);
+
+	left_h = 0;
+	right_h = 0;
+
+	avl_debug("at 0x%llx : < key %llu, value 0x%llx >\nleft 0x%llx ; right 0x%llx\n",
+		  (unsigned long long)node,
+		  (unsigned long long)node->key,
+		  (unsigned long long)node->value,
+		  (unsigned long long)node->left,
+		  (unsigned long long)node->right);
+
+	if (node->left) {
+		igt_assert(node->left->parent == node);
+		igt_assert_f(node->key >= node->left->key,
+			     "The order of keys is not preserved in the AVL tree");
+		left_h = node->left->height;
+		n += __traverse_validate(node->left);
+	}
+
+	if (node->right) {
+		igt_assert(node->right->parent == node);
+		igt_assert_f(node->right->key >= node->key,
+			     "The order of keys is not preserved in the AVL tree");
+		right_h = node->right->height;
+		n += __traverse_validate(node->right);
+	}
+
+	node_balance = left_h - right_h;
+	igt_assert(node_balance <= 1 && node_balance >= -1);
+	igt_assert(node->height == (left_h > right_h ? left_h : right_h) + 1);
+
+	return n;
+}
+
+static int avl_validate(struct igt_bst *bst)
+{
+	struct igt_avl *avl = bst->priv;
+
+	avl_debug("Tree traversal:\n");
+
+	/* an empty tree */
+	if (avl->root == NULL)
+		return 0;
+
+	igt_assert(!avl->root->parent);
+	return __traverse_validate(avl->root);
+}
+
+/* fix balance of all vertices from the given node to the root */
+static inline void __avl_fix_balance(struct igt_avl *avl, struct igt_avl_node *node)
+{
+	struct igt_avl_node *left, *right, *l_left, *l_right, *r_left, *r_right;
+	int32_t left_h, right_h, l_left_h, l_right_h, r_left_h, r_right_h;
+	int32_t balance, node_h;
+
+	while (node) {
+
+		node_h = node->height;
+		left = node->left;
+		left_h = (left ? left->height : 0);
+		right = node->right;
+		right_h = (right ? right->height : 0);
+		balance = left_h - right_h;
+
+		avl_debug("Correcting a node with key %llu at 0x%llx (%llu)\n",
+			 (unsigned long long)node->key,
+			  (unsigned long long)node,
+			  *((unsigned long long *)node->value));
+		avl_debug("Heights: %d [%d %d] : balance %d\n",
+			  node_h, left_h, right_h, balance);
+
+		if (balance > 1) {
+			avl_assert(balance == 2);
+			avl_assert(left);
+
+			/* 1st case: left son's subtree is too high */
+			l_left = left->left;
+			l_left_h = (l_left ? l_left->height : 0);
+			l_right = left->right;
+			l_right_h = (l_right ? l_right->height : 0);
+
+			if (l_right_h > l_left_h) {
+				avl_assert(l_right_h == right_h + 1);
+				avl_assert(l_left_h == right_h);
+				avl_assert(l_right);
+
+				/*
+				 * left son's (left's) right son (l_right) is too high,
+				 * rotate the left son and its right son
+				 *
+				 *       N                 N                N
+				 *      /                 /                /
+				 *     L    (rotate)     LR    (rename)   L
+				 *    / \    ----->     /  \    ----->   / \
+				 *  LL  LR             L   LRR          LL  LR
+				 *     /  \           / \
+				 *   LRL  LRR        LL  LRL
+				 *
+				 */
+
+				left->right = l_right->left;
+				if (l_right->left)
+					l_right->left->parent = left;
+				l_right->parent = node;
+				node->left = l_right;
+				l_right->left = left;
+				left->parent = l_right;
+
+				l_left = left;
+				left = l_right;
+				l_right = l_right->right;
+
+				l_left_h = --l_left->height;
+				l_right_h = (l_right ? l_right->height : 0);
+				left_h = ++left->height;
+			}
+
+			avl_assert(left);
+			avl_assert(left_h == right_h + 2);
+			avl_assert(l_left_h == right_h + 1);
+
+			/*
+			 * rotate the node and its left son
+			 *
+			 *       |               |               |
+			 *       N    (rotate)   L    (rename)   N
+			 *      / \    ----->   / \    ----->   / \
+			 *     L   R           LL  N          ... ...
+			 *    / \                 / \
+			 *  LL  LR               LR  R
+			 *
+			 */
+
+			node->left = l_right;
+			if (l_right)
+				l_right->parent = node;
+			left->parent = node->parent;
+			if (node->parent) {
+				if (node->parent->left == node)
+					node->parent->left = left;
+				else
+					node->parent->right = left;
+
+			} else {
+				avl->root = left;
+			}
+			node->parent = left;
+			left->right = node;
+
+			node->height = (l_right_h > right_h ? l_right_h : right_h) + 1;
+			left->height = (node->height > l_left_h ? node->height : l_left_h) + 1;
+
+			node = left;
+		}
+
+
+		if (balance < -1) {
+			avl_assert(balance == -2);
+			avl_assert(right);
+
+			/* 2nd case: right son's subtree is too high */
+			r_left = right->left;
+			r_left_h = (r_left ? r_left->height : 0);
+			r_right = right->right;
+			r_right_h = (r_right ? r_right->height : 0);
+
+			if (r_left_h > r_right_h) {
+				avl_assert(r_left_h == left_h + 1);
+				avl_assert(r_right_h == left_h);
+				avl_assert(r_left);
+
+				/*
+				 * right son's (right's) left son (r_left) is too high,
+				 * rotate the right son and its left son.
+				 *
+				 *       N                  N                N
+				 *        \                  \                \
+				 *         R   (rotate)      RL    (rename)    R
+				 *        / \   ----->      /  \    ----->    / \
+				 *      RL  RR            RLL   R            RL RR
+				 *     /  \                    / \
+				 *   RLL  RLR               RLR  RR
+				 *
+				 */
+
+				right->left = r_left->right;
+				if (r_left->right)
+					r_left->right->parent = right;
+				r_left->parent = node;
+				node->right = r_left;
+				r_left->right = right;
+				right->parent = r_left;
+
+				r_right = right;
+				right = r_left;
+				r_left = r_left->left;
+
+				r_right_h = --r_right->height;
+				r_left_h = (r_left ? r_left->height : 0);
+				right_h = ++right->height;
+			}
+
+			avl_assert(right);
+			avl_assert(right_h == left_h + 2);
+			avl_assert(r_right_h == left_h + 1);
+
+			/*
+			 * rotate the node and its right son
+			 *
+			 *       |               |               |
+			 *       N    (rotate)   R    (rename)   N
+			 *      / \    ----->   / \    ----->   / \
+			 *     L   R           N   RR         ... ...
+			 *        / \         / \
+			 *      RL   RR      L  RL
+			 *
+			 */
+
+			node->right = r_left;
+			if (r_left)
+				r_left->parent = node;
+			right->parent = node->parent;
+			if (node->parent) {
+				if (node->parent->left == node)
+					node->parent->left = right;
+				else
+					node->parent->right = right;
+
+			} else {
+				avl->root = right;
+			}
+			node->parent = right;
+			right->left = node;
+
+			node->height = (r_left_h > left_h ? r_left_h : left_h) + 1;
+			right->height = (node->height > r_right_h ? node->height : r_right_h) + 1;
+
+			node = right;
+		}
+
+		if (balance >= -1 && balance <= 1)
+			node->height = (left_h > right_h ? left_h : right_h) + 1;
+
+		avl_assert(node->height - node_h >= -1 && node->height - node_h <= 1);
+
+		if (node->height == node_h)
+			break;
+
+		node = node->parent;
+	}
+}
+
+static void *avl_insert(struct igt_bst *bst, void *value, uint64_t key)
+{
+	struct igt_avl *avl = bst->priv;
+	struct igt_avl_node *node, *parent;
+
+	node = avl->root;
+	parent = NULL;
+	while (node) {
+		parent = node;
+		if (key < node->key)
+			node = node->left;
+		else
+			node = node->right;
+	}
+
+	node = malloc(sizeof(struct igt_avl_node));
+	igt_assert(node);
+	node->key = key;
+	node->parent = parent;
+	node->left = NULL;
+	node->right = NULL;
+	node->height = 1;
+	node->value = value;
+	if (parent) {
+		if (key < parent->key)
+			parent->left = node;
+		else
+			parent->right = node;
+
+		__avl_fix_balance(avl, parent);
+	} else {
+		avl->root = node;
+	}
+
+	return node;
+}
+
+static inline void
+__avl_erase_node(struct igt_avl *avl, struct igt_avl_node *node,
+		 struct igt_avl_node *del_pos)
+{
+	struct igt_avl_node *parent, *son;
+
+	avl_assert(node);
+	avl_assert(del_pos);
+	avl_assert(!del_pos->left || !del_pos->right);
+	son = (del_pos->left ? del_pos->left : del_pos->right);
+	parent = del_pos->parent;
+
+	avl_debug("Erasing node 0x%llx with position 0x%llx\n",
+		  (unsigned long long)node, (unsigned long long)del_pos);
+
+	if (node != del_pos) {
+		/* move a node from the deleted position
+		 * to place of the deleted node
+		 */
+
+		del_pos->left = node->left;
+		if (del_pos->left)
+			del_pos->left->parent = del_pos;
+		del_pos->right = node->right;
+		if (del_pos->right)
+			del_pos->right->parent = del_pos;
+
+		del_pos->parent = node->parent;
+		if (node->parent) {
+			if (node->parent->left == node)
+				node->parent->left = del_pos;
+			else
+				node->parent->right = del_pos;
+
+		} else {
+			avl->root = del_pos;
+		}
+
+		del_pos->height = node->height;
+
+		if (parent == node)
+			parent = del_pos;
+
+	}
+
+	if (son)
+		son->parent = parent;
+
+	if (parent) {
+		if (parent->left == del_pos)
+			parent->left = son;
+		else
+			parent->right = son;
+
+		__avl_fix_balance(avl, parent);
+	} else {
+		avl->root = son;
+	}
+
+	avl_assert(del_pos->parent != del_pos);
+
+	free(node);
+}
+
+static void *avl_erase(struct igt_bst *bst, void *nodeptr)
+{
+	struct igt_avl_node *node, *del_pos;
+	void *value;
+
+	igt_assert(nodeptr);
+	node = (struct igt_avl_node *) nodeptr;
+	value = node->value;
+	del_pos = node->left;
+	if (del_pos) {
+		while (del_pos->right)
+			del_pos = del_pos->right;
+
+		__avl_erase_node(bst->priv, node, del_pos);
+	} else {
+		__avl_erase_node(bst->priv, node, node);
+	}
+
+	return value;
+}
+
+static void *avl_pop_successor(struct igt_bst *bst, uint64_t key)
+{
+	struct igt_avl *avl = bst->priv;
+	struct igt_avl_node *node, *succ, *parent;
+	void *value;
+
+	node = avl->root;
+	parent = NULL;
+	succ = NULL;
+	while (node) {
+		parent = node;
+		if (node->key >= key) {
+			succ = node;
+			node = node->left;
+		} else {
+			node = node->right;
+		}
+	}
+
+	if (!succ)
+		return NULL;
+
+	value = succ->value;
+	__avl_erase_node(avl, succ, parent);
+
+	return value;
+}
+
+static void *avl_pop_predecessor(struct igt_bst *bst, uint64_t key)
+{
+	struct igt_avl *avl = bst->priv;
+	struct igt_avl_node *node, *parent, *pred;
+	void *value;
+
+	node = avl->root;
+	parent = NULL;
+	pred = NULL;
+	while (node) {
+		parent = node;
+		if (node->key <= key) {
+			pred = node;
+			node = node->right;
+		} else {
+			node = node->left;
+		}
+	}
+
+	if (!pred)
+		return NULL;
+
+	value = pred->value;
+	__avl_erase_node(avl, pred, parent);
+
+	return value;
+}
+
+static void *avl_query_successor(struct igt_bst *bst, uint64_t key)
+{
+	struct igt_avl *avl = bst->priv;
+	struct igt_avl_node *node;
+	void *value = NULL;
+
+	node = avl->root;
+	while (node) {
+		if (node->key >= key) {
+			value = node->value;
+			node = node->left;
+		} else {
+			node = node->right;
+		}
+	}
+
+	return value;
+}
+
+static void *avl_query_predecessor(struct igt_bst *bst, uint64_t key)
+{
+	struct igt_avl *avl = bst->priv;
+	struct igt_avl_node *node;
+	void *value = NULL;
+
+	node = avl->root;
+	while (node) {
+		if (node->key <= key) {
+			value = node->value;
+			node = node->right;
+		} else {
+			node = node->left;
+		}
+	}
+
+	return value;
+}
+
+static bool avl_bst_empty(struct igt_bst *bst)
+{
+	struct igt_avl *avl = bst->priv;
+
+	return (avl->root == NULL);
+}
+
+
+static void *avl_get_value(void *nodeptr)
+{
+	return ((struct igt_avl_node *)nodeptr)->value;
+}
+
+static uint64_t avl_get_key(void *nodeptr)
+{
+	return ((struct igt_avl_node *)nodeptr)->key;
+}
+
+static void *avl_leftmost_entry(struct igt_bst *bst)
+{
+	struct igt_avl *avl = bst->priv;
+	struct igt_avl_node *node;
+
+	node = avl->root;
+	if (node) {
+		while (node->left)
+			node = node->left;
+	}
+
+	return node;
+}
+
+static void *avl_rightmost_entry(struct igt_bst *bst)
+{
+	struct igt_avl *avl = bst->priv;
+	struct igt_avl_node *node;
+
+	node = avl->root;
+	if (node) {
+		while (node->right)
+			node = node->right;
+	}
+	return node;
+}
+
+static void *avl_next_entry(void *nodeptr)
+{
+	struct igt_avl_node *node;
+
+	igt_assert(nodeptr);
+	node = (struct igt_avl_node *) nodeptr;
+	if (node->right) {
+		node = node->right;
+		while (node->left)
+			node = node->left;
+
+		return node;
+	}
+	while (node->parent) {
+		if (node->parent->left == node)
+			return node->parent;
+
+		node = node->parent;
+	}
+	return NULL;
+}
+
+static void *avl_prev_entry(void *nodeptr)
+{
+	struct igt_avl_node *node;
+
+	igt_assert(nodeptr);
+	node = (struct igt_avl_node *) nodeptr;
+	if (node->left) {
+		node = node->left;
+		while (node->right)
+			node = node->right;
+
+		return node;
+	}
+	while (node->parent) {
+		if (node->parent->right == node)
+			return node->parent;
+
+		node = node->parent;
+	}
+	return NULL;
+}
+
+static void __avl_free(struct igt_avl_node *node)
+{
+	avl_assert(node);
+
+	if (node->left)
+		__avl_free(node->left);
+
+	if (node->right)
+		__avl_free(node->right);
+
+	free(node);
+}
+
+static void avl_bst_free(struct igt_bst *bst)
+{
+	struct igt_avl *avl = bst->priv;
+
+	if (avl->root)
+		__avl_free(avl->root);
+
+	free(avl);
+}
+
+struct igt_bst *igt_bst_avl_create(void)
+{
+	struct igt_avl *avl;
+	struct igt_bst *bst;
+
+	avl = malloc(sizeof(struct igt_avl));
+	bst = malloc(sizeof(struct igt_bst));
+	igt_assert(avl);
+	igt_assert(bst);
+
+	avl->root = NULL;
+	bst->priv = avl;
+	bst->insert = avl_insert;
+	bst->erase = avl_erase;
+	bst->pop_successor = avl_pop_successor;
+	bst->pop_predecessor = avl_pop_predecessor;
+	bst->query_successor = avl_query_successor;
+	bst->query_predecessor = avl_query_predecessor;
+	bst->bst_empty = avl_bst_empty;
+	bst->get_value = avl_get_value;
+	bst->get_key = avl_get_key;
+	bst->leftmost_entry = avl_leftmost_entry;
+	bst->rightmost_entry = avl_rightmost_entry;
+	bst->next_entry = avl_next_entry;
+	bst->prev_entry = avl_prev_entry;
+	bst->bst_free = avl_bst_free;
+	bst->validate = avl_validate;
+
+	return bst;
+}
diff --git a/lib/meson.build b/lib/meson.build
index 67d405129..a1aa0ee12 100644
--- a/lib/meson.build
+++ b/lib/meson.build
@@ -11,6 +11,8 @@ lib_sources = [
 	'i915/gem_mman.c',
 	'i915/gem_vm.c',
 	'i915/intel_memory_region.c',
+	'igt_bst.c',
+	'igt_bst_avl.c',
 	'igt_collection.c',
 	'igt_color_encoding.c',
 	'igt_debugfs.c',
-- 
2.25.1

_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev

[igt-dev] [PATCH i-g-t 3/5] lib/intel_allocator_bst: Implement the allocator with a BST

[Andrzej Turko]

This implements an alternative to the simple allocator.
The BST allocator follows best-fit strategy.
Usage of a binary search tree speeds up finding free
blocks of memory (compared to a list).

Signed-off-by: Andrzej Turko <andrzej.turko@linux.intel.com>
Cc: Zbigniew Kempczyński <zbigniew.kempczynski@intel.com>
---
 lib/intel_allocator.c     |   7 +
 lib/intel_allocator.h     |   1 +
 lib/intel_allocator_bst.c | 672 ++++++++++++++++++++++++++++++++++++++
 lib/meson.build           |   1 +
 4 files changed, 681 insertions(+)
 create mode 100644 lib/intel_allocator_bst.c

diff --git a/lib/intel_allocator.c b/lib/intel_allocator.c
index 133176ed4..2ef487a05 100644
--- a/lib/intel_allocator.c
+++ b/lib/intel_allocator.c
@@ -71,6 +71,9 @@ intel_allocator_random_create(int fd, uint64_t start, uint64_t end);
 struct intel_allocator *
 intel_allocator_simple_create(int fd, uint64_t start, uint64_t end,
 			      enum allocator_strategy strategy);
+struct intel_allocator *
+intel_allocator_bst_create(int fd, uint64_t start, uint64_t end,
+			   enum allocator_strategy strategy);
 
 /*
  * Instead of trying to find first empty handle just get new one. Assuming
@@ -311,6 +314,10 @@ static struct intel_allocator *intel_allocator_create(int fd,
 		ial = intel_allocator_simple_create(fd, start, end,
 						    allocator_strategy);
 		break;
+	case INTEL_ALLOCATOR_BST:
+		ial = intel_allocator_bst_create(fd, start, end,
+						 allocator_strategy);
+		break;
 	default:
 		igt_assert_f(ial, "Allocator type %d not implemented\n",
 			     allocator_type);
diff --git a/lib/intel_allocator.h b/lib/intel_allocator.h
index 7d9d01123..93ecbc3e4 100644
--- a/lib/intel_allocator.h
+++ b/lib/intel_allocator.h
@@ -211,6 +211,7 @@ void intel_allocator_print(uint64_t allocator_handle);
 #define INTEL_ALLOCATOR_RELOC  1
 #define INTEL_ALLOCATOR_RANDOM 2
 #define INTEL_ALLOCATOR_SIMPLE 3
+#define INTEL_ALLOCATOR_BST    4
 
 #define GEN8_GTT_ADDRESS_WIDTH 48
 
diff --git a/lib/intel_allocator_bst.c b/lib/intel_allocator_bst.c
new file mode 100644
index 000000000..4affa4927
--- /dev/null
+++ b/lib/intel_allocator_bst.c
@@ -0,0 +1,672 @@
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright © 2021 Intel Corporation
+ */
+
+#include <stdlib.h>
+#include "igt.h"
+#include "igt_map.h"
+#include "igt_bst.h"
+#include "intel_allocator.h"
+
+/* The addresses of allocated objects will be
+ * strictly smaller than this value (the upper
+ * end of the address range cannot exceed it).
+ * This is to enable the use of canonical
+ * addresses.
+ */
+#define IALB_MAX_ADDR (1ull<<48)
+
+#define RESERVED 4096
+
+/* Avoid compilation warning */
+struct intel_allocator *
+intel_allocator_bst_create(int fd, uint64_t start, uint64_t end,
+			   enum allocator_strategy strategy);
+
+struct intel_allocator_bst {
+	struct igt_map *objects;
+	struct igt_map *reserved;
+	struct igt_bst *by_size;
+	struct igt_bst *by_offset;
+
+	uint64_t start;
+	uint64_t end;
+
+	/* statistics */
+	uint64_t total_size;
+	uint64_t allocated_size;
+	uint64_t allocated_objects;
+	uint64_t reserved_size;
+	uint64_t reserved_areas;
+};
+
+struct intel_allocator_bst_vma_hole {
+
+	/* pointer to the node in the by_size bst */
+	void *size_ptr;
+
+	/* pointer to the node in the by_offset bst */
+	void *offset_ptr;
+
+	uint64_t size;
+	uint64_t offset;
+};
+
+struct intel_allocator_record {
+	uint32_t handle;
+	uint64_t offset;
+	uint64_t size;
+};
+
+/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
+#define GOLDEN_RATIO_PRIME_32 0x9e370001UL
+
+/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
+#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL
+
+static inline uint32_t hash_handles(const void *val)
+{
+	uint32_t hash = *(uint32_t *) val;
+
+	hash = hash * GOLDEN_RATIO_PRIME_32;
+	return hash;
+}
+
+static int equal_handles(const void *a, const void *b)
+{
+	uint32_t *key1 = (uint32_t *) a, *key2 = (uint32_t *) b;
+
+	return *key1 == *key2;
+}
+
+static inline uint32_t hash_offsets(const void *val)
+{
+	uint64_t hash = *(uint64_t *) val;
+
+	hash = hash * GOLDEN_RATIO_PRIME_64;
+	/* High bits are more random, so use them. */
+	return hash >> 32;
+}
+
+static int equal_offsets(const void *a, const void *b)
+{
+	uint64_t *key1 = (uint64_t *) a, *key2 = (uint64_t *) b;
+
+	return *key1 == *key2;
+}
+
+static void map_entry_free_func(struct igt_map_entry *entry)
+{
+	free(entry->data);
+}
+
+static void holes_bst_validate(struct intel_allocator_bst *ialb)
+{
+	struct igt_bst *offset_bst, *size_bst;
+	struct intel_allocator_bst_vma_hole *hole;
+	void *nodeptr;
+	int by_offset_size, by_size_size;
+	uint64_t prev_offset;
+
+	offset_bst = ialb->by_offset;
+	size_bst = ialb->by_size;
+	by_offset_size = offset_bst->validate(offset_bst);
+	by_size_size = size_bst->validate(size_bst);
+	igt_assert(by_offset_size == by_size_size);
+
+	prev_offset = IALB_MAX_ADDR;
+	igt_bst_for_each_node_rev(offset_bst, nodeptr) {
+		hole = igt_bst_get_value(offset_bst, nodeptr);
+		igt_assert(hole);
+		/* Make sure the hole is stored under correct keys in
+		 * the balanced search trees.
+		 */
+		igt_assert(hole->offset == igt_bst_get_key(offset_bst, hole->offset_ptr));
+		igt_assert(hole->size == igt_bst_get_key(size_bst, hole->size_ptr));
+
+		igt_assert(hole->offset + hole->size > hole->offset);
+		/* Make sure no pair of holes is adjacent. */
+		igt_assert(prev_offset > hole->offset + hole->size);
+
+		prev_offset = hole->offset;
+	}
+}
+
+static void __intel_allocator_bst_alloc(struct intel_allocator_bst *ialb,
+					struct intel_allocator_bst_vma_hole *hole,
+					uint64_t offset, uint64_t size)
+{
+	struct igt_bst *offset_bst, *size_bst;
+	struct intel_allocator_bst_vma_hole *newhole;
+	uint64_t lower, higher;
+
+	igt_assert(hole->offset <= offset);
+	igt_assert(hole->offset + hole->size >= offset + size);
+
+	offset_bst = ialb->by_offset;
+	size_bst = ialb->by_size;
+
+	lower = offset - hole->offset;
+	higher = hole->size - size - lower;
+
+	if (lower > 0 && higher > 0) {
+		/* There are leftovers on both lower and higher addresses.
+		 * Create a hole for higher addresses from scratch and
+		 * one for lower addresses by modifying the existing hole.
+		 */
+
+		newhole = malloc(sizeof(struct intel_allocator_bst_vma_hole));
+		igt_assert(newhole);
+
+		newhole->offset = offset + size;
+		newhole->size = higher;
+
+		newhole->offset_ptr = igt_bst_insert(offset_bst, newhole, newhole->offset);
+		newhole->size_ptr = igt_bst_insert(size_bst, newhole, newhole->size);
+
+		hole->size = lower;
+		igt_bst_erase(size_bst, hole->size_ptr);
+		hole->size_ptr = igt_bst_insert(size_bst, hole, hole->size);
+
+	} else if (higher > 0) {
+		/* There is no free address space in this hole left
+		 * below the allocated object. Only a portion of
+		 * higher addresses is still free, so just adjust the
+		 * existing hole accordingly (change offset and size).
+		 */
+
+		hole->offset = offset + size;
+		hole->size = higher;
+
+		igt_bst_erase(offset_bst, hole->offset_ptr);
+		igt_bst_erase(size_bst, hole->size_ptr);
+
+		hole->offset_ptr = igt_bst_insert(offset_bst, hole, hole->offset);
+		hole->size_ptr = igt_bst_insert(size_bst, hole, hole->size);
+
+	} else if (lower > 0) {
+		/* The allocated block is aligned to the end of the
+		 * hole and the lower addresses are still free,
+		 * so shrink the existing hole (change size,
+		 * but not the offset).
+		 */
+
+		hole->size = lower;
+		igt_bst_erase(size_bst, hole->size_ptr);
+		hole->size_ptr = igt_bst_insert(size_bst, hole, hole->size);
+
+	} else {
+		/* There are no leftovers, just erase the hole. */
+
+		igt_bst_erase(offset_bst, hole->offset_ptr);
+		igt_bst_erase(size_bst, hole->size_ptr);
+		free(hole);
+	}
+}
+
+static void __intel_allocator_bst_add_hole(struct intel_allocator_bst *ialb,
+					   uint64_t offset, uint64_t size)
+{
+	struct igt_bst *offset_bst, *size_bst;
+	struct intel_allocator_bst_vma_hole *hole, *nxt, *prv;
+
+	offset_bst = ialb->by_offset;
+	size_bst = ialb->by_size;
+
+	prv = igt_bst_query_predecessor(offset_bst, offset);
+	if (prv && prv->offset + prv->size < offset)
+		prv = NULL;
+
+	nxt = igt_bst_query_successor(offset_bst, offset);
+	if (nxt && nxt->offset > offset + size)
+		nxt = NULL;
+
+	if (nxt && prv) {
+		/* There are holes adjacent to the new one
+		 * both below and above it in the address space.
+		 * Merge them all into a single hole:
+		 * erase the upper and increase size of the
+		 * lower one.
+		 */
+		prv->size += size + nxt->size;
+
+		igt_bst_erase(offset_bst, nxt->offset_ptr);
+		igt_bst_erase(size_bst, nxt->size_ptr);
+		free(nxt);
+
+		igt_bst_erase(size_bst, prv->size_ptr);
+		prv->size_ptr = igt_bst_insert(size_bst, prv, prv->size);
+
+	} else if (nxt) {
+		/* The only adjacent hole is above the new one,
+		 * so increase its size and update its offset.
+		 */
+		nxt->size += size;
+		nxt->offset = offset;
+
+		igt_bst_erase(offset_bst, nxt->offset_ptr);
+		igt_bst_erase(size_bst, nxt->size_ptr);
+
+		nxt->offset_ptr = igt_bst_insert(offset_bst, nxt, nxt->offset);
+		nxt->size_ptr = igt_bst_insert(size_bst, nxt, nxt->size);
+
+	} else if (prv) {
+		/* The only adjacent hole is below the new one,
+		 * just increase its size.
+		 */
+		prv->size += size;
+		igt_bst_erase(size_bst, prv->size_ptr);
+		prv->size_ptr = igt_bst_insert(size_bst, prv, prv->size);
+
+	} else {
+		/* There are no holes neighbouring the new one,
+		 * so just create a new hole.
+		 */
+		hole = malloc(sizeof(struct intel_allocator_bst_vma_hole));
+		igt_assert(hole);
+
+		hole->offset = offset;
+		hole->size = size;
+		hole->offset_ptr = igt_bst_insert(offset_bst, hole, offset);
+		hole->size_ptr = igt_bst_insert(size_bst, hole, size);
+
+	}
+}
+
+
+static void intel_allocator_bst_get_address_range(struct intel_allocator *ial,
+				      uint64_t *startp, uint64_t *endp)
+{
+	struct intel_allocator_bst *ialb = ial->priv;
+
+	if (startp)
+		*startp = ialb->start;
+
+	if (endp)
+		*endp = ialb->end;
+}
+
+static uint64_t intel_allocator_bst_alloc(struct intel_allocator *ial, uint32_t handle,
+					  uint64_t size, uint64_t alignment,
+					  enum allocator_strategy strategy)
+{
+	struct intel_allocator_bst *ialb = ial->priv;
+	struct intel_allocator_record *record;
+	struct intel_allocator_bst_vma_hole *hole;
+	uint64_t misalignment, offset;
+
+	igt_assert(size > 0);
+	alignment = (alignment > 0 ? alignment : 1);
+
+	record = igt_map_search(ialb->objects, &handle);
+
+	if (record) {
+		/* This block has already been allocated,
+		 * check that it satifies the requirements.
+		 */
+
+		igt_assert(size == record->size);
+		igt_assert(record->offset % alignment == 0);
+
+		return record->offset;
+	}
+
+	/* Look for a slightly bigger hole to make sure
+	 * the block can be aligned properly.
+	 */
+	hole = igt_bst_query_successor(ialb->by_size,
+				       size + alignment - 1);
+
+	/* Look for a smaller hole, maybe proper alignment
+	 * will still be possible.
+	 */
+	if (!hole)
+		hole = igt_bst_query_successor(ialb->by_size, size);
+
+	if (!hole)
+		return ALLOC_INVALID_ADDRESS;
+
+	if (strategy == ALLOC_STRATEGY_NONE)
+		strategy = ial->strategy;
+
+	switch (strategy) {
+	case ALLOC_STRATEGY_LOW_TO_HIGH:
+		misalignment = alignment - (hole->offset % alignment);
+		misalignment = misalignment == alignment ? 0 : misalignment;
+		offset = hole->offset + misalignment;
+
+		if (misalignment + size > hole->size)
+			return ALLOC_INVALID_ADDRESS;
+
+		break;
+	case ALLOC_STRATEGY_HIGH_TO_LOW:
+		offset = hole->offset + hole->size - size;
+		offset = offset - offset % alignment;
+
+		if (offset < hole->offset)
+			return ALLOC_INVALID_ADDRESS;
+
+		break;
+	default:
+		igt_assert_f(0, "Unsupported strategy.");
+	}
+
+	__intel_allocator_bst_alloc(ialb, hole, offset, size);
+
+	record = malloc(sizeof(struct intel_allocator_record));
+	igt_assert(record);
+	record->handle = handle;
+	record->offset = offset;
+	record->size = size;
+
+	igt_map_insert(ialb->objects, &record->handle, record);
+	ialb->allocated_objects++;
+	ialb->allocated_size += size;
+
+	return offset;
+}
+
+static bool intel_allocator_bst_is_allocated(struct intel_allocator *ial, uint32_t handle,
+					     uint64_t size, uint64_t offset)
+{
+	struct intel_allocator_bst *ialb = ial->priv;
+	struct intel_allocator_record *record;
+	bool same;
+
+	offset = DECANONICAL(offset);
+	record = igt_map_search(ialb->objects, &handle);
+	if (record) {
+		same = (record->handle == handle && record->size == size &&
+			record->offset == offset);
+	} else {
+		same = false;
+	}
+
+	return same;
+}
+
+static bool intel_allocator_bst_free(struct intel_allocator *ial, uint32_t handle)
+{
+	struct intel_allocator_bst *ialb = ial->priv;
+	struct intel_allocator_record *record;
+
+	record = igt_map_search(ialb->objects, &handle);
+
+	if (!record)
+		return false;
+
+	__intel_allocator_bst_add_hole(ialb, record->offset, record->size);
+	ialb->allocated_objects--;
+	ialb->allocated_size -= record->size;
+	igt_map_remove(ialb->objects, &handle, map_entry_free_func);
+
+	return true;
+}
+
+static bool intel_allocator_bst_reserve(struct intel_allocator *ial, uint32_t handle,
+					uint64_t start, uint64_t end)
+{
+	struct intel_allocator_bst *ialb = ial->priv;
+	struct intel_allocator_bst_vma_hole *hole;
+	struct intel_allocator_record *record;
+
+	start = DECANONICAL(start);
+	if (end != (1ull << GEN8_GTT_ADDRESS_WIDTH))
+		end = DECANONICAL(end);
+
+	igt_assert(start < end);
+	igt_assert(start >= ialb->start);
+	igt_assert(end <= ialb->end);
+
+	hole = igt_bst_query_predecessor(ialb->by_offset, start);
+	if (!hole)
+		return false;
+
+	igt_assert(hole->offset <= start);
+
+	if (hole->offset + hole->size < end)
+		return false;
+
+	__intel_allocator_bst_alloc(ialb, hole, start, end - start);
+
+	record = malloc(sizeof(struct intel_allocator_bst_vma_hole));
+	igt_assert(record);
+	record->offset = start;
+	record->size = end - start;
+	record->handle = handle;
+	igt_map_insert(ialb->reserved, &record->offset, record);
+	ialb->reserved_areas++;
+	ialb->reserved_size += end - start;
+
+	return true;
+}
+
+static bool intel_allocator_bst_unreserve(struct intel_allocator *ial, uint32_t handle,
+					  uint64_t start, uint64_t end)
+{
+	struct intel_allocator_bst *ialb = ial->priv;
+	struct intel_allocator_record *record;
+
+	start = DECANONICAL(start);
+	if (end != (1ull << GEN8_GTT_ADDRESS_WIDTH))
+		end = DECANONICAL(end);
+
+	record = igt_map_search(ialb->reserved, &start);
+
+	if (!record) {
+		igt_warn("Only a reserved block can be unreserved.\n");
+		return false;
+	}
+
+	if (record->size != end - start) {
+		igt_warn("Size of the block does not match the passed value.\n");
+		return false;
+	}
+
+	if (record->offset != start) {
+		igt_warn("Offset of the block does not match the passed value.\n");
+		return false;
+	}
+
+	if (record->handle != handle) {
+		igt_warn("Handle %u does not match the passed handle %u.\n",
+			 record->handle, handle);
+		return false;
+	}
+
+	__intel_allocator_bst_add_hole(ialb, start, end - start);
+	ialb->reserved_areas--;
+	ialb->reserved_size -= record->size;
+	igt_map_remove(ialb->reserved, &start, map_entry_free_func);
+
+	return true;
+}
+
+static bool intel_allocator_bst_is_reserved(struct intel_allocator *ial,
+					    uint64_t start, uint64_t end)
+{
+	struct intel_allocator_bst *ialb = ial->priv;
+	struct intel_allocator_record *record;
+
+	start = DECANONICAL(start);
+	if (end != (1ull << GEN8_GTT_ADDRESS_WIDTH))
+		end = DECANONICAL(end);
+
+	record = igt_map_search(ialb->reserved, &start);
+
+	if (!record)
+		return false;
+
+	if (record->offset == start && record->size == end - start)
+		return true;
+
+	return false;
+}
+
+static void intel_allocator_bst_destroy(struct intel_allocator *ial)
+{
+	struct intel_allocator_bst *ialb = ial->priv;
+	struct igt_bst *size_bst, *offset_bst;
+	void *nodeptr;
+
+	size_bst = ialb->by_size;
+	offset_bst = ialb->by_offset;
+
+	igt_bst_for_each_node(offset_bst, nodeptr)
+		free(offset_bst->get_value(nodeptr));
+
+	igt_bst_free(size_bst);
+	igt_bst_free(offset_bst);
+	free(offset_bst);
+	free(size_bst);
+
+	igt_map_destroy(ialb->objects, map_entry_free_func);
+	igt_map_destroy(ialb->reserved, map_entry_free_func);
+
+	free(ialb);
+	free(ial);
+}
+
+static bool intel_allocator_bst_is_empty(struct intel_allocator *ial)
+{
+	struct intel_allocator_bst *ialb = ial->priv;
+
+	return ialb->allocated_objects == 0 && ialb->reserved_areas == 0;
+}
+
+static void intel_allocator_bst_print(struct intel_allocator *ial, bool full)
+{
+	struct intel_allocator_bst *ialb = ial->priv;
+	struct intel_allocator_record *record;
+	struct intel_allocator_bst_vma_hole *hole;
+	struct igt_bst *offset_bst, *size_bst;
+	struct igt_map_entry *entry;
+	void *nodeptr;
+	uint64_t total_free;
+
+	igt_info("intel_allocator_bst <ial: %p, fd: %d> on "
+		 "[0x%"PRIX64" : 0x%"PRIx64"]\n", ial,
+		 ial->fd, ialb->start, ialb->end);
+
+	total_free = 0;
+	if (full) {
+		offset_bst = ialb->by_offset;
+		size_bst = ialb->by_size;
+
+		igt_info("holes by offset:\n");
+		igt_bst_for_each_node(offset_bst, nodeptr) {
+			hole = igt_bst_get_value(offset_bst, nodeptr);
+			igt_info("offset = %"PRIu64" (0x%"PRIx64") "
+				 "size = %"PRIu64" (0x%"PRIx64")\n",
+				 hole->offset, hole->offset, hole->size,
+				 hole->size);
+			total_free += hole->size;
+		}
+
+		igt_info("holes by size:\n");
+		igt_bst_for_each_node(size_bst, nodeptr) {
+			hole = igt_bst_get_value(size_bst, nodeptr);
+			igt_info("offset = %"PRIu64" (0x%"PRIx64") "
+				 "size = %"PRIu64" (0x%"PRIx64")\n",
+				 hole->offset, hole->offset, hole->size,
+				 hole->size);
+
+		}
+
+		igt_info("allocated objects:\n");
+		igt_map_foreach(ialb->objects, entry) {
+			record = entry->data;
+			igt_info("handle = %d, offset = %"PRIu64" "
+				"(0x%"PRIx64", size = %"PRIu64" (0x%"PRIx64")\n",
+				 record->handle, record->offset, record->offset,
+				 record->size, record->size);
+
+		}
+
+		igt_info("reserved areas:\n");
+		igt_map_foreach(ialb->reserved, entry) {
+			record = entry->data;
+			igt_info("handle = %d, offset = %"PRIu64" "
+				"(0x%"PRIx64", size = %"PRIu64" (0x%"PRIx64")\n",
+				 record->handle, record->offset, record->offset,
+				 record->size, record->size);
+
+		}
+
+	} else {
+		offset_bst = ialb->by_offset;
+
+		igt_bst_for_each_node(offset_bst, nodeptr) {
+			igt_bst_get_value(offset_bst, nodeptr);
+			total_free += hole->size;
+		}
+	}
+
+	igt_info("free space: %"PRIu64"B (0x%"PRIx64") (%.2f%% full)\n"
+		 "allocated objects: %"PRIu64", size: %"PRIu64
+		 " (%"PRIx64")\n"
+		 "reserved areas: %"PRIu64", size: %"PRIu64
+		 " (%"PRIx64")\n", total_free, total_free,
+		 ((double) (ialb->total_size - total_free) /
+		  (double) ialb->total_size) * 100.0,
+		 ialb->allocated_objects, ialb->allocated_size,
+		 ialb->allocated_size, ialb->reserved_areas,
+		 ialb->reserved_areas, ialb->reserved_size);
+
+	holes_bst_validate(ialb);
+}
+
+struct intel_allocator *
+intel_allocator_bst_create(int fd, uint64_t start, uint64_t end,
+			   enum allocator_strategy strategy)
+{
+	struct intel_allocator *ial;
+	struct intel_allocator_bst *ialb;
+
+	igt_debug("Using BST allocator\n");
+
+	ialb = malloc(sizeof(struct intel_allocator_bst));
+	igt_assert(ialb);
+	ial = malloc(sizeof(struct intel_allocator));
+	igt_assert(ial);
+
+	/* Allocated object are stored by 4-byte-long handles. */
+	ialb->objects = igt_map_create(hash_handles, equal_handles);
+	/* Reserved object are stored by 8-byte-long offsets. */
+	ialb->reserved = igt_map_create(hash_offsets, equal_offsets);
+	igt_assert(ialb->objects && ialb->reserved);
+
+	ialb->by_offset = igt_bst_avl_create();
+	ialb->by_size = igt_bst_avl_create();
+
+	igt_assert(start < end);
+	igt_assert(end <= IALB_MAX_ADDR);
+	ialb->start = start;
+	ialb->end = end;
+
+	ialb->total_size = ialb->end - ialb->start;
+	ialb->allocated_size = 0;
+	ialb->allocated_objects = 0;
+	ialb->reserved_size = 0;
+	ialb->reserved_areas = 0;
+	__intel_allocator_bst_add_hole(ialb, ialb->start, ialb->total_size);
+
+	ial->fd = fd;
+	ial->type = INTEL_ALLOCATOR_BST;
+	ial->strategy = strategy;
+	ial->refcount = 0;
+	ial->priv = ialb;
+	ial->get_address_range = intel_allocator_bst_get_address_range;
+	ial->alloc = intel_allocator_bst_alloc;
+	ial->is_allocated = intel_allocator_bst_is_allocated;
+	ial->free = intel_allocator_bst_free;
+	ial->reserve = intel_allocator_bst_reserve;
+	ial->unreserve = intel_allocator_bst_unreserve;
+	ial->is_reserved = intel_allocator_bst_is_reserved;
+	ial->destroy = intel_allocator_bst_destroy;
+	ial->is_empty = intel_allocator_bst_is_empty;
+	ial->print = intel_allocator_bst_print;
+
+	return ial;
+}
diff --git a/lib/meson.build b/lib/meson.build
index a1aa0ee12..62c8dbf20 100644
--- a/lib/meson.build
+++ b/lib/meson.build
@@ -38,6 +38,7 @@ lib_sources = [
 	'igt_x86.c',
 	'instdone.c',
 	'intel_allocator.c',
+	'intel_allocator_bst.c',
 	'intel_allocator_msgchannel.c',
 	'intel_allocator_random.c',
 	'intel_allocator_reloc.c',
-- 
2.25.1

_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev

[igt-dev] [PATCH i-g-t 4/5] tests/i915_api_intel_allocator: Add the BST allocator

[Andrzej Turko]

Include the BST allocator in the allocator test.

Signed-off-by: Andrzej Turko <andrzej.turko@linux.intel.com>
Cc: Zbigniew Kempczyński <zbigniew.kempczynski@intel.com>
---
 tests/i915/api_intel_allocator.c | 55 ++++++++++++++++++++------------
 1 file changed, 35 insertions(+), 20 deletions(-)

diff --git a/tests/i915/api_intel_allocator.c b/tests/i915/api_intel_allocator.c
index 4b74317ed..45e62cd59 100644
--- a/tests/i915/api_intel_allocator.c
+++ b/tests/i915/api_intel_allocator.c
@@ -25,13 +25,13 @@ static inline uint32_t gem_handle_gen(void)
 	return atomic_fetch_add(&next_handle, 1);
 }
 
-static void alloc_simple(int fd)
+static void alloc_sanity_check(int fd, uint8_t type)
 {
 	uint64_t ahnd;
 	uint64_t offset0, offset1, size = 0x1000, align = 0x1000, start, end;
 	bool is_allocated, freed;
 
-	ahnd = intel_allocator_open(fd, 0, INTEL_ALLOCATOR_SIMPLE);
+	ahnd = intel_allocator_open(fd, 0, type);
 
 	offset0 = intel_allocator_alloc(ahnd, 1, size, align);
 	offset1 = intel_allocator_alloc(ahnd, 1, size, align);
@@ -67,12 +67,12 @@ static void alloc_simple(int fd)
 	igt_assert_eq(intel_allocator_close(ahnd), true);
 }
 
-static void reserve_simple(int fd)
+static void reserve_sanity_check(int fd, uint8_t type)
 {
 	uint64_t ahnd, start, size = 0x1000;
 	bool reserved, unreserved;
 
-	ahnd = intel_allocator_open(fd, 0, INTEL_ALLOCATOR_SIMPLE);
+	ahnd = intel_allocator_open(fd, 0, type);
 	intel_allocator_get_address_range(ahnd, &start, NULL);
 
 	reserved = intel_allocator_reserve(ahnd, 0, size, start);
@@ -194,17 +194,19 @@ static void reuse(int fd, uint8_t type)
 	}
 	i--;
 
-	/* free previously allocated bo */
-	intel_allocator_free(ahnd, obj[i].handle);
-	/* alloc different buffer to fill freed hole */
-	tmp.handle = gem_handle_gen();
-	tmp.offset = intel_allocator_alloc(ahnd, tmp.handle, OBJ_SIZE, 0);
-	igt_assert(prev_offset == tmp.offset);
+	if (type == INTEL_ALLOCATOR_SIMPLE) {
+		/* free previously allocated bo */
+		intel_allocator_free(ahnd, obj[i].handle);
+		/* alloc different buffer to fill freed hole */
+		tmp.handle = gem_handle_gen();
+		tmp.offset = intel_allocator_alloc(ahnd, tmp.handle, OBJ_SIZE, 0);
+		igt_assert(prev_offset == tmp.offset);
 
-	obj[i].offset = intel_allocator_alloc(ahnd, obj[i].handle,
-					      obj[i].size, 0);
-	igt_assert(prev_offset != obj[i].offset);
-	intel_allocator_free(ahnd, tmp.handle);
+		obj[i].offset = intel_allocator_alloc(ahnd, obj[i].handle,
+						      obj[i].size, 0);
+		igt_assert(prev_offset != obj[i].offset);
+		intel_allocator_free(ahnd, tmp.handle);
+	}
 
 	for (i = 0; i < 128; i++)
 		intel_allocator_free(ahnd, obj[i].handle);
@@ -665,6 +667,7 @@ struct allocators {
 	{"simple", INTEL_ALLOCATOR_SIMPLE},
 	{"reloc",  INTEL_ALLOCATOR_RELOC},
 	{"random", INTEL_ALLOCATOR_RANDOM},
+	{"bst", INTEL_ALLOCATOR_BST},
 	{NULL, 0},
 };
 
@@ -679,18 +682,30 @@ igt_main
 		srandom(0xdeadbeef);
 	}
 
-	igt_subtest_f("alloc-simple")
-		alloc_simple(fd);
+	igt_subtest_f("alloc-sanity-check-simple")
+		alloc_sanity_check(fd, INTEL_ALLOCATOR_SIMPLE);
 
-	igt_subtest_f("reserve-simple")
-		reserve_simple(fd);
+	igt_subtest_f("alloc-sanity-check-bst")
+		alloc_sanity_check(fd, INTEL_ALLOCATOR_BST);
+
+	igt_subtest_f("reserve-sanity-check-simple")
+		reserve_sanity_check(fd, INTEL_ALLOCATOR_SIMPLE);
+
+	igt_subtest_f("reserve-sanity-check-bst")
+		reserve_sanity_check(fd, INTEL_ALLOCATOR_BST);
 
-	igt_subtest_f("reuse")
+	igt_subtest_f("reuse-simple")
 		reuse(fd, INTEL_ALLOCATOR_SIMPLE);
 
-	igt_subtest_f("reserve")
+	igt_subtest_f("reuse-bst")
+		reuse(fd, INTEL_ALLOCATOR_BST);
+
+	igt_subtest_f("reserve-simple")
 		reserve(fd, INTEL_ALLOCATOR_SIMPLE);
 
+	igt_subtest_f("reserve-bst")
+		reserve(fd, INTEL_ALLOCATOR_BST);
+
 	for (a = als; a->name; a++) {
 		igt_subtest_with_dynamic_f("%s-allocator", a->name) {
 			igt_dynamic("basic")
-- 
2.25.1

_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev

[igt-dev] [PATCH i-g-t 5/5] benchmarks/intel_allocator: Test the allocator performance

[Andrzej Turko]

This tests the allocator with regard to
both performance and efficient use of the
address space.

Signed-off-by: Andrzej Turko <andrzej.turko@linux.intel.com>
Cc: Zbigniew Kempczyński <zbigniew.kempczynski@intel.com>
---
 benchmarks/intel_allocator.c | 756 +++++++++++++++++++++++++++++++++++
 benchmarks/meson.build       |   1 +
 2 files changed, 757 insertions(+)
 create mode 100644 benchmarks/intel_allocator.c

diff --git a/benchmarks/intel_allocator.c b/benchmarks/intel_allocator.c
new file mode 100644
index 000000000..00bb2074e
--- /dev/null
+++ b/benchmarks/intel_allocator.c
@@ -0,0 +1,756 @@
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright © 2021 Intel Corporation
+ */
+
+#include "igt.h"
+#include "igt_map.h"
+#include "intel_allocator.h"
+
+//#define DBG
+#ifdef DBG
+#define ial_debug(...) fprintf(stderr, __VA_ARGS__)
+#define echo_query(...) fprintf(stderr, __VA_ARGS__)
+#else
+#define ial_debug(...) {}
+#define echo_query(...) {}
+#endif
+
+static _Atomic(uint32_t) next_handle;
+
+static inline uint32_t gem_handle_gen(void)
+{
+	return atomic_fetch_add(&next_handle, 1);
+}
+
+struct validated_allocator {
+	struct igt_list_head allocated;
+	struct igt_list_head reserved;
+
+	uint64_t allocator_handle;
+	uint64_t vas_start;
+	uint64_t vas_end;
+};
+
+struct va_block {
+	uint64_t offset;
+	uint64_t size;
+	uint32_t handle;
+	struct igt_list_head link;
+};
+
+struct alloc_block {
+	uint64_t size;
+	uint32_t handle;
+	struct igt_list_head link;
+};
+
+struct rsvd_block {
+	uint64_t size;
+	uint64_t offset;
+	uint32_t handle;
+};
+
+#define QUERY_ALLOC 1
+#define QUERY_FREE 2
+#define QUERY_IS_ALLOCATED 3
+#define QUERY_RESERVE 4
+#define QUERY_UNRESERVE 5
+#define QUERY_IS_RESERVED 6
+
+#define MAXTESTLEN (1 << 24)
+#define NO_CHECK 0
+#define CURSORY_CHECK 1
+#define THOROUGH_CHECK 2
+
+struct allocator_query {
+	int type;
+
+	union {
+		struct {
+			uint32_t handle;
+			uint64_t size;
+			uint64_t alignment;
+		} alloc;
+		struct {
+			uint32_t handle;
+		} free;
+		struct {
+			uint32_t handle;
+			uint64_t size;
+			uint64_t offset;
+		} is_allocated;
+		struct {
+			uint32_t handle;
+			uint64_t size;
+			uint64_t offset;
+		} reserve;
+		struct {
+			uint32_t handle;
+			uint64_t size;
+			uint64_t offset;
+		} unreserve;
+		struct {
+			uint64_t size;
+			uint64_t offset;
+		} is_reserved;
+	};
+};
+
+static void validate_allocator(struct validated_allocator *va)
+{
+	struct va_block *a, *b;
+	int same;
+	bool is_allocated, is_reserved;
+
+	igt_list_for_each_entry(a, &va->allocated, link) {
+
+		igt_assert(a->offset + a->size > a->offset);
+		same = 0;
+		igt_list_for_each_entry(b, &va->allocated, link) {
+
+			if (a->handle == b->handle) {
+				same++;
+			} else {
+				igt_assert_f((a->offset < b->offset &&
+					      a->offset + a->size <= b->offset) ||
+					     (b->offset < a->offset &&
+					      b->offset + b->size <= a->offset),
+					     "Two allocated blocks overlap");
+			}
+		}
+		igt_assert_f(same == 1, "A handle appears more than once.\n");
+	}
+
+	igt_list_for_each_entry(a, &va->reserved, link) {
+
+		igt_assert(a->offset + a->size > a->offset);
+		same = 0;
+		igt_list_for_each_entry(b, &va->reserved, link) {
+
+			if (a->offset == b->offset) {
+				same++;
+			} else {
+				igt_assert_f((a->offset < b->offset &&
+					      a->offset + a->size <= b->offset) ||
+					     (b->offset < a->offset &&
+					      b->offset + b->size <= a->offset),
+					     "Two reserved areas overlap");
+			}
+		}
+		igt_assert_f(same == 1, "The same area has been reserved more than once.\n");
+	}
+
+	igt_list_for_each_entry(a, &va->reserved, link) {
+		igt_list_for_each_entry(b, &va->allocated, link) {
+
+			igt_assert_f((a->offset < b->offset &&
+				      a->offset + a->size <= b->offset) ||
+				     (b->offset < a->offset &&
+				      b->offset + b->size <= a->offset),
+				     "An allocated block overlaps with a reserved area.\n");
+		}
+	}
+
+	igt_list_for_each_entry(a, &va->reserved, link) {
+		is_reserved = intel_allocator_is_reserved(va->allocator_handle,
+							  a->size,
+							  a->offset);
+		igt_assert_f(is_reserved, "The allocator has not reported a reserved area.\n");
+	}
+
+	igt_list_for_each_entry(a, &va->allocated, link) {
+		is_allocated = intel_allocator_is_allocated(va->allocator_handle,
+							    a->handle,
+							    a->size,
+							    a->offset);
+		igt_assert_f(is_allocated, "The allocator has not reported an allocated block.\n");
+	}
+}
+
+static struct va_block
+*get_by_handle(struct igt_list_head *list, uint32_t handle)
+{
+	struct va_block *entry;
+
+	igt_list_for_each_entry(entry, list, link) {
+		if (entry->handle == handle)
+			return entry;
+	}
+	return NULL;
+}
+
+static struct va_block
+*get_by_offset(struct igt_list_head *list, uint64_t offset)
+{
+	struct va_block *entry;
+
+	igt_list_for_each_entry(entry, list, link) {
+		if (entry->offset == offset)
+			return entry;
+	}
+	return NULL;
+}
+
+static struct va_block
+*get_overlapping(struct igt_list_head *list, uint64_t offset, uint64_t size)
+{
+	struct va_block *entry;
+	uint64_t start, end;
+	bool overlaps;
+
+	igt_list_for_each_entry(entry, list, link) {
+		start = entry->offset;
+		end = entry->offset + entry->size;
+
+		overlaps = ((start >= offset && start < offset + size) ||
+			    (end > offset && end <= offset + size));
+
+		if (overlaps)
+			return entry;
+	}
+	return NULL;
+}
+
+static uint64_t
+validated_allocator_alloc(struct validated_allocator *va, uint32_t handle,
+					  uint64_t size, uint64_t alignment)
+{
+	struct va_block *block;
+	uint64_t offset;
+
+	offset = __intel_allocator_alloc(va->allocator_handle, handle,
+					 size, alignment, ALLOC_STRATEGY_NONE);
+
+	block = get_by_handle(&va->allocated, handle);
+	if (block) {
+		igt_assert(block->offset == offset);
+		return offset;
+	}
+
+	/* not enough space */
+	if (offset == ALLOC_INVALID_ADDRESS)
+		return ALLOC_INVALID_ADDRESS;
+
+	igt_assert(offset >= va->vas_start &&
+		   offset + size <= va->vas_end);
+
+	if (alignment > 0)
+		igt_assert(offset % alignment == 0);
+
+	/* check that no allocated block overlaps */
+	igt_assert(!get_overlapping(&va->allocated, offset, size));
+	/* check that no reserved area overlaps */
+	igt_assert(!get_overlapping(&va->reserved, offset, size));
+
+	block = (struct va_block *) malloc(sizeof(struct va_block));
+	igt_assert(block);
+	block->offset = offset;
+	block->size = size;
+	block->handle = handle;
+	igt_list_add(&block->link, &va->allocated);
+
+	return offset;
+}
+
+static bool
+validated_allocator_free(struct validated_allocator *va, uint32_t handle)
+{
+	struct va_block *block;
+
+	block = get_by_handle(&va->allocated, handle);
+
+	if (block) {
+		igt_list_del(&block->link);
+		free(block);
+		igt_assert(intel_allocator_free(va->allocator_handle, handle));
+		return true;
+	} else {
+		igt_assert(!intel_allocator_free(va->allocator_handle, handle));
+		return false;
+	}
+}
+
+static bool
+validated_allocator_is_allocated(struct validated_allocator *va, uint32_t handle,
+				 uint64_t size, uint64_t offset)
+{
+	struct va_block *block;
+	bool is_allocated;
+
+	block = get_by_handle(&va->allocated, handle);
+
+	is_allocated =  (block && block->size == size &&
+			 block->offset == offset);
+
+	igt_assert(is_allocated == intel_allocator_is_allocated(va->allocator_handle,
+								handle, size, offset));
+
+	return is_allocated;
+}
+
+static bool
+validated_allocator_reserve(struct validated_allocator *va, uint32_t handle,
+			    uint64_t size, uint64_t offset)
+{
+	struct va_block *block;
+	bool reserved;
+
+	reserved = intel_allocator_reserve(va->allocator_handle, handle,
+					   size, offset);
+	if (!reserved) {
+		if (offset >= va->vas_start && offset + size <= va->vas_end)
+			igt_assert(get_overlapping(&va->reserved, offset, size) ||
+				   get_overlapping(&va->allocated, offset, size));
+
+		return false;
+	}
+	igt_assert(!get_overlapping(&va->allocated, offset, size));
+	igt_assert(!get_overlapping(&va->reserved, offset, size));
+
+	block = (struct va_block *) malloc(sizeof(struct va_block));
+	igt_assert(block);
+	block->handle = handle;
+	block->offset = offset;
+	block->size = size;
+	igt_list_add(&block->link, &va->reserved);
+
+	return true;
+}
+
+static bool
+validated_allocator_unreserve(struct validated_allocator *va, uint32_t handle,
+			      uint64_t size, uint64_t offset)
+{
+	struct va_block *block;
+
+	block = get_by_offset(&va->reserved, offset);
+
+	if (block && block->size == size && block->handle == handle) {
+		igt_assert(intel_allocator_unreserve(va->allocator_handle,
+						     handle, size, offset));
+		igt_list_del(&block->link);
+		free(block);
+		return true;
+	} else {
+		igt_assert(!intel_allocator_unreserve(va->allocator_handle,
+						      handle, size, offset));
+		return false;
+	}
+}
+
+static bool
+validated_allocator_is_reserved(struct validated_allocator *va,
+			    uint64_t size, uint64_t offset)
+{
+	struct va_block *block;
+	bool is_reserved;
+
+	block = get_by_offset(&va->reserved, offset);
+	is_reserved = (block && block->size == size);
+	igt_assert(is_reserved == intel_allocator_is_reserved(va->allocator_handle,
+							      size, offset));
+	return is_reserved;
+}
+
+static struct validated_allocator
+*validated_allocator_create(int fd, int allocator_type)
+{
+	struct validated_allocator *va;
+
+	va = (struct validated_allocator *) malloc(sizeof (struct validated_allocator));
+	igt_assert(va);
+	IGT_INIT_LIST_HEAD(&va->allocated);
+	IGT_INIT_LIST_HEAD(&va->reserved);
+
+	va->allocator_handle = intel_allocator_open(fd, 0, allocator_type);
+	intel_allocator_get_address_range(va->allocator_handle,
+					  &va->vas_start,
+					  &va->vas_end);
+
+	return va;
+}
+
+static bool validated_allocator_destroy(struct validated_allocator *va)
+{
+	bool is_empty;
+	struct va_block *entry, *tmp;
+
+	is_empty = igt_list_empty(&va->allocated) &&
+		   igt_list_empty(&va->reserved);
+	igt_assert_eq(is_empty, intel_allocator_close(va->allocator_handle));
+
+	igt_list_for_each_entry_safe(entry, tmp, &va->allocated, link) {
+		igt_list_del(&entry->link);
+		free(entry);
+	}
+
+	igt_list_for_each_entry_safe(entry, tmp, &va->reserved, link) {
+		igt_list_del(&entry->link);
+		free(entry);
+	}
+
+	free(va);
+	return is_empty;
+}
+
+static void get_device_address_range(int fd, uint64_t *start, uint64_t *end)
+{
+	uint64_t ahnd;
+
+	ahnd = intel_allocator_open(fd, 0, INTEL_ALLOCATOR_SIMPLE);
+	intel_allocator_get_address_range(ahnd, start, end);
+	intel_allocator_close(ahnd);
+}
+
+static void
+execute_test_no_check(int fd, int alloc_type, int nqueries,
+		      struct allocator_query *queries)
+{
+	uint64_t ahnd;
+	uint64_t offset;
+	uint64_t allocated_mem = 0, requested_mem = 0;
+	uint32_t real_allocs = 0, requested_allocs = 0;
+	int i = 0;
+
+	ahnd = intel_allocator_open(fd, 0, alloc_type);
+
+	for (i = 0; i < nqueries; i++) {
+
+		switch(queries[i].type) {
+		case QUERY_ALLOC:
+			offset = __intel_allocator_alloc(ahnd, queries[i].alloc.handle,
+							 queries[i].alloc.size,
+							 queries[i].alloc.alignment,
+							 ALLOC_STRATEGY_NONE);
+
+			allocated_mem += (offset == ALLOC_INVALID_ADDRESS ?
+						  0 : queries[i].alloc.size);
+			requested_mem += queries[i].alloc.size;
+			real_allocs += (offset == ALLOC_INVALID_ADDRESS ? 0 : 1);
+			requested_allocs += 1;
+			break;
+		case QUERY_FREE:
+			intel_allocator_free(ahnd, queries[i].free.handle);
+			break;
+		case QUERY_IS_ALLOCATED:
+			intel_allocator_is_allocated(ahnd, queries[i].is_allocated.handle,
+						     queries[i].is_allocated.size,
+						     queries[i].is_allocated.offset);
+			break;
+		case QUERY_RESERVE:
+			intel_allocator_reserve(ahnd, queries[i].reserve.handle,
+						queries[i].reserve.size,
+						queries[i].reserve.offset);
+			break;
+		case QUERY_UNRESERVE:
+			intel_allocator_unreserve(ahnd, queries[i].unreserve.handle,
+						  queries[i].unreserve.size,
+						  queries[i].unreserve.offset);
+			break;
+		case QUERY_IS_RESERVED:
+			intel_allocator_is_reserved(ahnd, queries[i].is_reserved.size,
+						    queries[i].is_reserved.offset);
+			break;
+		}
+	}
+	intel_allocator_close(ahnd);
+
+	igt_info("Test summary: %d allocations out of %d succedded (%f %%)\n",
+		 real_allocs, requested_allocs,
+		 ((float) real_allocs * 100) / (float) requested_allocs);
+
+}
+
+static void
+execute_test_check(int fd, int alloc_type, int nqueries,
+		   struct allocator_query *queries, int mode)
+{
+	struct validated_allocator *va;
+	uint64_t offset;
+	uint64_t allocated_mem = 0, requested_mem = 0;
+	uint32_t real_allocs = 0, requested_allocs = 0;
+	int i = 0;
+
+	va = validated_allocator_create(fd, alloc_type);
+
+	for (i = 0; i < nqueries; i++) {
+
+		ial_debug("\n");
+		switch(queries[i].type) {
+		case QUERY_ALLOC:
+			ial_debug("Alloc %d 0x%llx (0x%llx)\n", queries[i].alloc.handle,
+				  queries[i].alloc.size, queries[i].alloc.alignment);
+			offset = validated_allocator_alloc(va, queries[i].alloc.handle,
+							   queries[i].alloc.size,
+							   queries[i].alloc.alignment);
+
+			allocated_mem += (offset == ALLOC_INVALID_ADDRESS ?
+						  0 : queries[i].alloc.size);
+			requested_mem += queries[i].alloc.size;
+			real_allocs += (offset == ALLOC_INVALID_ADDRESS ? 0 : 1);
+			requested_allocs += 1;
+			break;
+		case QUERY_FREE:
+			ial_debug("Free %d\n", queries[i].free.handle);
+			validated_allocator_free(va, queries[i].free.handle);
+			break;
+		case QUERY_IS_ALLOCATED:
+			validated_allocator_is_allocated(va, queries[i].is_allocated.handle,
+							 queries[i].is_allocated.size,
+							 queries[i].is_allocated.offset);
+			break;
+		case QUERY_RESERVE:
+			ial_debug ("Reserve %d 0x%llx + 0x%llx\n", queries[i].reserve.handle,
+				   queries[i].reserve.size, queries[i].reserve.offset);
+			validated_allocator_reserve(va, queries[i].reserve.handle,
+						    queries[i].reserve.size,
+						    queries[i].reserve.offset);
+			break;
+		case QUERY_UNRESERVE:
+			ial_debug ("Unreserve %d 0x%llx 0x%llx\n", queries[i].reserve.handle,
+				   queries[i].reserve.size, queries[i].reserve.offset);
+			validated_allocator_unreserve(va, queries[i].unreserve.handle,
+						      queries[i].unreserve.size,
+						      queries[i].unreserve.offset);
+			break;
+		case QUERY_IS_RESERVED:
+			validated_allocator_is_reserved(va, queries[i].is_reserved.size,
+							queries[i].is_reserved.offset);
+			break;
+		}
+
+		if (mode == THOROUGH_CHECK) validate_allocator(va);
+	}
+
+	validated_allocator_destroy(va);
+
+	igt_info("Test summary: %d allocations out of %d succedded (%f %%)\n",
+		 real_allocs, requested_allocs,
+		 ((float) real_allocs * 100) / (float) requested_allocs);
+}
+
+static void
+execute_test(int fd, int alloc_type, int nqueries,
+	     struct allocator_query *queries, int mode)
+{
+	if (mode == NO_CHECK)
+		execute_test_no_check(fd, alloc_type, nqueries, queries);
+	else
+		execute_test_check(fd, alloc_type, nqueries, queries, mode);
+}
+
+static uint64_t randu64(void)
+{
+	uint64_t x = 0;
+	int rnd_bits = igt_fls(RAND_MAX);
+
+	for (int i = 0; i < 64; i += rnd_bits)
+		x = (x << rnd_bits) + rand();
+
+	return x;
+}
+
+static int
+create_simple_test(int fd, uint64_t min_size, int nq_stage,
+		   struct allocator_query *queries)
+{
+	uint64_t start, end, size, offset, free_space;
+	int i, j, stages, nq, objcount;
+	int perm[64];
+	uint64_t offsets[64], sizes[64];
+	struct igt_list_head alloc_list;
+	struct alloc_block *block, *entry;
+
+	IGT_INIT_LIST_HEAD(&alloc_list);
+	igt_assert(min_size > 0);
+	get_device_address_range(fd, &start, &end);
+
+	stages = 0;
+	for (size = min_size; start + size * 2ULL <= end; size *= 2ULL) {
+		perm[stages] = stages;
+		sizes[stages++] = size;
+	}
+
+	perm[stages] = stages;
+	sizes[stages++] = end - start - (size - min_size);
+	igt_permute_array(perm, stages, igt_exchange_int);
+	offset = start;
+
+	for (i = 0; i < stages; i++) {
+		offsets[perm[i]] = offset;
+		offset += sizes[perm[i]];
+	}
+
+	nq = 0;
+	for (i = 0; i < stages; i++) {
+		queries[nq].type = QUERY_RESERVE;
+		queries[nq].reserve.size = sizes[i];
+		queries[nq].reserve.offset = offsets[i];
+		queries[nq].reserve.handle = -1;
+		nq++;
+	}
+
+	free_space = 0;
+	objcount = 0;
+	for (i = 0; i < stages; i++) {
+
+		queries[nq].type = QUERY_UNRESERVE;
+		queries[nq].unreserve.size = sizes[i];
+		queries[nq].unreserve.offset = offsets[i];
+		queries[nq].unreserve.handle = -1;
+		nq++;
+		free_space += sizes[i];
+
+		for (j = nq_stage; j > 0; j--) {
+
+			if (objcount > 0 && rand() % 4 == 0) {
+
+				igt_list_for_each_entry(entry, &alloc_list, link) {
+					block = entry;
+					if (rand() % 10 == 0)
+						break;
+				}
+				igt_assert(block);
+				queries[nq].type = QUERY_FREE;
+				queries[nq].free.handle = block->handle;
+				nq++;
+
+				objcount--;
+				free_space += block->size;
+				igt_list_del(&block->link);
+				free(block);
+
+			} else if (free_space > 0) {
+
+				block = malloc(sizeof(struct alloc_block));
+				igt_assert(block);
+				block->handle = gem_handle_gen();
+				block->size = randu64() % free_space + 1;
+
+				igt_list_add(&block->link, &alloc_list);
+				objcount++;
+				free_space -= block->size;
+				queries[nq].type = QUERY_ALLOC;
+				queries[nq].alloc.size = block->size;
+				queries[nq].alloc.alignment = 1<<(rand() % 8);
+				queries[nq].alloc.handle = block->handle;
+				nq++;
+			}
+		}
+	}
+
+	igt_list_for_each_entry_safe(entry, block, &alloc_list, link) {
+		igt_list_del(&entry->link);
+		free(entry);
+	}
+
+	return nq;
+}
+
+static void basic_test(int fd, int alloc_type)
+{
+	struct validated_allocator *va;
+	uint64_t offsets[5];
+	bool reserved;
+
+	va = validated_allocator_create(fd, alloc_type);
+
+	offsets[1] = validated_allocator_alloc(va, 1, 123, 8);
+	igt_assert(offsets[1] != ALLOC_INVALID_ADDRESS);
+
+	offsets[2] = validated_allocator_alloc(va, 2, 123, 8);
+	igt_assert(offsets[2] != ALLOC_INVALID_ADDRESS);
+
+	reserved = validated_allocator_reserve(va, -1, 128, 1024);
+
+	igt_assert(validated_allocator_is_allocated(va, 1, 123, offsets[1]));
+	igt_assert(!validated_allocator_is_allocated(va, 2, 120, offsets[2]));
+	igt_assert(!validated_allocator_is_allocated(va, 2, 123, offsets[1]));
+	igt_assert(!validated_allocator_is_allocated(va, 3, 123, offsets[2]));
+
+	igt_assert(validated_allocator_free(va, 1));
+	igt_assert(validated_allocator_free(va, 2));
+	igt_assert(!validated_allocator_free(va, 1));
+
+	igt_assert(reserved == validated_allocator_unreserve(va, -1, 128, 1024));
+
+	igt_assert(validated_allocator_reserve(va, 1, 300, 2047));
+	igt_assert(validated_allocator_reserve(va, 2, 450, 1024));
+	igt_assert(!validated_allocator_reserve(va, 3, 20, 1005));
+
+	igt_assert(!validated_allocator_unreserve(va, 1, 540, 1024));
+	igt_assert(validated_allocator_unreserve(va, 1, 300, 2047));
+	igt_assert(!validated_allocator_unreserve(va, 2, 450, 2047));
+	igt_assert(validated_allocator_unreserve(va, 2, 450, 1024));
+
+	offsets[1] = validated_allocator_alloc(va, 2, 500, 32);
+
+	if (offsets[1] + 500 > offsets[1]) {
+		validated_allocator_reserve(va, -1, 100, offsets[1]+499);
+		validated_allocator_reserve(va, -1, 100, offsets[1]+500);
+	}
+
+	if (offsets[1] >= 100) {
+		validated_allocator_reserve(va, -1, 100, offsets[1] - 99);
+		validated_allocator_reserve(va, -1, 100, offsets[1] - 100);
+	}
+
+	igt_assert(!validated_allocator_destroy(va));
+}
+
+struct allocator_query query_array[MAXTESTLEN];
+
+struct allocators {
+	const char *name;
+	uint8_t type;
+} als[] = {
+	{"simple", INTEL_ALLOCATOR_SIMPLE},
+	{"bst", INTEL_ALLOCATOR_BST},
+	{NULL, 0},
+};
+
+igt_main
+{
+	int fd;
+	int testlen;
+	struct allocators *a;
+
+	igt_fixture {
+		fd = drm_open_driver(DRIVER_INTEL);
+		atomic_init(&next_handle, 1);
+		srandom(0xdeadbeef);
+	}
+
+	igt_subtest_with_dynamic("basic") {
+		for (a = als; a->name; a++) {
+			igt_dynamic_f("%s-allocator", a->name)
+				basic_test(fd, a->type);
+		}
+	}
+
+	igt_subtest_with_dynamic("short") {
+		testlen = create_simple_test(fd, 1ULL << 10,
+					     80, query_array);
+
+		for (a = als; a->name; a++) {
+			igt_dynamic_f("%s-allocator", a->name)
+					execute_test(fd, a->type, testlen,
+						     query_array, THOROUGH_CHECK);
+		}
+	}
+
+	igt_subtest_with_dynamic("long") {
+		testlen = create_simple_test(fd, 1ULL << 6,
+					     200000, query_array);
+
+		for (a = als; a->name; a++) {
+			igt_dynamic_f("%s-allocator", a->name)
+					execute_test(fd, a->type, testlen,
+						     query_array, NO_CHECK);
+		}
+	}
+
+	igt_fixture
+		close(fd);
+}
diff --git a/benchmarks/meson.build b/benchmarks/meson.build
index 98a08e25c..e084cb2ce 100644
--- a/benchmarks/meson.build
+++ b/benchmarks/meson.build
@@ -13,6 +13,7 @@ benchmark_progs = [
 	'gem_syslatency',
 	'gem_userptr_benchmark',
 	'gem_wsim',
+	'intel_allocator',
 	'kms_vblank',
 	'prime_lookup',
 	'vgem_mmap',
-- 
2.25.1

_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev

[igt-dev] ✓ Fi.CI.BAT: success for Implement the BST allocator

[Patchwork]

[-- Attachment #1.1: Type: text/plain, Size: 3413 bytes --]

== Series Details ==

Series: Implement the BST allocator
URL   : https://patchwork.freedesktop.org/series/93125/
State : success

== Summary ==

CI Bug Log - changes from CI_DRM_10411 -> IGTPW_6071
====================================================

Summary
-------

  **SUCCESS**

  No regressions found.

  External URL: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/index.html

Known issues
------------

  Here are the changes found in IGTPW_6071 that come from known issues:

### IGT changes ###

#### Issues hit ####

  * igt@i915_module_load@reload:
    - fi-tgl-y:           [PASS][1] -> [DMESG-WARN][2] ([i915#1982] / [k.org#205379])
   [1]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/fi-tgl-y/igt@i915_module_load@reload.html
   [2]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/fi-tgl-y/igt@i915_module_load@reload.html

  * igt@runner@aborted:
    - fi-bdw-5557u:       NOTRUN -> [FAIL][3] ([i915#1602] / [i915#2029])
   [3]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/fi-bdw-5557u/igt@runner@aborted.html

  
#### Possible fixes ####

  * igt@gem_exec_suspend@basic-s3:
    - fi-tgl-u2:          [FAIL][4] ([i915#1888]) -> [PASS][5]
   [4]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/fi-tgl-u2/igt@gem_exec_suspend@basic-s3.html
   [5]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/fi-tgl-u2/igt@gem_exec_suspend@basic-s3.html

  * igt@i915_selftest@live@hangcheck:
    - {fi-hsw-gt1}:       [DMESG-WARN][6] ([i915#3303]) -> [PASS][7]
   [6]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/fi-hsw-gt1/igt@i915_selftest@live@hangcheck.html
   [7]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/fi-hsw-gt1/igt@i915_selftest@live@hangcheck.html

  
  {name}: This element is suppressed. This means it is ignored when computing
          the status of the difference (SUCCESS, WARNING, or FAILURE).

  [i915#1602]: https://gitlab.freedesktop.org/drm/intel/issues/1602
  [i915#1888]: https://gitlab.freedesktop.org/drm/intel/issues/1888
  [i915#1982]: https://gitlab.freedesktop.org/drm/intel/issues/1982
  [i915#2029]: https://gitlab.freedesktop.org/drm/intel/issues/2029
  [i915#3303]: https://gitlab.freedesktop.org/drm/intel/issues/3303
  [k.org#205379]: https://bugzilla.kernel.org/show_bug.cgi?id=205379


Participating hosts (41 -> 36)
------------------------------

  Missing    (5): fi-ilk-m540 fi-hsw-4200u fi-bsw-cyan fi-ctg-p8600 fi-bdw-samus 


Build changes
-------------

  * CI: CI-20190529 -> None
  * IGT: IGT_6153 -> IGTPW_6071

  CI-20190529: 20190529
  CI_DRM_10411: 2c25ff42a7175b652d93ac3555d4ae13456beb4a @ git://anongit.freedesktop.org/gfx-ci/linux
  IGTPW_6071: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/index.html
  IGT_6153: a5dffe7499a2f7189718ddf1ccf49060b7c1529d @ https://gitlab.freedesktop.org/drm/igt-gpu-tools.git



== Testlist changes ==

+igt@api_intel_allocator@alloc-sanity-check-bst
+igt@api_intel_allocator@alloc-sanity-check-simple
+igt@api_intel_allocator@bst-allocator
+igt@api_intel_allocator@reserve-bst
+igt@api_intel_allocator@reserve-sanity-check-bst
+igt@api_intel_allocator@reserve-sanity-check-simple
+igt@api_intel_allocator@reuse-bst
+igt@api_intel_allocator@reuse-simple
-igt@api_intel_allocator@alloc-simple
-igt@api_intel_allocator@reserve
-igt@api_intel_allocator@reuse

== Logs ==

For more details see: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/index.html

[-- Attachment #1.2: Type: text/html, Size: 4169 bytes --]

[-- Attachment #2: Type: text/plain, Size: 154 bytes --]

_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev

[igt-dev] ✗ GitLab.Pipeline: warning for Implement the BST allocator

[Patchwork]

== Series Details ==

Series: Implement the BST allocator
URL   : https://patchwork.freedesktop.org/series/93125/
State : warning

== Summary ==

Pipeline status: FAILED.

see https://gitlab.freedesktop.org/gfx-ci/igt-ci-tags/-/pipelines/369421 for the overview.

test:ninja-test has failed (https://gitlab.freedesktop.org/gfx-ci/igt-ci-tags/-/jobs/12267483):
  
    9/305 lib igt_exit_handler                    TIMEOUT 30.08 s 
  
  --- command ---
  /builds/gfx-ci/igt-ci-tags/build/lib/tests/igt_exit_handler
  -------
  
   10/305 lib igt_fork                            TIMEOUT 30.03 s 
  
  --- command ---
  /builds/gfx-ci/igt-ci-tags/build/lib/tests/igt_fork
  -------
  
  Full log written to /builds/gfx-ci/igt-ci-tags/build/meson-logs/testlog.txt
  FAILED: meson-test 
  /usr/bin/meson test --no-rebuild --print-errorlogs
  ninja: build stopped: subcommand failed.
  section_end:1627497159:step_script
  ERROR: Job failed: execution took longer than 1h0m0s seconds
  

test:ninja-test-armhf has failed (https://gitlab.freedesktop.org/gfx-ci/igt-ci-tags/-/jobs/12267821):
      return options.run_func(options)
    File "/usr/lib/python3/dist-packages/mesonbuild/mtest.py", line 805, in run
      return th.doit()
    File "/usr/lib/python3/dist-packages/mesonbuild/mtest.py", line 555, in doit
      self.run_tests(tests)
    File "/usr/lib/python3/dist-packages/mesonbuild/mtest.py", line 715, in run_tests
      self.drain_futures(futures)
    File "/usr/lib/python3/dist-packages/mesonbuild/mtest.py", line 732, in drain_futures
      self.print_stats(numlen, tests, name, result.result(), i)
    File "/usr/lib/python3/dist-packages/mesonbuild/mtest.py", line 505, in print_stats
      result_str += "\n\n" + result.get_log()
    File "/usr/lib/python3/dist-packages/mesonbuild/mtest.py", line 178, in get_log
      res += self.stde
  TypeError: can only concatenate str (not "bytes") to str
  FAILED: meson-test 
  /usr/bin/meson test --no-rebuild --print-errorlogs
  ninja: build stopped: subcommand failed.
  section_end:1627497278:step_script
  ERROR: Job failed: execution took longer than 1h0m0s seconds
  

test:ninja-test-minimal has failed (https://gitlab.freedesktop.org/gfx-ci/igt-ci-tags/-/jobs/12267484):
      return options.run_func(options)
    File "/usr/lib/python3/dist-packages/mesonbuild/mtest.py", line 805, in run
      return th.doit()
    File "/usr/lib/python3/dist-packages/mesonbuild/mtest.py", line 555, in doit
      self.run_tests(tests)
    File "/usr/lib/python3/dist-packages/mesonbuild/mtest.py", line 715, in run_tests
      self.drain_futures(futures)
    File "/usr/lib/python3/dist-packages/mesonbuild/mtest.py", line 732, in drain_futures
      self.print_stats(numlen, tests, name, result.result(), i)
    File "/usr/lib/python3/dist-packages/mesonbuild/mtest.py", line 505, in print_stats
      result_str += "\n\n" + result.get_log()
    File "/usr/lib/python3/dist-packages/mesonbuild/mtest.py", line 178, in get_log
      res += self.stde
  TypeError: can only concatenate str (not "bytes") to str
  FAILED: meson-test 
  /usr/bin/meson test --no-rebuild --print-errorlogs
  ninja: build stopped: subcommand failed.
  section_end:1627497165:step_script
  ERROR: Job failed: execution took longer than 1h0m0s seconds

== Logs ==

For more details see: https://gitlab.freedesktop.org/gfx-ci/igt-ci-tags/-/pipelines/369421
_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev

[igt-dev] ✓ Fi.CI.IGT: success for Implement the BST allocator

[Patchwork]

[-- Attachment #1.1: Type: text/plain, Size: 30245 bytes --]

== Series Details ==

Series: Implement the BST allocator
URL   : https://patchwork.freedesktop.org/series/93125/
State : success

== Summary ==

CI Bug Log - changes from CI_DRM_10411_full -> IGTPW_6071_full
====================================================

Summary
-------

  **SUCCESS**

  No regressions found.

  External URL: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/index.html

New tests
---------

  New tests have been introduced between CI_DRM_10411_full and IGTPW_6071_full:

### New IGT tests (13) ###

  * igt@api_intel_allocator@alloc-sanity-check-bst:
    - Statuses : 4 pass(s)
    - Exec time: [0.0] s

  * igt@api_intel_allocator@alloc-sanity-check-simple:
    - Statuses : 6 pass(s)
    - Exec time: [0.0] s

  * igt@api_intel_allocator@bst-allocator:
    - Statuses :
    - Exec time: [None] s

  * igt@api_intel_allocator@bst-allocator@basic:
    - Statuses : 6 pass(s)
    - Exec time: [0.0, 0.00] s

  * igt@api_intel_allocator@bst-allocator@fork-reopen-allocator:
    - Statuses : 6 pass(s)
    - Exec time: [0.02, 0.06] s

  * igt@api_intel_allocator@bst-allocator@parallel-one:
    - Statuses : 6 pass(s)
    - Exec time: [0.01, 0.04] s

  * igt@api_intel_allocator@bst-allocator@print:
    - Statuses : 6 pass(s)
    - Exec time: [0.0] s

  * igt@api_intel_allocator@reserve-bst:
    - Statuses : 6 pass(s)
    - Exec time: [0.0] s

  * igt@api_intel_allocator@reserve-sanity-check-bst:
    - Statuses :
    - Exec time: [None] s

  * igt@api_intel_allocator@reserve-sanity-check-simple:
    - Statuses : 4 pass(s)
    - Exec time: [0.0] s

  * igt@api_intel_allocator@reuse-bst:
    - Statuses : 6 pass(s)
    - Exec time: [0.0, 0.00] s

  * igt@api_intel_allocator@reuse-simple:
    - Statuses : 6 pass(s)
    - Exec time: [0.0, 0.00] s

  * igt@kms_busy@extended-pageflip-hang-oldfb@pipe-b:
    - Statuses : 1 pass(s)
    - Exec time: [0.14] s

  

Known issues
------------

  Here are the changes found in IGTPW_6071_full that come from known issues:

### IGT changes ###

#### Issues hit ####

  * igt@feature_discovery@chamelium:
    - shard-tglb:         NOTRUN -> [SKIP][1] ([fdo#111827])
   [1]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb2/igt@feature_discovery@chamelium.html
    - shard-iclb:         NOTRUN -> [SKIP][2] ([fdo#111827])
   [2]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb1/igt@feature_discovery@chamelium.html

  * igt@gem_ctx_isolation@preservation-s3@vcs0:
    - shard-kbl:          [PASS][3] -> [DMESG-WARN][4] ([i915#180]) +2 similar issues
   [3]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-kbl7/igt@gem_ctx_isolation@preservation-s3@vcs0.html
   [4]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl6/igt@gem_ctx_isolation@preservation-s3@vcs0.html

  * igt@gem_ctx_persistence@process:
    - shard-snb:          NOTRUN -> [SKIP][5] ([fdo#109271] / [i915#1099]) +2 similar issues
   [5]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-snb5/igt@gem_ctx_persistence@process.html

  * igt@gem_ctx_sseu@mmap-args:
    - shard-tglb:         NOTRUN -> [SKIP][6] ([i915#280])
   [6]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb8/igt@gem_ctx_sseu@mmap-args.html

  * igt@gem_eio@unwedge-stress:
    - shard-tglb:         [PASS][7] -> [TIMEOUT][8] ([i915#2369] / [i915#3063] / [i915#3648])
   [7]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-tglb6/igt@gem_eio@unwedge-stress.html
   [8]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb1/igt@gem_eio@unwedge-stress.html
    - shard-snb:          NOTRUN -> [FAIL][9] ([i915#3354])
   [9]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-snb2/igt@gem_eio@unwedge-stress.html

  * igt@gem_exec_fair@basic-deadline:
    - shard-kbl:          NOTRUN -> [FAIL][10] ([i915#2846])
   [10]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl2/igt@gem_exec_fair@basic-deadline.html

  * igt@gem_exec_fair@basic-pace-share@rcs0:
    - shard-glk:          [PASS][11] -> [FAIL][12] ([i915#2842])
   [11]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-glk7/igt@gem_exec_fair@basic-pace-share@rcs0.html
   [12]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-glk4/igt@gem_exec_fair@basic-pace-share@rcs0.html

  * igt@gem_exec_fair@basic-pace@vecs0:
    - shard-tglb:         [PASS][13] -> [FAIL][14] ([i915#2842]) +2 similar issues
   [13]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-tglb3/igt@gem_exec_fair@basic-pace@vecs0.html
   [14]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb1/igt@gem_exec_fair@basic-pace@vecs0.html

  * igt@gem_exec_params@no-blt:
    - shard-tglb:         NOTRUN -> [SKIP][15] ([fdo#109283])
   [15]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb8/igt@gem_exec_params@no-blt.html
    - shard-iclb:         NOTRUN -> [SKIP][16] ([fdo#109283])
   [16]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb6/igt@gem_exec_params@no-blt.html

  * igt@gem_mmap_gtt@cpuset-big-copy:
    - shard-iclb:         NOTRUN -> [FAIL][17] ([i915#2428])
   [17]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb5/igt@gem_mmap_gtt@cpuset-big-copy.html

  * igt@gem_mmap_gtt@cpuset-medium-copy-odd:
    - shard-glk:          [PASS][18] -> [FAIL][19] ([i915#1888] / [i915#307])
   [18]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-glk9/igt@gem_mmap_gtt@cpuset-medium-copy-odd.html
   [19]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-glk8/igt@gem_mmap_gtt@cpuset-medium-copy-odd.html

  * igt@gem_mmap_gtt@hang-busy:
    - shard-glk:          [PASS][20] -> [SKIP][21] ([fdo#109271])
   [20]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-glk4/igt@gem_mmap_gtt@hang-busy.html
   [21]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-glk6/igt@gem_mmap_gtt@hang-busy.html
    - shard-apl:          [PASS][22] -> [SKIP][23] ([fdo#109271])
   [22]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-apl3/igt@gem_mmap_gtt@hang-busy.html
   [23]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl2/igt@gem_mmap_gtt@hang-busy.html

  * igt@gem_pread@exhaustion:
    - shard-snb:          NOTRUN -> [WARN][24] ([i915#2658])
   [24]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-snb2/igt@gem_pread@exhaustion.html

  * igt@gem_pwrite@basic-exhaustion:
    - shard-kbl:          NOTRUN -> [WARN][25] ([i915#2658])
   [25]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl4/igt@gem_pwrite@basic-exhaustion.html
    - shard-apl:          NOTRUN -> [WARN][26] ([i915#2658])
   [26]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl7/igt@gem_pwrite@basic-exhaustion.html

  * igt@gem_render_copy@x-tiled-to-vebox-yf-tiled:
    - shard-kbl:          NOTRUN -> [SKIP][27] ([fdo#109271]) +249 similar issues
   [27]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl7/igt@gem_render_copy@x-tiled-to-vebox-yf-tiled.html

  * igt@gem_userptr_blits@access-control:
    - shard-tglb:         NOTRUN -> [SKIP][28] ([i915#3297])
   [28]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb2/igt@gem_userptr_blits@access-control.html

  * igt@gem_userptr_blits@dmabuf-sync:
    - shard-kbl:          NOTRUN -> [SKIP][29] ([fdo#109271] / [i915#3323])
   [29]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl3/igt@gem_userptr_blits@dmabuf-sync.html

  * igt@gem_userptr_blits@input-checking:
    - shard-tglb:         NOTRUN -> [DMESG-WARN][30] ([i915#3002])
   [30]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb5/igt@gem_userptr_blits@input-checking.html
    - shard-apl:          NOTRUN -> [DMESG-WARN][31] ([i915#3002])
   [31]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl8/igt@gem_userptr_blits@input-checking.html
    - shard-glk:          NOTRUN -> [DMESG-WARN][32] ([i915#3002])
   [32]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-glk7/igt@gem_userptr_blits@input-checking.html
    - shard-iclb:         NOTRUN -> [DMESG-WARN][33] ([i915#3002])
   [33]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb3/igt@gem_userptr_blits@input-checking.html

  * igt@gen7_exec_parse@basic-allowed:
    - shard-tglb:         NOTRUN -> [SKIP][34] ([fdo#109289])
   [34]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb5/igt@gen7_exec_parse@basic-allowed.html
    - shard-iclb:         NOTRUN -> [SKIP][35] ([fdo#109289]) +1 similar issue
   [35]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb2/igt@gen7_exec_parse@basic-allowed.html

  * igt@gen9_exec_parse@bb-start-far:
    - shard-iclb:         NOTRUN -> [SKIP][36] ([i915#2856])
   [36]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb4/igt@gen9_exec_parse@bb-start-far.html
    - shard-tglb:         NOTRUN -> [SKIP][37] ([i915#2856])
   [37]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb2/igt@gen9_exec_parse@bb-start-far.html

  * igt@i915_pm_dc@dc6-dpms:
    - shard-kbl:          NOTRUN -> [FAIL][38] ([i915#545]) +1 similar issue
   [38]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl4/igt@i915_pm_dc@dc6-dpms.html

  * igt@i915_pm_rc6_residency@media-rc6-accuracy:
    - shard-tglb:         NOTRUN -> [SKIP][39] ([fdo#109289] / [fdo#111719])
   [39]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb8/igt@i915_pm_rc6_residency@media-rc6-accuracy.html

  * igt@i915_pm_rpm@basic-rte:
    - shard-kbl:          NOTRUN -> [FAIL][40] ([i915#579])
   [40]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl1/igt@i915_pm_rpm@basic-rte.html
    - shard-apl:          NOTRUN -> [FAIL][41] ([i915#579])
   [41]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl1/igt@i915_pm_rpm@basic-rte.html
    - shard-tglb:         NOTRUN -> [FAIL][42] ([i915#579])
   [42]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb3/igt@i915_pm_rpm@basic-rte.html

  * igt@i915_pm_rpm@pc8-residency:
    - shard-iclb:         NOTRUN -> [SKIP][43] ([i915#579])
   [43]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb5/igt@i915_pm_rpm@pc8-residency.html
    - shard-tglb:         NOTRUN -> [SKIP][44] ([i915#579])
   [44]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb1/igt@i915_pm_rpm@pc8-residency.html

  * igt@kms_big_fb@linear-32bpp-rotate-180:
    - shard-glk:          NOTRUN -> [DMESG-WARN][45] ([i915#118] / [i915#95])
   [45]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-glk5/igt@kms_big_fb@linear-32bpp-rotate-180.html

  * igt@kms_big_fb@x-tiled-max-hw-stride-32bpp-rotate-0-hflip:
    - shard-kbl:          NOTRUN -> [SKIP][46] ([fdo#109271] / [i915#3777]) +2 similar issues
   [46]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl2/igt@kms_big_fb@x-tiled-max-hw-stride-32bpp-rotate-0-hflip.html

  * igt@kms_big_fb@x-tiled-max-hw-stride-32bpp-rotate-180-hflip:
    - shard-apl:          NOTRUN -> [SKIP][47] ([fdo#109271] / [i915#3777]) +2 similar issues
   [47]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl8/igt@kms_big_fb@x-tiled-max-hw-stride-32bpp-rotate-180-hflip.html

  * igt@kms_big_fb@y-tiled-max-hw-stride-32bpp-rotate-0-hflip:
    - shard-glk:          NOTRUN -> [SKIP][48] ([fdo#109271] / [i915#3777])
   [48]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-glk7/igt@kms_big_fb@y-tiled-max-hw-stride-32bpp-rotate-0-hflip.html

  * igt@kms_big_fb@yf-tiled-max-hw-stride-64bpp-rotate-0-hflip:
    - shard-tglb:         NOTRUN -> [SKIP][49] ([fdo#111615])
   [49]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb2/igt@kms_big_fb@yf-tiled-max-hw-stride-64bpp-rotate-0-hflip.html
    - shard-iclb:         NOTRUN -> [SKIP][50] ([fdo#110723])
   [50]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb2/igt@kms_big_fb@yf-tiled-max-hw-stride-64bpp-rotate-0-hflip.html

  * igt@kms_ccs@pipe-c-crc-primary-rotation-180-y_tiled_gen12_mc_ccs:
    - shard-iclb:         NOTRUN -> [SKIP][51] ([fdo#109278]) +12 similar issues
   [51]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb2/igt@kms_ccs@pipe-c-crc-primary-rotation-180-y_tiled_gen12_mc_ccs.html

  * igt@kms_ccs@pipe-d-bad-aux-stride-y_tiled_ccs:
    - shard-tglb:         NOTRUN -> [SKIP][52] ([i915#3689]) +4 similar issues
   [52]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb6/igt@kms_ccs@pipe-d-bad-aux-stride-y_tiled_ccs.html

  * igt@kms_chamelium@hdmi-hpd-enable-disable-mode:
    - shard-snb:          NOTRUN -> [SKIP][53] ([fdo#109271] / [fdo#111827]) +21 similar issues
   [53]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-snb7/igt@kms_chamelium@hdmi-hpd-enable-disable-mode.html

  * igt@kms_chamelium@hdmi-hpd-fast:
    - shard-iclb:         NOTRUN -> [SKIP][54] ([fdo#109284] / [fdo#111827]) +1 similar issue
   [54]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb8/igt@kms_chamelium@hdmi-hpd-fast.html

  * igt@kms_color_chamelium@pipe-b-ctm-0-5:
    - shard-apl:          NOTRUN -> [SKIP][55] ([fdo#109271] / [fdo#111827]) +23 similar issues
   [55]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl2/igt@kms_color_chamelium@pipe-b-ctm-0-5.html

  * igt@kms_color_chamelium@pipe-b-ctm-limited-range:
    - shard-tglb:         NOTRUN -> [SKIP][56] ([fdo#109284] / [fdo#111827]) +3 similar issues
   [56]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb3/igt@kms_color_chamelium@pipe-b-ctm-limited-range.html
    - shard-glk:          NOTRUN -> [SKIP][57] ([fdo#109271] / [fdo#111827]) +2 similar issues
   [57]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-glk3/igt@kms_color_chamelium@pipe-b-ctm-limited-range.html

  * igt@kms_color_chamelium@pipe-c-ctm-max:
    - shard-kbl:          NOTRUN -> [SKIP][58] ([fdo#109271] / [fdo#111827]) +18 similar issues
   [58]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl2/igt@kms_color_chamelium@pipe-c-ctm-max.html

  * igt@kms_color_chamelium@pipe-d-ctm-negative:
    - shard-iclb:         NOTRUN -> [SKIP][59] ([fdo#109278] / [fdo#109284] / [fdo#111827])
   [59]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb7/igt@kms_color_chamelium@pipe-d-ctm-negative.html

  * igt@kms_content_protection@atomic-dpms:
    - shard-apl:          NOTRUN -> [TIMEOUT][60] ([i915#1319]) +1 similar issue
   [60]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl6/igt@kms_content_protection@atomic-dpms.html
    - shard-kbl:          NOTRUN -> [TIMEOUT][61] ([i915#1319])
   [61]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl2/igt@kms_content_protection@atomic-dpms.html

  * igt@kms_cursor_crc@pipe-b-cursor-512x170-offscreen:
    - shard-tglb:         NOTRUN -> [SKIP][62] ([fdo#109279] / [i915#3359]) +1 similar issue
   [62]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb1/igt@kms_cursor_crc@pipe-b-cursor-512x170-offscreen.html

  * igt@kms_cursor_crc@pipe-b-cursor-512x512-offscreen:
    - shard-iclb:         NOTRUN -> [SKIP][63] ([fdo#109278] / [fdo#109279])
   [63]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb1/igt@kms_cursor_crc@pipe-b-cursor-512x512-offscreen.html

  * igt@kms_cursor_crc@pipe-b-cursor-max-size-sliding:
    - shard-tglb:         NOTRUN -> [SKIP][64] ([i915#3359])
   [64]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb7/igt@kms_cursor_crc@pipe-b-cursor-max-size-sliding.html

  * igt@kms_cursor_crc@pipe-d-cursor-32x32-sliding:
    - shard-tglb:         NOTRUN -> [SKIP][65] ([i915#3319])
   [65]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb5/igt@kms_cursor_crc@pipe-d-cursor-32x32-sliding.html

  * igt@kms_cursor_edge_walk@pipe-d-128x128-right-edge:
    - shard-snb:          NOTRUN -> [SKIP][66] ([fdo#109271]) +434 similar issues
   [66]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-snb7/igt@kms_cursor_edge_walk@pipe-d-128x128-right-edge.html

  * igt@kms_cursor_legacy@cursorb-vs-flipa-varying-size:
    - shard-iclb:         NOTRUN -> [SKIP][67] ([fdo#109274] / [fdo#109278])
   [67]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb8/igt@kms_cursor_legacy@cursorb-vs-flipa-varying-size.html

  * igt@kms_flip@2x-nonexisting-fb-interruptible:
    - shard-iclb:         NOTRUN -> [SKIP][68] ([fdo#109274]) +2 similar issues
   [68]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb1/igt@kms_flip@2x-nonexisting-fb-interruptible.html

  * igt@kms_flip@flip-vs-expired-vblank-interruptible@c-hdmi-a1:
    - shard-glk:          [PASS][69] -> [FAIL][70] ([i915#79])
   [69]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-glk7/igt@kms_flip@flip-vs-expired-vblank-interruptible@c-hdmi-a1.html
   [70]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-glk3/igt@kms_flip@flip-vs-expired-vblank-interruptible@c-hdmi-a1.html

  * igt@kms_flip@flip-vs-suspend@c-dp1:
    - shard-apl:          NOTRUN -> [DMESG-WARN][71] ([i915#180]) +2 similar issues
   [71]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl6/igt@kms_flip@flip-vs-suspend@c-dp1.html

  * igt@kms_frontbuffer_tracking@fbcpsr-2p-primscrn-pri-indfb-draw-blt:
    - shard-tglb:         NOTRUN -> [SKIP][72] ([fdo#111825]) +12 similar issues
   [72]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb8/igt@kms_frontbuffer_tracking@fbcpsr-2p-primscrn-pri-indfb-draw-blt.html

  * igt@kms_frontbuffer_tracking@fbcpsr-2p-scndscrn-cur-indfb-draw-pwrite:
    - shard-iclb:         NOTRUN -> [SKIP][73] ([fdo#109280]) +8 similar issues
   [73]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb1/igt@kms_frontbuffer_tracking@fbcpsr-2p-scndscrn-cur-indfb-draw-pwrite.html

  * igt@kms_frontbuffer_tracking@fbcpsr-rgb565-draw-mmap-cpu:
    - shard-glk:          NOTRUN -> [SKIP][74] ([fdo#109271]) +36 similar issues
   [74]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-glk5/igt@kms_frontbuffer_tracking@fbcpsr-rgb565-draw-mmap-cpu.html

  * igt@kms_hdr@bpc-switch-suspend:
    - shard-kbl:          NOTRUN -> [FAIL][75] ([i915#1188])
   [75]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl2/igt@kms_hdr@bpc-switch-suspend.html
    - shard-apl:          NOTRUN -> [FAIL][76] ([i915#1188])
   [76]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl6/igt@kms_hdr@bpc-switch-suspend.html

  * igt@kms_pipe_crc_basic@compare-crc-sanitycheck-pipe-d:
    - shard-apl:          NOTRUN -> [SKIP][77] ([fdo#109271] / [i915#533]) +1 similar issue
   [77]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl8/igt@kms_pipe_crc_basic@compare-crc-sanitycheck-pipe-d.html
    - shard-glk:          NOTRUN -> [SKIP][78] ([fdo#109271] / [i915#533])
   [78]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-glk8/igt@kms_pipe_crc_basic@compare-crc-sanitycheck-pipe-d.html
    - shard-kbl:          NOTRUN -> [SKIP][79] ([fdo#109271] / [i915#533])
   [79]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl4/igt@kms_pipe_crc_basic@compare-crc-sanitycheck-pipe-d.html

  * igt@kms_plane_alpha_blend@pipe-a-alpha-opaque-fb:
    - shard-apl:          NOTRUN -> [FAIL][80] ([fdo#108145] / [i915#265]) +4 similar issues
   [80]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl1/igt@kms_plane_alpha_blend@pipe-a-alpha-opaque-fb.html

  * igt@kms_plane_alpha_blend@pipe-b-alpha-transparent-fb:
    - shard-apl:          NOTRUN -> [FAIL][81] ([i915#265]) +1 similar issue
   [81]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl7/igt@kms_plane_alpha_blend@pipe-b-alpha-transparent-fb.html
    - shard-kbl:          NOTRUN -> [FAIL][82] ([i915#265])
   [82]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl4/igt@kms_plane_alpha_blend@pipe-b-alpha-transparent-fb.html

  * igt@kms_plane_alpha_blend@pipe-c-alpha-opaque-fb:
    - shard-kbl:          NOTRUN -> [FAIL][83] ([fdo#108145] / [i915#265]) +3 similar issues
   [83]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl6/igt@kms_plane_alpha_blend@pipe-c-alpha-opaque-fb.html

  * igt@kms_plane_multiple@atomic-pipe-c-tiling-yf:
    - shard-tglb:         NOTRUN -> [SKIP][84] ([fdo#112054])
   [84]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb8/igt@kms_plane_multiple@atomic-pipe-c-tiling-yf.html

  * igt@kms_psr2_sf@overlay-primary-update-sf-dmg-area-3:
    - shard-kbl:          NOTRUN -> [SKIP][85] ([fdo#109271] / [i915#658]) +3 similar issues
   [85]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl7/igt@kms_psr2_sf@overlay-primary-update-sf-dmg-area-3.html

  * igt@kms_psr2_sf@plane-move-sf-dmg-area-1:
    - shard-tglb:         NOTRUN -> [SKIP][86] ([i915#2920])
   [86]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb3/igt@kms_psr2_sf@plane-move-sf-dmg-area-1.html
    - shard-glk:          NOTRUN -> [SKIP][87] ([fdo#109271] / [i915#658])
   [87]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-glk9/igt@kms_psr2_sf@plane-move-sf-dmg-area-1.html
    - shard-iclb:         NOTRUN -> [SKIP][88] ([i915#658])
   [88]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb3/igt@kms_psr2_sf@plane-move-sf-dmg-area-1.html

  * igt@kms_psr2_su@frontbuffer:
    - shard-iclb:         [PASS][89] -> [SKIP][90] ([fdo#109642] / [fdo#111068] / [i915#658])
   [89]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-iclb2/igt@kms_psr2_su@frontbuffer.html
   [90]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb6/igt@kms_psr2_su@frontbuffer.html

  * igt@kms_psr2_su@page_flip:
    - shard-apl:          NOTRUN -> [SKIP][91] ([fdo#109271] / [i915#658]) +3 similar issues
   [91]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl6/igt@kms_psr2_su@page_flip.html

  * igt@kms_psr@psr2_cursor_plane_move:
    - shard-tglb:         NOTRUN -> [FAIL][92] ([i915#132] / [i915#3467])
   [92]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb6/igt@kms_psr@psr2_cursor_plane_move.html

  * igt@kms_selftest@all@damage_iter_no_damage:
    - shard-snb:          NOTRUN -> [INCOMPLETE][93] ([i915#3871])
   [93]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-snb6/igt@kms_selftest@all@damage_iter_no_damage.html

  * igt@kms_sysfs_edid_timing:
    - shard-apl:          NOTRUN -> [FAIL][94] ([IGT#2])
   [94]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl1/igt@kms_sysfs_edid_timing.html

  * igt@kms_vblank@pipe-a-ts-continuation-suspend:
    - shard-kbl:          [PASS][95] -> [DMESG-WARN][96] ([i915#180] / [i915#295])
   [95]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-kbl3/igt@kms_vblank@pipe-a-ts-continuation-suspend.html
   [96]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl7/igt@kms_vblank@pipe-a-ts-continuation-suspend.html

  * igt@kms_writeback@writeback-fb-id:
    - shard-apl:          NOTRUN -> [SKIP][97] ([fdo#109271] / [i915#2437])
   [97]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl8/igt@kms_writeback@writeback-fb-id.html

  * igt@nouveau_crc@pipe-a-source-outp-complete:
    - shard-tglb:         NOTRUN -> [SKIP][98] ([i915#2530])
   [98]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb5/igt@nouveau_crc@pipe-a-source-outp-complete.html
    - shard-iclb:         NOTRUN -> [SKIP][99] ([i915#2530])
   [99]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb2/igt@nouveau_crc@pipe-a-source-outp-complete.html

  * igt@nouveau_crc@pipe-b-ctx-flip-skip-current-frame:
    - shard-apl:          NOTRUN -> [SKIP][100] ([fdo#109271]) +305 similar issues
   [100]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl6/igt@nouveau_crc@pipe-b-ctx-flip-skip-current-frame.html

  * igt@perf_pmu@rc6-suspend:
    - shard-kbl:          NOTRUN -> [DMESG-WARN][101] ([i915#180]) +1 similar issue
   [101]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl7/igt@perf_pmu@rc6-suspend.html

  * igt@prime_nv_api@nv_self_import_to_different_fd:
    - shard-tglb:         NOTRUN -> [SKIP][102] ([fdo#109291])
   [102]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb3/igt@prime_nv_api@nv_self_import_to_different_fd.html
    - shard-iclb:         NOTRUN -> [SKIP][103] ([fdo#109291])
   [103]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb1/igt@prime_nv_api@nv_self_import_to_different_fd.html

  * igt@sysfs_clients@fair-3:
    - shard-kbl:          NOTRUN -> [SKIP][104] ([fdo#109271] / [i915#2994]) +3 similar issues
   [104]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl2/igt@sysfs_clients@fair-3.html

  * igt@sysfs_clients@pidname:
    - shard-iclb:         NOTRUN -> [SKIP][105] ([i915#2994])
   [105]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb1/igt@sysfs_clients@pidname.html
    - shard-apl:          NOTRUN -> [SKIP][106] ([fdo#109271] / [i915#2994]) +1 similar issue
   [106]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl8/igt@sysfs_clients@pidname.html
    - shard-glk:          NOTRUN -> [SKIP][107] ([fdo#109271] / [i915#2994])
   [107]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-glk7/igt@sysfs_clients@pidname.html
    - shard-tglb:         NOTRUN -> [SKIP][108] ([i915#2994])
   [108]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-tglb8/igt@sysfs_clients@pidname.html

  
#### Possible fixes ####

  * igt@gem_eio@in-flight-suspend:
    - shard-kbl:          [INCOMPLETE][109] ([i915#155]) -> [PASS][110]
   [109]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-kbl4/igt@gem_eio@in-flight-suspend.html
   [110]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl2/igt@gem_eio@in-flight-suspend.html

  * igt@gem_exec_fair@basic-none-share@rcs0:
    - shard-apl:          [SKIP][111] ([fdo#109271]) -> [PASS][112]
   [111]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-apl2/igt@gem_exec_fair@basic-none-share@rcs0.html
   [112]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl6/igt@gem_exec_fair@basic-none-share@rcs0.html

  * igt@gem_exec_fair@basic-throttle@rcs0:
    - shard-iclb:         [FAIL][113] ([i915#2849]) -> [PASS][114]
   [113]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-iclb2/igt@gem_exec_fair@basic-throttle@rcs0.html
   [114]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb6/igt@gem_exec_fair@basic-throttle@rcs0.html

  * igt@kms_big_fb@linear-32bpp-rotate-0:
    - shard-glk:          [DMESG-WARN][115] ([i915#118] / [i915#95]) -> [PASS][116] +2 similar issues
   [115]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-glk9/igt@kms_big_fb@linear-32bpp-rotate-0.html
   [116]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-glk1/igt@kms_big_fb@linear-32bpp-rotate-0.html

  * igt@kms_flip@flip-vs-suspend-interruptible@c-dp1:
    - shard-apl:          [DMESG-WARN][117] ([i915#180]) -> [PASS][118]
   [117]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-apl3/igt@kms_flip@flip-vs-suspend-interruptible@c-dp1.html
   [118]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl7/igt@kms_flip@flip-vs-suspend-interruptible@c-dp1.html

  * igt@kms_plane@plane-panning-bottom-right-suspend@pipe-b-planes:
    - shard-kbl:          [DMESG-WARN][119] ([i915#180]) -> [PASS][120] +5 similar issues
   [119]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-kbl1/igt@kms_plane@plane-panning-bottom-right-suspend@pipe-b-planes.html
   [120]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl3/igt@kms_plane@plane-panning-bottom-right-suspend@pipe-b-planes.html

  * igt@kms_psr@psr2_no_drrs:
    - shard-iclb:         [SKIP][121] ([fdo#109441]) -> [PASS][122] +2 similar issues
   [121]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-iclb5/igt@kms_psr@psr2_no_drrs.html
   [122]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb2/igt@kms_psr@psr2_no_drrs.html

  
#### Warnings ####

  * igt@i915_pm_dc@dc3co-vpb-simulation:
    - shard-iclb:         [SKIP][123] ([i915#588]) -> [SKIP][124] ([i915#658])
   [123]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-iclb2/igt@i915_pm_dc@dc3co-vpb-simulation.html
   [124]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb8/igt@i915_pm_dc@dc3co-vpb-simulation.html

  * igt@i915_pm_dc@dc9-dpms:
    - shard-apl:          [SKIP][125] ([fdo#109271]) -> [FAIL][126] ([i915#3343])
   [125]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-apl6/igt@i915_pm_dc@dc9-dpms.html
   [126]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-apl8/igt@i915_pm_dc@dc9-dpms.html

  * igt@kms_pipe_crc_basic@suspend-read-crc-pipe-a:
    - shard-kbl:          [DMESG-WARN][127] ([i915#180]) -> [INCOMPLETE][128] ([i915#155] / [i915#794])
   [127]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-kbl1/igt@kms_pipe_crc_basic@suspend-read-crc-pipe-a.html
   [128]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-kbl4/igt@kms_pipe_crc_basic@suspend-read-crc-pipe-a.html

  * igt@kms_psr2_sf@overlay-plane-update-sf-dmg-area-4:
    - shard-iclb:         [SKIP][129] ([i915#658]) -> [SKIP][130] ([i915#2920]) +2 similar issues
   [129]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-iclb7/igt@kms_psr2_sf@overlay-plane-update-sf-dmg-area-4.html
   [130]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb2/igt@kms_psr2_sf@overlay-plane-update-sf-dmg-area-4.html

  * igt@kms_psr2_sf@primary-plane-update-sf-dmg-area-1:
    - shard-iclb:         [SKIP][131] ([i915#2920]) -> [SKIP][132] ([i915#658])
   [131]: https://intel-gfx-ci.01.org/tree/drm-tip/CI_DRM_10411/shard-iclb2/igt@kms_psr2_sf@primary-plane-update-sf-dmg-area-1.html
   [132]: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/shard-iclb4/igt@kms_psr2_sf@primary-plane-update-sf-dmg-area-1.html

  * igt@runner@aborted:
    - shard-kbl:          ([FAIL][133], [FAIL][134], [FAIL][135], [FAIL][136], [FAIL][137], [FAIL][138], [FAIL][139], [FAIL][140], [FAIL][141], [FAIL][142], [FAIL][143], [FAIL][144]) ([i915#1436] / [i915#180] / [i915#1814] / [i915#2426] / [i915#2505] / [i915#300

== Logs ==

For more details see: https://intel-gfx-ci.01.org/tree/drm-tip/IGTPW_6071/index.html

[-- Attachment #1.2: Type: text/html, Size: 34122 bytes --]

[-- Attachment #2: Type: text/plain, Size: 154 bytes --]

_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev