Re: [PATCH v2 1/3] drm/buddy: Improve contiguous memory allocation

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 




On 11/09/23 03:46, Matthew Auld wrote:
On 09/09/2023 17:09, Arunpravin Paneer Selvam wrote:
Problem statement: The current method roundup_power_of_two()
to allocate contiguous address triggers -ENOSPC in some cases
even though we have enough free spaces and so to help with
that we introduce a try harder mechanism.

In case of -ENOSPC, the new try harder mechanism rounddown the
original size to power of 2 and iterating over the round down
sized freelist blocks to allocate the required size traversing
RHS and LHS.

As part of the above new method implementation we moved
contiguous/alignment size computation part and trim function
to the drm buddy file.

v2: Modify the alloc_range() function to return total allocated size
     on -ENOSPC err and traverse RHS/LHS to allocate the required
     size (Matthew).

Signed-off-by: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@xxxxxxx>
---
  drivers/gpu/drm/drm_buddy.c | 138 ++++++++++++++++++++++++++++++++----
  include/drm/drm_buddy.h     |   6 +-
  2 files changed, 127 insertions(+), 17 deletions(-)

diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
index 7098f125b54a..e909eed9cf60 100644
--- a/drivers/gpu/drm/drm_buddy.c
+++ b/drivers/gpu/drm/drm_buddy.c
@@ -480,10 +480,12 @@ alloc_from_freelist(struct drm_buddy *mm,
  static int __alloc_range(struct drm_buddy *mm,
               struct list_head *dfs,
               u64 start, u64 size,
-             struct list_head *blocks)
+             struct list_head *blocks,
+             u64 *total_allocated_on_err)
  {
      struct drm_buddy_block *block;
      struct drm_buddy_block *buddy;
+    u64 total_allocated = 0;
      LIST_HEAD(allocated);
      u64 end;
      int err;
@@ -520,6 +522,7 @@ static int __alloc_range(struct drm_buddy *mm,
              }
                mark_allocated(block);
+            total_allocated += drm_buddy_block_size(mm, block);
              mm->avail -= drm_buddy_block_size(mm, block);
              list_add_tail(&block->link, &allocated);
              continue;
@@ -551,13 +554,20 @@ static int __alloc_range(struct drm_buddy *mm,
          __drm_buddy_free(mm, block);
    err_free:
-    drm_buddy_free_list(mm, &allocated);
+    if (err == -ENOSPC && total_allocated_on_err) {
+        list_splice_tail(&allocated, blocks);
+        *total_allocated_on_err = total_allocated;
+    } else {
+        drm_buddy_free_list(mm, &allocated);
+    }
+
      return err;
  }
    static int __drm_buddy_alloc_range(struct drm_buddy *mm,
                     u64 start,
                     u64 size,
+                   u64 *total_allocated_on_err,
                     struct list_head *blocks)
  {
      LIST_HEAD(dfs);
@@ -566,7 +576,62 @@ static int __drm_buddy_alloc_range(struct drm_buddy *mm,
      for (i = 0; i < mm->n_roots; ++i)
          list_add_tail(&mm->roots[i]->tmp_link, &dfs);
  -    return __alloc_range(mm, &dfs, start, size, blocks);
+    return __alloc_range(mm, &dfs, start, size,
+                 blocks, total_allocated_on_err);
+}
+
+static int __alloc_contig_try_harder(struct drm_buddy *mm,
+                     u64 size,
+                     u64 min_block_size,
+                     struct list_head *blocks)
+{
+    u64 rhs_offset, lhs_offset, lhs_size, filled;
+    struct drm_buddy_block *block;
+    struct list_head *list;
+    LIST_HEAD(blocks_lhs);
+    unsigned long pages;
+    unsigned int order;
+    u64 modify_size;
+    int err;
+
+    modify_size = rounddown_pow_of_two(size);
+    pages = modify_size >> ilog2(mm->chunk_size);
+    order = fls(pages) - 1;
+    if (order == 0)
+        return -ENOSPC;
+
+    list = &mm->free_list[order];
+    if (list_empty(list))
+        return -ENOSPC;
+
+    list_for_each_entry_reverse(block, list, link) {
+        /* Allocate blocks traversing RHS */
+        rhs_offset = drm_buddy_block_offset(block);
+        err =  __drm_buddy_alloc_range(mm, rhs_offset, size,
+                           &filled, blocks);
+        if (!err || err != -ENOSPC)
+            return err;
+
+        lhs_size = max((size - filled), min_block_size);
+        if (!IS_ALIGNED(lhs_size, min_block_size))
+            lhs_size = round_up(lhs_size, min_block_size);
+
+        /* Allocate blocks traversing LHS */
+        lhs_offset = drm_buddy_block_offset(block) - lhs_size;
+        err =  __drm_buddy_alloc_range(mm, lhs_offset, lhs_size,
+                           NULL, &blocks_lhs);
+        if (!err) {
+            list_splice(&blocks_lhs, blocks);
+            return 0;

I guess we could attempt to trim this also (could tweak the trim to work on multiple nodes)? But I guess in practice should be pretty meh, given that the extra rhs is hopefully not too big in the corner case where the alignment doesn't fit the min_block_size?

Thanks for the review. good point. I will take a look into it.

Regards,

Arun.


Anyway, for patches 1-3,
Reviewed-by: Matthew Auld <matthew.auld@xxxxxxxxx>

+        } else if (err != -ENOSPC) {
+            drm_buddy_free_list(mm, blocks);
+            return err;
+        }
+        /* Free blocks for the next iteration */
+        drm_buddy_free_list(mm, blocks);
+    }
+
+    return -ENOSPC;
  }
    /**
@@ -626,7 +691,7 @@ int drm_buddy_block_trim(struct drm_buddy *mm,
        new_start = drm_buddy_block_offset(block);
      list_add(&block->tmp_link, &dfs);
-    err =  __alloc_range(mm, &dfs, new_start, new_size, blocks);
+    err =  __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL);
      if (err) {
          mark_allocated(block);
          mm->avail -= drm_buddy_block_size(mm, block);
@@ -645,7 +710,7 @@ EXPORT_SYMBOL(drm_buddy_block_trim);
   * @start: start of the allowed range for this block
   * @end: end of the allowed range for this block
   * @size: size of the allocation
- * @min_page_size: alignment of the allocation
+ * @min_block_size: alignment of the allocation
   * @blocks: output list head to add allocated blocks
   * @flags: DRM_BUDDY_*_ALLOCATION flags
   *
@@ -660,23 +725,24 @@ EXPORT_SYMBOL(drm_buddy_block_trim);
   */
  int drm_buddy_alloc_blocks(struct drm_buddy *mm,
                 u64 start, u64 end, u64 size,
-               u64 min_page_size,
+               u64 min_block_size,
                 struct list_head *blocks,
                 unsigned long flags)
  {
      struct drm_buddy_block *block = NULL;
+    u64 original_size, original_min_size;
      unsigned int min_order, order;
-    unsigned long pages;
      LIST_HEAD(allocated);
+    unsigned long pages;
      int err;
        if (size < mm->chunk_size)
          return -EINVAL;
  -    if (min_page_size < mm->chunk_size)
+    if (min_block_size < mm->chunk_size)
          return -EINVAL;
  -    if (!is_power_of_2(min_page_size))
+    if (!is_power_of_2(min_block_size))
          return -EINVAL;
        if (!IS_ALIGNED(start | end | size, mm->chunk_size))
@@ -690,14 +756,23 @@ int drm_buddy_alloc_blocks(struct drm_buddy *mm,
        /* Actual range allocation */
      if (start + size == end)
-        return __drm_buddy_alloc_range(mm, start, size, blocks);
-
-    if (!IS_ALIGNED(size, min_page_size))
-        return -EINVAL;
+        return __drm_buddy_alloc_range(mm, start, size, NULL, blocks);
+
+    original_size = size;
+    original_min_size = min_block_size;
+
+    /* Roundup the size to power of 2 */
+    if (flags & DRM_BUDDY_CONTIGUOUS_ALLOCATION) {
+        size = roundup_pow_of_two(size);
+        min_block_size = size;
+    /* Align size value to min_block_size */
+    } else if (!IS_ALIGNED(size, min_block_size)) {
+        size = round_up(size, min_block_size);
+    }
        pages = size >> ilog2(mm->chunk_size);
      order = fls(pages) - 1;
-    min_order = ilog2(min_page_size) - ilog2(mm->chunk_size);
+    min_order = ilog2(min_block_size) - ilog2(mm->chunk_size);
        do {
          order = min(order, (unsigned int)fls(pages) - 1);
@@ -716,6 +791,16 @@ int drm_buddy_alloc_blocks(struct drm_buddy *mm,
                  break;
                if (order-- == min_order) {
+                if (flags & DRM_BUDDY_CONTIGUOUS_ALLOCATION &&
+                    !(flags & DRM_BUDDY_RANGE_ALLOCATION))
+                    /*
+                     * Try contiguous block allocation through
+                     * try harder method
+                     */
+                    return __alloc_contig_try_harder(mm,
+                                     original_size,
+                                     original_min_size,
+                                     blocks);
                  err = -ENOSPC;
                  goto err_free;
              }
@@ -732,6 +817,31 @@ int drm_buddy_alloc_blocks(struct drm_buddy *mm,
              break;
      } while (1);
  +    /* Trim the allocated block to the required size */
+    if (original_size != size) {
+        struct list_head *trim_list;
+        LIST_HEAD(temp);
+        u64 trim_size;
+
+        trim_list = &allocated;
+        trim_size = original_size;
+
+        if (!list_is_singular(&allocated)) {
+            block = list_last_entry(&allocated, typeof(*block), link);
+            list_move(&block->link, &temp);
+            trim_list = &temp;
+            trim_size = drm_buddy_block_size(mm, block) -
+                (size - original_size);
+        }
+
+        drm_buddy_block_trim(mm,
+                     trim_size,
+                     trim_list);
+
+        if (!list_empty(&temp))
+            list_splice_tail(trim_list, &allocated);
+    }
+
      list_splice_tail(&allocated, blocks);
      return 0;
  diff --git a/include/drm/drm_buddy.h b/include/drm/drm_buddy.h
index 572077ff8ae7..a5b39fc01003 100644
--- a/include/drm/drm_buddy.h
+++ b/include/drm/drm_buddy.h
@@ -22,8 +22,9 @@
      start__ >= max__ || size__ > max__ - start__; \
  })
  -#define DRM_BUDDY_RANGE_ALLOCATION (1 << 0)
-#define DRM_BUDDY_TOPDOWN_ALLOCATION (1 << 1)
+#define DRM_BUDDY_RANGE_ALLOCATION        BIT(0)
+#define DRM_BUDDY_TOPDOWN_ALLOCATION        BIT(1)
+#define DRM_BUDDY_CONTIGUOUS_ALLOCATION        BIT(2)
    struct drm_buddy_block {
  #define DRM_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)
@@ -155,5 +156,4 @@ void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p);
  void drm_buddy_block_print(struct drm_buddy *mm,
                 struct drm_buddy_block *block,
                 struct drm_printer *p);
-
  #endif



[Index of Archives]     [AMD Graphics]     [Linux USB Devel]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]

  Powered by Linux