From patchwork Fri Apr 4 13:52:55 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lauri Kasanen X-Patchwork-Id: 3938471 Return-Path: X-Original-To: patchwork-dri-devel@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.19.201]) by patchwork2.web.kernel.org (Postfix) with ESMTP id 690B0BFF02 for ; Fri, 4 Apr 2014 13:52:25 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 49A2020396 for ; Fri, 4 Apr 2014 13:52:24 +0000 (UTC) Received: from gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) by mail.kernel.org (Postfix) with ESMTP id 12A2A2038D for ; Fri, 4 Apr 2014 13:52:23 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 646DC6ED86; Fri, 4 Apr 2014 06:52:22 -0700 (PDT) X-Original-To: dri-devel@lists.freedesktop.org Delivered-To: dri-devel@lists.freedesktop.org Received: from mout.gmx.net (mout.gmx.net [212.227.17.22]) by gabe.freedesktop.org (Postfix) with ESMTP id AFCD66ED86 for ; Fri, 4 Apr 2014 06:52:20 -0700 (PDT) Received: from Valinor ([84.248.177.169]) by mail.gmx.com (mrgmx103) with ESMTPA (Nemesis) id 0LvlWS-1X6FKR22fM-017S0F for ; Fri, 04 Apr 2014 15:52:19 +0200 Date: Fri, 4 Apr 2014 16:52:55 +0300 From: Lauri Kasanen To: dri-devel@lists.freedesktop.org Subject: [RFC 1/3] drm/ttm: Add a priority queue Message-Id: <20140404165255.19190bc8.cand@gmx.com> X-Mailer: Sylpheed 3.1.4 (GTK+ 2.18.6; x86_64-unknown-linux-gnu) Mime-Version: 1.0 X-Provags-ID: V03:K0:wUmTu0LeEJqRSHqnPdJ+VGh6qt8DBOzAK1nGs+cCb9N48jcAwwR YRnMbzu4izocNYLxE1h/LDeVNHovmB6dlwUD+Z00r86rU3/IxcWhcvk1B+g1aVCdjRbec6c wOdfXhecybYuovtq3+jSQkqZL2CiLNudLN+UyZKisMIpbDuMfrG8ocPoZ15M/82cJTm/5z7 DkBmk0s6KOzVOpoO4lh8Q== X-BeenThere: dri-devel@lists.freedesktop.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Direct Rendering Infrastructure - Development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dri-devel-bounces@lists.freedesktop.org Sender: "dri-devel" X-Spam-Status: No, score=-4.8 required=5.0 tests=BAYES_00,FREEMAIL_FROM, RCVD_IN_DNSWL_MED, RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Signed-off-by: Lauri Kasanen --- 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 +#include + +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 +#include +#include + +/** + * 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