49 	struct i915_buddy_block *block;  in i915_block_alloc()  local
51 	block = kmem_cache_zalloc(global.slab_blocks, GFP_KERNEL);  in i915_block_alloc()
52 	if (!block)  in i915_block_alloc()
55 	block->header = offset;  in i915_block_alloc()
56 	block->header |= order;  in i915_block_alloc()
57 	block->parent = parent;  in i915_block_alloc()
59 	return block;  in i915_block_alloc()
62 static void i915_block_free(struct i915_buddy_block *block)  in i915_block_free()  argument
64 	kmem_cache_free(global.slab_blocks, block);  in i915_block_free()
67 static void mark_allocated(struct i915_buddy_block *block)  in mark_allocated()  argument
69 	block->header &= ~I915_BUDDY_HEADER_STATE;  in mark_allocated()
70 	block->header |= I915_BUDDY_ALLOCATED;  in mark_allocated()
72 	list_del(&block->link);  in mark_allocated()
76 		      struct i915_buddy_block *block)  in mark_free()  argument
78 	block->header &= ~I915_BUDDY_HEADER_STATE;  in mark_free()
79 	block->header |= I915_BUDDY_FREE;  in mark_free()
81 	list_add(&block->link,  in mark_free()
82 		 &mm->free_list[i915_buddy_block_order(block)]);  in mark_free()
85 static void mark_split(struct i915_buddy_block *block)  in mark_split()  argument
87 	block->header &= ~I915_BUDDY_HEADER_STATE;  in mark_split()
88 	block->header |= I915_BUDDY_SPLIT;  in mark_split()
90 	list_del(&block->link);  in mark_split()
188 		       struct i915_buddy_block *block)  in split_block()  argument
190 	unsigned int block_order = i915_buddy_block_order(block) - 1;  in split_block()
191 	u64 offset = i915_buddy_block_offset(block);  in split_block()
193 	GEM_BUG_ON(!i915_buddy_block_is_free(block));  in split_block()
194 	GEM_BUG_ON(!i915_buddy_block_order(block));  in split_block()
196 	block->left = i915_block_alloc(block, block_order, offset);  in split_block()
197 	if (!block->left)  in split_block()
200 	block->right = i915_block_alloc(block, block_order,  in split_block()
202 	if (!block->right) {  in split_block()
203 		i915_block_free(block->left);  in split_block()
207 	mark_free(mm, block->left);  in split_block()
208 	mark_free(mm, block->right);  in split_block()
210 	mark_split(block);  in split_block()
216 get_buddy(struct i915_buddy_block *block)  in get_buddy()  argument
220 	parent = block->parent;  in get_buddy()
224 	if (parent->left == block)  in get_buddy()
231 			      struct i915_buddy_block *block)  in __i915_buddy_free()  argument
235 	while ((parent = block->parent)) {  in __i915_buddy_free()
238 		buddy = get_buddy(block);  in __i915_buddy_free()
245 		i915_block_free(block);  in __i915_buddy_free()
248 		block = parent;  in __i915_buddy_free()
251 	mark_free(mm, block);  in __i915_buddy_free()
255 		     struct i915_buddy_block *block)  in i915_buddy_free()  argument
257 	GEM_BUG_ON(!i915_buddy_block_is_allocated(block));  in i915_buddy_free()
258 	__i915_buddy_free(mm, block);  in i915_buddy_free()
263 	struct i915_buddy_block *block, *on;  in i915_buddy_free_list()  local
265 	list_for_each_entry_safe(block, on, objects, link) {  in i915_buddy_free_list()
266 		i915_buddy_free(mm, block);  in i915_buddy_free_list()
283 	struct i915_buddy_block *block = NULL;  in i915_buddy_alloc()  local
288 		block = list_first_entry_or_null(&mm->free_list[i],  in i915_buddy_alloc()
291 		if (block)  in i915_buddy_alloc()
295 	if (!block)  in i915_buddy_alloc()
298 	GEM_BUG_ON(!i915_buddy_block_is_free(block));  in i915_buddy_alloc()
301 		err = split_block(mm, block);  in i915_buddy_alloc()
306 		block = block->left;  in i915_buddy_alloc()
310 	mark_allocated(block);  in i915_buddy_alloc()
311 	kmemleak_update_trace(block);  in i915_buddy_alloc()
312 	return block;  in i915_buddy_alloc()
316 		__i915_buddy_free(mm, block);  in i915_buddy_alloc()
344 	struct i915_buddy_block *block;  in i915_buddy_alloc_range()  local
370 		block = list_first_entry_or_null(&dfs,  in i915_buddy_alloc_range()
373 		if (!block)  in i915_buddy_alloc_range()
376 		list_del(&block->tmp_link);  in i915_buddy_alloc_range()
378 		block_start = i915_buddy_block_offset(block);  in i915_buddy_alloc_range()
379 		block_end = block_start + i915_buddy_block_size(mm, block) - 1;  in i915_buddy_alloc_range()
384 		if (i915_buddy_block_is_allocated(block)) {  in i915_buddy_alloc_range()
390 			if (!i915_buddy_block_is_free(block)) {  in i915_buddy_alloc_range()
395 			mark_allocated(block);  in i915_buddy_alloc_range()
396 			list_add_tail(&block->link, &allocated);  in i915_buddy_alloc_range()
400 		if (!i915_buddy_block_is_split(block)) {  in i915_buddy_alloc_range()
401 			err = split_block(mm, block);  in i915_buddy_alloc_range()
406 		list_add(&block->right->tmp_link, &dfs);  in i915_buddy_alloc_range()
407 		list_add(&block->left->tmp_link, &dfs);  in i915_buddy_alloc_range()
419 	buddy = get_buddy(block);  in i915_buddy_alloc_range()
421 	    (i915_buddy_block_is_free(block) &&  in i915_buddy_alloc_range()
423 		__i915_buddy_free(mm, block);  in i915_buddy_alloc_range()