drm_mm.h

Go to the documentation of this file.

/**************************************************************************
 *
 * Copyright 2006-2008 Tungsten Graphics, Inc., Cedar Park, TX. USA.
 * Copyright 2016 Intel Corporation
 * All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sub license, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice (including the
 * next paragraph) shall be included in all copies or substantial portions
 * of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
 * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
 * USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 *
 **************************************************************************/
/*
 * Authors:
 * Thomas Hellstrom <thomas-at-tungstengraphics-dot-com>
 */
 
#ifndef _DRM_MM_H_
#define _DRM_MM_H_
 
/*
 * Generic range manager structs
 */
#include <linux/bug.h>
#include <linux/rbtree.h>
#include <linux/limits.h>
#include <linux/mm_types.h>
#include <linux/list.h>
#include <linux/spinlock.h>
#include <linux/bitops.h>   /* __ffs() and __set_bit() -- drm_mm.c:1887 and
                 * :478 spell both, and mainline's drm_mm.c
                 * gets them without naming this include: its
                 * slab.h/mm_types.h chain reaches bitops.h,
                 * where DCL's are slimmer and do not. Left to
                 * the caller it is an implicit declaration,
                 * which compiles as a warning and then fails
                 * to link. */
#ifdef CONFIG_DRM_DEBUG_MM
#include <linux/stackdepot.h>
#endif
#include <linux/types.h>
 
struct drm_printer;
 
#ifdef CONFIG_DRM_DEBUG_MM
#define DRM_MM_BUG_ON(expr) BUG_ON(expr)
#else
#define DRM_MM_BUG_ON(expr) BUILD_BUG_ON_INVALID(expr)
#endif
 
enum drm_mm_insert_mode {
    DRM_MM_INSERT_BEST = 0,
 
    DRM_MM_INSERT_LOW,
 
    DRM_MM_INSERT_HIGH,
 
    DRM_MM_INSERT_EVICT,
 
    DRM_MM_INSERT_ONCE = BIT(31),
 
    DRM_MM_INSERT_HIGHEST = DRM_MM_INSERT_HIGH | DRM_MM_INSERT_ONCE,
 
    DRM_MM_INSERT_LOWEST  = DRM_MM_INSERT_LOW | DRM_MM_INSERT_ONCE,
};
 
struct drm_mm_node {
    unsigned long color;
    u64 start;
    u64 size;
    /* private: */
    struct drm_mm *mm;
    struct list_head node_list;
    struct list_head hole_stack;
    struct rb_node rb;
    struct rb_node rb_hole_size;
    struct rb_node rb_hole_addr;
    u64 __subtree_last;
    u64 hole_size;
    u64 subtree_max_hole;
    unsigned long flags;
#define DRM_MM_NODE_ALLOCATED_BIT   0
#define DRM_MM_NODE_SCANNED_BIT     1
#ifdef CONFIG_DRM_DEBUG_MM
    depot_stack_handle_t stack;
#endif
};
 
struct drm_mm {
    void (*color_adjust)(const struct drm_mm_node *node,
                 unsigned long color,
                 u64 *start, u64 *end);
 
    /* private: */
    /* List of all memory nodes that immediately precede a free hole. */
    struct list_head hole_stack;
    /* head_node.node_list is the list of all memory nodes, ordered
     * according to the (increasing) start address of the memory node. */
    struct drm_mm_node head_node;
    /* Keep an interval_tree for fast lookup of drm_mm_nodes by address. */
    struct rb_root_cached interval_tree;
    struct rb_root_cached holes_size;
    struct rb_root holes_addr;
 
    unsigned long scan_active;
};
 
struct drm_mm_scan {
    /* private: */
    struct drm_mm *mm;
 
    u64 size;
    u64 alignment;
    u64 remainder_mask;
 
    u64 range_start;
    u64 range_end;
 
    u64 hit_start;
    u64 hit_end;
 
    unsigned long color;
    enum drm_mm_insert_mode mode;
};
 
static inline bool drm_mm_node_allocated(const struct drm_mm_node *node)
{
    return test_bit(DRM_MM_NODE_ALLOCATED_BIT, &node->flags);
}
 
static inline bool drm_mm_initialized(const struct drm_mm *mm)
{
    return READ_ONCE(mm->hole_stack.next);
}
 
static inline bool drm_mm_hole_follows(const struct drm_mm_node *node)
{
    return node->hole_size;
}
 
static inline u64 __drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
{
    return hole_node->start + hole_node->size;
}
 
static inline u64 drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
{
    DRM_MM_BUG_ON(!drm_mm_hole_follows(hole_node));
    return __drm_mm_hole_node_start(hole_node);
}
 
static inline u64 __drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
{
    return list_next_entry(hole_node, node_list)->start;
}
 
static inline u64 drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
{
    return __drm_mm_hole_node_end(hole_node);
}
 
#define drm_mm_nodes(mm) (&(mm)->head_node.node_list)
 
#define drm_mm_for_each_node(entry, mm) \
    list_for_each_entry(entry, drm_mm_nodes(mm), node_list)
 
#define drm_mm_for_each_node_safe(entry, next, mm) \
    list_for_each_entry_safe(entry, next, drm_mm_nodes(mm), node_list)
 
#define drm_mm_for_each_hole(pos, mm, hole_start, hole_end) \
    for (pos = list_first_entry(&(mm)->hole_stack, \
                    typeof(*pos), hole_stack); \
         &pos->hole_stack != &(mm)->hole_stack ? \
         hole_start = drm_mm_hole_node_start(pos), \
         hole_end = hole_start + pos->hole_size, \
         1 : 0; \
         pos = list_next_entry(pos, hole_stack))
 
/*
 * Basic range manager support (drm_mm.c)
 */
int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node);
int drm_mm_insert_node_in_range(struct drm_mm *mm,
                struct drm_mm_node *node,
                u64 size,
                u64 alignment,
                unsigned long color,
                u64 start,
                u64 end,
                enum drm_mm_insert_mode mode);
 
static inline int
drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node,
               u64 size, u64 alignment,
               unsigned long color,
               enum drm_mm_insert_mode mode)
{
    return drm_mm_insert_node_in_range(mm, node,
                       size, alignment, color,
                       0, U64_MAX, mode);
}
 
static inline int drm_mm_insert_node(struct drm_mm *mm,
                     struct drm_mm_node *node,
                     u64 size)
{
    return drm_mm_insert_node_generic(mm, node, size, 0, 0, 0);
}
 
void drm_mm_remove_node(struct drm_mm_node *node);
void drm_mm_init(struct drm_mm *mm, u64 start, u64 size);
void drm_mm_takedown(struct drm_mm *mm);
 
static inline bool drm_mm_clean(const struct drm_mm *mm)
{
    return list_empty(drm_mm_nodes(mm));
}
 
struct drm_mm_node *
__drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last);
 
#define drm_mm_for_each_node_in_range(node__, mm__, start__, end__) \
    for (node__ = __drm_mm_interval_first((mm__), (start__), (end__)-1); \
         node__->start < (end__);                   \
         node__ = list_next_entry(node__, node_list))
 
void drm_mm_scan_init_with_range(struct drm_mm_scan *scan,
                 struct drm_mm *mm,
                 u64 size, u64 alignment, unsigned long color,
                 u64 start, u64 end,
                 enum drm_mm_insert_mode mode);
 
static inline void drm_mm_scan_init(struct drm_mm_scan *scan,
                    struct drm_mm *mm,
                    u64 size,
                    u64 alignment,
                    unsigned long color,
                    enum drm_mm_insert_mode mode)
{
    drm_mm_scan_init_with_range(scan, mm,
                    size, alignment, color,
                    0, U64_MAX, mode);
}
 
bool drm_mm_scan_add_block(struct drm_mm_scan *scan,
               struct drm_mm_node *node);
bool drm_mm_scan_remove_block(struct drm_mm_scan *scan,
                  struct drm_mm_node *node);
struct drm_mm_node *drm_mm_scan_color_evict(struct drm_mm_scan *scan);
 
void drm_mm_print(const struct drm_mm *mm, struct drm_printer *p);
 
#endif