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