+}
+
+static inline enum free_tree
+get_tree_for_block(struct drm_buddy_block *block)
+{
+ return drm_buddy_block_is_clear(block) ? CLEAR_TREE : DIRTY_TREE;
+}
+
+static inline enum free_tree
+get_tree_for_flags(unsigned long flags)
+{
+ return (flags & DRM_BUDDY_CLEAR_ALLOCATION) ? CLEAR_TREE :
DIRTY_TREE;
+}
+
+static inline struct drm_buddy_block *
+rbtree_get_free_block(struct rb_node *node)
+{
+ return node ? rb_entry(node, struct drm_buddy_block, rb) : NULL;
+}
+
+static inline struct drm_buddy_block *
+rbtree_prev_free_block(struct rb_node *node)
+{
+ return rbtree_get_free_block(rb_prev(node));
+}
+
+static inline struct drm_buddy_block *
+rbtree_first_free_block(struct rb_root *root)
+{
+ return rbtree_get_free_block(rb_first(root));
+}
+
+static inline struct drm_buddy_block *
+rbtree_last_free_block(struct rb_root *root)
+{
+ return rbtree_get_free_block(rb_last(root));
+}
+
+static inline bool rbtree_is_empty(struct rb_root *root)
+{
+ return RB_EMPTY_ROOT(root);
+}
+
static void rbtree_insert(struct drm_buddy *mm,
- struct drm_buddy_block *block)
+ struct drm_buddy_block *block,
+ enum free_tree tree)
{
- struct rb_root *root = &mm-
>free_tree[drm_buddy_block_order(block)];
- struct rb_node **link = &root->rb_node;
- struct rb_node *parent = NULL;
+ struct rb_node **link, *parent = NULL;
struct drm_buddy_block *node;
- u64 offset;
+ struct rb_root *root;
+ unsigned int order;
+
+ order = drm_buddy_block_order(block);
- offset = drm_buddy_block_offset(block);
+ root = get_root(mm, order, tree);
+ link = &root->rb_node;
while (*link) {
parent = *link;
- node = rb_entry(parent, struct drm_buddy_block, rb);
+ node = rbtree_get_free_block(parent);
- if (offset < drm_buddy_block_offset(node))
+ if (drm_buddy_block_offset(block) <
drm_buddy_block_offset(node))
link = &parent->rb_left;
else
link = &parent->rb_right;
@@ -106,27 +164,19 @@ static void rbtree_insert(struct drm_buddy *mm,
static void rbtree_remove(struct drm_buddy *mm,
struct drm_buddy_block *block)
{
+ unsigned int order = drm_buddy_block_order(block);
+ enum free_tree tree;
struct rb_root *root;
- root = &mm->free_tree[drm_buddy_block_order(block)];
+ tree = drm_buddy_block_is_clear(block) ?
+ CLEAR_TREE : DIRTY_TREE;
+
+ root = get_root(mm, order, tree);
rb_erase(&block->rb, root);
RB_CLEAR_NODE(&block->rb);
}
-static inline struct drm_buddy_block *
-rbtree_last_entry(struct drm_buddy *mm, unsigned int order)
-{
- struct rb_node *node = rb_last(&mm->free_tree[order]);
-
- return node ? rb_entry(node, struct drm_buddy_block, rb) : NULL;
-}
-
-static bool rbtree_is_empty(struct drm_buddy *mm, unsigned int order)
-{
- return RB_EMPTY_ROOT(&mm->free_tree[order]);
-}
-
static void clear_reset(struct drm_buddy_block *block)
{
block->header &= ~DRM_BUDDY_HEADER_CLEAR;
@@ -149,10 +199,14 @@ static void mark_allocated(struct drm_buddy *mm,
static void mark_free(struct drm_buddy *mm,
struct drm_buddy_block *block)
{
+ enum free_tree tree;
+
block->header &= ~DRM_BUDDY_HEADER_STATE;
block->header |= DRM_BUDDY_FREE;
- rbtree_insert(mm, block);
+ tree = get_tree_for_block(block);
+
+ rbtree_insert(mm, block, tree);
}
static void mark_split(struct drm_buddy *mm,
@@ -238,6 +292,7 @@ static int __force_merge(struct drm_buddy *mm,
u64 end,
unsigned int min_order)
{
+ enum free_tree tree;
unsigned int order;
int i;
@@ -247,50 +302,49 @@ static int __force_merge(struct drm_buddy *mm,
if (min_order > mm->max_order)
return -EINVAL;
- for (i = min_order - 1; i >= 0; i--) {
- struct drm_buddy_block *block, *prev_block, *first_block;
-
- first_block = rb_entry(rb_first(&mm->free_tree[i]), struct
drm_buddy_block, rb);
+ for_each_free_tree(tree) {
+ for (i = min_order - 1; i >= 0; i--) {
+ struct rb_root *root = get_root(mm, i, tree);
+ struct drm_buddy_block *block, *prev_block;
- for_each_rb_free_block_reverse_safe(block, prev_block,
&mm->free_tree[i], rb) {
- struct drm_buddy_block *buddy;
- u64 block_start, block_end;
+ for_each_rb_free_block_reverse_safe(block, prev_block,
root, rb) {
+ struct drm_buddy_block *buddy;
+ u64 block_start, block_end;
- if (!block->parent)
- continue;
+ if (!block->parent)
+ continue;
- block_start = drm_buddy_block_offset(block);
- block_end = block_start + drm_buddy_block_size(mm,
block) - 1;
+ block_start = drm_buddy_block_offset(block);
+ block_end = block_start + drm_buddy_block_size(mm,
block) - 1;
- if (!contains(start, end, block_start, block_end))
- continue;
+ if (!contains(start, end, block_start, block_end))
+ continue;
- buddy = __get_buddy(block);
- if (!drm_buddy_block_is_free(buddy))
- continue;
+ buddy = __get_buddy(block);
+ if (!drm_buddy_block_is_free(buddy))
+ continue;
- WARN_ON(drm_buddy_block_is_clear(block) ==
- drm_buddy_block_is_clear(buddy));
+ WARN_ON(drm_buddy_block_is_clear(block) ==
+ drm_buddy_block_is_clear(buddy));
- /*
- * If the prev block is same as buddy, don't access the
- * block in the next iteration as we would free the
- * buddy block as part of the free function.
- */
- if (prev_block && prev_block == buddy) {
- if (prev_block != first_block)
- prev_block = rb_entry(rb_prev(&prev_block->rb),
- struct drm_buddy_block,
- rb);
- }
+ /*
+ * If the prev block is same as buddy, don't access the
+ * block in the next iteration as we would free the
+ * buddy block as part of the free function.
+ */
+ if (prev_block && prev_block == buddy) {
+ if (prev_block != rbtree_first_free_block(root))
+ prev_block =
rbtree_prev_free_block(&prev_block->rb);
+ }
- rbtree_remove(mm, block);
- if (drm_buddy_block_is_clear(block))
- mm->clear_avail -= drm_buddy_block_size(mm, block);
+ rbtree_remove(mm, block);
+ if (drm_buddy_block_is_clear(block))
+ mm->clear_avail -= drm_buddy_block_size(mm, block);
- order = __drm_buddy_free(mm, block, true);
- if (order >= min_order)
- return 0;
+ order = __drm_buddy_free(mm, block, true);
+ if (order >= min_order)
+ return 0;
+ }
}
}
@@ -311,7 +365,7 @@ static int __force_merge(struct drm_buddy *mm,
*/
int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size)
{
- unsigned int i;
+ unsigned int i, j;
u64 offset;
if (size < chunk_size)
@@ -333,14 +387,16 @@ int drm_buddy_init(struct drm_buddy *mm, u64
size, u64 chunk_size)
BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER);
- mm->free_tree = kmalloc_array(mm->max_order + 1,
- sizeof(struct rb_root),
- GFP_KERNEL);
- if (!mm->free_tree)
- return -ENOMEM;
+ for (i = 0; i < MAX_FREE_TREES; i++) {
+ mm->free_trees[i] = kmalloc_array(mm->max_order + 1,
+ sizeof(struct rb_root),
+ GFP_KERNEL);
+ if (!mm->free_trees[i])
+ goto out_free_tree;
- for (i = 0; i <= mm->max_order; ++i)
- mm->free_tree[i] = RB_ROOT;
+ for (j = 0; j <= mm->max_order; ++j)
+ mm->free_trees[i][j] = RB_ROOT;
+ }
mm->n_roots = hweight64(size);
@@ -388,7 +444,8 @@ int drm_buddy_init(struct drm_buddy *mm, u64
size, u64 chunk_size)
drm_block_free(mm, mm->roots[i]);
kfree(mm->roots);
out_free_tree:
- kfree(mm->free_tree);
+ while (i--)
+ kfree(mm->free_trees[i]);
return -ENOMEM;
}
EXPORT_SYMBOL(drm_buddy_init);
@@ -424,8 +481,9 @@ void drm_buddy_fini(struct drm_buddy *mm)
WARN_ON(mm->avail != mm->size);
+ for (i = 0; i < MAX_FREE_TREES; i++)
+ kfree(mm->free_trees[i]);
kfree(mm->roots);
- kfree(mm->free_tree);
}
EXPORT_SYMBOL(drm_buddy_fini);
@@ -449,15 +507,15 @@ static int split_block(struct drm_buddy *mm,
return -ENOMEM;
}
- mark_free(mm, block->left);
- mark_free(mm, block->right);
-
if (drm_buddy_block_is_clear(block)) {
mark_cleared(block->left);
mark_cleared(block->right);
clear_reset(block);
}
+ mark_free(mm, block->left);
+ mark_free(mm, block->right);
+
mark_split(mm, block);
return 0;
@@ -491,6 +549,7 @@ EXPORT_SYMBOL(drm_get_buddy);
*/
void drm_buddy_reset_clear(struct drm_buddy *mm, bool is_clear)
{
+ enum free_tree src_tree, dst_tree;
u64 root_size, size, start;
unsigned int order;
int i;
@@ -505,19 +564,24 @@ void drm_buddy_reset_clear(struct drm_buddy
*mm, bool is_clear)
size -= root_size;
}
+ src_tree = is_clear ? DIRTY_TREE : CLEAR_TREE;
+ dst_tree = is_clear ? CLEAR_TREE : DIRTY_TREE;
+
for (i = 0; i <= mm->max_order; ++i) {
+ struct rb_root *root = get_root(mm, order, src_tree);
struct drm_buddy_block *block;
- for_each_rb_free_block_reverse(block, &mm->free_tree[i],
rb) {
- if (is_clear != drm_buddy_block_is_clear(block)) {
- if (is_clear) {
- mark_cleared(block);
- mm->clear_avail += drm_buddy_block_size(mm, block);
- } else {
- clear_reset(block);
- mm->clear_avail -= drm_buddy_block_size(mm, block);
- }
+ for_each_rb_free_block_reverse(block, root, rb) {
+ rbtree_remove(mm, block);
+ if (is_clear) {
+ mark_cleared(block);
+ mm->clear_avail += drm_buddy_block_size(mm, block);
+ } else {
+ clear_reset(block);
+ mm->clear_avail -= drm_buddy_block_size(mm, block);
}
+
+ rbtree_insert(mm, block, dst_tree);
}
}
}
@@ -707,26 +771,22 @@ __drm_buddy_alloc_range_bias(struct drm_buddy *mm,
}
static struct drm_buddy_block *
-get_maxblock(struct drm_buddy *mm, unsigned int order,
- unsigned long flags)
+get_maxblock(struct drm_buddy *mm,
+ unsigned int order,
+ enum free_tree tree)
{
struct drm_buddy_block *max_block = NULL, *block = NULL;
+ struct rb_root *root;
unsigned int i;
for (i = order; i <= mm->max_order; ++i) {
- struct drm_buddy_block *tmp_block;
-
- for_each_rb_free_block_reverse(tmp_block, &mm->free_tree[i],
rb) {
- if (block_incompatible(tmp_block, flags))
+ root = get_root(mm, i, tree);
+ if (!rbtree_is_empty(root)) {
+ block = rbtree_last_free_block(root);
+ if (!block)
continue;
-
- block = tmp_block;
- break;
}
- if (!block)
- continue;
-
if (!max_block) {
max_block = block;
continue;
@@ -747,36 +807,38 @@ alloc_from_freetree(struct drm_buddy *mm,
unsigned long flags)
{
struct drm_buddy_block *block = NULL;
+ struct rb_root *root;
+ enum free_tree tree;
unsigned int tmp;
int err;
+ tree = get_tree_for_flags(flags);
+
if (flags & DRM_BUDDY_TOPDOWN_ALLOCATION) {
- block = get_maxblock(mm, order, flags);
+ block = get_maxblock(mm, order, tree);
if (block)
/* Store the obtained block order */
tmp = drm_buddy_block_order(block);
} else {
for (tmp = order; tmp <= mm->max_order; ++tmp) {
- struct drm_buddy_block *tmp_block;
-
- for_each_rb_free_block_reverse(tmp_block, &mm-
>free_tree[tmp], rb) {
- if (block_incompatible(tmp_block, flags))
- continue;
-
- block = tmp_block;
- break;
+ /* Get RB tree root for this order and tree */
+ root = get_root(mm, tmp, tree);
+ if (!rbtree_is_empty(root)) {
