Branch data     Line data    Source code

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