Home | History | Annotate | Line # | Download | only in i915 
      1 /*	$NetBSD: i915_buddy.h,v 1.2 2021/12/18 23:45:28 riastradh Exp $	*/
      2 
      3 /* SPDX-License-Identifier: MIT */
      4 /*
      5  * Copyright  2019 Intel Corporation
      6  */
      7 
      8 #ifndef __I915_BUDDY_H__
      9 #define __I915_BUDDY_H__
     10 
     11 #include <linux/bitops.h>
     12 #include <linux/list.h>
     13 
     14 struct i915_buddy_block {
     15 #define I915_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)
     16 #define I915_BUDDY_HEADER_STATE  GENMASK_ULL(11, 10)
     17 #define   I915_BUDDY_ALLOCATED	   (1 << 10)
     18 #define   I915_BUDDY_FREE	   (2 << 10)
     19 #define   I915_BUDDY_SPLIT	   (3 << 10)
     20 #define I915_BUDDY_HEADER_ORDER  GENMASK_ULL(9, 0)
     21 	u64 header;
     22 
     23 	struct i915_buddy_block *left;
     24 	struct i915_buddy_block *right;
     25 	struct i915_buddy_block *parent;
     26 
     27 	void *private; /* owned by creator */
     28 
     29 	/*
     30 	 * While the block is allocated by the user through i915_buddy_alloc*,
     31 	 * the user has ownership of the link, for example to maintain within
     32 	 * a list, if so desired. As soon as the block is freed with
     33 	 * i915_buddy_free* ownership is given back to the mm.
     34 	 */
     35 	struct list_head link;
     36 	struct list_head tmp_link;
     37 };
     38 
     39 #define I915_BUDDY_MAX_ORDER  I915_BUDDY_HEADER_ORDER
     40 
     41 /*
     42  * Binary Buddy System.
     43  *
     44  * Locking should be handled by the user, a simple mutex around
     45  * i915_buddy_alloc* and i915_buddy_free* should suffice.
     46  */
     47 struct i915_buddy_mm {
     48 	/* Maintain a free list for each order. */
     49 	struct list_head *free_list;
     50 
     51 	/*
     52 	 * Maintain explicit binary tree(s) to track the allocation of the
     53 	 * address space. This gives us a simple way of finding a buddy block
     54 	 * and performing the potentially recursive merge step when freeing a
     55 	 * block.  Nodes are either allocated or free, in which case they will
     56 	 * also exist on the respective free list.
     57 	 */
     58 	struct i915_buddy_block **roots;
     59 
     60 	/*
     61 	 * Anything from here is public, and remains static for the lifetime of
     62 	 * the mm. Everything above is considered do-not-touch.
     63 	 */
     64 	unsigned int n_roots;
     65 	unsigned int max_order;
     66 
     67 	/* Must be at least PAGE_SIZE */
     68 	u64 chunk_size;
     69 	u64 size;
     70 };
     71 
     72 static inline u64
     73 i915_buddy_block_offset(struct i915_buddy_block *block)
     74 {
     75 	return block->header & I915_BUDDY_HEADER_OFFSET;
     76 }
     77 
     78 static inline unsigned int
     79 i915_buddy_block_order(struct i915_buddy_block *block)
     80 {
     81 	return block->header & I915_BUDDY_HEADER_ORDER;
     82 }
     83 
     84 static inline unsigned int
     85 i915_buddy_block_state(struct i915_buddy_block *block)
     86 {
     87 	return block->header & I915_BUDDY_HEADER_STATE;
     88 }
     89 
     90 static inline bool
     91 i915_buddy_block_is_allocated(struct i915_buddy_block *block)
     92 {
     93 	return i915_buddy_block_state(block) == I915_BUDDY_ALLOCATED;
     94 }
     95 
     96 static inline bool
     97 i915_buddy_block_is_free(struct i915_buddy_block *block)
     98 {
     99 	return i915_buddy_block_state(block) == I915_BUDDY_FREE;
    100 }
    101 
    102 static inline bool
    103 i915_buddy_block_is_split(struct i915_buddy_block *block)
    104 {
    105 	return i915_buddy_block_state(block) == I915_BUDDY_SPLIT;
    106 }
    107 
    108 static inline u64
    109 i915_buddy_block_size(struct i915_buddy_mm *mm,
    110 		      struct i915_buddy_block *block)
    111 {
    112 	return mm->chunk_size << i915_buddy_block_order(block);
    113 }
    114 
    115 int i915_buddy_init(struct i915_buddy_mm *mm, u64 size, u64 chunk_size);
    116 
    117 void i915_buddy_fini(struct i915_buddy_mm *mm);
    118 
    119 struct i915_buddy_block *
    120 i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order);
    121 
    122 int i915_buddy_alloc_range(struct i915_buddy_mm *mm,
    123 			   struct list_head *blocks,
    124 			   u64 start, u64 size);
    125 
    126 void i915_buddy_free(struct i915_buddy_mm *mm, struct i915_buddy_block *block);
    127 
    128 void i915_buddy_free_list(struct i915_buddy_mm *mm, struct list_head *objects);
    129 
    130 #endif
    131