[PATCH 1/2] nb-1
Matthew Auld
matthew.auld at intel.com
Mon Nov 9 21:17:59 UTC 2020
---
drivers/gpu/drm/i915/Makefile | 1 +
drivers/gpu/drm/i915/i915_nb_buddy.c | 310 +++++++++++++++++++++++++++
drivers/gpu/drm/i915/i915_nb_buddy.h | 109 ++++++++++
3 files changed, 420 insertions(+)
create mode 100644 drivers/gpu/drm/i915/i915_nb_buddy.c
create mode 100644 drivers/gpu/drm/i915/i915_nb_buddy.h
diff --git a/drivers/gpu/drm/i915/Makefile b/drivers/gpu/drm/i915/Makefile
index e5574e506a5c..baaa4db91d5f 100644
--- a/drivers/gpu/drm/i915/Makefile
+++ b/drivers/gpu/drm/i915/Makefile
@@ -161,6 +161,7 @@ i915-y += \
i915_gem_gtt.o \
i915_gem.o \
i915_globals.o \
+ i915_nb_buddy.o \
i915_query.o \
i915_request.o \
i915_scheduler.o \
diff --git a/drivers/gpu/drm/i915/i915_nb_buddy.c b/drivers/gpu/drm/i915/i915_nb_buddy.c
new file mode 100644
index 000000000000..bf57edcf5659
--- /dev/null
+++ b/drivers/gpu/drm/i915/i915_nb_buddy.c
@@ -0,0 +1,310 @@
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright © 2020 Intel Corporation
+ *
+ * Based on:
+ * NBBS: A Non-blocking Buddy System for Multi-core Machines
+ * https://arxiv.org/pdf/1804.03436.pdf
+ */
+
+#include <linux/slab.h>
+
+#include "i915_nb_buddy.h"
+
+#include "i915_gem.h"
+#include "i915_utils.h"
+
+static inline u64 clean_coal(u64 state, unsigned long child_idx)
+{
+ return state & ~(I915_BUDDY_COAL_LEFT >> (child_idx & 1));
+}
+
+static inline u64 mark(u64 state, unsigned long child_idx)
+{
+ return state | (I915_BUDDY_OCC_LEFT >> (child_idx & 1));
+}
+
+static inline u64 unmark(u64 state, unsigned long child_idx)
+{
+ return state & ~((I915_BUDDY_OCC_LEFT |
+ I915_BUDDY_COAL_LEFT) >> (child_idx & 1));
+}
+
+static inline bool is_coal(u64 state, unsigned long child_idx)
+{
+ return state & (I915_BUDDY_COAL_LEFT >> (child_idx & 1));
+}
+
+static inline bool is_occ_buddy(u64 state, unsigned long child_idx)
+{
+ return state & (I915_BUDDY_OCC_RIGHT << (child_idx & 1));
+}
+
+static inline bool is_coal_buddy(u64 state, unsigned long child_idx)
+{
+ return state & (I915_BUDDY_COAL_RIGHT << (child_idx & 1));
+}
+
+static inline int get_level(u64 i)
+{
+ return ilog2(i + 1);
+}
+
+static inline unsigned long get_parent(unsigned long idx)
+{
+ return (idx - 1) >> 1;
+}
+
+int i915_nb_buddy_init(struct i915_nb_buddy_mm *mm, u64 size, u64 chunk_size)
+{
+ int order;
+
+ if (size < chunk_size)
+ return -EINVAL;
+
+ if (chunk_size < PAGE_SIZE)
+ return -EINVAL;
+
+ if (!is_power_of_2(chunk_size))
+ return -EINVAL;
+
+ /* XXX: need to actually handle non-power-of-two address space */
+
+ size = rounddown_pow_of_two(size);
+
+ mm->size = size;
+ mm->chunk_size = chunk_size;
+ mm->chunk_shift = ilog2(chunk_size);
+ mm->max_order = ilog2(size) - ilog2(chunk_size);
+
+ mm->tree = kcalloc((2ULL << mm->max_order) - 1,
+ sizeof(struct i915_nb_buddy_block),
+ GFP_KERNEL);
+ if (!mm->tree)
+ return -ENOMEM;
+
+ order = mm->max_order;
+ while (order >= 0) {
+ int level = mm->max_order - order;
+ unsigned long start = (1ULL << level) - 1;
+ unsigned long end = (2ULL << level) - 1;
+ u64 size = mm->chunk_size << order;
+ u64 offset = 0;
+
+ while (start < end) {
+ struct i915_nb_buddy_block *block = &mm->tree[start];
+
+ block->offset = offset;
+ block->order = order;
+ block->state = 0;
+
+ offset += size;
+ start++;
+ }
+
+ order--;
+ }
+
+ return 0;
+}
+
+void i915_nb_buddy_fini(struct i915_nb_buddy_mm *mm)
+{
+ kfree(mm->tree);
+}
+
+static void __free_node(struct i915_nb_buddy_mm *mm, unsigned long idx,
+ int max_level)
+{
+ u64 curr_val, new_val;
+ unsigned long current_idx, child;
+ unsigned int level;
+
+ current_idx = idx;
+ level = get_level(idx);
+
+ do {
+ child = current_idx;
+ current_idx = get_parent(current_idx);
+
+ do {
+ curr_val = mm->tree[current_idx].state;
+ if (!is_coal(curr_val, child))
+ return;
+
+ new_val = unmark(curr_val, child);
+ } while (!try_cmpxchg(&mm->tree[current_idx].state,
+ curr_val,
+ new_val));
+ --level;
+ } while (level > max_level && !is_occ_buddy(new_val, child));
+}
+
+static void free_node(struct i915_nb_buddy_mm *mm,
+ unsigned long idx,
+ int max_level)
+{
+ unsigned long current_idx, runner;
+ int level;
+
+ level = get_level(idx);
+ current_idx = get_parent(idx);
+ runner = idx;
+
+ /*
+ * As a first pass we need to move up the tree starting at idx, and mark
+ * all the nodes that we need to coalesce i.e the buddy happens to also
+ * be free and so we need to 'merge' the nodes, stopping at the root
+ * node(or max_level), or if we find that the buddy is not currently
+ * free.
+ */
+
+ while (level > max_level) {
+ u64 curr_val, old_val, new_val;
+ unsigned long or_val =
+ I915_BUDDY_COAL_LEFT >> (current_idx & 1);
+
+ do {
+ curr_val = mm->tree[current_idx].state;
+ new_val = curr_val | or_val;
+ old_val = cmpxchg(&mm->tree[current_idx].state,
+ curr_val, new_val);
+ } while (old_val != new_val);
+
+ if (is_occ_buddy(old_val, runner) &&
+ !is_coal_buddy(old_val, runner))
+ break;
+
+ runner = current_idx;
+ current_idx = get_parent(current_idx);
+ level--;
+ }
+
+ /* This node is now free, so we can now unmark it */
+ mm->tree[idx].state = 0;
+
+ /*
+ * For the second pass we now need to reset or unmark all the nodes we
+ * marked as coalesced or in-the-process-of-being-freed, in the previous
+ * step. This is the actual free step.
+ */
+ if (level != max_level)
+ __free_node(mm, idx, max_level);
+}
+
+void i915_nb_buddy_free(struct i915_nb_buddy_mm *mm,
+ struct i915_nb_buddy_block *block)
+{
+ u64 offset = i915_nb_buddy_block_offset(block);
+ int order = i915_nb_buddy_block_order(block);
+ int level = mm->max_order - order;
+ unsigned long start = (1ULL << level) - 1;
+ unsigned long idx = start + (offset >> (mm->chunk_shift + order));
+
+ free_node(mm, idx, 0);
+}
+
+static bool try_alloc(struct i915_nb_buddy_mm *mm,
+ unsigned long idx,
+ unsigned long *failed_at)
+{
+ unsigned long current_idx, child;
+ int level;
+
+ /* Try to claim the node as ours */
+ if (!try_cmpxchg(&mm->tree[idx].state, 0, I915_BUDDY_BUSY)) {
+ *failed_at = idx;
+ return false;
+ }
+
+ level = get_level(idx);
+ current_idx = idx;
+
+ /*
+ * Now we just need update the state of the rest of tree to indicate the
+ * respective sub-tree(s) are now partially occupied. Since this is
+ * lockless we might race with another thread that allocates some larger
+ * block or range that contains our sub-node, so as part of this step we
+ * will always see any such fatal-state-change further up the tree and
+ * bail.
+ *
+ * Since we return the idx of the failed node, the caller, as on
+ * optimisation can skip the problematic sub-tree, when selecting the
+ * next node, which can be very significant in reducing the search
+ * space.
+ */
+
+ while (level) {
+ u64 curr_val, new_val;
+
+ child = current_idx;
+ current_idx = get_parent(current_idx);
+
+ do {
+ curr_val = mm->tree[current_idx].state;
+
+ if (curr_val & I915_BUDDY_OCC) {
+ free_node(mm, idx, level);
+ *failed_at = current_idx;
+ return false;
+ }
+
+ new_val = clean_coal(curr_val, child);
+ new_val = mark(curr_val, child);
+ } while (!try_cmpxchg(&mm->tree[current_idx].state,
+ curr_val, new_val));
+
+ --level;
+ }
+
+ return true;
+}
+
+struct i915_nb_buddy_block *
+i915_nb_buddy_alloc(struct i915_nb_buddy_mm *mm, unsigned int order)
+{
+ unsigned long start;
+ unsigned long end;
+ int level;
+
+ if (order > mm->max_order)
+ return NULL;
+
+ level = mm->max_order - order;
+ start = (1ULL << level) - 1;
+ end = (2ULL << level) - 1;
+
+ while (start < end) {
+ struct i915_nb_buddy_block *block = &mm->tree[start];
+ unsigned long failed_at;
+ int level_failed;
+ int d;
+
+ /*
+ * XXX: this is pure garbage, need something better to find free
+ * nodes whilst also being non-blocking. Looping forever over
+ * the already allocated nodes will result in a slap to the
+ * face.
+ */
+
+ if (block->state & I915_BUDDY_BUSY) {
+ start++;
+ continue;
+ }
+
+ if (try_alloc(mm, start, &failed_at))
+ return block;
+
+ /*
+ * Depending on where the allocation failed, we should
+ * be able to skip over large parts of the tree in our
+ * quest for a free node at this level.
+ */
+ level_failed = get_level(failed_at);
+
+ d = 1ULL << (level - level_failed);
+ start = (failed_at + 1) * d;
+ }
+
+ return NULL;
+}
diff --git a/drivers/gpu/drm/i915/i915_nb_buddy.h b/drivers/gpu/drm/i915/i915_nb_buddy.h
new file mode 100644
index 000000000000..02bb2059bd63
--- /dev/null
+++ b/drivers/gpu/drm/i915/i915_nb_buddy.h
@@ -0,0 +1,109 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * Copyright © 2020 Intel Corporation
+ *
+ * Based on:
+ * NBBS: A Non-blocking Buddy System for Multi-core Machines
+ * https://arxiv.org/pdf/1804.03436.pdf
+ */
+
+#ifndef __I915_NB_BUDDY_H__
+#define __I915_NB_BUDDY_H__
+
+#include <linux/bitops.h>
+#include <linux/list.h>
+
+struct i915_nb_buddy_block {
+ u64 offset;
+ unsigned int order;
+/* Some left or right sub-tree of this node is currently occupied/allocated */
+#define I915_BUDDY_OCC_RIGHT BIT(4)
+#define I915_BUDDY_OCC_LEFT BIT(3)
+/*
+ * Some left or right sub-tree of this node is in the process of being marked as
+ * free or coalesced. These bits are always cleared once the free operation is
+ * complete.
+ */
+#define I915_BUDDY_COAL_RIGHT BIT(2)
+#define I915_BUDDY_COAL_LEFT BIT(1)
+/* This node is currently occupied/allocated */
+#define I915_BUDDY_OCC BIT(0)
+ u64 state;
+
+ void *private; /* owned by creator */
+
+ /*
+ * While the block is allocated by the user through i915_nb_buddy_alloc*,
+ * the user has ownership of the link, for example to maintain within
+ * a list, if so desired. As soon as the block is freed with
+ * i915_buddy_free* ownership is given back to the mm.
+ */
+ struct list_head link;
+};
+
+#define I915_BUDDY_BUSY (I915_BUDDY_OCC | \
+ I915_BUDDY_OCC_LEFT | \
+ I915_BUDDY_OCC_RIGHT)
+
+/*
+ * Non-blocking Binary Buddy System.
+ */
+struct i915_nb_buddy_mm {
+ struct i915_nb_buddy_block *tree;
+
+ unsigned int max_order;
+
+ /* Must be at least PAGE_SIZE */
+ u64 chunk_size;
+ int chunk_shift;
+ u64 size;
+};
+
+static inline u64
+i915_nb_buddy_block_offset(struct i915_nb_buddy_block *block)
+{
+ return block->offset;
+}
+
+static inline unsigned int
+i915_nb_buddy_block_order(struct i915_nb_buddy_block *block)
+{
+ return block->order;
+}
+
+static inline unsigned int
+i915_nb_buddy_block_state(struct i915_nb_buddy_block *block)
+{
+ return block->state;
+}
+
+static inline bool
+i915_nb_buddy_block_is_allocated(struct i915_nb_buddy_block *block)
+{
+ return i915_nb_buddy_block_state(block) & I915_BUDDY_OCC;
+}
+
+static inline bool
+i915_nb_buddy_block_is_free(struct i915_nb_buddy_block *block)
+{
+ return !(i915_nb_buddy_block_state(block) & I915_BUDDY_BUSY);
+}
+
+static inline u64
+i915_nb_buddy_block_size(struct i915_nb_buddy_mm *mm,
+ struct i915_nb_buddy_block *block)
+{
+ return mm->chunk_size << i915_nb_buddy_block_order(block);
+}
+
+int i915_nb_buddy_init(struct i915_nb_buddy_mm *mm, u64 size, u64 chunk_size);
+
+void i915_nb_buddy_fini(struct i915_nb_buddy_mm *mm);
+
+struct i915_nb_buddy_block *
+i915_nb_buddy_alloc(struct i915_nb_buddy_mm *mm, unsigned int order);
+
+void i915_nb_buddy_free(struct i915_nb_buddy_mm *mm,
+ struct i915_nb_buddy_block *block);
+
+#endif
--
2.26.2
More information about the Intel-gfx-trybot
mailing list