Line data    Source code

       1             : /* SPDX-License-Identifier: MIT */
       2             : /*
       3             :  * Copyright © 2021 Intel Corporation
       4             :  */
       5             : 
       6             : #ifndef __DRM_BUDDY_H__
       7             : #define __DRM_BUDDY_H__
       8             : 
       9             : #include <linux/bitops.h>
      10             : #include <linux/list.h>
      11             : #include <linux/slab.h>
      12             : #include <linux/sched.h>
      13             : 
      14             : #include <drm/drm_print.h>
      15             : 
      16             : #define range_overflows(start, size, max) ({ \
      17             :         typeof(start) start__ = (start); \
      18             :         typeof(size) size__ = (size); \
      19             :         typeof(max) max__ = (max); \
      20             :         (void)(&start__ == &size__); \
      21             :         (void)(&start__ == &max__); \
      22             :         start__ >= max__ || size__ > max__ - start__; \
      23             : })
      24             : 
      25             : #define DRM_BUDDY_RANGE_ALLOCATION (1 << 0)
      26             : #define DRM_BUDDY_TOPDOWN_ALLOCATION (1 << 1)
      27             : 
      28             : struct drm_buddy_block {
      29             : #define DRM_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)
      30             : #define DRM_BUDDY_HEADER_STATE  GENMASK_ULL(11, 10)
      31             : #define   DRM_BUDDY_ALLOCATED      (1 << 10)
      32             : #define   DRM_BUDDY_FREE           (2 << 10)
      33             : #define   DRM_BUDDY_SPLIT          (3 << 10)
      34             : /* Free to be used, if needed in the future */
      35             : #define DRM_BUDDY_HEADER_UNUSED GENMASK_ULL(9, 6)
      36             : #define DRM_BUDDY_HEADER_ORDER  GENMASK_ULL(5, 0)
      37             :         u64 header;
      38             : 
      39             :         struct drm_buddy_block *left;
      40             :         struct drm_buddy_block *right;
      41             :         struct drm_buddy_block *parent;
      42             : 
      43             :         void *private; /* owned by creator */
      44             : 
      45             :         /*
      46             :          * While the block is allocated by the user through drm_buddy_alloc*,
      47             :          * the user has ownership of the link, for example to maintain within
      48             :          * a list, if so desired. As soon as the block is freed with
      49             :          * drm_buddy_free* ownership is given back to the mm.
      50             :          */
      51             :         struct list_head link;
      52             :         struct list_head tmp_link;
      53             : };
      54             : 
      55             : /* Order-zero must be at least PAGE_SIZE */
      56             : #define DRM_BUDDY_MAX_ORDER (63 - PAGE_SHIFT)
      57             : 
      58             : /*
      59             :  * Binary Buddy System.
      60             :  *
      61             :  * Locking should be handled by the user, a simple mutex around
      62             :  * drm_buddy_alloc* and drm_buddy_free* should suffice.
      63             :  */
      64             : struct drm_buddy {
      65             :         /* Maintain a free list for each order. */
      66             :         struct list_head *free_list;
      67             : 
      68             :         /*
      69             :          * Maintain explicit binary tree(s) to track the allocation of the
      70             :          * address space. This gives us a simple way of finding a buddy block
      71             :          * and performing the potentially recursive merge step when freeing a
      72             :          * block.  Nodes are either allocated or free, in which case they will
      73             :          * also exist on the respective free list.
      74             :          */
      75             :         struct drm_buddy_block **roots;
      76             : 
      77             :         /*
      78             :          * Anything from here is public, and remains static for the lifetime of
      79             :          * the mm. Everything above is considered do-not-touch.
      80             :          */
      81             :         unsigned int n_roots;
      82             :         unsigned int max_order;
      83             : 
      84             :         /* Must be at least PAGE_SIZE */
      85             :         u64 chunk_size;
      86             :         u64 size;
      87             :         u64 avail;
      88             : };
      89             : 
      90             : static inline u64
      91             : drm_buddy_block_offset(struct drm_buddy_block *block)
      92             : {
      93       70067 :         return block->header & DRM_BUDDY_HEADER_OFFSET;
      94             : }
      95             : 
      96             : static inline unsigned int
      97             : drm_buddy_block_order(struct drm_buddy_block *block)
      98             : {
      99      111652 :         return block->header & DRM_BUDDY_HEADER_ORDER;
     100             : }
     101             : 
     102             : static inline unsigned int
     103             : drm_buddy_block_state(struct drm_buddy_block *block)
     104             : {
     105       80441 :         return block->header & DRM_BUDDY_HEADER_STATE;
     106             : }
     107             : 
     108             : static inline bool
     109             : drm_buddy_block_is_allocated(struct drm_buddy_block *block)
     110             : {
     111       21001 :         return drm_buddy_block_state(block) == DRM_BUDDY_ALLOCATED;
     112             : }
     113             : 
     114             : static inline bool
     115             : drm_buddy_block_is_free(struct drm_buddy_block *block)
     116             : {
     117       20106 :         return drm_buddy_block_state(block) == DRM_BUDDY_FREE;
     118             : }
     119             : 
     120             : static inline bool
     121             : drm_buddy_block_is_split(struct drm_buddy_block *block)
     122             : {
     123         817 :         return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT;
     124             : }
     125             : 
     126             : static inline u64
     127             : drm_buddy_block_size(struct drm_buddy *mm,
     128             :                      struct drm_buddy_block *block)
     129             : {
     130      124580 :         return mm->chunk_size << drm_buddy_block_order(block);
     131             : }
     132             : 
     133             : int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size);
     134             : 
     135             : void drm_buddy_fini(struct drm_buddy *mm);
     136             : 
     137             : struct drm_buddy_block *
     138             : drm_get_buddy(struct drm_buddy_block *block);
     139             : 
     140             : int drm_buddy_alloc_blocks(struct drm_buddy *mm,
     141             :                            u64 start, u64 end, u64 size,
     142             :                            u64 min_page_size,
     143             :                            struct list_head *blocks,
     144             :                            unsigned long flags);
     145             : 
     146             : int drm_buddy_block_trim(struct drm_buddy *mm,
     147             :                          u64 new_size,
     148             :                          struct list_head *blocks);
     149             : 
     150             : void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block);
     151             : 
     152             : void drm_buddy_free_list(struct drm_buddy *mm, struct list_head *objects);
     153             : 
     154             : void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p);
     155             : void drm_buddy_block_print(struct drm_buddy *mm,
     156             :                            struct drm_buddy_block *block,
     157             :                            struct drm_printer *p);
     158             : 
     159             : #endif