96 static inline u32 *__sync_seqno(struct i915_syncmap *p)  in __sync_seqno()  argument
98 	GEM_BUG_ON(p->height);  in __sync_seqno()
99 	return p->seqno;  in __sync_seqno()
102 static inline struct i915_syncmap **__sync_child(struct i915_syncmap *p)  in __sync_child()  argument
104 	GEM_BUG_ON(!p->height);  in __sync_child()
105 	return p->child;  in __sync_child()
109 __sync_branch_idx(const struct i915_syncmap *p, u64 id)  in __sync_branch_idx()  argument
111 	return (id >> p->height) & MASK;  in __sync_branch_idx()
115 __sync_leaf_idx(const struct i915_syncmap *p, u64 id)  in __sync_leaf_idx()  argument
117 	GEM_BUG_ON(p->height);  in __sync_leaf_idx()
121 static inline u64 __sync_branch_prefix(const struct i915_syncmap *p, u64 id)  in __sync_branch_prefix()  argument
123 	return id >> p->height >> SHIFT;  in __sync_branch_prefix()
126 static inline u64 __sync_leaf_prefix(const struct i915_syncmap *p, u64 id)  in __sync_leaf_prefix()  argument
128 	GEM_BUG_ON(p->height);  in __sync_leaf_prefix()
153 	struct i915_syncmap *p;  in i915_syncmap_is_later()  local
156 	p = *root;  in i915_syncmap_is_later()
157 	if (!p)  in i915_syncmap_is_later()
160 	if (likely(__sync_leaf_prefix(p, id) == p->prefix))  in i915_syncmap_is_later()
165 		p = p->parent;  in i915_syncmap_is_later()
166 		if (!p)  in i915_syncmap_is_later()
169 		if (__sync_branch_prefix(p, id) == p->prefix)  in i915_syncmap_is_later()
175 		if (!p->height)  in i915_syncmap_is_later()
178 		p = __sync_child(p)[__sync_branch_idx(p, id)];  in i915_syncmap_is_later()
179 		if (!p)  in i915_syncmap_is_later()
182 		if (__sync_branch_prefix(p, id) != p->prefix)  in i915_syncmap_is_later()
186 	*root = p;  in i915_syncmap_is_later()
188 	idx = __sync_leaf_idx(p, id);  in i915_syncmap_is_later()
189 	if (!(p->bitmap & BIT(idx)))  in i915_syncmap_is_later()
192 	return seqno_later(__sync_seqno(p)[idx], seqno);  in i915_syncmap_is_later()
198 	struct i915_syncmap *p;  in __sync_alloc_leaf()  local
200 	p = kmalloc(struct_size(p, seqno, KSYNCMAP), GFP_KERNEL);  in __sync_alloc_leaf()
201 	if (unlikely(!p))  in __sync_alloc_leaf()
204 	p->parent = parent;  in __sync_alloc_leaf()
205 	p->height = 0;  in __sync_alloc_leaf()
206 	p->bitmap = 0;  in __sync_alloc_leaf()
207 	p->prefix = __sync_leaf_prefix(p, id);  in __sync_alloc_leaf()
208 	return p;  in __sync_alloc_leaf()
211 static inline void __sync_set_seqno(struct i915_syncmap *p, u64 id, u32 seqno)  in __sync_set_seqno()  argument
213 	unsigned int idx = __sync_leaf_idx(p, id);  in __sync_set_seqno()
215 	p->bitmap |= BIT(idx);  in __sync_set_seqno()
216 	__sync_seqno(p)[idx] = seqno;  in __sync_set_seqno()  local
219 static inline void __sync_set_child(struct i915_syncmap *p,  in __sync_set_child()  argument
223 	p->bitmap |= BIT(idx);  in __sync_set_child()
224 	__sync_child(p)[idx] = child;  in __sync_set_child()  local
229 	struct i915_syncmap *p = *root;  in __sync_set()  local
232 	if (!p) {  in __sync_set()
233 		p = __sync_alloc_leaf(NULL, id);  in __sync_set()
234 		if (unlikely(!p))  in __sync_set()
241 	GEM_BUG_ON(__sync_leaf_prefix(p, id) == p->prefix);  in __sync_set()
245 		if (!p->parent)  in __sync_set()
248 		p = p->parent;  in __sync_set()
250 		if (__sync_branch_prefix(p, id) == p->prefix)  in __sync_set()
278 		if (__sync_branch_prefix(p, id) != p->prefix) {  in __sync_set()
288 			above = fls64(__sync_branch_prefix(p, id) ^ p->prefix);  in __sync_set()
290 			next->height = above + p->height;  in __sync_set()
294 			if (p->parent) {  in __sync_set()
295 				idx = __sync_branch_idx(p->parent, id);  in __sync_set()
296 				__sync_child(p->parent)[idx] = next;  in __sync_set()  local
297 				GEM_BUG_ON(!(p->parent->bitmap & BIT(idx)));  in __sync_set()
299 			next->parent = p->parent;  in __sync_set()
302 			idx = p->prefix >> (above - SHIFT) & MASK;  in __sync_set()
303 			__sync_set_child(next, idx, p);  in __sync_set()
304 			p->parent = next;  in __sync_set()
307 			p = next;  in __sync_set()
309 			if (!p->height)  in __sync_set()
314 		GEM_BUG_ON(!p->height);  in __sync_set()
315 		idx = __sync_branch_idx(p, id);  in __sync_set()
316 		next = __sync_child(p)[idx];  in __sync_set()
318 			next = __sync_alloc_leaf(p, id);  in __sync_set()
322 			__sync_set_child(p, idx, next);  in __sync_set()
323 			p = next;  in __sync_set()
327 		p = next;  in __sync_set()
331 	GEM_BUG_ON(p->prefix != __sync_leaf_prefix(p, id));  in __sync_set()
332 	__sync_set_seqno(p, id, seqno);  in __sync_set()
333 	*root = p;  in __sync_set()
352 	struct i915_syncmap *p = *root;  in i915_syncmap_set()  local
358 	if (likely(p && __sync_leaf_prefix(p, id) == p->prefix)) {  in i915_syncmap_set()
359 		__sync_set_seqno(p, id, seqno);  in i915_syncmap_set()
366 static void __sync_free(struct i915_syncmap *p)  in __sync_free()  argument
368 	if (p->height) {  in __sync_free()
371 		while ((i = ffs(p->bitmap))) {  in __sync_free()
372 			p->bitmap &= ~0u << i;  in __sync_free()
373 			__sync_free(__sync_child(p)[i - 1]);  in __sync_free()
377 	kfree(p);  in __sync_free()
394 	struct i915_syncmap *p;  in i915_syncmap_free()  local
396 	p = *root;  in i915_syncmap_free()
397 	if (!p)  in i915_syncmap_free()
400 	while (p->parent)  in i915_syncmap_free()
401 		p = p->parent;  in i915_syncmap_free()
403 	__sync_free(p);  in i915_syncmap_free()