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