75 static void mark_free(struct i915_buddy_mm *mm,  in mark_free()  argument
82 		 &mm->free_list[i915_buddy_block_order(block)]);  in mark_free()
93 int i915_buddy_init(struct i915_buddy_mm *mm, u64 size, u64 chunk_size)  in i915_buddy_init()  argument
109 	mm->size = size;  in i915_buddy_init()
110 	mm->chunk_size = chunk_size;  in i915_buddy_init()
111 	mm->max_order = ilog2(size) - ilog2(chunk_size);  in i915_buddy_init()
113 	GEM_BUG_ON(mm->max_order > I915_BUDDY_MAX_ORDER);  in i915_buddy_init()
115 	mm->free_list = kmalloc_array(mm->max_order + 1,  in i915_buddy_init()
118 	if (!mm->free_list)  in i915_buddy_init()
121 	for (i = 0; i <= mm->max_order; ++i)  in i915_buddy_init()
122 		INIT_LIST_HEAD(&mm->free_list[i]);  in i915_buddy_init()
124 	mm->n_roots = hweight64(size);  in i915_buddy_init()
126 	mm->roots = kmalloc_array(mm->n_roots,  in i915_buddy_init()
129 	if (!mm->roots)  in i915_buddy_init()
151 		mark_free(mm, root);  in i915_buddy_init()
153 		GEM_BUG_ON(i > mm->max_order);  in i915_buddy_init()
154 		GEM_BUG_ON(i915_buddy_block_size(mm, root) < chunk_size);  in i915_buddy_init()
156 		mm->roots[i] = root;  in i915_buddy_init()
167 		i915_block_free(mm->roots[i]);  in i915_buddy_init()
168 	kfree(mm->roots);  in i915_buddy_init()
170 	kfree(mm->free_list);  in i915_buddy_init()
174 void i915_buddy_fini(struct i915_buddy_mm *mm)  in i915_buddy_fini()  argument
178 	for (i = 0; i < mm->n_roots; ++i) {  in i915_buddy_fini()
179 		GEM_WARN_ON(!i915_buddy_block_is_free(mm->roots[i]));  in i915_buddy_fini()
180 		i915_block_free(mm->roots[i]);  in i915_buddy_fini()
183 	kfree(mm->roots);  in i915_buddy_fini()
184 	kfree(mm->free_list);  in i915_buddy_fini()
187 static int split_block(struct i915_buddy_mm *mm,  in split_block()  argument
201 					offset + (mm->chunk_size << block_order));  in split_block()
207 	mark_free(mm, block->left);  in split_block()
208 	mark_free(mm, block->right);  in split_block()
230 static void __i915_buddy_free(struct i915_buddy_mm *mm,  in __i915_buddy_free()  argument
251 	mark_free(mm, block);  in __i915_buddy_free()
254 void i915_buddy_free(struct i915_buddy_mm *mm,  in i915_buddy_free()  argument
258 	__i915_buddy_free(mm, block);  in i915_buddy_free()
261 void i915_buddy_free_list(struct i915_buddy_mm *mm, struct list_head *objects)  in i915_buddy_free_list()  argument
266 		i915_buddy_free(mm, block);  in i915_buddy_free_list()
275  *   0 = 2^0 * mm->chunk_size
276  *   1 = 2^1 * mm->chunk_size
277  *   2 = 2^2 * mm->chunk_size
281 i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order)  in i915_buddy_alloc()  argument
287 	for (i = order; i <= mm->max_order; ++i) {  in i915_buddy_alloc()
288 		block = list_first_entry_or_null(&mm->free_list[i],  in i915_buddy_alloc()
301 		err = split_block(mm, block);  in i915_buddy_alloc()
316 		__i915_buddy_free(mm, block);  in i915_buddy_alloc()
340 int i915_buddy_alloc_range(struct i915_buddy_mm *mm,  in i915_buddy_alloc_range()  argument
352 	if (size < mm->chunk_size)  in i915_buddy_alloc_range()
355 	if (!IS_ALIGNED(size | start, mm->chunk_size))  in i915_buddy_alloc_range()
358 	if (range_overflows(start, size, mm->size))  in i915_buddy_alloc_range()
361 	for (i = 0; i < mm->n_roots; ++i)  in i915_buddy_alloc_range()
362 		list_add_tail(&mm->roots[i]->tmp_link, &dfs);  in i915_buddy_alloc_range()
379 		block_end = block_start + i915_buddy_block_size(mm, block) - 1;  in i915_buddy_alloc_range()
401 			err = split_block(mm, block);  in i915_buddy_alloc_range()
423 		__i915_buddy_free(mm, block);  in i915_buddy_alloc_range()
426 	i915_buddy_free_list(mm, &allocated);  in i915_buddy_alloc_range()