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
expect_pfn_sg(struct pfn_table * pt,npages_fn_t npages_fn,struct rnd_state * rnd,const char * who,unsigned long timeout)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
expect_pfn_sg_page_iter(struct pfn_table * pt,const char * who,unsigned long timeout)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
expect_pfn_sgtiter(struct pfn_table * pt,const char * who,unsigned long timeout)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
expect_pfn_sgtable(struct pfn_table * pt,npages_fn_t npages_fn,struct rnd_state * rnd,const char * who,unsigned long timeout)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
one(unsigned long n,unsigned long count,struct rnd_state * rnd)165 static unsigned int one(unsigned long n,
166 unsigned long count,
167 struct rnd_state *rnd)
168 {
169 return 1;
170 }
171
grow(unsigned long n,unsigned long count,struct rnd_state * rnd)172 static unsigned int grow(unsigned long n,
173 unsigned long count,
174 struct rnd_state *rnd)
175 {
176 return n + 1;
177 }
178
shrink(unsigned long n,unsigned long count,struct rnd_state * rnd)179 static unsigned int shrink(unsigned long n,
180 unsigned long count,
181 struct rnd_state *rnd)
182 {
183 return count - n;
184 }
185
random(unsigned long n,unsigned long count,struct rnd_state * rnd)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
random_page_size_pages(unsigned long n,unsigned long count,struct rnd_state * rnd)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
page_contiguous(struct page * first,struct page * last,unsigned long npages)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
alloc_table(struct pfn_table * pt,unsigned long count,unsigned long max,npages_fn_t npages_fn,struct rnd_state * rnd,int alloc_error)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
igt_sg_alloc(void * ignored)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
igt_sg_trim(void * ignored)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
scatterlist_mock_selftests(void)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