1*3f2dd94aSFrançois Tigeot /*
2*3f2dd94aSFrançois Tigeot * Copyright © 2017 Intel Corporation
3*3f2dd94aSFrançois Tigeot *
4*3f2dd94aSFrançois Tigeot * Permission is hereby granted, free of charge, to any person obtaining a
5*3f2dd94aSFrançois Tigeot * copy of this software and associated documentation files (the "Software"),
6*3f2dd94aSFrançois Tigeot * to deal in the Software without restriction, including without limitation
7*3f2dd94aSFrançois Tigeot * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8*3f2dd94aSFrançois Tigeot * and/or sell copies of the Software, and to permit persons to whom the
9*3f2dd94aSFrançois Tigeot * Software is furnished to do so, subject to the following conditions:
10*3f2dd94aSFrançois Tigeot *
11*3f2dd94aSFrançois Tigeot * The above copyright notice and this permission notice (including the next
12*3f2dd94aSFrançois Tigeot * paragraph) shall be included in all copies or substantial portions of the
13*3f2dd94aSFrançois Tigeot * Software.
14*3f2dd94aSFrançois Tigeot *
15*3f2dd94aSFrançois Tigeot * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16*3f2dd94aSFrançois Tigeot * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17*3f2dd94aSFrançois Tigeot * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18*3f2dd94aSFrançois Tigeot * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19*3f2dd94aSFrançois Tigeot * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20*3f2dd94aSFrançois Tigeot * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21*3f2dd94aSFrançois Tigeot * IN THE SOFTWARE.
22*3f2dd94aSFrançois Tigeot *
23*3f2dd94aSFrançois Tigeot */
24*3f2dd94aSFrançois Tigeot
25*3f2dd94aSFrançois Tigeot #include <linux/slab.h>
26*3f2dd94aSFrançois Tigeot
27*3f2dd94aSFrançois Tigeot #include "i915_syncmap.h"
28*3f2dd94aSFrançois Tigeot
29*3f2dd94aSFrançois Tigeot #include "i915_gem.h" /* GEM_BUG_ON() */
30*3f2dd94aSFrançois Tigeot #include "i915_selftest.h"
31*3f2dd94aSFrançois Tigeot
32*3f2dd94aSFrançois Tigeot #define SHIFT ilog2(KSYNCMAP)
33*3f2dd94aSFrançois Tigeot #define MASK (KSYNCMAP - 1)
34*3f2dd94aSFrançois Tigeot
35*3f2dd94aSFrançois Tigeot /*
36*3f2dd94aSFrançois Tigeot * struct i915_syncmap is a layer of a radixtree that maps a u64 fence
37*3f2dd94aSFrançois Tigeot * context id to the last u32 fence seqno waited upon from that context.
38*3f2dd94aSFrançois Tigeot * Unlike lib/radixtree it uses a parent pointer that allows traversal back to
39*3f2dd94aSFrançois Tigeot * the root. This allows us to access the whole tree via a single pointer
40*3f2dd94aSFrançois Tigeot * to the most recently used layer. We expect fence contexts to be dense
41*3f2dd94aSFrançois Tigeot * and most reuse to be on the same i915_gem_context but on neighbouring
42*3f2dd94aSFrançois Tigeot * engines (i.e. on adjacent contexts) and reuse the same leaf, a very
43*3f2dd94aSFrançois Tigeot * effective lookup cache. If the new lookup is not on the same leaf, we
44*3f2dd94aSFrançois Tigeot * expect it to be on the neighbouring branch.
45*3f2dd94aSFrançois Tigeot *
46*3f2dd94aSFrançois Tigeot * A leaf holds an array of u32 seqno, and has height 0. The bitmap field
47*3f2dd94aSFrançois Tigeot * allows us to store whether a particular seqno is valid (i.e. allows us
48*3f2dd94aSFrançois Tigeot * to distinguish unset from 0).
49*3f2dd94aSFrançois Tigeot *
50*3f2dd94aSFrançois Tigeot * A branch holds an array of layer pointers, and has height > 0, and always
51*3f2dd94aSFrançois Tigeot * has at least 2 layers (either branches or leaves) below it.
52*3f2dd94aSFrançois Tigeot *
53*3f2dd94aSFrançois Tigeot * For example,
54*3f2dd94aSFrançois Tigeot * for x in
55*3f2dd94aSFrançois Tigeot * 0 1 2 0x10 0x11 0x200 0x201
56*3f2dd94aSFrançois Tigeot * 0x500000 0x500001 0x503000 0x503001
57*3f2dd94aSFrançois Tigeot * 0xE<<60:
58*3f2dd94aSFrançois Tigeot * i915_syncmap_set(&sync, x, lower_32_bits(x));
59*3f2dd94aSFrançois Tigeot * will build a tree like:
60*3f2dd94aSFrançois Tigeot * 0xXXXXXXXXXXXXXXXX
61*3f2dd94aSFrançois Tigeot * 0-> 0x0000000000XXXXXX
62*3f2dd94aSFrançois Tigeot * | 0-> 0x0000000000000XXX
63*3f2dd94aSFrançois Tigeot * | | 0-> 0x00000000000000XX
64*3f2dd94aSFrançois Tigeot * | | | 0-> 0x000000000000000X 0:0, 1:1, 2:2
65*3f2dd94aSFrançois Tigeot * | | | 1-> 0x000000000000001X 0:10, 1:11
66*3f2dd94aSFrançois Tigeot * | | 2-> 0x000000000000020X 0:200, 1:201
67*3f2dd94aSFrançois Tigeot * | 5-> 0x000000000050XXXX
68*3f2dd94aSFrançois Tigeot * | 0-> 0x000000000050000X 0:500000, 1:500001
69*3f2dd94aSFrançois Tigeot * | 3-> 0x000000000050300X 0:503000, 1:503001
70*3f2dd94aSFrançois Tigeot * e-> 0xe00000000000000X e:e
71*3f2dd94aSFrançois Tigeot */
72*3f2dd94aSFrançois Tigeot
73*3f2dd94aSFrançois Tigeot struct i915_syncmap {
74*3f2dd94aSFrançois Tigeot u64 prefix;
75*3f2dd94aSFrançois Tigeot unsigned int height;
76*3f2dd94aSFrançois Tigeot unsigned int bitmap;
77*3f2dd94aSFrançois Tigeot struct i915_syncmap *parent;
78*3f2dd94aSFrançois Tigeot /*
79*3f2dd94aSFrançois Tigeot * Following this header is an array of either seqno or child pointers:
80*3f2dd94aSFrançois Tigeot * union {
81*3f2dd94aSFrançois Tigeot * u32 seqno[KSYNCMAP];
82*3f2dd94aSFrançois Tigeot * struct i915_syncmap *child[KSYNCMAP];
83*3f2dd94aSFrançois Tigeot * };
84*3f2dd94aSFrançois Tigeot */
85*3f2dd94aSFrançois Tigeot };
86*3f2dd94aSFrançois Tigeot
87*3f2dd94aSFrançois Tigeot /**
88*3f2dd94aSFrançois Tigeot * i915_syncmap_init -- initialise the #i915_syncmap
89*3f2dd94aSFrançois Tigeot * @root - pointer to the #i915_syncmap
90*3f2dd94aSFrançois Tigeot */
i915_syncmap_init(struct i915_syncmap ** root)91*3f2dd94aSFrançois Tigeot void i915_syncmap_init(struct i915_syncmap **root)
92*3f2dd94aSFrançois Tigeot {
93*3f2dd94aSFrançois Tigeot BUILD_BUG_ON_NOT_POWER_OF_2(KSYNCMAP);
94*3f2dd94aSFrançois Tigeot BUILD_BUG_ON_NOT_POWER_OF_2(SHIFT);
95*3f2dd94aSFrançois Tigeot BUILD_BUG_ON(KSYNCMAP > BITS_PER_BYTE * sizeof((*root)->bitmap));
96*3f2dd94aSFrançois Tigeot *root = NULL;
97*3f2dd94aSFrançois Tigeot }
98*3f2dd94aSFrançois Tigeot
__sync_seqno(struct i915_syncmap * p)99*3f2dd94aSFrançois Tigeot static inline u32 *__sync_seqno(struct i915_syncmap *p)
100*3f2dd94aSFrançois Tigeot {
101*3f2dd94aSFrançois Tigeot GEM_BUG_ON(p->height);
102*3f2dd94aSFrançois Tigeot return (u32 *)(p + 1);
103*3f2dd94aSFrançois Tigeot }
104*3f2dd94aSFrançois Tigeot
__sync_child(struct i915_syncmap * p)105*3f2dd94aSFrançois Tigeot static inline struct i915_syncmap **__sync_child(struct i915_syncmap *p)
106*3f2dd94aSFrançois Tigeot {
107*3f2dd94aSFrançois Tigeot GEM_BUG_ON(!p->height);
108*3f2dd94aSFrançois Tigeot return (struct i915_syncmap **)(p + 1);
109*3f2dd94aSFrançois Tigeot }
110*3f2dd94aSFrançois Tigeot
111*3f2dd94aSFrançois Tigeot static inline unsigned int
__sync_branch_idx(const struct i915_syncmap * p,u64 id)112*3f2dd94aSFrançois Tigeot __sync_branch_idx(const struct i915_syncmap *p, u64 id)
113*3f2dd94aSFrançois Tigeot {
114*3f2dd94aSFrançois Tigeot return (id >> p->height) & MASK;
115*3f2dd94aSFrançois Tigeot }
116*3f2dd94aSFrançois Tigeot
117*3f2dd94aSFrançois Tigeot static inline unsigned int
__sync_leaf_idx(const struct i915_syncmap * p,u64 id)118*3f2dd94aSFrançois Tigeot __sync_leaf_idx(const struct i915_syncmap *p, u64 id)
119*3f2dd94aSFrançois Tigeot {
120*3f2dd94aSFrançois Tigeot GEM_BUG_ON(p->height);
121*3f2dd94aSFrançois Tigeot return id & MASK;
122*3f2dd94aSFrançois Tigeot }
123*3f2dd94aSFrançois Tigeot
__sync_branch_prefix(const struct i915_syncmap * p,u64 id)124*3f2dd94aSFrançois Tigeot static inline u64 __sync_branch_prefix(const struct i915_syncmap *p, u64 id)
125*3f2dd94aSFrançois Tigeot {
126*3f2dd94aSFrançois Tigeot return id >> p->height >> SHIFT;
127*3f2dd94aSFrançois Tigeot }
128*3f2dd94aSFrançois Tigeot
__sync_leaf_prefix(const struct i915_syncmap * p,u64 id)129*3f2dd94aSFrançois Tigeot static inline u64 __sync_leaf_prefix(const struct i915_syncmap *p, u64 id)
130*3f2dd94aSFrançois Tigeot {
131*3f2dd94aSFrançois Tigeot GEM_BUG_ON(p->height);
132*3f2dd94aSFrançois Tigeot return id >> SHIFT;
133*3f2dd94aSFrançois Tigeot }
134*3f2dd94aSFrançois Tigeot
seqno_later(u32 a,u32 b)135*3f2dd94aSFrançois Tigeot static inline bool seqno_later(u32 a, u32 b)
136*3f2dd94aSFrançois Tigeot {
137*3f2dd94aSFrançois Tigeot return (s32)(a - b) >= 0;
138*3f2dd94aSFrançois Tigeot }
139*3f2dd94aSFrançois Tigeot
140*3f2dd94aSFrançois Tigeot /**
141*3f2dd94aSFrançois Tigeot * i915_syncmap_is_later -- compare against the last know sync point
142*3f2dd94aSFrançois Tigeot * @root - pointer to the #i915_syncmap
143*3f2dd94aSFrançois Tigeot * @id - the context id (other timeline) we are synchronising to
144*3f2dd94aSFrançois Tigeot * @seqno - the sequence number along the other timeline
145*3f2dd94aSFrançois Tigeot *
146*3f2dd94aSFrançois Tigeot * If we have already synchronised this @root timeline with another (@id) then
147*3f2dd94aSFrançois Tigeot * we can omit any repeated or earlier synchronisation requests. If the two
148*3f2dd94aSFrançois Tigeot * timelines are already coupled, we can also omit the dependency between the
149*3f2dd94aSFrançois Tigeot * two as that is already known via the timeline.
150*3f2dd94aSFrançois Tigeot *
151*3f2dd94aSFrançois Tigeot * Returns true if the two timelines are already synchronised wrt to @seqno,
152*3f2dd94aSFrançois Tigeot * false if not and the synchronisation must be emitted.
153*3f2dd94aSFrançois Tigeot */
i915_syncmap_is_later(struct i915_syncmap ** root,u64 id,u32 seqno)154*3f2dd94aSFrançois Tigeot bool i915_syncmap_is_later(struct i915_syncmap **root, u64 id, u32 seqno)
155*3f2dd94aSFrançois Tigeot {
156*3f2dd94aSFrançois Tigeot struct i915_syncmap *p;
157*3f2dd94aSFrançois Tigeot unsigned int idx;
158*3f2dd94aSFrançois Tigeot
159*3f2dd94aSFrançois Tigeot p = *root;
160*3f2dd94aSFrançois Tigeot if (!p)
161*3f2dd94aSFrançois Tigeot return false;
162*3f2dd94aSFrançois Tigeot
163*3f2dd94aSFrançois Tigeot if (likely(__sync_leaf_prefix(p, id) == p->prefix))
164*3f2dd94aSFrançois Tigeot goto found;
165*3f2dd94aSFrançois Tigeot
166*3f2dd94aSFrançois Tigeot /* First climb the tree back to a parent branch */
167*3f2dd94aSFrançois Tigeot do {
168*3f2dd94aSFrançois Tigeot p = p->parent;
169*3f2dd94aSFrançois Tigeot if (!p)
170*3f2dd94aSFrançois Tigeot return false;
171*3f2dd94aSFrançois Tigeot
172*3f2dd94aSFrançois Tigeot if (__sync_branch_prefix(p, id) == p->prefix)
173*3f2dd94aSFrançois Tigeot break;
174*3f2dd94aSFrançois Tigeot } while (1);
175*3f2dd94aSFrançois Tigeot
176*3f2dd94aSFrançois Tigeot /* And then descend again until we find our leaf */
177*3f2dd94aSFrançois Tigeot do {
178*3f2dd94aSFrançois Tigeot if (!p->height)
179*3f2dd94aSFrançois Tigeot break;
180*3f2dd94aSFrançois Tigeot
181*3f2dd94aSFrançois Tigeot p = __sync_child(p)[__sync_branch_idx(p, id)];
182*3f2dd94aSFrançois Tigeot if (!p)
183*3f2dd94aSFrançois Tigeot return false;
184*3f2dd94aSFrançois Tigeot
185*3f2dd94aSFrançois Tigeot if (__sync_branch_prefix(p, id) != p->prefix)
186*3f2dd94aSFrançois Tigeot return false;
187*3f2dd94aSFrançois Tigeot } while (1);
188*3f2dd94aSFrançois Tigeot
189*3f2dd94aSFrançois Tigeot *root = p;
190*3f2dd94aSFrançois Tigeot found:
191*3f2dd94aSFrançois Tigeot idx = __sync_leaf_idx(p, id);
192*3f2dd94aSFrançois Tigeot if (!(p->bitmap & BIT(idx)))
193*3f2dd94aSFrançois Tigeot return false;
194*3f2dd94aSFrançois Tigeot
195*3f2dd94aSFrançois Tigeot return seqno_later(__sync_seqno(p)[idx], seqno);
196*3f2dd94aSFrançois Tigeot }
197*3f2dd94aSFrançois Tigeot
198*3f2dd94aSFrançois Tigeot static struct i915_syncmap *
__sync_alloc_leaf(struct i915_syncmap * parent,u64 id)199*3f2dd94aSFrançois Tigeot __sync_alloc_leaf(struct i915_syncmap *parent, u64 id)
200*3f2dd94aSFrançois Tigeot {
201*3f2dd94aSFrançois Tigeot struct i915_syncmap *p;
202*3f2dd94aSFrançois Tigeot
203*3f2dd94aSFrançois Tigeot p = kmalloc(sizeof(*p) + KSYNCMAP * sizeof(u32), M_DRM, GFP_KERNEL);
204*3f2dd94aSFrançois Tigeot if (unlikely(!p))
205*3f2dd94aSFrançois Tigeot return NULL;
206*3f2dd94aSFrançois Tigeot
207*3f2dd94aSFrançois Tigeot p->parent = parent;
208*3f2dd94aSFrançois Tigeot p->height = 0;
209*3f2dd94aSFrançois Tigeot p->bitmap = 0;
210*3f2dd94aSFrançois Tigeot p->prefix = __sync_leaf_prefix(p, id);
211*3f2dd94aSFrançois Tigeot return p;
212*3f2dd94aSFrançois Tigeot }
213*3f2dd94aSFrançois Tigeot
__sync_set_seqno(struct i915_syncmap * p,u64 id,u32 seqno)214*3f2dd94aSFrançois Tigeot static inline void __sync_set_seqno(struct i915_syncmap *p, u64 id, u32 seqno)
215*3f2dd94aSFrançois Tigeot {
216*3f2dd94aSFrançois Tigeot unsigned int idx = __sync_leaf_idx(p, id);
217*3f2dd94aSFrançois Tigeot
218*3f2dd94aSFrançois Tigeot p->bitmap |= BIT(idx);
219*3f2dd94aSFrançois Tigeot __sync_seqno(p)[idx] = seqno;
220*3f2dd94aSFrançois Tigeot }
221*3f2dd94aSFrançois Tigeot
__sync_set_child(struct i915_syncmap * p,unsigned int idx,struct i915_syncmap * child)222*3f2dd94aSFrançois Tigeot static inline void __sync_set_child(struct i915_syncmap *p,
223*3f2dd94aSFrançois Tigeot unsigned int idx,
224*3f2dd94aSFrançois Tigeot struct i915_syncmap *child)
225*3f2dd94aSFrançois Tigeot {
226*3f2dd94aSFrançois Tigeot p->bitmap |= BIT(idx);
227*3f2dd94aSFrançois Tigeot __sync_child(p)[idx] = child;
228*3f2dd94aSFrançois Tigeot }
229*3f2dd94aSFrançois Tigeot
__sync_set(struct i915_syncmap ** root,u64 id,u32 seqno)230*3f2dd94aSFrançois Tigeot static noinline int __sync_set(struct i915_syncmap **root, u64 id, u32 seqno)
231*3f2dd94aSFrançois Tigeot {
232*3f2dd94aSFrançois Tigeot struct i915_syncmap *p = *root;
233*3f2dd94aSFrançois Tigeot unsigned int idx;
234*3f2dd94aSFrançois Tigeot
235*3f2dd94aSFrançois Tigeot if (!p) {
236*3f2dd94aSFrançois Tigeot p = __sync_alloc_leaf(NULL, id);
237*3f2dd94aSFrançois Tigeot if (unlikely(!p))
238*3f2dd94aSFrançois Tigeot return -ENOMEM;
239*3f2dd94aSFrançois Tigeot
240*3f2dd94aSFrançois Tigeot goto found;
241*3f2dd94aSFrançois Tigeot }
242*3f2dd94aSFrançois Tigeot
243*3f2dd94aSFrançois Tigeot /* Caller handled the likely cached case */
244*3f2dd94aSFrançois Tigeot GEM_BUG_ON(__sync_leaf_prefix(p, id) == p->prefix);
245*3f2dd94aSFrançois Tigeot
246*3f2dd94aSFrançois Tigeot /* Climb back up the tree until we find a common prefix */
247*3f2dd94aSFrançois Tigeot do {
248*3f2dd94aSFrançois Tigeot if (!p->parent)
249*3f2dd94aSFrançois Tigeot break;
250*3f2dd94aSFrançois Tigeot
251*3f2dd94aSFrançois Tigeot p = p->parent;
252*3f2dd94aSFrançois Tigeot
253*3f2dd94aSFrançois Tigeot if (__sync_branch_prefix(p, id) == p->prefix)
254*3f2dd94aSFrançois Tigeot break;
255*3f2dd94aSFrançois Tigeot } while (1);
256*3f2dd94aSFrançois Tigeot
257*3f2dd94aSFrançois Tigeot /*
258*3f2dd94aSFrançois Tigeot * No shortcut, we have to descend the tree to find the right layer
259*3f2dd94aSFrançois Tigeot * containing this fence.
260*3f2dd94aSFrançois Tigeot *
261*3f2dd94aSFrançois Tigeot * Each layer in the tree holds 16 (KSYNCMAP) pointers, either fences
262*3f2dd94aSFrançois Tigeot * or lower layers. Leaf nodes (height = 0) contain the fences, all
263*3f2dd94aSFrançois Tigeot * other nodes (height > 0) are internal layers that point to a lower
264*3f2dd94aSFrançois Tigeot * node. Each internal layer has at least 2 descendents.
265*3f2dd94aSFrançois Tigeot *
266*3f2dd94aSFrançois Tigeot * Starting at the top, we check whether the current prefix matches. If
267*3f2dd94aSFrançois Tigeot * it doesn't, we have gone past our target and need to insert a join
268*3f2dd94aSFrançois Tigeot * into the tree, and a new leaf node for the target as a descendent
269*3f2dd94aSFrançois Tigeot * of the join, as well as the original layer.
270*3f2dd94aSFrançois Tigeot *
271*3f2dd94aSFrançois Tigeot * The matching prefix means we are still following the right branch
272*3f2dd94aSFrançois Tigeot * of the tree. If it has height 0, we have found our leaf and just
273*3f2dd94aSFrançois Tigeot * need to replace the fence slot with ourselves. If the height is
274*3f2dd94aSFrançois Tigeot * not zero, our slot contains the next layer in the tree (unless
275*3f2dd94aSFrançois Tigeot * it is empty, in which case we can add ourselves as a new leaf).
276*3f2dd94aSFrançois Tigeot * As descend the tree the prefix grows (and height decreases).
277*3f2dd94aSFrançois Tigeot */
278*3f2dd94aSFrançois Tigeot do {
279*3f2dd94aSFrançois Tigeot struct i915_syncmap *next;
280*3f2dd94aSFrançois Tigeot
281*3f2dd94aSFrançois Tigeot if (__sync_branch_prefix(p, id) != p->prefix) {
282*3f2dd94aSFrançois Tigeot unsigned int above;
283*3f2dd94aSFrançois Tigeot
284*3f2dd94aSFrançois Tigeot /* Insert a join above the current layer */
285*3f2dd94aSFrançois Tigeot next = kzalloc(sizeof(*next) + KSYNCMAP * sizeof(next),
286*3f2dd94aSFrançois Tigeot GFP_KERNEL);
287*3f2dd94aSFrançois Tigeot if (unlikely(!next))
288*3f2dd94aSFrançois Tigeot return -ENOMEM;
289*3f2dd94aSFrançois Tigeot
290*3f2dd94aSFrançois Tigeot /* Compute the height at which these two diverge */
291*3f2dd94aSFrançois Tigeot above = fls64(__sync_branch_prefix(p, id) ^ p->prefix);
292*3f2dd94aSFrançois Tigeot above = round_up(above, SHIFT);
293*3f2dd94aSFrançois Tigeot next->height = above + p->height;
294*3f2dd94aSFrançois Tigeot next->prefix = __sync_branch_prefix(next, id);
295*3f2dd94aSFrançois Tigeot
296*3f2dd94aSFrançois Tigeot /* Insert the join into the parent */
297*3f2dd94aSFrançois Tigeot if (p->parent) {
298*3f2dd94aSFrançois Tigeot idx = __sync_branch_idx(p->parent, id);
299*3f2dd94aSFrançois Tigeot __sync_child(p->parent)[idx] = next;
300*3f2dd94aSFrançois Tigeot GEM_BUG_ON(!(p->parent->bitmap & BIT(idx)));
301*3f2dd94aSFrançois Tigeot }
302*3f2dd94aSFrançois Tigeot next->parent = p->parent;
303*3f2dd94aSFrançois Tigeot
304*3f2dd94aSFrançois Tigeot /* Compute the idx of the other branch, not our id! */
305*3f2dd94aSFrançois Tigeot idx = p->prefix >> (above - SHIFT) & MASK;
306*3f2dd94aSFrançois Tigeot __sync_set_child(next, idx, p);
307*3f2dd94aSFrançois Tigeot p->parent = next;
308*3f2dd94aSFrançois Tigeot
309*3f2dd94aSFrançois Tigeot /* Ascend to the join */
310*3f2dd94aSFrançois Tigeot p = next;
311*3f2dd94aSFrançois Tigeot } else {
312*3f2dd94aSFrançois Tigeot if (!p->height)
313*3f2dd94aSFrançois Tigeot break;
314*3f2dd94aSFrançois Tigeot }
315*3f2dd94aSFrançois Tigeot
316*3f2dd94aSFrançois Tigeot /* Descend into the next layer */
317*3f2dd94aSFrançois Tigeot GEM_BUG_ON(!p->height);
318*3f2dd94aSFrançois Tigeot idx = __sync_branch_idx(p, id);
319*3f2dd94aSFrançois Tigeot next = __sync_child(p)[idx];
320*3f2dd94aSFrançois Tigeot if (!next) {
321*3f2dd94aSFrançois Tigeot next = __sync_alloc_leaf(p, id);
322*3f2dd94aSFrançois Tigeot if (unlikely(!next))
323*3f2dd94aSFrançois Tigeot return -ENOMEM;
324*3f2dd94aSFrançois Tigeot
325*3f2dd94aSFrançois Tigeot __sync_set_child(p, idx, next);
326*3f2dd94aSFrançois Tigeot p = next;
327*3f2dd94aSFrançois Tigeot break;
328*3f2dd94aSFrançois Tigeot }
329*3f2dd94aSFrançois Tigeot
330*3f2dd94aSFrançois Tigeot p = next;
331*3f2dd94aSFrançois Tigeot } while (1);
332*3f2dd94aSFrançois Tigeot
333*3f2dd94aSFrançois Tigeot found:
334*3f2dd94aSFrançois Tigeot GEM_BUG_ON(p->prefix != __sync_leaf_prefix(p, id));
335*3f2dd94aSFrançois Tigeot __sync_set_seqno(p, id, seqno);
336*3f2dd94aSFrançois Tigeot *root = p;
337*3f2dd94aSFrançois Tigeot return 0;
338*3f2dd94aSFrançois Tigeot }
339*3f2dd94aSFrançois Tigeot
340*3f2dd94aSFrançois Tigeot /**
341*3f2dd94aSFrançois Tigeot * i915_syncmap_set -- mark the most recent syncpoint between contexts
342*3f2dd94aSFrançois Tigeot * @root - pointer to the #i915_syncmap
343*3f2dd94aSFrançois Tigeot * @id - the context id (other timeline) we have synchronised to
344*3f2dd94aSFrançois Tigeot * @seqno - the sequence number along the other timeline
345*3f2dd94aSFrançois Tigeot *
346*3f2dd94aSFrançois Tigeot * When we synchronise this @root timeline with another (@id), we also know
347*3f2dd94aSFrançois Tigeot * that we have synchronized with all previous seqno along that timeline. If
348*3f2dd94aSFrançois Tigeot * we then have a request to synchronise with the same seqno or older, we can
349*3f2dd94aSFrançois Tigeot * omit it, see i915_syncmap_is_later()
350*3f2dd94aSFrançois Tigeot *
351*3f2dd94aSFrançois Tigeot * Returns 0 on success, or a negative error code.
352*3f2dd94aSFrançois Tigeot */
i915_syncmap_set(struct i915_syncmap ** root,u64 id,u32 seqno)353*3f2dd94aSFrançois Tigeot int i915_syncmap_set(struct i915_syncmap **root, u64 id, u32 seqno)
354*3f2dd94aSFrançois Tigeot {
355*3f2dd94aSFrançois Tigeot struct i915_syncmap *p = *root;
356*3f2dd94aSFrançois Tigeot
357*3f2dd94aSFrançois Tigeot /*
358*3f2dd94aSFrançois Tigeot * We expect to be called in sequence following is_later(id), which
359*3f2dd94aSFrançois Tigeot * should have preloaded the root for us.
360*3f2dd94aSFrançois Tigeot */
361*3f2dd94aSFrançois Tigeot if (likely(p && __sync_leaf_prefix(p, id) == p->prefix)) {
362*3f2dd94aSFrançois Tigeot __sync_set_seqno(p, id, seqno);
363*3f2dd94aSFrançois Tigeot return 0;
364*3f2dd94aSFrançois Tigeot }
365*3f2dd94aSFrançois Tigeot
366*3f2dd94aSFrançois Tigeot return __sync_set(root, id, seqno);
367*3f2dd94aSFrançois Tigeot }
368*3f2dd94aSFrançois Tigeot
__sync_free(struct i915_syncmap * p)369*3f2dd94aSFrançois Tigeot static void __sync_free(struct i915_syncmap *p)
370*3f2dd94aSFrançois Tigeot {
371*3f2dd94aSFrançois Tigeot if (p->height) {
372*3f2dd94aSFrançois Tigeot unsigned int i;
373*3f2dd94aSFrançois Tigeot
374*3f2dd94aSFrançois Tigeot while ((i = ffs(p->bitmap))) {
375*3f2dd94aSFrançois Tigeot p->bitmap &= ~0u << i;
376*3f2dd94aSFrançois Tigeot __sync_free(__sync_child(p)[i - 1]);
377*3f2dd94aSFrançois Tigeot }
378*3f2dd94aSFrançois Tigeot }
379*3f2dd94aSFrançois Tigeot
380*3f2dd94aSFrançois Tigeot kfree(p);
381*3f2dd94aSFrançois Tigeot }
382*3f2dd94aSFrançois Tigeot
383*3f2dd94aSFrançois Tigeot /**
384*3f2dd94aSFrançois Tigeot * i915_syncmap_free -- free all memory associated with the syncmap
385*3f2dd94aSFrançois Tigeot * @root - pointer to the #i915_syncmap
386*3f2dd94aSFrançois Tigeot *
387*3f2dd94aSFrançois Tigeot * Either when the timeline is to be freed and we no longer need the sync
388*3f2dd94aSFrançois Tigeot * point tracking, or when the fences are all known to be signaled and the
389*3f2dd94aSFrançois Tigeot * sync point tracking is redundant, we can free the #i915_syncmap to recover
390*3f2dd94aSFrançois Tigeot * its allocations.
391*3f2dd94aSFrançois Tigeot *
392*3f2dd94aSFrançois Tigeot * Will reinitialise the @root pointer so that the #i915_syncmap is ready for
393*3f2dd94aSFrançois Tigeot * reuse.
394*3f2dd94aSFrançois Tigeot */
i915_syncmap_free(struct i915_syncmap ** root)395*3f2dd94aSFrançois Tigeot void i915_syncmap_free(struct i915_syncmap **root)
396*3f2dd94aSFrançois Tigeot {
397*3f2dd94aSFrançois Tigeot struct i915_syncmap *p;
398*3f2dd94aSFrançois Tigeot
399*3f2dd94aSFrançois Tigeot p = *root;
400*3f2dd94aSFrançois Tigeot if (!p)
401*3f2dd94aSFrançois Tigeot return;
402*3f2dd94aSFrançois Tigeot
403*3f2dd94aSFrançois Tigeot while (p->parent)
404*3f2dd94aSFrançois Tigeot p = p->parent;
405*3f2dd94aSFrançois Tigeot
406*3f2dd94aSFrançois Tigeot __sync_free(p);
407*3f2dd94aSFrançois Tigeot *root = NULL;
408*3f2dd94aSFrançois Tigeot }
409*3f2dd94aSFrançois Tigeot
410*3f2dd94aSFrançois Tigeot #if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
411*3f2dd94aSFrançois Tigeot #include "selftests/i915_syncmap.c"
412*3f2dd94aSFrançois Tigeot #endif
413