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
32struct pfn_table {
33 struct sg_table st;
34 unsigned long start, end;
35};
36
37typedef unsigned int (*npages_fn_t)(unsigned long n,
38 unsigned long count,
39 struct rnd_state *rnd);
40
41static 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
81static 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(piter: &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
112static 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
142static 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
165static unsigned int one(unsigned long n,
166 unsigned long count,
167 struct rnd_state *rnd)
168{
169 return 1;
170}
171
172static unsigned int grow(unsigned long n,
173 unsigned long count,
174 struct rnd_state *rnd)
175{
176 return n + 1;
177}
178
179static unsigned int shrink(unsigned long n,
180 unsigned long count,
181 struct rnd_state *rnd)
182{
183 return count - n;
184}
185
186static unsigned int random(unsigned long n,
187 unsigned long count,
188 struct rnd_state *rnd)
189{
190 return 1 + (prandom_u32_state(state: rnd) % 1024);
191}
192
193static 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(state: rnd) % 3)];
205}
206
207static inline bool page_contiguous(struct page *first,
208 struct page *last,
209 unsigned long npages)
210{
211 return first + npages == last;
212}
213
214static 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 /* restricted by sg_alloc_table */
224 if (overflows_type(max, unsigned int))
225 return -E2BIG;
226
227 if (sg_alloc_table(&pt->st, max,
228 GFP_KERNEL | __GFP_NORETRY | __GFP_NOWARN))
229 return alloc_error;
230
231 /* count should be less than 20 to prevent overflowing sg->length */
232 GEM_BUG_ON(overflows_type(count * PAGE_SIZE, sg->length));
233
234 /* Construct a table where each scatterlist contains different number
235 * of entries. The idea is to check that we can iterate the individual
236 * pages from inside the coalesced lists.
237 */
238 pt->start = PFN_BIAS;
239 pfn = pt->start;
240 sg = pt->st.sgl;
241 for (n = 0; n < count; n++) {
242 unsigned long npages = npages_fn(n, count, rnd);
243
244 /* Nobody expects the Sparse Memmap! */
245 if (!page_contiguous(pfn_to_page(pfn),
246 pfn_to_page(pfn + npages),
247 npages)) {
248 sg_free_table(&pt->st);
249 return -ENOSPC;
250 }
251
252 if (n)
253 sg = sg_next(sg);
254 sg_set_page(sg, pfn_to_page(pfn), len: npages * PAGE_SIZE, offset: 0);
255
256 GEM_BUG_ON(page_to_pfn(sg_page(sg)) != pfn);
257 GEM_BUG_ON(sg->length != npages * PAGE_SIZE);
258 GEM_BUG_ON(sg->offset != 0);
259
260 pfn += npages;
261 }
262 sg_mark_end(sg);
263 pt->st.nents = n;
264 pt->end = pfn;
265
266 return 0;
267}
268
269static const npages_fn_t npages_funcs[] = {
270 one,
271 grow,
272 shrink,
273 random,
274 random_page_size_pages,
275 NULL,
276};
277
278static int igt_sg_alloc(void *ignored)
279{
280 IGT_TIMEOUT(end_time);
281 const unsigned long max_order = 20; /* approximating a 4GiB object */
282 struct rnd_state prng;
283 unsigned long prime;
284 int alloc_error = -ENOMEM;
285
286 for_each_prime_number(prime, max_order) {
287 unsigned long size = BIT(prime);
288 int offset;
289
290 for (offset = -1; offset <= 1; offset++) {
291 unsigned long sz = size + offset;
292 const npages_fn_t *npages;
293 struct pfn_table pt;
294 int err;
295
296 for (npages = npages_funcs; *npages; npages++) {
297 prandom_seed_state(state: &prng,
298 seed: i915_selftest.random_seed);
299 err = alloc_table(pt: &pt, count: sz, max: sz, npages_fn: *npages, rnd: &prng,
300 alloc_error);
301 if (err == -ENOSPC)
302 break;
303 if (err)
304 return err;
305
306 prandom_seed_state(state: &prng,
307 seed: i915_selftest.random_seed);
308 err = expect_pfn_sgtable(pt: &pt, npages_fn: *npages, rnd: &prng,
309 who: "sg_alloc_table",
310 timeout: end_time);
311 sg_free_table(&pt.st);
312 if (err)
313 return err;
314 }
315 }
316
317 /* Test at least one continuation before accepting oom */
318 if (size > SG_MAX_SINGLE_ALLOC)
319 alloc_error = -ENOSPC;
320 }
321
322 return 0;
323}
324
325static int igt_sg_trim(void *ignored)
326{
327 IGT_TIMEOUT(end_time);
328 const unsigned long max = PAGE_SIZE; /* not prime! */
329 struct pfn_table pt;
330 unsigned long prime;
331 int alloc_error = -ENOMEM;
332
333 for_each_prime_number(prime, max) {
334 const npages_fn_t *npages;
335 int err;
336
337 for (npages = npages_funcs; *npages; npages++) {
338 struct rnd_state prng;
339
340 prandom_seed_state(state: &prng, seed: i915_selftest.random_seed);
341 err = alloc_table(pt: &pt, count: prime, max, npages_fn: *npages, rnd: &prng,
342 alloc_error);
343 if (err == -ENOSPC)
344 break;
345 if (err)
346 return err;
347
348 if (i915_sg_trim(orig_st: &pt.st)) {
349 if (pt.st.orig_nents != prime ||
350 pt.st.nents != prime) {
351 pr_err("i915_sg_trim failed (nents %u, orig_nents %u), expected %lu\n",
352 pt.st.nents, pt.st.orig_nents, prime);
353 err = -EINVAL;
354 } else {
355 prandom_seed_state(state: &prng,
356 seed: i915_selftest.random_seed);
357 err = expect_pfn_sgtable(pt: &pt,
358 npages_fn: *npages, rnd: &prng,
359 who: "i915_sg_trim",
360 timeout: end_time);
361 }
362 }
363 sg_free_table(&pt.st);
364 if (err)
365 return err;
366 }
367
368 /* Test at least one continuation before accepting oom */
369 if (prime > SG_MAX_SINGLE_ALLOC)
370 alloc_error = -ENOSPC;
371 }
372
373 return 0;
374}
375
376int scatterlist_mock_selftests(void)
377{
378 static const struct i915_subtest tests[] = {
379 SUBTEST(igt_sg_alloc),
380 SUBTEST(igt_sg_trim),
381 };
382
383 return i915_subtests(tests, NULL);
384}
385

source code of linux/drivers/gpu/drm/i915/selftests/scatterlist.c