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 | |
25 | #include <linux/bitops.h> |
26 | #include <linux/kernel.h> |
27 | #include <linux/random.h> |
28 | #include <linux/slab.h> |
29 | #include <linux/types.h> |
30 | |
31 | #include "i915_random.h" |
32 | #include "i915_utils.h" |
33 | |
34 | u64 i915_prandom_u64_state(struct rnd_state *rnd) |
35 | { |
36 | u64 x; |
37 | |
38 | x = prandom_u32_state(state: rnd); |
39 | x <<= 32; |
40 | x |= prandom_u32_state(state: rnd); |
41 | |
42 | return x; |
43 | } |
44 | |
45 | void i915_prandom_shuffle(void *arr, size_t elsz, size_t count, |
46 | struct rnd_state *state) |
47 | { |
48 | char stack[128]; |
49 | |
50 | if (WARN_ON(elsz > sizeof(stack) || count > U32_MAX)) |
51 | return; |
52 | |
53 | if (!elsz || !count) |
54 | return; |
55 | |
56 | /* Fisher-Yates shuffle courtesy of Knuth */ |
57 | while (--count) { |
58 | size_t swp; |
59 | |
60 | swp = i915_prandom_u32_max_state(ep_ro: count + 1, state); |
61 | if (swp == count) |
62 | continue; |
63 | |
64 | memcpy(stack, arr + count * elsz, elsz); |
65 | memcpy(arr + count * elsz, arr + swp * elsz, elsz); |
66 | memcpy(arr + swp * elsz, stack, elsz); |
67 | } |
68 | } |
69 | |
70 | void i915_random_reorder(unsigned int *order, unsigned int count, |
71 | struct rnd_state *state) |
72 | { |
73 | i915_prandom_shuffle(arr: order, elsz: sizeof(*order), count, state); |
74 | } |
75 | |
76 | unsigned int *i915_random_order(unsigned int count, struct rnd_state *state) |
77 | { |
78 | unsigned int *order, i; |
79 | |
80 | order = kmalloc_array(n: count, size: sizeof(*order), |
81 | GFP_KERNEL | __GFP_RETRY_MAYFAIL | __GFP_NOWARN); |
82 | if (!order) |
83 | return order; |
84 | |
85 | for (i = 0; i < count; i++) |
86 | order[i] = i; |
87 | |
88 | i915_random_reorder(order, count, state); |
89 | return order; |
90 | } |
91 | |
92 | u64 igt_random_offset(struct rnd_state *state, |
93 | u64 start, u64 end, |
94 | u64 len, u64 align) |
95 | { |
96 | u64 range, addr; |
97 | |
98 | BUG_ON(range_overflows(start, len, end)); |
99 | BUG_ON(round_up(start, align) > round_down(end - len, align)); |
100 | |
101 | range = round_down(end - len, align) - round_up(start, align); |
102 | if (range) { |
103 | addr = i915_prandom_u64_state(rnd: state); |
104 | div64_u64_rem(dividend: addr, divisor: range, remainder: &addr); |
105 | start += addr; |
106 | } |
107 | |
108 | return round_up(start, align); |
109 | } |
110 | |