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                 cond_resched();
 268         }
 269         INIT_LIST_HEAD(objects);
 270 }
 271
 272 /*
 273  * Allocate power-of-two block. The order value here translates to:
 274  *
 275  *   0 = 2^0 * mm->chunk_size
 276  *   1 = 2^1 * mm->chunk_size
 277  *   2 = 2^2 * mm->chunk_size
 278  *   ...
 279  */
 280 struct i915_buddy_block *
 281 i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order)
 282 {
 283         struct i915_buddy_block *block = NULL;
 284         unsigned int i;
 285         int err;
 286
 287         for (i = order; i <= mm->max_order; ++i) {
 288                 block = list_first_entry_or_null(&mm->free_list[i],
 289                                                  struct i915_buddy_block,
 290                                                  link);
 291                 if (block)
 292                         break;
 293         }
 294
 295         if (!block)
 296                 return ERR_PTR(-ENOSPC);
 297
 298         GEM_BUG_ON(!i915_buddy_block_is_free(block));
 299
 300         while (i != order) {
 301                 err = split_block(mm, block);
 302                 if (unlikely(err))
 303                         goto out_free;
 304
 305                 /* Go low */
 306                 block = block->left;
 307                 i--;
 308         }
 309
 310         mark_allocated(block);
 311         kmemleak_update_trace(block);
 312         return block;
 313
 314 out_free:
 315         if (i != order)
 316                 __i915_buddy_free(mm, block);
 317         return ERR_PTR(err);
 318 }
 319
 320 static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
 321 {
 322         return s1 <= e2 && e1 >= s2;
 323 }
 324
 325 static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2)
 326 {
 327         return s1 <= s2 && e1 >= e2;
 328 }
 329
 330 /*
 331  * Allocate range. Note that it's safe to chain together multiple alloc_ranges
 332  * with the same blocks list.
 333  *
 334  * Intended for pre-allocating portions of the address space, for example to
 335  * reserve a block for the initial framebuffer or similar, hence the expectation
 336  * here is that i915_buddy_alloc() is still the main vehicle for
 337  * allocations, so if that's not the case then the drm_mm range allocator is
 338  * probably a much better fit, and so you should probably go use that instead.
 339  */
 340 int i915_buddy_alloc_range(struct i915_buddy_mm *mm,
 341                            struct list_head *blocks,
 342                            u64 start, u64 size)
 343 {
 344         struct i915_buddy_block *block;
 345         struct i915_buddy_block *buddy;
 346         LIST_HEAD(allocated);
 347         LIST_HEAD(dfs);
 348         u64 end;
 349         int err;
 350         int i;
 351
 352         if (size < mm->chunk_size)
 353                 return -EINVAL;
 354
 355         if (!IS_ALIGNED(size | start, mm->chunk_size))
 356                 return -EINVAL;
 357
 358         if (range_overflows(start, size, mm->size))
 359                 return -EINVAL;
 360
 361         for (i = 0; i < mm->n_roots; ++i)
 362                 list_add_tail(&mm->roots[i]->tmp_link, &dfs);
 363
 364         end = start + size - 1;
 365
 366         do {
 367                 u64 block_start;
 368                 u64 block_end;
 369
 370                 block = list_first_entry_or_null(&dfs,
 371                                                  struct i915_buddy_block,
 372                                                  tmp_link);
 373                 if (!block)
 374                         break;
 375
 376                 list_del(&block->tmp_link);
 377
 378                 block_start = i915_buddy_block_offset(block);
 379                 block_end = block_start + i915_buddy_block_size(mm, block) - 1;
 380
 381                 if (!overlaps(start, end, block_start, block_end))
 382                         continue;
 383
 384                 if (i915_buddy_block_is_allocated(block)) {
 385                         err = -ENOSPC;
 386                         goto err_free;
 387                 }
 388
 389                 if (contains(start, end, block_start, block_end)) {
 390                         if (!i915_buddy_block_is_free(block)) {
 391                                 err = -ENOSPC;
 392                                 goto err_free;
 393                         }
 394
 395                         mark_allocated(block);
 396                         list_add_tail(&block->link, &allocated);
 397                         continue;
 398                 }
 399
 400                 if (!i915_buddy_block_is_split(block)) {
 401                         err = split_block(mm, block);
 402                         if (unlikely(err))
 403                                 goto err_undo;
 404                 }
 405
 406                 list_add(&block->right->tmp_link, &dfs);
 407                 list_add(&block->left->tmp_link, &dfs);
 408         } while (1);
 409
 410         list_splice_tail(&allocated, blocks);
 411         return 0;
 412
 413 err_undo:
 414         /*
 415          * We really don't want to leave around a bunch of split blocks, since
 416          * bigger is better, so make sure we merge everything back before we
 417          * free the allocated blocks.
 418          */
 419         buddy = get_buddy(block);
 420         if (buddy &&
 421             (i915_buddy_block_is_free(block) &&
 422              i915_buddy_block_is_free(buddy)))
 423                 __i915_buddy_free(mm, block);
 424
 425 err_free:
 426         i915_buddy_free_list(mm, &allocated);
 427         return err;
 428 }
 429
 430 #if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
 431 #include "selftests/i915_buddy.c"
 432 #endif