drm/selftests/test-drm_buddy.c

0001 // SPDX-License-Identifier: MIT
0002 /*
0003  * Copyright © 2019 Intel Corporation
0004  */
0005
0006 #define pr_fmt(fmt) "drm_buddy: " fmt
0007
0008 #include <linux/module.h>
0009 #include <linux/prime_numbers.h>
0010 #include <linux/sched/signal.h>
0011
0012 #include <drm/drm_buddy.h>
0013
0014 #include "../lib/drm_random.h"
0015
0016 #define TESTS "drm_buddy_selftests.h"
0017 #include "drm_selftest.h"
0018
0019 #define IGT_TIMEOUT(name__) \
0020     unsigned long name__ = jiffies + MAX_SCHEDULE_TIMEOUT
0021
0022 static unsigned int random_seed;
0023
0024 static inline u64 get_size(int order, u64 chunk_size)
0025 {
0026     return (1 << order) * chunk_size;
0027 }
0028
0029 __printf(2, 3)
0030 static bool __igt_timeout(unsigned long timeout, const char *fmt, ...)
0031 {
0032     va_list va;
0033
0034     if (!signal_pending(current)) {
0035         cond_resched();
0036         if (time_before(jiffies, timeout))
0037             return false;
0038     }
0039
0040     if (fmt) {
0041         va_start(va, fmt);
0042         vprintk(fmt, va);
0043         va_end(va);
0044     }
0045
0046     return true;
0047 }
0048
0049 static inline const char *yesno(bool v)
0050 {
0051     return v ? "yes" : "no";
0052 }
0053
0054 static void __igt_dump_block(struct drm_buddy *mm,
0055                  struct drm_buddy_block *block,
0056                  bool buddy)
0057 {
0058     pr_err("block info: header=%llx, state=%u, order=%d, offset=%llx size=%llx root=%s buddy=%s\n",
0059            block->header,
0060            drm_buddy_block_state(block),
0061            drm_buddy_block_order(block),
0062            drm_buddy_block_offset(block),
0063            drm_buddy_block_size(mm, block),
0064            yesno(!block->parent),
0065            yesno(buddy));
0066 }
0067
0068 static void igt_dump_block(struct drm_buddy *mm,
0069                struct drm_buddy_block *block)
0070 {
0071     struct drm_buddy_block *buddy;
0072
0073     __igt_dump_block(mm, block, false);
0074
0075     buddy = drm_get_buddy(block);
0076     if (buddy)
0077         __igt_dump_block(mm, buddy, true);
0078 }
0079
0080 static int igt_check_block(struct drm_buddy *mm,
0081                struct drm_buddy_block *block)
0082 {
0083     struct drm_buddy_block *buddy;
0084     unsigned int block_state;
0085     u64 block_size;
0086     u64 offset;
0087     int err = 0;
0088
0089     block_state = drm_buddy_block_state(block);
0090
0091     if (block_state != DRM_BUDDY_ALLOCATED &&
0092         block_state != DRM_BUDDY_FREE &&
0093         block_state != DRM_BUDDY_SPLIT) {
0094         pr_err("block state mismatch\n");
0095         err = -EINVAL;
0096     }
0097
0098     block_size = drm_buddy_block_size(mm, block);
0099     offset = drm_buddy_block_offset(block);
0100
0101     if (block_size < mm->chunk_size) {
0102         pr_err("block size smaller than min size\n");
0103         err = -EINVAL;
0104     }
0105
0106     if (!is_power_of_2(block_size)) {
0107         pr_err("block size not power of two\n");
0108         err = -EINVAL;
0109     }
0110
0111     if (!IS_ALIGNED(block_size, mm->chunk_size)) {
0112         pr_err("block size not aligned to min size\n");
0113         err = -EINVAL;
0114     }
0115
0116     if (!IS_ALIGNED(offset, mm->chunk_size)) {
0117         pr_err("block offset not aligned to min size\n");
0118         err = -EINVAL;
0119     }
0120
0121     if (!IS_ALIGNED(offset, block_size)) {
0122         pr_err("block offset not aligned to block size\n");
0123         err = -EINVAL;
0124     }
0125
0126     buddy = drm_get_buddy(block);
0127
0128     if (!buddy && block->parent) {
0129         pr_err("buddy has gone fishing\n");
0130         err = -EINVAL;
0131     }
0132
0133     if (buddy) {
0134         if (drm_buddy_block_offset(buddy) != (offset ^ block_size)) {
0135             pr_err("buddy has wrong offset\n");
0136             err = -EINVAL;
0137         }
0138
0139         if (drm_buddy_block_size(mm, buddy) != block_size) {
0140             pr_err("buddy size mismatch\n");
0141             err = -EINVAL;
0142         }
0143
0144         if (drm_buddy_block_state(buddy) == block_state &&
0145             block_state == DRM_BUDDY_FREE) {
0146             pr_err("block and its buddy are free\n");
0147             err = -EINVAL;
0148         }
0149     }
0150
0151     return err;
0152 }
0153
0154 static int igt_check_blocks(struct drm_buddy *mm,
0155                 struct list_head *blocks,
0156                 u64 expected_size,
0157                 bool is_contiguous)
0158 {
0159     struct drm_buddy_block *block;
0160     struct drm_buddy_block *prev;
0161     u64 total;
0162     int err = 0;
0163
0164     block = NULL;
0165     prev = NULL;
0166     total = 0;
0167
0168     list_for_each_entry(block, blocks, link) {
0169         err = igt_check_block(mm, block);
0170
0171         if (!drm_buddy_block_is_allocated(block)) {
0172             pr_err("block not allocated\n"),
0173                    err = -EINVAL;
0174         }
0175
0176         if (is_contiguous && prev) {
0177             u64 prev_block_size;
0178             u64 prev_offset;
0179             u64 offset;
0180
0181             prev_offset = drm_buddy_block_offset(prev);
0182             prev_block_size = drm_buddy_block_size(mm, prev);
0183             offset = drm_buddy_block_offset(block);
0184
0185             if (offset != (prev_offset + prev_block_size)) {
0186                 pr_err("block offset mismatch\n");
0187                 err = -EINVAL;
0188             }
0189         }
0190
0191         if (err)
0192             break;
0193
0194         total += drm_buddy_block_size(mm, block);
0195         prev = block;
0196     }
0197
0198     if (!err) {
0199         if (total != expected_size) {
0200             pr_err("size mismatch, expected=%llx, found=%llx\n",
0201                    expected_size, total);
0202             err = -EINVAL;
0203         }
0204         return err;
0205     }
0206
0207     if (prev) {
0208         pr_err("prev block, dump:\n");
0209         igt_dump_block(mm, prev);
0210     }
0211
0212     pr_err("bad block, dump:\n");
0213     igt_dump_block(mm, block);
0214
0215     return err;
0216 }
0217
0218 static int igt_check_mm(struct drm_buddy *mm)
0219 {
0220     struct drm_buddy_block *root;
0221     struct drm_buddy_block *prev;
0222     unsigned int i;
0223     u64 total;
0224     int err = 0;
0225
0226     if (!mm->n_roots) {
0227         pr_err("n_roots is zero\n");
0228         return -EINVAL;
0229     }
0230
0231     if (mm->n_roots != hweight64(mm->size)) {
0232         pr_err("n_roots mismatch, n_roots=%u, expected=%lu\n",
0233                mm->n_roots, hweight64(mm->size));
0234         return -EINVAL;
0235     }
0236
0237     root = NULL;
0238     prev = NULL;
0239     total = 0;
0240
0241     for (i = 0; i < mm->n_roots; ++i) {
0242         struct drm_buddy_block *block;
0243         unsigned int order;
0244
0245         root = mm->roots[i];
0246         if (!root) {
0247             pr_err("root(%u) is NULL\n", i);
0248             err = -EINVAL;
0249             break;
0250         }
0251
0252         err = igt_check_block(mm, root);
0253
0254         if (!drm_buddy_block_is_free(root)) {
0255             pr_err("root not free\n");
0256             err = -EINVAL;
0257         }
0258
0259         order = drm_buddy_block_order(root);
0260
0261         if (!i) {
0262             if (order != mm->max_order) {
0263                 pr_err("max order root missing\n");
0264                 err = -EINVAL;
0265             }
0266         }
0267
0268         if (prev) {
0269             u64 prev_block_size;
0270             u64 prev_offset;
0271             u64 offset;
0272
0273             prev_offset = drm_buddy_block_offset(prev);
0274             prev_block_size = drm_buddy_block_size(mm, prev);
0275             offset = drm_buddy_block_offset(root);
0276
0277             if (offset != (prev_offset + prev_block_size)) {
0278                 pr_err("root offset mismatch\n");
0279                 err = -EINVAL;
0280             }
0281         }
0282
0283         block = list_first_entry_or_null(&mm->free_list[order],
0284                          struct drm_buddy_block,
0285                          link);
0286         if (block != root) {
0287             pr_err("root mismatch at order=%u\n", order);
0288             err = -EINVAL;
0289         }
0290
0291         if (err)
0292             break;
0293
0294         prev = root;
0295         total += drm_buddy_block_size(mm, root);
0296     }
0297
0298     if (!err) {
0299         if (total != mm->size) {
0300             pr_err("expected mm size=%llx, found=%llx\n", mm->size,
0301                    total);
0302             err = -EINVAL;
0303         }
0304         return err;
0305     }
0306
0307     if (prev) {
0308         pr_err("prev root(%u), dump:\n", i - 1);
0309         igt_dump_block(mm, prev);
0310     }
0311
0312     if (root) {
0313         pr_err("bad root(%u), dump:\n", i);
0314         igt_dump_block(mm, root);
0315     }
0316
0317     return err;
0318 }
0319
0320 static void igt_mm_config(u64 *size, u64 *chunk_size)
0321 {
0322     DRM_RND_STATE(prng, random_seed);
0323     u32 s, ms;
0324
0325     /* Nothing fancy, just try to get an interesting bit pattern */
0326
0327     prandom_seed_state(&prng, random_seed);
0328
0329     /* Let size be a random number of pages up to 8 GB (2M pages) */
0330     s = 1 + drm_prandom_u32_max_state((BIT(33 - 12)) - 1, &prng);
0331     /* Let the chunk size be a random power of 2 less than size */
0332     ms = BIT(drm_prandom_u32_max_state(ilog2(s), &prng));
0333     /* Round size down to the chunk size */
0334     s &= -ms;
0335
0336     /* Convert from pages to bytes */
0337     *chunk_size = (u64)ms << 12;
0338     *size = (u64)s << 12;
0339 }
0340
0341 static int igt_buddy_alloc_pathological(void *arg)
0342 {
0343     u64 mm_size, size, min_page_size, start = 0;
0344     struct drm_buddy_block *block;
0345     const int max_order = 3;
0346     unsigned long flags = 0;
0347     int order, top, err;
0348     struct drm_buddy mm;
0349     LIST_HEAD(blocks);
0350     LIST_HEAD(holes);
0351     LIST_HEAD(tmp);
0352
0353     /*
0354      * Create a pot-sized mm, then allocate one of each possible
0355      * order within. This should leave the mm with exactly one
0356      * page left. Free the largest block, then whittle down again.
0357      * Eventually we will have a fully 50% fragmented mm.
0358      */
0359
0360     mm_size = PAGE_SIZE << max_order;
0361     err = drm_buddy_init(&mm, mm_size, PAGE_SIZE);
0362     if (err) {
0363         pr_err("buddy_init failed(%d)\n", err);
0364         return err;
0365     }
0366     BUG_ON(mm.max_order != max_order);
0367
0368     for (top = max_order; top; top--) {
0369         /* Make room by freeing the largest allocated block */
0370         block = list_first_entry_or_null(&blocks, typeof(*block), link);
0371         if (block) {
0372             list_del(&block->link);
0373             drm_buddy_free_block(&mm, block);
0374         }
0375
0376         for (order = top; order--; ) {
0377             size = min_page_size = get_size(order, PAGE_SIZE);
0378             err = drm_buddy_alloc_blocks(&mm, start, mm_size, size,
0379                              min_page_size, &tmp, flags);
0380             if (err) {
0381                 pr_info("buddy_alloc hit -ENOMEM with order=%d, top=%d\n",
0382                     order, top);
0383                 goto err;
0384             }
0385
0386             block = list_first_entry_or_null(&tmp,
0387                              struct drm_buddy_block,
0388                              link);
0389             if (!block) {
0390                 pr_err("alloc_blocks has no blocks\n");
0391                 err = -EINVAL;
0392                 goto err;
0393             }
0394
0395             list_move_tail(&block->link, &blocks);
0396         }
0397
0398         /* There should be one final page for this sub-allocation */
0399         size = min_page_size = get_size(0, PAGE_SIZE);
0400         err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
0401         if (err) {
0402             pr_info("buddy_alloc hit -ENOMEM for hole\n");
0403             goto err;
0404         }
0405
0406         block = list_first_entry_or_null(&tmp,
0407                          struct drm_buddy_block,
0408                          link);
0409         if (!block) {
0410             pr_err("alloc_blocks has no blocks\n");
0411             err = -EINVAL;
0412             goto err;
0413         }
0414
0415         list_move_tail(&block->link, &holes);
0416
0417         size = min_page_size = get_size(top, PAGE_SIZE);
0418         err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
0419         if (!err) {
0420             pr_info("buddy_alloc unexpectedly succeeded at top-order %d/%d, it should be full!",
0421                 top, max_order);
0422             block = list_first_entry_or_null(&tmp,
0423                              struct drm_buddy_block,
0424                              link);
0425             if (!block) {
0426                 pr_err("alloc_blocks has no blocks\n");
0427                 err = -EINVAL;
0428                 goto err;
0429             }
0430
0431             list_move_tail(&block->link, &blocks);
0432             err = -EINVAL;
0433             goto err;
0434         }
0435     }
0436
0437     drm_buddy_free_list(&mm, &holes);
0438
0439     /* Nothing larger than blocks of chunk_size now available */
0440     for (order = 1; order <= max_order; order++) {
0441         size = min_page_size = get_size(order, PAGE_SIZE);
0442         err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
0443         if (!err) {
0444             pr_info("buddy_alloc unexpectedly succeeded at order %d, it should be full!",
0445                 order);
0446             block = list_first_entry_or_null(&tmp,
0447                              struct drm_buddy_block,
0448                              link);
0449             if (!block) {
0450                 pr_err("alloc_blocks has no blocks\n");
0451                 err = -EINVAL;
0452                 goto err;
0453             }
0454
0455             list_move_tail(&block->link, &blocks);
0456             err = -EINVAL;
0457             goto err;
0458         }
0459     }
0460
0461     if (err)
0462         err = 0;
0463
0464 err:
0465     list_splice_tail(&holes, &blocks);
0466     drm_buddy_free_list(&mm, &blocks);
0467     drm_buddy_fini(&mm);
0468     return err;
0469 }
0470
0471 static int igt_buddy_alloc_smoke(void *arg)
0472 {
0473     u64 mm_size, min_page_size, chunk_size, start = 0;
0474     unsigned long flags = 0;
0475     struct drm_buddy mm;
0476     int *order;
0477     int err, i;
0478
0479     DRM_RND_STATE(prng, random_seed);
0480     IGT_TIMEOUT(end_time);
0481
0482     igt_mm_config(&mm_size, &chunk_size);
0483
0484     err = drm_buddy_init(&mm, mm_size, chunk_size);
0485     if (err) {
0486         pr_err("buddy_init failed(%d)\n", err);
0487         return err;
0488     }
0489
0490     order = drm_random_order(mm.max_order + 1, &prng);
0491     if (!order) {
0492         err = -ENOMEM;
0493         goto out_fini;
0494     }
0495
0496     for (i = 0; i <= mm.max_order; ++i) {
0497         struct drm_buddy_block *block;
0498         int max_order = order[i];
0499         bool timeout = false;
0500         LIST_HEAD(blocks);
0501         u64 total, size;
0502         LIST_HEAD(tmp);
0503         int order;
0504
0505         err = igt_check_mm(&mm);
0506         if (err) {
0507             pr_err("pre-mm check failed, abort\n");
0508             break;
0509         }
0510
0511         order = max_order;
0512         total = 0;
0513
0514         do {
0515 retry:
0516             size = min_page_size = get_size(order, chunk_size);
0517             err = drm_buddy_alloc_blocks(&mm, start, mm_size, size,
0518                              min_page_size, &tmp, flags);
0519             if (err) {
0520                 if (err == -ENOMEM) {
0521                     pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
0522                         order);
0523                 } else {
0524                     if (order--) {
0525                         err = 0;
0526                         goto retry;
0527                     }
0528
0529                     pr_err("buddy_alloc with order=%d failed(%d)\n",
0530                            order, err);
0531                 }
0532
0533                 break;
0534             }
0535
0536             block = list_first_entry_or_null(&tmp,
0537                              struct drm_buddy_block,
0538                              link);
0539             if (!block) {
0540                 pr_err("alloc_blocks has no blocks\n");
0541                 err = -EINVAL;
0542                 break;
0543             }
0544
0545             list_move_tail(&block->link, &blocks);
0546
0547             if (drm_buddy_block_order(block) != order) {
0548                 pr_err("buddy_alloc order mismatch\n");
0549                 err = -EINVAL;
0550                 break;
0551             }
0552
0553             total += drm_buddy_block_size(&mm, block);
0554
0555             if (__igt_timeout(end_time, NULL)) {
0556                 timeout = true;
0557                 break;
0558             }
0559         } while (total < mm.size);
0560
0561         if (!err)
0562             err = igt_check_blocks(&mm, &blocks, total, false);
0563
0564         drm_buddy_free_list(&mm, &blocks);
0565
0566         if (!err) {
0567             err = igt_check_mm(&mm);
0568             if (err)
0569                 pr_err("post-mm check failed\n");
0570         }
0571
0572         if (err || timeout)
0573             break;
0574
0575         cond_resched();
0576     }
0577
0578     if (err == -ENOMEM)
0579         err = 0;
0580
0581     kfree(order);
0582 out_fini:
0583     drm_buddy_fini(&mm);
0584
0585     return err;
0586 }
0587
0588 static int igt_buddy_alloc_pessimistic(void *arg)
0589 {
0590     u64 mm_size, size, min_page_size, start = 0;
0591     struct drm_buddy_block *block, *bn;
0592     const unsigned int max_order = 16;
0593     unsigned long flags = 0;
0594     struct drm_buddy mm;
0595     unsigned int order;
0596     LIST_HEAD(blocks);
0597     LIST_HEAD(tmp);
0598     int err;
0599
0600     /*
0601      * Create a pot-sized mm, then allocate one of each possible
0602      * order within. This should leave the mm with exactly one
0603      * page left.
0604      */
0605
0606     mm_size = PAGE_SIZE << max_order;
0607     err = drm_buddy_init(&mm, mm_size, PAGE_SIZE);
0608     if (err) {
0609         pr_err("buddy_init failed(%d)\n", err);
0610         return err;
0611     }
0612     BUG_ON(mm.max_order != max_order);
0613
0614     for (order = 0; order < max_order; order++) {
0615         size = min_page_size = get_size(order, PAGE_SIZE);
0616         err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
0617         if (err) {
0618             pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
0619                 order);
0620             goto err;
0621         }
0622
0623         block = list_first_entry_or_null(&tmp,
0624                          struct drm_buddy_block,
0625                          link);
0626         if (!block) {
0627             pr_err("alloc_blocks has no blocks\n");
0628             err = -EINVAL;
0629             goto err;
0630         }
0631
0632         list_move_tail(&block->link, &blocks);
0633     }
0634
0635     /* And now the last remaining block available */
0636     size = min_page_size = get_size(0, PAGE_SIZE);
0637     err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
0638     if (err) {
0639         pr_info("buddy_alloc hit -ENOMEM on final alloc\n");
0640         goto err;
0641     }
0642
0643     block = list_first_entry_or_null(&tmp,
0644                      struct drm_buddy_block,
0645                      link);
0646     if (!block) {
0647         pr_err("alloc_blocks has no blocks\n");
0648         err = -EINVAL;
0649         goto err;
0650     }
0651
0652     list_move_tail(&block->link, &blocks);
0653
0654     /* Should be completely full! */
0655     for (order = max_order; order--; ) {
0656         size = min_page_size = get_size(order, PAGE_SIZE);
0657         err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
0658         if (!err) {
0659             pr_info("buddy_alloc unexpectedly succeeded at order %d, it should be full!",
0660                 order);
0661             block = list_first_entry_or_null(&tmp,
0662                              struct drm_buddy_block,
0663                              link);
0664             if (!block) {
0665                 pr_err("alloc_blocks has no blocks\n");
0666                 err = -EINVAL;
0667                 goto err;
0668             }
0669
0670             list_move_tail(&block->link, &blocks);
0671             err = -EINVAL;
0672             goto err;
0673         }
0674     }
0675
0676     block = list_last_entry(&blocks, typeof(*block), link);
0677     list_del(&block->link);
0678     drm_buddy_free_block(&mm, block);
0679
0680     /* As we free in increasing size, we make available larger blocks */
0681     order = 1;
0682     list_for_each_entry_safe(block, bn, &blocks, link) {
0683         list_del(&block->link);
0684         drm_buddy_free_block(&mm, block);
0685
0686         size = min_page_size = get_size(order, PAGE_SIZE);
0687         err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
0688         if (err) {
0689             pr_info("buddy_alloc (realloc) hit -ENOMEM with order=%d\n",
0690                 order);
0691             goto err;
0692         }
0693
0694         block = list_first_entry_or_null(&tmp,
0695                          struct drm_buddy_block,
0696                          link);
0697         if (!block) {
0698             pr_err("alloc_blocks has no blocks\n");
0699             err = -EINVAL;
0700             goto err;
0701         }
0702
0703         list_del(&block->link);
0704         drm_buddy_free_block(&mm, block);
0705         order++;
0706     }
0707
0708     /* To confirm, now the whole mm should be available */
0709     size = min_page_size = get_size(max_order, PAGE_SIZE);
0710     err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
0711     if (err) {
0712         pr_info("buddy_alloc (realloc) hit -ENOMEM with order=%d\n",
0713             max_order);
0714         goto err;
0715     }
0716
0717     block = list_first_entry_or_null(&tmp,
0718                      struct drm_buddy_block,
0719                      link);
0720     if (!block) {
0721         pr_err("alloc_blocks has no blocks\n");
0722         err = -EINVAL;
0723         goto err;
0724     }
0725
0726     list_del(&block->link);
0727     drm_buddy_free_block(&mm, block);
0728
0729 err:
0730     drm_buddy_free_list(&mm, &blocks);
0731     drm_buddy_fini(&mm);
0732     return err;
0733 }
0734
0735 static int igt_buddy_alloc_optimistic(void *arg)
0736 {
0737     u64 mm_size, size, min_page_size, start = 0;
0738     struct drm_buddy_block *block;
0739     unsigned long flags = 0;
0740     const int max_order = 16;
0741     struct drm_buddy mm;
0742     LIST_HEAD(blocks);
0743     LIST_HEAD(tmp);
0744     int order, err;
0745
0746     /*
0747      * Create a mm with one block of each order available, and
0748      * try to allocate them all.
0749      */
0750
0751     mm_size = PAGE_SIZE * ((1 << (max_order + 1)) - 1);
0752     err = drm_buddy_init(&mm,
0753                  mm_size,
0754                  PAGE_SIZE);
0755     if (err) {
0756         pr_err("buddy_init failed(%d)\n", err);
0757         return err;
0758     }
0759
0760     BUG_ON(mm.max_order != max_order);
0761
0762     for (order = 0; order <= max_order; order++) {
0763         size = min_page_size = get_size(order, PAGE_SIZE);
0764         err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
0765         if (err) {
0766             pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
0767                 order);
0768             goto err;
0769         }
0770
0771         block = list_first_entry_or_null(&tmp,
0772                          struct drm_buddy_block,
0773                          link);
0774         if (!block) {
0775             pr_err("alloc_blocks has no blocks\n");
0776             err = -EINVAL;
0777             goto err;
0778         }
0779
0780         list_move_tail(&block->link, &blocks);
0781     }
0782
0783     /* Should be completely full! */
0784     size = min_page_size = get_size(0, PAGE_SIZE);
0785     err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
0786     if (!err) {
0787         pr_info("buddy_alloc unexpectedly succeeded, it should be full!");
0788         block = list_first_entry_or_null(&tmp,
0789                          struct drm_buddy_block,
0790                          link);
0791         if (!block) {
0792             pr_err("alloc_blocks has no blocks\n");
0793             err = -EINVAL;
0794             goto err;
0795         }
0796
0797         list_move_tail(&block->link, &blocks);
0798         err = -EINVAL;
0799         goto err;
0800     } else {
0801         err = 0;
0802     }
0803
0804 err:
0805     drm_buddy_free_list(&mm, &blocks);
0806     drm_buddy_fini(&mm);
0807     return err;
0808 }
0809
0810 static int igt_buddy_alloc_range(void *arg)
0811 {
0812     unsigned long flags = DRM_BUDDY_RANGE_ALLOCATION;
0813     u64 offset, size, rem, chunk_size, end;
0814     unsigned long page_num;
0815     struct drm_buddy mm;
0816     LIST_HEAD(blocks);
0817     int err;
0818
0819     igt_mm_config(&size, &chunk_size);
0820
0821     err = drm_buddy_init(&mm, size, chunk_size);
0822     if (err) {
0823         pr_err("buddy_init failed(%d)\n", err);
0824         return err;
0825     }
0826
0827     err = igt_check_mm(&mm);
0828     if (err) {
0829         pr_err("pre-mm check failed, abort, abort, abort!\n");
0830         goto err_fini;
0831     }
0832
0833     rem = mm.size;
0834     offset = 0;
0835
0836     for_each_prime_number_from(page_num, 1, ULONG_MAX - 1) {
0837         struct drm_buddy_block *block;
0838         LIST_HEAD(tmp);
0839
0840         size = min(page_num * mm.chunk_size, rem);
0841         end = offset + size;
0842
0843         err = drm_buddy_alloc_blocks(&mm, offset, end, size, mm.chunk_size, &tmp, flags);
0844         if (err) {
0845             if (err == -ENOMEM) {
0846                 pr_info("alloc_range hit -ENOMEM with size=%llx\n",
0847                     size);
0848             } else {
0849                 pr_err("alloc_range with offset=%llx, size=%llx failed(%d)\n",
0850                        offset, size, err);
0851             }
0852
0853             break;
0854         }
0855
0856         block = list_first_entry_or_null(&tmp,
0857                          struct drm_buddy_block,
0858                          link);
0859         if (!block) {
0860             pr_err("alloc_range has no blocks\n");
0861             err = -EINVAL;
0862             break;
0863         }
0864
0865         if (drm_buddy_block_offset(block) != offset) {
0866             pr_err("alloc_range start offset mismatch, found=%llx, expected=%llx\n",
0867                    drm_buddy_block_offset(block), offset);
0868             err = -EINVAL;
0869         }
0870
0871         if (!err)
0872             err = igt_check_blocks(&mm, &tmp, size, true);
0873
0874         list_splice_tail(&tmp, &blocks);
0875
0876         if (err)
0877             break;
0878
0879         offset += size;
0880
0881         rem -= size;
0882         if (!rem)
0883             break;
0884
0885         cond_resched();
0886     }
0887
0888     if (err == -ENOMEM)
0889         err = 0;
0890
0891     drm_buddy_free_list(&mm, &blocks);
0892
0893     if (!err) {
0894         err = igt_check_mm(&mm);
0895         if (err)
0896             pr_err("post-mm check failed\n");
0897     }
0898
0899 err_fini:
0900     drm_buddy_fini(&mm);
0901
0902     return err;
0903 }
0904
0905 static int igt_buddy_alloc_limit(void *arg)
0906 {
0907     u64 size = U64_MAX, start = 0;
0908     struct drm_buddy_block *block;
0909     unsigned long flags = 0;
0910     LIST_HEAD(allocated);
0911     struct drm_buddy mm;
0912     int err;
0913
0914     err = drm_buddy_init(&mm, size, PAGE_SIZE);
0915     if (err)
0916         return err;
0917
0918     if (mm.max_order != DRM_BUDDY_MAX_ORDER) {
0919         pr_err("mm.max_order(%d) != %d\n",
0920                mm.max_order, DRM_BUDDY_MAX_ORDER);
0921         err = -EINVAL;
0922         goto out_fini;
0923     }
0924
0925     size = mm.chunk_size << mm.max_order;
0926     err = drm_buddy_alloc_blocks(&mm, start, size, size,
0927                      PAGE_SIZE, &allocated, flags);
0928
0929     if (unlikely(err))
0930         goto out_free;
0931
0932     block = list_first_entry_or_null(&allocated,
0933                      struct drm_buddy_block,
0934                      link);
0935
0936     if (!block) {
0937         err = -EINVAL;
0938         goto out_fini;
0939     }
0940
0941     if (drm_buddy_block_order(block) != mm.max_order) {
0942         pr_err("block order(%d) != %d\n",
0943                drm_buddy_block_order(block), mm.max_order);
0944         err = -EINVAL;
0945         goto out_free;
0946     }
0947
0948     if (drm_buddy_block_size(&mm, block) !=
0949         BIT_ULL(mm.max_order) * PAGE_SIZE) {
0950         pr_err("block size(%llu) != %llu\n",
0951                drm_buddy_block_size(&mm, block),
0952                BIT_ULL(mm.max_order) * PAGE_SIZE);
0953         err = -EINVAL;
0954         goto out_free;
0955     }
0956
0957 out_free:
0958     drm_buddy_free_list(&mm, &allocated);
0959 out_fini:
0960     drm_buddy_fini(&mm);
0961     return err;
0962 }
0963
0964 static int igt_sanitycheck(void *ignored)
0965 {
0966     pr_info("%s - ok!\n", __func__);
0967     return 0;
0968 }
0969
0970 #include "drm_selftest.c"
0971
0972 static int __init test_drm_buddy_init(void)
0973 {
0974     int err;
0975
0976     while (!random_seed)
0977         random_seed = get_random_int();
0978
0979     pr_info("Testing DRM buddy manager (struct drm_buddy), with random_seed=0x%x\n",
0980         random_seed);
0981     err = run_selftests(selftests, ARRAY_SIZE(selftests), NULL);
0982
0983     return err > 0 ? 0 : err;
0984 }
0985
0986 static void __exit test_drm_buddy_exit(void)
0987 {
0988 }
0989
0990 module_init(test_drm_buddy_init);
0991 module_exit(test_drm_buddy_exit);
0992
0993 MODULE_AUTHOR("Intel Corporation");
0994 MODULE_LICENSE("GPL");