summaryrefslogtreecommitdiffstats
path: root/drivers/gpu/drm/i915/i915_syncmap.c
blob: 60404dbb2e9fa9f3484989cdfe34bacd202d0ca9 (plain)
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
26
27
28
29
30
31
32
33
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
/*
 * Copyright © 2017 Intel Corporation
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 *
 */

#include <linux/slab.h>

#include "i915_syncmap.h"

#include "i915_gem.h" /* GEM_BUG_ON() */
#include "i915_selftest.h"

#define SHIFT ilog2(KSYNCMAP)
#define MASK (KSYNCMAP - 1)

/*
 * struct i915_syncmap is a layer of a radixtree that maps a u64 fence
 * context id to the last u32 fence seqno waited upon from that context.
 * Unlike lib/radixtree it uses a parent pointer that allows traversal back to
 * the root. This allows us to access the whole tree via a single pointer
 * to the most recently used layer. We expect fence contexts to be dense
 * and most reuse to be on the same i915_gem_context but on neighbouring
 * engines (i.e. on adjacent contexts) and reuse the same leaf, a very
 * effective lookup cache. If the new lookup is not on the same leaf, we
 * expect it to be on the neighbouring branch.
 *
 * A leaf holds an array of u32 seqno, and has height 0. The bitmap field
 * allows us to store whether a particular seqno is valid (i.e. allows us
 * to distinguish unset from 0).
 *
 * A branch holds an array of layer pointers, and has height > 0, and always
 * has at least 2 layers (either branches or leaves) below it.
 *
 * For example,
 *	for x in
 *	  0 1 2 0x10 0x11 0x200 0x201
 *	  0x500000 0x500001 0x503000 0x503001
 *	  0xE<<60:
 *		i915_syncmap_set(&sync, x, lower_32_bits(x));
 * will build a tree like:
 *	0xXXXXXXXXXXXXXXXX
 *	0-> 0x0000000000XXXXXX
 *	|   0-> 0x0000000000000XXX
 *	|   |   0-> 0x00000000000000XX
 *	|   |   |   0-> 0x000000000000000X 0:0, 1:1, 2:2
 *	|   |   |   1-> 0x000000000000001X 0:10, 1:11
 *	|   |   2-> 0x000000000000020X 0:200, 1:201
 *	|   5-> 0x000000000050XXXX
 *	|       0-> 0x000000000050000X 0:500000, 1:500001
 *	|       3-> 0x000000000050300X 0:503000, 1:503001
 *	e-> 0xe00000000000000X e:e
 */

struct i915_syncmap {
	u64 prefix;
	unsigned int height;
	unsigned int bitmap;
	struct i915_syncmap *parent;
	/*
	 * Following this header is an array of either seqno or child pointers:
	 * union {
	 *	u32 seqno[KSYNCMAP];
	 *	struct i915_syncmap *child[KSYNCMAP];
	 * };
	 */
};

/**
 * i915_syncmap_init -- initialise the #i915_syncmap
 * @root: pointer to the #i915_syncmap
 */
void i915_syncmap_init(struct i915_syncmap **root)
{
	BUILD_BUG_ON_NOT_POWER_OF_2(KSYNCMAP);
	BUILD_BUG_ON_NOT_POWER_OF_2(SHIFT);
	BUILD_BUG_ON(KSYNCMAP > BITS_PER_TYPE((*root)->bitmap));
	*root = NULL;
}

static inline u32 *__sync_seqno(struct i915_syncmap *p)
{
	GEM_BUG_ON(p->height);
	return (u32 *)(p + 1);
}

static inline struct i915_syncmap **__sync_child(struct i915_syncmap *p)
{
	GEM_BUG_ON(!p->height);
	return (struct i915_syncmap **)(p + 1);
}

static inline unsigned int
__sync_branch_idx(const struct i915_syncmap *p, u64 id)
{
	return (id >> p->height) & MASK;
}

static inline unsigned int
__sync_leaf_idx(const struct i915_syncmap *p, u64 id)
{
	GEM_BUG_ON(p->height);
	return id & MASK;
}

static inline u64 __sync_branch_prefix(const struct i915_syncmap *p, u64 id)
{
	return id >> p->height >> SHIFT;
}

static inline u64 __sync_leaf_prefix(const struct i915_syncmap *p, u64 id)
{
	GEM_BUG_ON(p->height);
	return id >> SHIFT;
}

static inline bool seqno_later(u32 a, u32 b)
{
	return (s32)(a - b) >= 0;
}

/**
 * i915_syncmap_is_later -- compare against the last know sync point
 * @root: pointer to the #i915_syncmap
 * @id: the context id (other timeline) we are synchronising to
 * @seqno: the sequence number along the other timeline
 *
 * If we have already synchronised this @root timeline with another (@id) then
 * we can omit any repeated or earlier synchronisation requests. If the two
 * timelines are already coupled, we can also omit the dependency between the
 * two as that is already known via the timeline.
 *
 * Returns true if the two timelines are already synchronised wrt to @seqno,
 * false if not and the synchronisation must be emitted.
 */
bool i915_syncmap_is_later(struct i915_syncmap **root, u64 id, u32 seqno)
{
	struct i915_syncmap *p;
	unsigned int idx;

	p = *root;
	if (!p)
		return false;

	if (likely(__sync_leaf_prefix(p, id) == p->prefix))
		goto found;

	/* First climb the tree back to a parent branch */
	do {
		p = p->parent;
		if (!p)
			return false;

		if (__sync_branch_prefix(p, id) == p->prefix)
			break;
	} while (1);

	/* And then descend again until we find our leaf */
	do {
		if (!p->height)
			break;

		p = __sync_child(p)[__sync_branch_idx(p, id)];
		if (!p)
			return false;

		if (__sync_branch_prefix(p, id) != p->prefix)
			return false;
	} while (1);

	*root = p;
found:
	idx = __sync_leaf_idx(p, id);
	if (!(p->bitmap & BIT(idx)))
		return false;

	return seqno_later(__sync_seqno(p)[idx], seqno);
}

static struct i915_syncmap *
__sync_alloc_leaf(struct i915_syncmap *parent, u64 id)
{
	struct i915_syncmap *p;

	p = kmalloc(sizeof(*p) + KSYNCMAP * sizeof(u32), GFP_KERNEL);
	if (unlikely(!p))
		return NULL;

	p->parent = parent;
	p->height = 0;
	p->bitmap = 0;
	p->prefix = __sync_leaf_prefix(p, id);
	return p;
}

static inline void __sync_set_seqno(struct i915_syncmap *p, u64 id, u32 seqno)
{
	unsigned int idx = __sync_leaf_idx(p, id);

	p->bitmap |= BIT(idx);
	__sync_seqno(p)[idx] = seqno;
}

static inline void __sync_set_child(struct i915_syncmap *p,
				    unsigned int idx,
				    struct i915_syncmap *child)
{
	p->bitmap |= BIT(idx);
	__sync_child(p)[idx] = child;
}

static noinline int __sync_set(struct i915_syncmap **root, u64 id, u32 seqno)
{
	struct i915_syncmap *p = *root;
	unsigned int idx;

	if (!p) {
		p = __sync_alloc_leaf(NULL, id);
		if (unlikely(!p))
			return -ENOMEM;

		goto found;
	}

	/* Caller handled the likely cached case */
	GEM_BUG_ON(__sync_leaf_prefix(p, id) == p->prefix);

	/* Climb back up the tree until we find a common prefix */
	do {
		if (!p->parent)
			break;

		p = p->parent;

		if (__sync_branch_prefix(p, id) == p->prefix)
			break;
	} while (1);

	/*
	 * No shortcut, we have to descend the tree to find the right layer
	 * containing this fence.
	 *
	 * Each layer in the tree holds 16 (KSYNCMAP) pointers, either fences
	 * or lower layers. Leaf nodes (height = 0) contain the fences, all
	 * other nodes (height > 0) are internal layers that point to a lower
	 * node. Each internal layer has at least 2 descendents.
	 *
	 * Starting at the top, we check whether the current prefix matches. If
	 * it doesn't, we have gone past our target and need to insert a join
	 * into the tree, and a new leaf node for the target as a descendent
	 * of the join, as well as the original layer.
	 *
	 * The matching prefix means we are still following the right branch
	 * of the tree. If it has height 0, we have found our leaf and just
	 * need to replace the fence slot with ourselves. If the height is
	 * not zero, our slot contains the next layer in the tree (unless
	 * it is empty, in which case we can add ourselves as a new leaf).
	 * As descend the tree the prefix grows (and height decreases).
	 */
	do {
		struct i915_syncmap *next;

		if (__sync_branch_prefix(p, id) != p->prefix) {
			unsigned int above;

			/* Insert a join above the current layer */
			next = kzalloc(sizeof(*next) + KSYNCMAP * sizeof(next),
				       GFP_KERNEL);
			if (unlikely(!next))
				return -ENOMEM;

			/* Compute the height at which these two diverge */
			above = fls64(__sync_branch_prefix(p, id) ^ p->prefix);
			above = round_up(above, SHIFT);
			next->height = above + p->height;
			next->prefix = __sync_branch_prefix(next, id);

			/* Insert the join into the parent */
			if (p->parent) {
				idx = __sync_branch_idx(p->parent, id);
				__sync_child(p->parent)[idx] = next;
				GEM_BUG_ON(!(p->parent->bitmap & BIT(idx)));
			}
			next->parent = p->parent;

			/* Compute the idx of the other branch, not our id! */
			idx = p->prefix >> (above - SHIFT) & MASK;
			__sync_set_child(next, idx, p);
			p->parent = next;

			/* Ascend to the join */
			p = next;
		} else {
			if (!p->height)
				break;
		}

		/* Descend into the next layer */
		GEM_BUG_ON(!p->height);
		idx = __sync_branch_idx(p, id);
		next = __sync_child(p)[idx];
		if (!next) {
			next = __sync_alloc_leaf(p, id);
			if (unlikely(!next))
				return -ENOMEM;

			__sync_set_child(p, idx, next);
			p = next;
			break;
		}

		p = next;
	} while (1);

found:
	GEM_BUG_ON(p->prefix != __sync_leaf_prefix(p, id));
	__sync_set_seqno(p, id, seqno);
	*root = p;
	return 0;
}

/**
 * i915_syncmap_set -- mark the most recent syncpoint between contexts
 * @root: pointer to the #i915_syncmap
 * @id: the context id (other timeline) we have synchronised to
 * @seqno: the sequence number along the other timeline
 *
 * When we synchronise this @root timeline with another (@id), we also know
 * that we have synchronized with all previous seqno along that timeline. If
 * we then have a request to synchronise with the same seqno or older, we can
 * omit it, see i915_syncmap_is_later()
 *
 * Returns 0 on success, or a negative error code.
 */
int i915_syncmap_set(struct i915_syncmap **root, u64 id, u32 seqno)
{
	struct i915_syncmap *p = *root;

	/*
	 * We expect to be called in sequence following is_later(id), which
	 * should have preloaded the root for us.
	 */
	if (likely(p && __sync_leaf_prefix(p, id) == p->prefix)) {
		__sync_set_seqno(p, id, seqno);
		return 0;
	}

	return __sync_set(root, id, seqno);
}

static void __sync_free(struct i915_syncmap *p)
{
	if (p->height) {
		unsigned int i;

		while ((i = ffs(p->bitmap))) {
			p->bitmap &= ~0u << i;
			__sync_free(__sync_child(p)[i - 1]);
		}
	}

	kfree(p);
}

/**
 * i915_syncmap_free -- free all memory associated with the syncmap
 * @root: pointer to the #i915_syncmap
 *
 * Either when the timeline is to be freed and we no longer need the sync
 * point tracking, or when the fences are all known to be signaled and the
 * sync point tracking is redundant, we can free the #i915_syncmap to recover
 * its allocations.
 *
 * Will reinitialise the @root pointer so that the #i915_syncmap is ready for
 * reuse.
 */
void i915_syncmap_free(struct i915_syncmap **root)
{
	struct i915_syncmap *p;

	p = *root;
	if (!p)
		return;

	while (p->parent)
		p = p->parent;

	__sync_free(p);
	*root = NULL;
}

#if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
#include "selftests/i915_syncmap.c"
#endif