1 /*
2 * Copyright (c) 2021-2022, ARM Limited. All rights reserved.
3 *
4 * SPDX-License-Identifier: BSD-3-Clause
5 */
6
7 #include <assert.h>
8 #include <stdbool.h>
9 #include <stdint.h>
10 #include <lib/spinlock.h>
11 #include <plat/common/plat_trng.h>
12
13 /*
14 * # Entropy pool
15 * Note that the TRNG Firmware interface can request up to 192 bits of entropy
16 * in a single call or three 64bit words per call. We have 4 words in the pool
17 * so that when we have 1-63 bits in the pool, and we have a request for
18 * 192 bits of entropy, we don't have to throw out the leftover 1-63 bits of
19 * entropy.
20 */
21 #define WORDS_IN_POOL (4)
22 static uint64_t entropy[WORDS_IN_POOL];
23 /* index in bits of the first bit of usable entropy */
24 static uint32_t entropy_bit_index;
25 /* then number of valid bits in the entropy pool */
26 static uint32_t entropy_bit_size;
27
28 static spinlock_t trng_pool_lock;
29
30 #define BITS_PER_WORD (sizeof(entropy[0]) * 8)
31 #define BITS_IN_POOL (WORDS_IN_POOL * BITS_PER_WORD)
32 #define ENTROPY_MIN_WORD (entropy_bit_index / BITS_PER_WORD)
33 #define ENTROPY_FREE_BIT (entropy_bit_size + entropy_bit_index)
34 #define _ENTROPY_FREE_WORD (ENTROPY_FREE_BIT / BITS_PER_WORD)
35 #define ENTROPY_FREE_INDEX (_ENTROPY_FREE_WORD % WORDS_IN_POOL)
36 /* ENTROPY_WORD_INDEX(0) includes leftover bits in the lower bits */
37 #define ENTROPY_WORD_INDEX(i) ((ENTROPY_MIN_WORD + i) % WORDS_IN_POOL)
38
39 /*
40 * Fill the entropy pool until we have at least as many bits as requested.
41 * Returns true after filling the pool, and false if the entropy source is out
42 * of entropy and the pool could not be filled.
43 * Assumes locks are taken.
44 */
trng_fill_entropy(uint32_t nbits)45 static bool trng_fill_entropy(uint32_t nbits)
46 {
47 while (nbits > entropy_bit_size) {
48 bool valid = plat_get_entropy(&entropy[ENTROPY_FREE_INDEX]);
49
50 if (valid) {
51 entropy_bit_size += BITS_PER_WORD;
52 assert(entropy_bit_size <= BITS_IN_POOL);
53 } else {
54 return false;
55 }
56 }
57 return true;
58 }
59
60 /*
61 * Pack entropy into the out buffer, filling and taking locks as needed.
62 * Returns true on success, false on failure.
63 *
64 * Note: out must have enough space for nbits of entropy
65 */
trng_pack_entropy(uint32_t nbits,uint64_t * out)66 bool trng_pack_entropy(uint32_t nbits, uint64_t *out)
67 {
68 bool ret = true;
69 uint32_t bits_to_discard = nbits;
70 spin_lock(&trng_pool_lock);
71
72 if (!trng_fill_entropy(nbits)) {
73 ret = false;
74 goto out;
75 }
76
77 const unsigned int rshift = entropy_bit_index % BITS_PER_WORD;
78 const unsigned int lshift = BITS_PER_WORD - rshift;
79 const int to_fill = ((nbits + BITS_PER_WORD - 1) / BITS_PER_WORD);
80 int word_i;
81
82 for (word_i = 0; word_i < to_fill; word_i++) {
83 /*
84 * Repack the entropy from the pool into the passed in out
85 * buffer. This takes lesser bits from the valid upper bits
86 * of word_i and more bits from the lower bits of (word_i + 1).
87 *
88 * I found the following diagram useful. note: `e` represents
89 * valid entropy, ` ` represents invalid bits (not entropy) and
90 * `x` represents valid entropy that must not end up in the
91 * packed word.
92 *
93 * |---------entropy pool----------|
94 * C var |--(word_i + 1)-|----word_i-----|
95 * bit idx |7 6 5 4 3 2 1 0|7 6 5 4 3 2 1 0|
96 * [x,x,e,e,e,e,e,e|e,e, , , , , , ]
97 * | [e,e,e,e,e,e,e,e] |
98 * | |--out[word_i]--| |
99 * lshift|---| |--rshift---|
100 *
101 * ==== Which is implemented as ====
102 *
103 * |---------entropy pool----------|
104 * C var |--(word_i + 1)-|----word_i-----|
105 * bit idx |7 6 5 4 3 2 1 0|7 6 5 4 3 2 1 0|
106 * [x,x,e,e,e,e,e,e|e,e, , , , , , ]
107 * C expr << lshift >> rshift
108 * bit idx 5 4 3 2 1 0 7 6
109 * [e,e,e,e,e,e,0,0|0,0,0,0,0,0,e,e]
110 * ==== bit-wise or ====
111 * 5 4 3 2 1 0 7 6
112 * [e,e,e,e,e,e,e,e]
113 */
114 out[word_i] |= entropy[ENTROPY_WORD_INDEX(word_i)] >> rshift;
115
116 /**
117 * Discarding the used/packed entropy bits from the respective
118 * words, (word_i) and (word_i+1) as applicable.
119 * In each iteration of the loop, we pack 64bits of entropy to
120 * the output buffer. The bits are picked linearly starting from
121 * 1st word (entropy[0]) till 4th word (entropy[3]) and then
122 * rolls back (entropy[0]). Discarding of bits is managed
123 * similarly.
124 *
125 * The following diagram illustrates the logic:
126 *
127 * |---------entropy pool----------|
128 * C var |--(word_i + 1)-|----word_i-----|
129 * bit idx |7 6 5 4 3 2 1 0|7 6 5 4 3 2 1 0|
130 * [e,e,e,e,e,e,e,e|e,e,0,0,0,0,0,0]
131 * | [e,e,e,e,e,e,e,e] |
132 * | |--out[word_i]--| |
133 * lshift|---| |--rshift---|
134 * |e,e|0,0,0,0,0,0,0,0|0,0,0,0,0,0|
135 * |<== || ==>|
136 * bits_to_discard (from these bytes)
137 *
138 * variable(bits_to_discard): Tracks the amount of bits to be
139 * discarded and is updated accordingly in each iteration.
140 *
141 * It monitors these packed bits from respective word_i and
142 * word_i+1 and overwrites them with zeros accordingly.
143 * It discards linearly from the lowest index and moves upwards
144 * until bits_to_discard variable becomes zero.
145 *
146 * In the above diagram,for example, we pack 2bytes(7th and 6th
147 * from word_i) and 6bytes(0th till 5th from word_i+1), combine
148 * and pack them as 64bit to output buffer out[i].
149 * Depending on the number of bits requested, we discard the
150 * bits from these packed bytes by overwriting them with zeros.
151 */
152
153 /*
154 * If the bits to be discarded is lesser than the amount of bits
155 * copied to the output buffer from word_i, we discard that much
156 * amount of bits only.
157 */
158 if (bits_to_discard < (BITS_PER_WORD - rshift)) {
159 entropy[ENTROPY_WORD_INDEX(word_i)] &=
160 (~0ULL << ((bits_to_discard+rshift) % BITS_PER_WORD));
161 bits_to_discard = 0;
162 } else {
163 /*
164 * If the bits to be discarded is more than the amount of valid
165 * upper bits from word_i, which has been copied to the output
166 * buffer, we just set the entire word_i to 0, as the lower bits
167 * will be already zeros from previous operations, and the
168 * bits_to_discard is updated precisely.
169 */
170 entropy[ENTROPY_WORD_INDEX(word_i)] = 0;
171 bits_to_discard -= (BITS_PER_WORD - rshift);
172 }
173
174 /*
175 * Note that a shift of 64 bits is treated as a shift of 0 bits.
176 * When the shift amount is the same as the BITS_PER_WORD, we
177 * don't want to include the next word of entropy, so we skip
178 * the `|=` operation.
179 */
180 if (lshift != BITS_PER_WORD) {
181 out[word_i] |= entropy[ENTROPY_WORD_INDEX(word_i + 1)]
182 << lshift;
183 /**
184 * Discarding the remaining packed bits from upperword
185 * (word[i+1]) which was copied to output buffer by
186 * overwriting with zeros.
187 *
188 * If the remaining bits to be discarded is lesser than
189 * the amount of bits from [word_i+1], which has been
190 * copied to the output buffer, we overwrite that much
191 * amount of bits only.
192 */
193 if (bits_to_discard < (BITS_PER_WORD - lshift)) {
194 entropy[ENTROPY_WORD_INDEX(word_i+1)] &=
195 (~0ULL << ((bits_to_discard) % BITS_PER_WORD));
196 bits_to_discard = 0;
197 } else {
198 /*
199 * If bits to discard is more than the bits from word_i+1
200 * which got packed into the output, then we discard all
201 * those copied bits.
202 *
203 * Note: we cannot set the entire word_i+1 to 0, as
204 * there are still some unused valid entropy bits at the
205 * upper end for future use.
206 */
207 entropy[ENTROPY_WORD_INDEX(word_i+1)] &=
208 (~0ULL << ((BITS_PER_WORD - lshift) % BITS_PER_WORD));
209 bits_to_discard -= (BITS_PER_WORD - lshift);
210 }
211
212 }
213 }
214 const uint64_t mask = ~0ULL >> (BITS_PER_WORD - (nbits % BITS_PER_WORD));
215
216 out[to_fill - 1] &= mask;
217
218 entropy_bit_index = (entropy_bit_index + nbits) % BITS_IN_POOL;
219 entropy_bit_size -= nbits;
220
221 out:
222 spin_unlock(&trng_pool_lock);
223
224 return ret;
225 }
226
trng_entropy_pool_setup(void)227 void trng_entropy_pool_setup(void)
228 {
229 int i;
230
231 for (i = 0; i < WORDS_IN_POOL; i++) {
232 entropy[i] = 0;
233 }
234 entropy_bit_index = 0;
235 entropy_bit_size = 0;
236 }
237
