1 /* 2 * Copyright © 2016 Intel Corporation 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21 * IN THE SOFTWARE. 22 */ 23 24 #include <linux/prime_numbers.h> 25 #include <linux/random.h> 26 27 #include "i915_selftest.h" 28 #include "i915_utils.h" 29 30 #define PFN_BIAS (1 << 10) 31 32 struct pfn_table { 33 struct sg_table st; 34 unsigned long start, end; 35 }; 36 37 typedef unsigned int (*npages_fn_t)(unsigned long n, 38 unsigned long count, 39 struct rnd_state *rnd); 40 41 static noinline int expect_pfn_sg(struct pfn_table *pt, 42 npages_fn_t npages_fn, 43 struct rnd_state *rnd, 44 const char *who, 45 unsigned long timeout) 46 { 47 struct scatterlist *sg; 48 unsigned long pfn, n; 49 50 pfn = pt->start; 51 for_each_sg(pt->st.sgl, sg, pt->st.nents, n) { 52 struct page *page = sg_page(sg); 53 unsigned int npages = npages_fn(n, pt->st.nents, rnd); 54 55 if (page_to_pfn(page) != pfn) { 56 pr_err("%s: %s left pages out of order, expected pfn %lu, found pfn %lu (using for_each_sg)\n", 57 __func__, who, pfn, page_to_pfn(page)); 58 return -EINVAL; 59 } 60 61 if (sg->length != npages * PAGE_SIZE) { 62 pr_err("%s: %s copied wrong sg length, expected size %lu, found %u (using for_each_sg)\n", 63 __func__, who, npages * PAGE_SIZE, sg->length); 64 return -EINVAL; 65 } 66 67 if (igt_timeout(timeout, "%s timed out\n", who)) 68 return -EINTR; 69 70 pfn += npages; 71 } 72 if (pfn != pt->end) { 73 pr_err("%s: %s finished on wrong pfn, expected %lu, found %lu\n", 74 __func__, who, pt->end, pfn); 75 return -EINVAL; 76 } 77 78 return 0; 79 } 80 81 static noinline int expect_pfn_sg_page_iter(struct pfn_table *pt, 82 const char *who, 83 unsigned long timeout) 84 { 85 struct sg_page_iter sgiter; 86 unsigned long pfn; 87 88 pfn = pt->start; 89 for_each_sg_page(pt->st.sgl, &sgiter, pt->st.nents, 0) { 90 struct page *page = sg_page_iter_page(&sgiter); 91 92 if (page != pfn_to_page(pfn)) { 93 pr_err("%s: %s left pages out of order, expected pfn %lu, found pfn %lu (using for_each_sg_page)\n", 94 __func__, who, pfn, page_to_pfn(page)); 95 return -EINVAL; 96 } 97 98 if (igt_timeout(timeout, "%s timed out\n", who)) 99 return -EINTR; 100 101 pfn++; 102 } 103 if (pfn != pt->end) { 104 pr_err("%s: %s finished on wrong pfn, expected %lu, found %lu\n", 105 __func__, who, pt->end, pfn); 106 return -EINVAL; 107 } 108 109 return 0; 110 } 111 112 static noinline int expect_pfn_sgtiter(struct pfn_table *pt, 113 const char *who, 114 unsigned long timeout) 115 { 116 struct sgt_iter sgt; 117 struct page *page; 118 unsigned long pfn; 119 120 pfn = pt->start; 121 for_each_sgt_page(page, sgt, &pt->st) { 122 if (page != pfn_to_page(pfn)) { 123 pr_err("%s: %s left pages out of order, expected pfn %lu, found pfn %lu (using for_each_sgt_page)\n", 124 __func__, who, pfn, page_to_pfn(page)); 125 return -EINVAL; 126 } 127 128 if (igt_timeout(timeout, "%s timed out\n", who)) 129 return -EINTR; 130 131 pfn++; 132 } 133 if (pfn != pt->end) { 134 pr_err("%s: %s finished on wrong pfn, expected %lu, found %lu\n", 135 __func__, who, pt->end, pfn); 136 return -EINVAL; 137 } 138 139 return 0; 140 } 141 142 static int expect_pfn_sgtable(struct pfn_table *pt, 143 npages_fn_t npages_fn, 144 struct rnd_state *rnd, 145 const char *who, 146 unsigned long timeout) 147 { 148 int err; 149 150 err = expect_pfn_sg(pt, npages_fn, rnd, who, timeout); 151 if (err) 152 return err; 153 154 err = expect_pfn_sg_page_iter(pt, who, timeout); 155 if (err) 156 return err; 157 158 err = expect_pfn_sgtiter(pt, who, timeout); 159 if (err) 160 return err; 161 162 return 0; 163 } 164 165 static unsigned int one(unsigned long n, 166 unsigned long count, 167 struct rnd_state *rnd) 168 { 169 return 1; 170 } 171 172 static unsigned int grow(unsigned long n, 173 unsigned long count, 174 struct rnd_state *rnd) 175 { 176 return n + 1; 177 } 178 179 static unsigned int shrink(unsigned long n, 180 unsigned long count, 181 struct rnd_state *rnd) 182 { 183 return count - n; 184 } 185 186 static unsigned int random(unsigned long n, 187 unsigned long count, 188 struct rnd_state *rnd) 189 { 190 return 1 + (prandom_u32_state(rnd) % 1024); 191 } 192 193 static unsigned int random_page_size_pages(unsigned long n, 194 unsigned long count, 195 struct rnd_state *rnd) 196 { 197 /* 4K, 64K, 2M */ 198 static unsigned int page_count[] = { 199 BIT(12) >> PAGE_SHIFT, 200 BIT(16) >> PAGE_SHIFT, 201 BIT(21) >> PAGE_SHIFT, 202 }; 203 204 return page_count[(prandom_u32_state(rnd) % 3)]; 205 } 206 207 static inline bool page_contiguous(struct page *first, 208 struct page *last, 209 unsigned long npages) 210 { 211 return first + npages == last; 212 } 213 214 static int alloc_table(struct pfn_table *pt, 215 unsigned long count, unsigned long max, 216 npages_fn_t npages_fn, 217 struct rnd_state *rnd, 218 int alloc_error) 219 { 220 struct scatterlist *sg; 221 unsigned long n, pfn; 222 223 if (sg_alloc_table(&pt->st, max, 224 GFP_KERNEL | __GFP_NORETRY | __GFP_NOWARN)) 225 return alloc_error; 226 227 /* count should be less than 20 to prevent overflowing sg->length */ 228 GEM_BUG_ON(overflows_type(count * PAGE_SIZE, sg->length)); 229 230 /* Construct a table where each scatterlist contains different number 231 * of entries. The idea is to check that we can iterate the individual 232 * pages from inside the coalesced lists. 233 */ 234 pt->start = PFN_BIAS; 235 pfn = pt->start; 236 sg = pt->st.sgl; 237 for (n = 0; n < count; n++) { 238 unsigned long npages = npages_fn(n, count, rnd); 239 240 /* Nobody expects the Sparse Memmap! */ 241 if (!page_contiguous(pfn_to_page(pfn), 242 pfn_to_page(pfn + npages), 243 npages)) { 244 sg_free_table(&pt->st); 245 return -ENOSPC; 246 } 247 248 if (n) 249 sg = sg_next(sg); 250 sg_set_page(sg, pfn_to_page(pfn), npages * PAGE_SIZE, 0); 251 252 GEM_BUG_ON(page_to_pfn(sg_page(sg)) != pfn); 253 GEM_BUG_ON(sg->length != npages * PAGE_SIZE); 254 GEM_BUG_ON(sg->offset != 0); 255 256 pfn += npages; 257 } 258 sg_mark_end(sg); 259 pt->st.nents = n; 260 pt->end = pfn; 261 262 return 0; 263 } 264 265 static const npages_fn_t npages_funcs[] = { 266 one, 267 grow, 268 shrink, 269 random, 270 random_page_size_pages, 271 NULL, 272 }; 273 274 static int igt_sg_alloc(void *ignored) 275 { 276 IGT_TIMEOUT(end_time); 277 const unsigned long max_order = 20; /* approximating a 4GiB object */ 278 struct rnd_state prng; 279 unsigned long prime; 280 int alloc_error = -ENOMEM; 281 282 for_each_prime_number(prime, max_order) { 283 unsigned long size = BIT(prime); 284 int offset; 285 286 for (offset = -1; offset <= 1; offset++) { 287 unsigned long sz = size + offset; 288 const npages_fn_t *npages; 289 struct pfn_table pt; 290 int err; 291 292 for (npages = npages_funcs; *npages; npages++) { 293 prandom_seed_state(&prng, 294 i915_selftest.random_seed); 295 err = alloc_table(&pt, sz, sz, *npages, &prng, 296 alloc_error); 297 if (err == -ENOSPC) 298 break; 299 if (err) 300 return err; 301 302 prandom_seed_state(&prng, 303 i915_selftest.random_seed); 304 err = expect_pfn_sgtable(&pt, *npages, &prng, 305 "sg_alloc_table", 306 end_time); 307 sg_free_table(&pt.st); 308 if (err) 309 return err; 310 } 311 } 312 313 /* Test at least one continuation before accepting oom */ 314 if (size > SG_MAX_SINGLE_ALLOC) 315 alloc_error = -ENOSPC; 316 } 317 318 return 0; 319 } 320 321 static int igt_sg_trim(void *ignored) 322 { 323 IGT_TIMEOUT(end_time); 324 const unsigned long max = PAGE_SIZE; /* not prime! */ 325 struct pfn_table pt; 326 unsigned long prime; 327 int alloc_error = -ENOMEM; 328 329 for_each_prime_number(prime, max) { 330 const npages_fn_t *npages; 331 int err; 332 333 for (npages = npages_funcs; *npages; npages++) { 334 struct rnd_state prng; 335 336 prandom_seed_state(&prng, i915_selftest.random_seed); 337 err = alloc_table(&pt, prime, max, *npages, &prng, 338 alloc_error); 339 if (err == -ENOSPC) 340 break; 341 if (err) 342 return err; 343 344 if (i915_sg_trim(&pt.st)) { 345 if (pt.st.orig_nents != prime || 346 pt.st.nents != prime) { 347 pr_err("i915_sg_trim failed (nents %u, orig_nents %u), expected %lu\n", 348 pt.st.nents, pt.st.orig_nents, prime); 349 err = -EINVAL; 350 } else { 351 prandom_seed_state(&prng, 352 i915_selftest.random_seed); 353 err = expect_pfn_sgtable(&pt, 354 *npages, &prng, 355 "i915_sg_trim", 356 end_time); 357 } 358 } 359 sg_free_table(&pt.st); 360 if (err) 361 return err; 362 } 363 364 /* Test at least one continuation before accepting oom */ 365 if (prime > SG_MAX_SINGLE_ALLOC) 366 alloc_error = -ENOSPC; 367 } 368 369 return 0; 370 } 371 372 int scatterlist_mock_selftests(void) 373 { 374 static const struct i915_subtest tests[] = { 375 SUBTEST(igt_sg_alloc), 376 SUBTEST(igt_sg_trim), 377 }; 378 379 return i915_subtests(tests, NULL); 380 } 381