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