Signed-off-by: Lauri Kasanen cand@gmx.com --- drivers/gpu/drm/ttm/Makefile | 2 +- drivers/gpu/drm/ttm/ttm_priority.c | 152 +++++++++++++++++++++++++++++++++++++ include/drm/ttm/ttm_priority.h | 90 ++++++++++++++++++++++ 3 files changed, 243 insertions(+), 1 deletion(-) create mode 100644 drivers/gpu/drm/ttm/ttm_priority.c create mode 100644 include/drm/ttm/ttm_priority.h
diff --git a/drivers/gpu/drm/ttm/Makefile b/drivers/gpu/drm/ttm/Makefile index b433b9f..4411599 100644 --- a/drivers/gpu/drm/ttm/Makefile +++ b/drivers/gpu/drm/ttm/Makefile @@ -5,6 +5,6 @@ ccflags-y := -Iinclude/drm ttm-y := ttm_agp_backend.o ttm_memory.o ttm_tt.o ttm_bo.o \ ttm_bo_util.o ttm_bo_vm.o ttm_module.o \ ttm_object.o ttm_lock.o ttm_execbuf_util.o ttm_page_alloc.o \ - ttm_bo_manager.o ttm_page_alloc_dma.o + ttm_bo_manager.o ttm_page_alloc_dma.o ttm_priority.o
obj-$(CONFIG_DRM_TTM) += ttm.o diff --git a/drivers/gpu/drm/ttm/ttm_priority.c b/drivers/gpu/drm/ttm/ttm_priority.c new file mode 100644 index 0000000..a7cf8d1 --- /dev/null +++ b/drivers/gpu/drm/ttm/ttm_priority.c @@ -0,0 +1,152 @@ +/************************************************************************** + * + * Copyright (c) 2014 Lauri Kasanen + * 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. + * + **************************************************************************/ + + +#include <drm/ttm/ttm_priority.h> +#include <linux/bug.h> + +static void ttm_prio_insert_rb(struct rb_root * const root, + struct ttm_pqueue_entry * const data, + struct rb_node *parent, + struct rb_node **where) +{ + BUG_ON(!where || (!parent && root->rb_node)); + + rb_link_node(&data->node, parent, where); + rb_insert_color(&data->node, root); +} + +static struct ttm_pqueue_entry *ttm_prio_search_rb(struct rb_root *root, + u64 score, + struct rb_node **parent, + struct rb_node ***where) +{ + struct rb_node **new = &root->rb_node; + + while (*new) { + struct ttm_pqueue_entry *this = container_of(*new, + struct ttm_pqueue_entry, + node); + + *parent = *new; + + if (score < this->score) + new = &((*new)->rb_left); + else if (score > this->score) + new = &((*new)->rb_right); + else + return this; + + BUG_ON(*parent == *new); + } + + *where = new; + + return NULL; +} + +void ttm_prio_add(struct ttm_pqueue * const queue, + struct ttm_pqueue_entry * const entry) +{ + struct rb_root * const tree = &queue->tree; + struct rb_node **place = NULL, *parent = NULL; + struct ttm_pqueue_entry *test; + + if (ttm_prio_is_queued(entry)) + ttm_prio_remove(queue, entry); + + test = ttm_prio_search_rb(tree, entry->score, &parent, &place); + + if (!test) + ttm_prio_insert_rb(tree, entry, parent, place); + else + list_add_tail(&entry->list, &test->list); +} + +struct ttm_pqueue_entry *ttm_prio_query_lowest(const struct ttm_pqueue * const queue) +{ + const struct rb_root * const root = &queue->tree; + struct rb_node *node; + + node = rb_first(root); + if (!node) + return NULL; + + return container_of(node, struct ttm_pqueue_entry, node); +} + +void ttm_prio_remove(struct ttm_pqueue * const queue, + struct ttm_pqueue_entry * const entry) +{ + struct rb_root * const tree = &queue->tree; + + if (list_empty(&entry->list)) { + rb_erase(&entry->node, tree); + RB_CLEAR_NODE(&entry->node); + } else { + struct ttm_pqueue_entry *next = list_first_entry(&entry->list, + struct ttm_pqueue_entry, + list); + if (RB_EMPTY_NODE(&next->node) && !RB_EMPTY_NODE(&entry->node)) + rb_replace_node(&entry->node, &next->node, tree); + + list_del_init(&entry->list); + RB_CLEAR_NODE(&entry->node); + } +} + +void ttm_prio_init_entry(struct ttm_pqueue_entry * const entry) +{ + entry->score = 0; + RB_CLEAR_NODE(&entry->node); + INIT_LIST_HEAD(&entry->list); +} + +struct ttm_pqueue_entry *ttm_prio_query_next(struct ttm_pqueue_entry * const entry) +{ + struct ttm_pqueue_entry *next = list_next_entry(entry, list); + struct rb_node *node; + + if (list_empty(&entry->list)) { + node = rb_next(&entry->node); + if (!node) + return NULL; + return container_of(node, struct ttm_pqueue_entry, node); + } else if (!RB_EMPTY_NODE(&next->node)) { + node = rb_next(&next->node); + if (!node) + return NULL; + return container_of(node, struct ttm_pqueue_entry, node); + } else { + return next; + } +} + +int ttm_prio_is_queued(const struct ttm_pqueue_entry * const entry) +{ + return !(list_empty(&entry->list) && RB_EMPTY_NODE(&entry->node)); +} diff --git a/include/drm/ttm/ttm_priority.h b/include/drm/ttm/ttm_priority.h new file mode 100644 index 0000000..c3390cd --- /dev/null +++ b/include/drm/ttm/ttm_priority.h @@ -0,0 +1,90 @@ +/************************************************************************** + * + * Copyright (c) 2014 Lauri Kasanen + * 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. + * + **************************************************************************/ + +#ifndef TTM_PRIORITY_H +#define TTM_PRIORITY_H + +#include <linux/list.h> +#include <linux/rbtree.h> +#include <linux/types.h> + +/** + * struct ttm_pqueue - zero-initialize it when allocating + */ + +struct ttm_pqueue { + struct rb_root tree; +}; + +struct ttm_pqueue_entry { + u64 score; + struct rb_node node; + struct list_head list; +}; + +void ttm_prio_init_entry(struct ttm_pqueue_entry * const entry); + +/** + * ttm_prio_add - add this entry to the priority queue. + * Set the score before calling this. + */ + +void ttm_prio_add(struct ttm_pqueue * const queue, + struct ttm_pqueue_entry * const entry); + +/** + * ttm_prio_query_lowest - return the entry with the lowest score. + * + * Returns NULL if there are none. + */ + +struct ttm_pqueue_entry *ttm_prio_query_lowest(const struct ttm_pqueue * const queue); + +/** + * ttm_prio_remove - remove a previously queried entry from the queue. + */ + +void ttm_prio_remove(struct ttm_pqueue * const queue, + struct ttm_pqueue_entry * const entry); + +/** + * ttm_prio_query_next - walk the queue + * + * Returns NULL if there is no next entry. + */ + +struct ttm_pqueue_entry *ttm_prio_query_next(struct ttm_pqueue_entry * const entry); + +/** + * ttm_prio_is_queued - test if an entry is in the queue. + * + * Returns 1 if it is, 0 if not. + */ + +int ttm_prio_is_queued(const struct ttm_pqueue_entry * const entry); + +#endif