i915/selftests/scatterlist.c

0001 /*
0002  * Copyright © 2016 Intel Corporation
0003  *
0004  * Permission is hereby granted, free of charge, to any person obtaining a
0005  * copy of this software and associated documentation files (the "Software"),
0006  * to deal in the Software without restriction, including without limitation
0007  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
0008  * and/or sell copies of the Software, and to permit persons to whom the
0009  * Software is furnished to do so, subject to the following conditions:
0010  *
0011  * The above copyright notice and this permission notice (including the next
0012  * paragraph) shall be included in all copies or substantial portions of the
0013  * Software.
0014  *
0015  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
0016  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
0017  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
0018  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
0019  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
0020  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
0021  * IN THE SOFTWARE.
0022  */
0023
0024 #include <linux/prime_numbers.h>
0025 #include <linux/random.h>
0026
0027 #include "i915_selftest.h"
0028 #include "i915_utils.h"
0029
0030 #define PFN_BIAS (1 << 10)
0031
0032 struct pfn_table {
0033     struct sg_table st;
0034     unsigned long start, end;
0035 };
0036
0037 typedef unsigned int (*npages_fn_t)(unsigned long n,
0038                     unsigned long count,
0039                     struct rnd_state *rnd);
0040
0041 static noinline int expect_pfn_sg(struct pfn_table *pt,
0042                   npages_fn_t npages_fn,
0043                   struct rnd_state *rnd,
0044                   const char *who,
0045                   unsigned long timeout)
0046 {
0047     struct scatterlist *sg;
0048     unsigned long pfn, n;
0049
0050     pfn = pt->start;
0051     for_each_sg(pt->st.sgl, sg, pt->st.nents, n) {
0052         struct page *page = sg_page(sg);
0053         unsigned int npages = npages_fn(n, pt->st.nents, rnd);
0054
0055         if (page_to_pfn(page) != pfn) {
0056             pr_err("%s: %s left pages out of order, expected pfn %lu, found pfn %lu (using for_each_sg)\n",
0057                    __func__, who, pfn, page_to_pfn(page));
0058             return -EINVAL;
0059         }
0060
0061         if (sg->length != npages * PAGE_SIZE) {
0062             pr_err("%s: %s copied wrong sg length, expected size %lu, found %u (using for_each_sg)\n",
0063                    __func__, who, npages * PAGE_SIZE, sg->length);
0064             return -EINVAL;
0065         }
0066
0067         if (igt_timeout(timeout, "%s timed out\n", who))
0068             return -EINTR;
0069
0070         pfn += npages;
0071     }
0072     if (pfn != pt->end) {
0073         pr_err("%s: %s finished on wrong pfn, expected %lu, found %lu\n",
0074                __func__, who, pt->end, pfn);
0075         return -EINVAL;
0076     }
0077
0078     return 0;
0079 }
0080
0081 static noinline int expect_pfn_sg_page_iter(struct pfn_table *pt,
0082                         const char *who,
0083                         unsigned long timeout)
0084 {
0085     struct sg_page_iter sgiter;
0086     unsigned long pfn;
0087
0088     pfn = pt->start;
0089     for_each_sg_page(pt->st.sgl, &sgiter, pt->st.nents, 0) {
0090         struct page *page = sg_page_iter_page(&sgiter);
0091
0092         if (page != pfn_to_page(pfn)) {
0093             pr_err("%s: %s left pages out of order, expected pfn %lu, found pfn %lu (using for_each_sg_page)\n",
0094                    __func__, who, pfn, page_to_pfn(page));
0095             return -EINVAL;
0096         }
0097
0098         if (igt_timeout(timeout, "%s timed out\n", who))
0099             return -EINTR;
0100
0101         pfn++;
0102     }
0103     if (pfn != pt->end) {
0104         pr_err("%s: %s finished on wrong pfn, expected %lu, found %lu\n",
0105                __func__, who, pt->end, pfn);
0106         return -EINVAL;
0107     }
0108
0109     return 0;
0110 }
0111
0112 static noinline int expect_pfn_sgtiter(struct pfn_table *pt,
0113                        const char *who,
0114                        unsigned long timeout)
0115 {
0116     struct sgt_iter sgt;
0117     struct page *page;
0118     unsigned long pfn;
0119
0120     pfn = pt->start;
0121     for_each_sgt_page(page, sgt, &pt->st) {
0122         if (page != pfn_to_page(pfn)) {
0123             pr_err("%s: %s left pages out of order, expected pfn %lu, found pfn %lu (using for_each_sgt_page)\n",
0124                    __func__, who, pfn, page_to_pfn(page));
0125             return -EINVAL;
0126         }
0127
0128         if (igt_timeout(timeout, "%s timed out\n", who))
0129             return -EINTR;
0130
0131         pfn++;
0132     }
0133     if (pfn != pt->end) {
0134         pr_err("%s: %s finished on wrong pfn, expected %lu, found %lu\n",
0135                __func__, who, pt->end, pfn);
0136         return -EINVAL;
0137     }
0138
0139     return 0;
0140 }
0141
0142 static int expect_pfn_sgtable(struct pfn_table *pt,
0143                   npages_fn_t npages_fn,
0144                   struct rnd_state *rnd,
0145                   const char *who,
0146                   unsigned long timeout)
0147 {
0148     int err;
0149
0150     err = expect_pfn_sg(pt, npages_fn, rnd, who, timeout);
0151     if (err)
0152         return err;
0153
0154     err = expect_pfn_sg_page_iter(pt, who, timeout);
0155     if (err)
0156         return err;
0157
0158     err = expect_pfn_sgtiter(pt, who, timeout);
0159     if (err)
0160         return err;
0161
0162     return 0;
0163 }
0164
0165 static unsigned int one(unsigned long n,
0166             unsigned long count,
0167             struct rnd_state *rnd)
0168 {
0169     return 1;
0170 }
0171
0172 static unsigned int grow(unsigned long n,
0173              unsigned long count,
0174              struct rnd_state *rnd)
0175 {
0176     return n + 1;
0177 }
0178
0179 static unsigned int shrink(unsigned long n,
0180                unsigned long count,
0181                struct rnd_state *rnd)
0182 {
0183     return count - n;
0184 }
0185
0186 static unsigned int random(unsigned long n,
0187                unsigned long count,
0188                struct rnd_state *rnd)
0189 {
0190     return 1 + (prandom_u32_state(rnd) % 1024);
0191 }
0192
0193 static unsigned int random_page_size_pages(unsigned long n,
0194                        unsigned long count,
0195                        struct rnd_state *rnd)
0196 {
0197     /* 4K, 64K, 2M */
0198     static unsigned int page_count[] = {
0199         BIT(12) >> PAGE_SHIFT,
0200         BIT(16) >> PAGE_SHIFT,
0201         BIT(21) >> PAGE_SHIFT,
0202     };
0203
0204     return page_count[(prandom_u32_state(rnd) % 3)];
0205 }
0206
0207 static inline bool page_contiguous(struct page *first,
0208                    struct page *last,
0209                    unsigned long npages)
0210 {
0211     return first + npages == last;
0212 }
0213
0214 static int alloc_table(struct pfn_table *pt,
0215                unsigned long count, unsigned long max,
0216                npages_fn_t npages_fn,
0217                struct rnd_state *rnd,
0218                int alloc_error)
0219 {
0220     struct scatterlist *sg;
0221     unsigned long n, pfn;
0222
0223     if (sg_alloc_table(&pt->st, max,
0224                GFP_KERNEL | __GFP_NORETRY | __GFP_NOWARN))
0225         return alloc_error;
0226
0227     /* count should be less than 20 to prevent overflowing sg->length */
0228     GEM_BUG_ON(overflows_type(count * PAGE_SIZE, sg->length));
0229
0230     /* Construct a table where each scatterlist contains different number
0231      * of entries. The idea is to check that we can iterate the individual
0232      * pages from inside the coalesced lists.
0233      */
0234     pt->start = PFN_BIAS;
0235     pfn = pt->start;
0236     sg = pt->st.sgl;
0237     for (n = 0; n < count; n++) {
0238         unsigned long npages = npages_fn(n, count, rnd);
0239
0240         /* Nobody expects the Sparse Memmap! */
0241         if (!page_contiguous(pfn_to_page(pfn),
0242                      pfn_to_page(pfn + npages),
0243                      npages)) {
0244             sg_free_table(&pt->st);
0245             return -ENOSPC;
0246         }
0247
0248         if (n)
0249             sg = sg_next(sg);
0250         sg_set_page(sg, pfn_to_page(pfn), npages * PAGE_SIZE, 0);
0251
0252         GEM_BUG_ON(page_to_pfn(sg_page(sg)) != pfn);
0253         GEM_BUG_ON(sg->length != npages * PAGE_SIZE);
0254         GEM_BUG_ON(sg->offset != 0);
0255
0256         pfn += npages;
0257     }
0258     sg_mark_end(sg);
0259     pt->st.nents = n;
0260     pt->end = pfn;
0261
0262     return 0;
0263 }
0264
0265 static const npages_fn_t npages_funcs[] = {
0266     one,
0267     grow,
0268     shrink,
0269     random,
0270     random_page_size_pages,
0271     NULL,
0272 };
0273
0274 static int igt_sg_alloc(void *ignored)
0275 {
0276     IGT_TIMEOUT(end_time);
0277     const unsigned long max_order = 20; /* approximating a 4GiB object */
0278     struct rnd_state prng;
0279     unsigned long prime;
0280     int alloc_error = -ENOMEM;
0281
0282     for_each_prime_number(prime, max_order) {
0283         unsigned long size = BIT(prime);
0284         int offset;
0285
0286         for (offset = -1; offset <= 1; offset++) {
0287             unsigned long sz = size + offset;
0288             const npages_fn_t *npages;
0289             struct pfn_table pt;
0290             int err;
0291
0292             for (npages = npages_funcs; *npages; npages++) {
0293                 prandom_seed_state(&prng,
0294                            i915_selftest.random_seed);
0295                 err = alloc_table(&pt, sz, sz, *npages, &prng,
0296                           alloc_error);
0297                 if (err == -ENOSPC)
0298                     break;
0299                 if (err)
0300                     return err;
0301
0302                 prandom_seed_state(&prng,
0303                            i915_selftest.random_seed);
0304                 err = expect_pfn_sgtable(&pt, *npages, &prng,
0305                              "sg_alloc_table",
0306                              end_time);
0307                 sg_free_table(&pt.st);
0308                 if (err)
0309                     return err;
0310             }
0311         }
0312
0313         /* Test at least one continuation before accepting oom */
0314         if (size > SG_MAX_SINGLE_ALLOC)
0315             alloc_error = -ENOSPC;
0316     }
0317
0318     return 0;
0319 }
0320
0321 static int igt_sg_trim(void *ignored)
0322 {
0323     IGT_TIMEOUT(end_time);
0324     const unsigned long max = PAGE_SIZE; /* not prime! */
0325     struct pfn_table pt;
0326     unsigned long prime;
0327     int alloc_error = -ENOMEM;
0328
0329     for_each_prime_number(prime, max) {
0330         const npages_fn_t *npages;
0331         int err;
0332
0333         for (npages = npages_funcs; *npages; npages++) {
0334             struct rnd_state prng;
0335
0336             prandom_seed_state(&prng, i915_selftest.random_seed);
0337             err = alloc_table(&pt, prime, max, *npages, &prng,
0338                       alloc_error);
0339             if (err == -ENOSPC)
0340                 break;
0341             if (err)
0342                 return err;
0343
0344             if (i915_sg_trim(&pt.st)) {
0345                 if (pt.st.orig_nents != prime ||
0346                     pt.st.nents != prime) {
0347                     pr_err("i915_sg_trim failed (nents %u, orig_nents %u), expected %lu\n",
0348                            pt.st.nents, pt.st.orig_nents, prime);
0349                     err = -EINVAL;
0350                 } else {
0351                     prandom_seed_state(&prng,
0352                                i915_selftest.random_seed);
0353                     err = expect_pfn_sgtable(&pt,
0354                                  *npages, &prng,
0355                                  "i915_sg_trim",
0356                                  end_time);
0357                 }
0358             }
0359             sg_free_table(&pt.st);
0360             if (err)
0361                 return err;
0362         }
0363
0364         /* Test at least one continuation before accepting oom */
0365         if (prime > SG_MAX_SINGLE_ALLOC)
0366             alloc_error = -ENOSPC;
0367     }
0368
0369     return 0;
0370 }
0371
0372 int scatterlist_mock_selftests(void)
0373 {
0374     static const struct i915_subtest tests[] = {
0375         SUBTEST(igt_sg_alloc),
0376         SUBTEST(igt_sg_trim),
0377     };
0378
0379     return i915_subtests(tests, NULL);
0380 }