From patchwork Tue May 18 21:11:49 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Daniel Vetter X-Patchwork-Id: 100625 Received: from gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) by demeter.kernel.org (8.14.3/8.14.3) with ESMTP id o4ILKQiw012485 for ; Tue, 18 May 2010 21:21:01 GMT Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 9DEDB9EC8F for ; Tue, 18 May 2010 14:20:26 -0700 (PDT) X-Original-To: intel-gfx@lists.freedesktop.org Delivered-To: intel-gfx@lists.freedesktop.org Received: from mail.ffwll.ch (cable-static-49-187.intergga.ch [157.161.49.187]) by gabe.freedesktop.org (Postfix) with ESMTP id 507429E890; Tue, 18 May 2010 14:11:11 -0700 (PDT) Received: by mail.ffwll.ch (Postfix, from userid 1000) id 2AC5020C20F; Tue, 18 May 2010 23:12:00 +0200 (CEST) X-Spam-ASN: X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on orange.ffwll.ch X-Spam-Level: X-Spam-Hammy: 0.000-+--H*Ad:U*dri-devel, 0.000-+--HCc:D*freedesktop.org, 0.000-+--HCc:D*lists.freedesktop.org X-Spam-Status: No, score=-4.4 required=6.0 tests=ALL_TRUSTED,BAYES_00 autolearn=ham version=3.2.5 X-Spam-Spammy: 0.993-1--abused, 0.993-1--nonzero, 0.987-1--539 Received: from biene (unknown [192.168.23.129]) by mail.ffwll.ch (Postfix) with ESMTP id 2D96920C23A; Tue, 18 May 2010 23:11:36 +0200 (CEST) Received: from daniel by biene with local (Exim 4.71) (envelope-from ) id 1OEU4z-00011X-PM; Tue, 18 May 2010 23:11:57 +0200 From: Daniel Vetter To: intel-gfx@lists.freedesktop.org Date: Tue, 18 May 2010 23:11:49 +0200 Message-Id: <1274217111-3882-8-git-send-email-daniel.vetter@ffwll.ch> X-Mailer: git-send-email 1.7.1 In-Reply-To: <1274217111-3882-1-git-send-email-daniel.vetter@ffwll.ch> References: <1274217111-3882-1-git-send-email-daniel.vetter@ffwll.ch> Cc: Daniel Vetter , dri-devel@lists.freedesktop.org Subject: [Intel-gfx] [PATCH 7/9] drm: implement helper functions for scanning lru list X-BeenThere: intel-gfx@lists.freedesktop.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: Intel graphics driver community testing & development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: intel-gfx-bounces+patchwork-intel-gfx=patchwork.kernel.org@lists.freedesktop.org Errors-To: intel-gfx-bounces+patchwork-intel-gfx=patchwork.kernel.org@lists.freedesktop.org X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-4.2.3 (demeter.kernel.org [140.211.167.41]); Tue, 18 May 2010 21:21:02 +0000 (UTC) diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index fd86a6c..da99edc 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -53,9 +53,9 @@ static struct drm_mm_node *drm_mm_kmalloc(struct drm_mm *mm, int atomic) struct drm_mm_node *child; if (atomic) - child = kmalloc(sizeof(*child), GFP_ATOMIC); + child = kzalloc(sizeof(*child), GFP_ATOMIC); else - child = kmalloc(sizeof(*child), GFP_KERNEL); + child = kzalloc(sizeof(*child), GFP_KERNEL); if (unlikely(child == NULL)) { spin_lock(&mm->unused_lock); @@ -85,7 +85,7 @@ int drm_mm_pre_get(struct drm_mm *mm) spin_lock(&mm->unused_lock); while (mm->num_unused < MM_UNUSED_TARGET) { spin_unlock(&mm->unused_lock); - node = kmalloc(sizeof(*node), GFP_KERNEL); + node = kzalloc(sizeof(*node), GFP_KERNEL); spin_lock(&mm->unused_lock); if (unlikely(node == NULL)) { @@ -134,7 +134,6 @@ static struct drm_mm_node *drm_mm_split_at_start(struct drm_mm_node *parent, INIT_LIST_HEAD(&child->free_stack); - child->free = 0; child->size = size; child->start = parent->start; child->mm = parent->mm; @@ -235,6 +234,9 @@ void drm_mm_put_block(struct drm_mm_node *cur) int merged = 0; + BUG_ON(cur->scanned_block || cur->scanned_prev_free + || cur->scanned_next_free); + if (cur_head->prev != root_head) { prev_node = list_entry(cur_head->prev, struct drm_mm_node, node_list); @@ -312,6 +314,8 @@ struct drm_mm_node *drm_mm_search_free(const struct drm_mm *mm, struct drm_mm_node *best; unsigned long best_size; + BUG_ON(mm->scanned_blocks); + best = NULL; best_size = ~0UL; @@ -343,6 +347,8 @@ struct drm_mm_node *drm_mm_search_free_in_range(const struct drm_mm *mm, struct drm_mm_node *best; unsigned long best_size; + BUG_ON(mm->scanned_blocks); + best = NULL; best_size = ~0UL; @@ -366,6 +372,158 @@ struct drm_mm_node *drm_mm_search_free_in_range(const struct drm_mm *mm, } EXPORT_SYMBOL(drm_mm_search_free_in_range); +/** + * Initializa lru scanning. + * + * This simply sets up the scanning routines with the parameters for the desired + * hole. + * + * Warning: As long as the scan list is non-empty, no other operations than + * adding/removing nodes to/from the scan list are allowed. + */ +void drm_mm_init_scan(struct drm_mm *mm, unsigned long size, + unsigned alignment) +{ + mm->scan_alignment = alignment; + mm->scan_size = size; + mm->scanned_blocks = 0; + mm->scan_hit_start = 0; + mm->scan_hit_size = 0; +} +EXPORT_SYMBOL(drm_mm_init_scan); + +/** + * Add a node to the scan list that might be freed to make space for the desired + * hole. + * + * Returns non-zero, if a hole has been found, zero otherwise. + */ +int drm_mm_scan_add_block(struct drm_mm_node *node) +{ + struct drm_mm *mm = node->mm; + struct list_head *prev_free, *next_free; + struct drm_mm_node *prev_node, *next_node; + + mm->scanned_blocks++; + + prev_free = next_free = NULL; + + BUG_ON(node->free); + node->scanned_block = 1; + node->free = 1; + + if (node->node_list.prev != &mm->node_list) { + prev_node = list_entry(node->node_list.prev, struct drm_mm_node, + node_list); + + if (prev_node->free) { + list_del(&prev_node->node_list); + + node->start = prev_node->start; + node->size += prev_node->size; + + prev_node->scanned_prev_free = 1; + + prev_free = &prev_node->free_stack; + } + } + + if (node->node_list.next != &mm->node_list) { + next_node = list_entry(node->node_list.next, struct drm_mm_node, + node_list); + + if (next_node->free) { + list_del(&next_node->node_list); + + node->size += next_node->size; + + next_node->scanned_next_free = 1; + + next_free = &next_node->free_stack; + } + } + + /* The free_stack list is not used for allocated objects, so these two + * pointers can be abused (as long as no allocations in this memory + * manager happens). */ + node->free_stack.prev = prev_free; + node->free_stack.next = next_free; + + if (check_free_mm_node(node, mm->scan_size, mm->scan_alignment)) { + mm->scan_hit_start = node->start; + mm->scan_hit_size = node->size; + + return 1; + } + + return 0; +} +EXPORT_SYMBOL(drm_mm_scan_add_block); + +/** + * Remove a node from the scan list. + * + * Nodes _must_ be removed in the exact same order from the scan list as they + * have been added, otherwise the internal state of the memory manager will be + * corrupted. + * + * When the scan list is empty, the selected memory nodes can be freed. An + * immediatly following drm_mm_search_free with best_match = 0 will then return + * the just freed block (because its at the top of the free_stack list). + * + * Returns one if this block should be evicted, zero otherwise. Will always + * return zero when no hole has been found. + */ +int drm_mm_scan_remove_block(struct drm_mm_node *node) +{ + struct drm_mm *mm = node->mm; + struct drm_mm_node *prev_node, *next_node; + + mm->scanned_blocks--; + + BUG_ON(!node->scanned_block); + node->scanned_block = 0; + node->free = 0; + + prev_node = list_entry(node->free_stack.prev, struct drm_mm_node, + free_stack); + next_node = list_entry(node->free_stack.next, struct drm_mm_node, + free_stack); + + if (prev_node) { + BUG_ON(!prev_node->scanned_prev_free); + prev_node->scanned_prev_free = 0; + + list_add_tail(&prev_node->node_list, &node->node_list); + + node->start = prev_node->start + prev_node->size; + node->size -= prev_node->size; + } + + if (next_node) { + BUG_ON(!next_node->scanned_next_free); + next_node->scanned_next_free = 0; + + list_add(&next_node->node_list, &node->node_list); + + node->size -= next_node->size; + } + + INIT_LIST_HEAD(&node->free_stack); + + /* Only need to check for containement because start&size for the + * complete resulting free block (not just the desired part) is + * stored. */ + if (node->start >= mm->scan_hit_start && + node->start + node->size + <= mm->scan_hit_start + mm->scan_hit_size) { + return 1; + } + + return 0; +} +EXPORT_SYMBOL(drm_mm_scan_remove_block); + int drm_mm_clean(struct drm_mm * mm) { struct list_head *head = &mm->node_list; @@ -380,6 +538,7 @@ int drm_mm_init(struct drm_mm * mm, unsigned long start, unsigned long size) INIT_LIST_HEAD(&mm->free_stack); INIT_LIST_HEAD(&mm->unused_nodes); mm->num_unused = 0; + mm->scanned_blocks = 0; spin_lock_init(&mm->unused_lock); return drm_mm_create_tail_node(mm, start, size, 0); diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h index e8740cc..bf01531 100644 --- a/include/drm/drm_mm.h +++ b/include/drm/drm_mm.h @@ -44,7 +44,10 @@ struct drm_mm_node { struct list_head free_stack; struct list_head node_list; - int free; + unsigned free : 1; + unsigned scanned_block : 1; + unsigned scanned_prev_free : 1; + unsigned scanned_next_free : 1; unsigned long start; unsigned long size; struct drm_mm *mm; @@ -59,6 +62,11 @@ struct drm_mm { struct list_head unused_nodes; int num_unused; spinlock_t unused_lock; + unsigned scan_alignment; + unsigned long scan_size; + unsigned long scan_hit_start; + unsigned scan_hit_size; + unsigned scanned_blocks; }; /* @@ -135,6 +143,11 @@ static inline struct drm_mm *drm_get_mm(struct drm_mm_node *block) return block->mm; } +void drm_mm_init_scan(struct drm_mm *mm, unsigned long size, + unsigned alignment); +int drm_mm_scan_add_block(struct drm_mm_node *node); +int drm_mm_scan_remove_block(struct drm_mm_node *node); + extern void drm_mm_debug_table(struct drm_mm *mm, const char *prefix); #ifdef CONFIG_DEBUG_FS int drm_mm_dump_table(struct seq_file *m, struct drm_mm *mm);