drivers/gpu/drm/i915/i915_buddy.c

   1 // SPDX-License-Identifier: MIT
   2 /*
   3  * Copyright © 2019 Intel Corporation
   4  */
   5
   6 #include <linux/kmemleak.h>
   7 #include <linux/slab.h>
   8
   9 #include "i915_buddy.h"
  10
  11 #include "i915_gem.h"
  12 #include "i915_globals.h"
  13 #include "i915_utils.h"
  14
  15 static struct i915_global_block {
  16         struct i915_global base;
  17         struct kmem_cache *slab_blocks;
  18 } global;
  19
  20 static void i915_global_buddy_shrink(void)
  21 {
  22         kmem_cache_shrink(global.slab_blocks);
  23 }
  24
  25 static void i915_global_buddy_exit(void)
  26 {
  27         kmem_cache_destroy(global.slab_blocks);
  28 }
  29
  30 static struct i915_global_block global = { {
  31         .shrink = i915_global_buddy_shrink,
  32         .exit = i915_global_buddy_exit,
  33 } };
  34
  35 int __init i915_global_buddy_init(void)
  36 {
  37         global.slab_blocks = KMEM_CACHE(i915_buddy_block, SLAB_HWCACHE_ALIGN);
  38         if (!global.slab_blocks)
  39                 return -ENOMEM;
  40
  41         i915_global_register(&global.base);
  42         return 0;
  43 }
  44
  45 static struct i915_buddy_block *i915_block_alloc(struct i915_buddy_block *parent,
  46                                                  unsigned int order,
  47                                                  u64 offset)
  48 {
  49         struct i915_buddy_block *block;
  50
  51         block = kmem_cache_zalloc(global.slab_blocks, GFP_KERNEL);
  52         if (!block)
  53                 return NULL;
  54
  55         block->header = offset;
  56         block->header |= order;
  57         block->parent = parent;
  58
  59         return block;
  60 }
  61
  62 static void i915_block_free(struct i915_buddy_block *block)
  63 {
  64         kmem_cache_free(global.slab_blocks, block);
  65 }
  66
  67 static void mark_allocated(struct i915_buddy_block *block)
  68 {
  69         block->header &= ~I915_BUDDY_HEADER_STATE;
  70         block->header |= I915_BUDDY_ALLOCATED;
  71
  72         list_del(&block->link);
  73 }
  74
  75 static void mark_free(struct i915_buddy_mm *mm,
  76                       struct i915_buddy_block *block)
  77 {
  78         block->header &= ~I915_BUDDY_HEADER_STATE;
  79         block->header |= I915_BUDDY_FREE;
  80
  81         list_add(&block->link,
  82                  &mm->free_list[i915_buddy_block_order(block)]);
  83 }
  84
  85 static void mark_split(struct i915_buddy_block *block)
  86 {
  87         block->header &= ~I915_BUDDY_HEADER_STATE;
  88         block->header |= I915_BUDDY_SPLIT;
  89
  90         list_del(&block->link);
  91 }
  92
  93 int i915_buddy_init(struct i915_buddy_mm *mm, u64 size, u64 chunk_size)
  94 {
  95         unsigned int i;
  96         u64 offset;
  97
  98         if (size < chunk_size)
  99                 return -EINVAL;
 100
 101         if (chunk_size < PAGE_SIZE)
 102                 return -EINVAL;
 103
 104         if (!is_power_of_2(chunk_size))
 105                 return -EINVAL;
 106
 107         size = round_down(size, chunk_size);
 108
 109         mm->size = size;
 110         mm->chunk_size = chunk_size;
 111         mm->max_order = ilog2(size) - ilog2(chunk_size);
 112
 113         GEM_BUG_ON(mm->max_order > I915_BUDDY_MAX_ORDER);
 114
 115         mm->free_list = kmalloc_array(mm->max_order + 1,
 116                                       sizeof(struct list_head),
 117                                       GFP_KERNEL);
 118         if (!mm->free_list)
 119                 return -ENOMEM;
 120
 121         for (i = 0; i <= mm->max_order; ++i)
 122                 INIT_LIST_HEAD(&mm->free_list[i]);
 123
 124         mm->n_roots = hweight64(size);
 125
 126         mm->roots = kmalloc_array(mm->n_roots,
 127                                   sizeof(struct i915_buddy_block *),
 128                                   GFP_KERNEL);
 129         if (!mm->roots)
 130                 goto out_free_list;
 131
 132         offset = 0;
 133         i = 0;
 134
 135         /*
 136          * Split into power-of-two blocks, in case we are given a size that is
 137          * not itself a power-of-two.
 138          */
 139         do {
 140                 struct i915_buddy_block *root;
 141                 unsigned int order;
 142                 u64 root_size;
 143
 144                 root_size = rounddown_pow_of_two(size);
 145                 order = ilog2(root_size) - ilog2(chunk_size);
 146
 147                 root = i915_block_alloc(NULL, order, offset);
 148                 if (!root)
 149                         goto out_free_roots;
 150
 151                 mark_free(mm, root);
 152
 153                 GEM_BUG_ON(i > mm->max_order);
 154                 GEM_BUG_ON(i915_buddy_block_size(mm, root) < chunk_size);
 155
 156                 mm->roots[i] = root;
 157
 158                 offset += root_size;
 159                 size -= root_size;
 160                 i++;
 161         } while (size);
 162
 163         return 0;
 164
 165 out_free_roots:
 166         while (i--)
 167                 i915_block_free(mm->roots[i]);
 168         kfree(mm->roots);
 169 out_free_list:
 170         kfree(mm->free_list);
 171         return -ENOMEM;
 172 }
 173
 174 void i915_buddy_fini(struct i915_buddy_mm *mm)
 175 {
 176         int i;
 177
 178         for (i = 0; i < mm->n_roots; ++i) {
 179                 GEM_WARN_ON(!i915_buddy_block_is_free(mm->roots[i]));
 180                 i915_block_free(mm->roots[i]);
 181         }
 182
 183         kfree(mm->roots);
 184         kfree(mm->free_list);
 185 }
 186
 187 static int split_block(struct i915_buddy_mm *mm,
 188                        struct i915_buddy_block *block)
 189 {
 190         unsigned int block_order = i915_buddy_block_order(block) - 1;
 191         u64 offset = i915_buddy_block_offset(block);
 192
 193         GEM_BUG_ON(!i915_buddy_block_is_free(block));
 194         GEM_BUG_ON(!i915_buddy_block_order(block));
 195
 196         block->left = i915_block_alloc(block, block_order, offset);
 197         if (!block->left)
 198                 return -ENOMEM;
 199
 200         block->right = i915_block_alloc(block, block_order,
 201                                         offset + (mm->chunk_size << block_order));
 202         if (!block->right) {
 203                 i915_block_free(block->left);
 204                 return -ENOMEM;
 205         }
 206
 207         mark_free(mm, block->left);
 208         mark_free(mm, block->right);
 209
 210         mark_split(block);
 211
 212         return 0;
 213 }
 214
 215 static struct i915_buddy_block *
 216 get_buddy(struct i915_buddy_block *block)
 217 {
 218         struct i915_buddy_block *parent;
 219
 220         parent = block->parent;
 221         if (!parent)
 222                 return NULL;
 223
 224         if (parent->left == block)
 225                 return parent->right;
 226
 227         return parent->left;
 228 }
 229
 230 static void __i915_buddy_free(struct i915_buddy_mm *mm,
 231                               struct i915_buddy_block *block)
 232 {
 233         struct i915_buddy_block *parent;
 234
 235         while ((parent = block->parent)) {
 236                 struct i915_buddy_block *buddy;
 237
 238                 buddy = get_buddy(block);
 239
 240                 if (!i915_buddy_block_is_free(buddy))
 241                         break;
 242
 243                 list_del(&buddy->link);
 244
 245                 i915_block_free(block);
 246                 i915_block_free(buddy);
 247
 248                 block = parent;
 249         }
 250
 251         mark_free(mm, block);
 252 }
 253
 254 void i915_buddy_free(struct i915_buddy_mm *mm,
 255                      struct i915_buddy_block *block)
 256 {
 257         GEM_BUG_ON(!i915_buddy_block_is_allocated(block));
 258         __i915_buddy_free(mm, block);
 259 }
 260
 261 void i915_buddy_free_list(struct i915_buddy_mm *mm, struct list_head *objects)
 262 {
 263         struct i915_buddy_block *block, *on;
 264
 265         list_for_each_entry_safe(block, on, objects, link)
 266                 i915_buddy_free(mm, block);
 267         INIT_LIST_HEAD(objects);
 268 }
 269
 270 /*
 271  * Allocate power-of-two block. The order value here translates to:
 272  *
 273  *   0 = 2^0 * mm->chunk_size
 274  *   1 = 2^1 * mm->chunk_size
 275  *   2 = 2^2 * mm->chunk_size
 276  *   ...
 277  */
 278 struct i915_buddy_block *
 279 i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order)
 280 {
 281         struct i915_buddy_block *block = NULL;
 282         unsigned int i;
 283         int err;
 284
 285         for (i = order; i <= mm->max_order; ++i) {
 286                 block = list_first_entry_or_null(&mm->free_list[i],
 287                                                  struct i915_buddy_block,
 288                                                  link);
 289                 if (block)
 290                         break;
 291         }
 292
 293         if (!block)
 294                 return ERR_PTR(-ENOSPC);
 295
 296         GEM_BUG_ON(!i915_buddy_block_is_free(block));
 297
 298         while (i != order) {
 299                 err = split_block(mm, block);
 300                 if (unlikely(err))
 301                         goto out_free;
 302
 303                 /* Go low */
 304                 block = block->left;
 305                 i--;
 306         }
 307
 308         mark_allocated(block);
 309         kmemleak_update_trace(block);
 310         return block;
 311
 312 out_free:
 313         __i915_buddy_free(mm, block);
 314         return ERR_PTR(err);
 315 }
 316
 317 static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
 318 {
 319         return s1 <= e2 && e1 >= s2;
 320 }
 321
 322 static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2)
 323 {
 324         return s1 <= s2 && e1 >= e2;
 325 }
 326
 327 /*
 328  * Allocate range. Note that it's safe to chain together multiple alloc_ranges
 329  * with the same blocks list.
 330  *
 331  * Intended for pre-allocating portions of the address space, for example to
 332  * reserve a block for the initial framebuffer or similar, hence the expectation
 333  * here is that i915_buddy_alloc() is still the main vehicle for
 334  * allocations, so if that's not the case then the drm_mm range allocator is
 335  * probably a much better fit, and so you should probably go use that instead.
 336  */
 337 int i915_buddy_alloc_range(struct i915_buddy_mm *mm,
 338                            struct list_head *blocks,
 339                            u64 start, u64 size)
 340 {
 341         struct i915_buddy_block *block;
 342         struct i915_buddy_block *buddy;
 343         LIST_HEAD(allocated);
 344         LIST_HEAD(dfs);
 345         u64 end;
 346         int err;
 347         int i;
 348
 349         if (size < mm->chunk_size)
 350                 return -EINVAL;
 351
 352         if (!IS_ALIGNED(size | start, mm->chunk_size))
 353                 return -EINVAL;
 354
 355         if (range_overflows(start, size, mm->size))
 356                 return -EINVAL;
 357
 358         for (i = 0; i < mm->n_roots; ++i)
 359                 list_add_tail(&mm->roots[i]->tmp_link, &dfs);
 360
 361         end = start + size - 1;
 362
 363         do {
 364                 u64 block_start;
 365                 u64 block_end;
 366
 367                 block = list_first_entry_or_null(&dfs,
 368                                                  struct i915_buddy_block,
 369                                                  tmp_link);
 370                 if (!block)
 371                         break;
 372
 373                 list_del(&block->tmp_link);
 374
 375                 block_start = i915_buddy_block_offset(block);
 376                 block_end = block_start + i915_buddy_block_size(mm, block) - 1;
 377
 378                 if (!overlaps(start, end, block_start, block_end))
 379                         continue;
 380
 381                 if (i915_buddy_block_is_allocated(block)) {
 382                         err = -ENOSPC;
 383                         goto err_free;
 384                 }
 385
 386                 if (contains(start, end, block_start, block_end)) {
 387                         if (!i915_buddy_block_is_free(block)) {
 388                                 err = -ENOSPC;
 389                                 goto err_free;
 390                         }
 391
 392                         mark_allocated(block);
 393                         list_add_tail(&block->link, &allocated);
 394                         continue;
 395                 }
 396
 397                 if (!i915_buddy_block_is_split(block)) {
 398                         err = split_block(mm, block);
 399                         if (unlikely(err))
 400                                 goto err_undo;
 401                 }
 402
 403                 list_add(&block->right->tmp_link, &dfs);
 404                 list_add(&block->left->tmp_link, &dfs);
 405         } while (1);
 406
 407         list_splice_tail(&allocated, blocks);
 408         return 0;
 409
 410 err_undo:
 411         /*
 412          * We really don't want to leave around a bunch of split blocks, since
 413          * bigger is better, so make sure we merge everything back before we
 414          * free the allocated blocks.
 415          */
 416         buddy = get_buddy(block);
 417         if (buddy &&
 418             (i915_buddy_block_is_free(block) &&
 419              i915_buddy_block_is_free(buddy)))
 420                 __i915_buddy_free(mm, block);
 421
 422 err_free:
 423         i915_buddy_free_list(mm, &allocated);
 424         return err;
 425 }
 426
 427 #if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
 428 #include "selftests/i915_buddy.c"
 429 #endif