99 static inline u32 *__sync_seqno(struct i915_syncmap *p)  in __sync_seqno()  argument
101 	GEM_BUG_ON(p->height);  in __sync_seqno()
102 	return (u32 *)(p + 1);  in __sync_seqno()
105 static inline struct i915_syncmap **__sync_child(struct i915_syncmap *p)  in __sync_child()  argument
107 	GEM_BUG_ON(!p->height);  in __sync_child()
108 	return (struct i915_syncmap **)(p + 1);  in __sync_child()
112 __sync_branch_idx(const struct i915_syncmap *p, u64 id)  in __sync_branch_idx()  argument
114 	return (id >> p->height) & MASK;  in __sync_branch_idx()
118 __sync_leaf_idx(const struct i915_syncmap *p, u64 id)  in __sync_leaf_idx()  argument
120 	GEM_BUG_ON(p->height);  in __sync_leaf_idx()
124 static inline u64 __sync_branch_prefix(const struct i915_syncmap *p, u64 id)  in __sync_branch_prefix()  argument
126 	return id >> p->height >> SHIFT;  in __sync_branch_prefix()
129 static inline u64 __sync_leaf_prefix(const struct i915_syncmap *p, u64 id)  in __sync_leaf_prefix()  argument
131 	GEM_BUG_ON(p->height);  in __sync_leaf_prefix()
156 	struct i915_syncmap *p;  in i915_syncmap_is_later()  local
159 	p = *root;  in i915_syncmap_is_later()
160 	if (!p)  in i915_syncmap_is_later()
163 	if (likely(__sync_leaf_prefix(p, id) == p->prefix))  in i915_syncmap_is_later()
168 		p = p->parent;  in i915_syncmap_is_later()
169 		if (!p)  in i915_syncmap_is_later()
172 		if (__sync_branch_prefix(p, id) == p->prefix)  in i915_syncmap_is_later()
178 		if (!p->height)  in i915_syncmap_is_later()
181 		p = __sync_child(p)[__sync_branch_idx(p, id)];  in i915_syncmap_is_later()
182 		if (!p)  in i915_syncmap_is_later()
185 		if (__sync_branch_prefix(p, id) != p->prefix)  in i915_syncmap_is_later()
189 	*root = p;  in i915_syncmap_is_later()
191 	idx = __sync_leaf_idx(p, id);  in i915_syncmap_is_later()
192 	if (!(p->bitmap & BIT(idx)))  in i915_syncmap_is_later()
195 	return seqno_later(__sync_seqno(p)[idx], seqno);  in i915_syncmap_is_later()
201 	struct i915_syncmap *p;  in __sync_alloc_leaf()  local
203 	p = kmalloc(sizeof(*p) + KSYNCMAP * sizeof(u32), GFP_KERNEL);  in __sync_alloc_leaf()
204 	if (unlikely(!p))  in __sync_alloc_leaf()
207 	p->parent = parent;  in __sync_alloc_leaf()
208 	p->height = 0;  in __sync_alloc_leaf()
209 	p->bitmap = 0;  in __sync_alloc_leaf()
210 	p->prefix = __sync_leaf_prefix(p, id);  in __sync_alloc_leaf()
211 	return p;  in __sync_alloc_leaf()
214 static inline void __sync_set_seqno(struct i915_syncmap *p, u64 id, u32 seqno)  in __sync_set_seqno()  argument
216 	unsigned int idx = __sync_leaf_idx(p, id);  in __sync_set_seqno()
218 	p->bitmap |= BIT(idx);  in __sync_set_seqno()
219 	__sync_seqno(p)[idx] = seqno;  in __sync_set_seqno()  local
222 static inline void __sync_set_child(struct i915_syncmap *p,  in __sync_set_child()  argument
226 	p->bitmap |= BIT(idx);  in __sync_set_child()
227 	__sync_child(p)[idx] = child;  in __sync_set_child()  local
232 	struct i915_syncmap *p = *root;  in __sync_set()  local
235 	if (!p) {  in __sync_set()
236 		p = __sync_alloc_leaf(NULL, id);  in __sync_set()
237 		if (unlikely(!p))  in __sync_set()
244 	GEM_BUG_ON(__sync_leaf_prefix(p, id) == p->prefix);  in __sync_set()
248 		if (!p->parent)  in __sync_set()
251 		p = p->parent;  in __sync_set()
253 		if (__sync_branch_prefix(p, id) == p->prefix)  in __sync_set()
281 		if (__sync_branch_prefix(p, id) != p->prefix) {  in __sync_set()
291 			above = fls64(__sync_branch_prefix(p, id) ^ p->prefix);  in __sync_set()
293 			next->height = above + p->height;  in __sync_set()
297 			if (p->parent) {  in __sync_set()
298 				idx = __sync_branch_idx(p->parent, id);  in __sync_set()
299 				__sync_child(p->parent)[idx] = next;  in __sync_set()  local
300 				GEM_BUG_ON(!(p->parent->bitmap & BIT(idx)));  in __sync_set()
302 			next->parent = p->parent;  in __sync_set()
305 			idx = p->prefix >> (above - SHIFT) & MASK;  in __sync_set()
306 			__sync_set_child(next, idx, p);  in __sync_set()
307 			p->parent = next;  in __sync_set()
310 			p = next;  in __sync_set()
312 			if (!p->height)  in __sync_set()
317 		GEM_BUG_ON(!p->height);  in __sync_set()
318 		idx = __sync_branch_idx(p, id);  in __sync_set()
319 		next = __sync_child(p)[idx];  in __sync_set()
321 			next = __sync_alloc_leaf(p, id);  in __sync_set()
325 			__sync_set_child(p, idx, next);  in __sync_set()
326 			p = next;  in __sync_set()
330 		p = next;  in __sync_set()
334 	GEM_BUG_ON(p->prefix != __sync_leaf_prefix(p, id));  in __sync_set()
335 	__sync_set_seqno(p, id, seqno);  in __sync_set()
336 	*root = p;  in __sync_set()
355 	struct i915_syncmap *p = *root;  in i915_syncmap_set()  local
361 	if (likely(p && __sync_leaf_prefix(p, id) == p->prefix)) {  in i915_syncmap_set()
362 		__sync_set_seqno(p, id, seqno);  in i915_syncmap_set()
369 static void __sync_free(struct i915_syncmap *p)  in __sync_free()  argument
371 	if (p->height) {  in __sync_free()
374 		while ((i = ffs(p->bitmap))) {  in __sync_free()
375 			p->bitmap &= ~0u << i;  in __sync_free()
376 			__sync_free(__sync_child(p)[i - 1]);  in __sync_free()
380 	kfree(p);  in __sync_free()
397 	struct i915_syncmap *p;  in i915_syncmap_free()  local
399 	p = *root;  in i915_syncmap_free()
400 	if (!p)  in i915_syncmap_free()
403 	while (p->parent)  in i915_syncmap_free()
404 		p = p->parent;  in i915_syncmap_free()
406 	__sync_free(p);  in i915_syncmap_free()