1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#include <linux/slab.h>
26
27#include "i915_syncmap.h"
28
29#include "i915_gem.h"
30#include "i915_selftest.h"
31
32#define SHIFT ilog2(KSYNCMAP)
33#define MASK (KSYNCMAP - 1)
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73struct i915_syncmap {
74 u64 prefix;
75 unsigned int height;
76 unsigned int bitmap;
77 struct i915_syncmap *parent;
78
79
80
81
82
83
84
85};
86
87
88
89
90
91void i915_syncmap_init(struct i915_syncmap **root)
92{
93 BUILD_BUG_ON_NOT_POWER_OF_2(KSYNCMAP);
94 BUILD_BUG_ON_NOT_POWER_OF_2(SHIFT);
95 BUILD_BUG_ON(KSYNCMAP > BITS_PER_BYTE * sizeof((*root)->bitmap));
96 *root = NULL;
97}
98
99static inline u32 *__sync_seqno(struct i915_syncmap *p)
100{
101 GEM_BUG_ON(p->height);
102 return (u32 *)(p + 1);
103}
104
105static inline struct i915_syncmap **__sync_child(struct i915_syncmap *p)
106{
107 GEM_BUG_ON(!p->height);
108 return (struct i915_syncmap **)(p + 1);
109}
110
111static inline unsigned int
112__sync_branch_idx(const struct i915_syncmap *p, u64 id)
113{
114 return (id >> p->height) & MASK;
115}
116
117static inline unsigned int
118__sync_leaf_idx(const struct i915_syncmap *p, u64 id)
119{
120 GEM_BUG_ON(p->height);
121 return id & MASK;
122}
123
124static inline u64 __sync_branch_prefix(const struct i915_syncmap *p, u64 id)
125{
126 return id >> p->height >> SHIFT;
127}
128
129static inline u64 __sync_leaf_prefix(const struct i915_syncmap *p, u64 id)
130{
131 GEM_BUG_ON(p->height);
132 return id >> SHIFT;
133}
134
135static inline bool seqno_later(u32 a, u32 b)
136{
137 return (s32)(a - b) >= 0;
138}
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154bool i915_syncmap_is_later(struct i915_syncmap **root, u64 id, u32 seqno)
155{
156 struct i915_syncmap *p;
157 unsigned int idx;
158
159 p = *root;
160 if (!p)
161 return false;
162
163 if (likely(__sync_leaf_prefix(p, id) == p->prefix))
164 goto found;
165
166
167 do {
168 p = p->parent;
169 if (!p)
170 return false;
171
172 if (__sync_branch_prefix(p, id) == p->prefix)
173 break;
174 } while (1);
175
176
177 do {
178 if (!p->height)
179 break;
180
181 p = __sync_child(p)[__sync_branch_idx(p, id)];
182 if (!p)
183 return false;
184
185 if (__sync_branch_prefix(p, id) != p->prefix)
186 return false;
187 } while (1);
188
189 *root = p;
190found:
191 idx = __sync_leaf_idx(p, id);
192 if (!(p->bitmap & BIT(idx)))
193 return false;
194
195 return seqno_later(__sync_seqno(p)[idx], seqno);
196}
197
198static struct i915_syncmap *
199__sync_alloc_leaf(struct i915_syncmap *parent, u64 id)
200{
201 struct i915_syncmap *p;
202
203 p = kmalloc(sizeof(*p) + KSYNCMAP * sizeof(u32), GFP_KERNEL);
204 if (unlikely(!p))
205 return NULL;
206
207 p->parent = parent;
208 p->height = 0;
209 p->bitmap = 0;
210 p->prefix = __sync_leaf_prefix(p, id);
211 return p;
212}
213
214static inline void __sync_set_seqno(struct i915_syncmap *p, u64 id, u32 seqno)
215{
216 unsigned int idx = __sync_leaf_idx(p, id);
217
218 p->bitmap |= BIT(idx);
219 __sync_seqno(p)[idx] = seqno;
220}
221
222static inline void __sync_set_child(struct i915_syncmap *p,
223 unsigned int idx,
224 struct i915_syncmap *child)
225{
226 p->bitmap |= BIT(idx);
227 __sync_child(p)[idx] = child;
228}
229
230static noinline int __sync_set(struct i915_syncmap **root, u64 id, u32 seqno)
231{
232 struct i915_syncmap *p = *root;
233 unsigned int idx;
234
235 if (!p) {
236 p = __sync_alloc_leaf(NULL, id);
237 if (unlikely(!p))
238 return -ENOMEM;
239
240 goto found;
241 }
242
243
244 GEM_BUG_ON(__sync_leaf_prefix(p, id) == p->prefix);
245
246
247 do {
248 if (!p->parent)
249 break;
250
251 p = p->parent;
252
253 if (__sync_branch_prefix(p, id) == p->prefix)
254 break;
255 } while (1);
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278 do {
279 struct i915_syncmap *next;
280
281 if (__sync_branch_prefix(p, id) != p->prefix) {
282 unsigned int above;
283
284
285 next = kzalloc(sizeof(*next) + KSYNCMAP * sizeof(next),
286 GFP_KERNEL);
287 if (unlikely(!next))
288 return -ENOMEM;
289
290
291 above = fls64(__sync_branch_prefix(p, id) ^ p->prefix);
292 above = round_up(above, SHIFT);
293 next->height = above + p->height;
294 next->prefix = __sync_branch_prefix(next, id);
295
296
297 if (p->parent) {
298 idx = __sync_branch_idx(p->parent, id);
299 __sync_child(p->parent)[idx] = next;
300 GEM_BUG_ON(!(p->parent->bitmap & BIT(idx)));
301 }
302 next->parent = p->parent;
303
304
305 idx = p->prefix >> (above - SHIFT) & MASK;
306 __sync_set_child(next, idx, p);
307 p->parent = next;
308
309
310 p = next;
311 } else {
312 if (!p->height)
313 break;
314 }
315
316
317 GEM_BUG_ON(!p->height);
318 idx = __sync_branch_idx(p, id);
319 next = __sync_child(p)[idx];
320 if (!next) {
321 next = __sync_alloc_leaf(p, id);
322 if (unlikely(!next))
323 return -ENOMEM;
324
325 __sync_set_child(p, idx, next);
326 p = next;
327 break;
328 }
329
330 p = next;
331 } while (1);
332
333found:
334 GEM_BUG_ON(p->prefix != __sync_leaf_prefix(p, id));
335 __sync_set_seqno(p, id, seqno);
336 *root = p;
337 return 0;
338}
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353int i915_syncmap_set(struct i915_syncmap **root, u64 id, u32 seqno)
354{
355 struct i915_syncmap *p = *root;
356
357
358
359
360
361 if (likely(p && __sync_leaf_prefix(p, id) == p->prefix)) {
362 __sync_set_seqno(p, id, seqno);
363 return 0;
364 }
365
366 return __sync_set(root, id, seqno);
367}
368
369static void __sync_free(struct i915_syncmap *p)
370{
371 if (p->height) {
372 unsigned int i;
373
374 while ((i = ffs(p->bitmap))) {
375 p->bitmap &= ~0u << i;
376 __sync_free(__sync_child(p)[i - 1]);
377 }
378 }
379
380 kfree(p);
381}
382
383
384
385
386
387
388
389
390
391
392
393
394
395void i915_syncmap_free(struct i915_syncmap **root)
396{
397 struct i915_syncmap *p;
398
399 p = *root;
400 if (!p)
401 return;
402
403 while (p->parent)
404 p = p->parent;
405
406 __sync_free(p);
407 *root = NULL;
408}
409
410#if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
411#include "selftests/i915_syncmap.c"
412#endif
413