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