From patchwork Fri Nov 19 15:58:04 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?b?TWljaGHDheKAmiBOYXphcmV3aWN6?= X-Patchwork-Id: 340341 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by demeter1.kernel.org (8.14.4/8.14.3) with ESMTP id oAJG392J030106 for ; Fri, 19 Nov 2010 16:03:10 GMT Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755042Ab0KSQBi (ORCPT ); Fri, 19 Nov 2010 11:01:38 -0500 Received: from mailout2.w1.samsung.com ([210.118.77.12]:25566 "EHLO mailout2.w1.samsung.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755354Ab0KSP62 (ORCPT ); Fri, 19 Nov 2010 10:58:28 -0500 Received: from eu_spt1 (mailout2.w1.samsung.com [210.118.77.12]) by mailout2.w1.samsung.com (iPlanet Messaging Server 5.2 Patch 2 (built Jul 14 2004)) with ESMTP id <0LC500GIH31EPH@mailout2.w1.samsung.com>; Fri, 19 Nov 2010 15:58:26 +0000 (GMT) Received: from linux.samsung.com ([106.116.38.10]) by spt1.w1.samsung.com (iPlanet Messaging Server 5.2 Patch 2 (built Jul 14 2004)) with ESMTPA id <0LC50012X31C14@spt1.w1.samsung.com>; Fri, 19 Nov 2010 15:58:26 +0000 (GMT) Received: from pikus.digital.local (unknown [106.116.48.169]) by linux.samsung.com (Postfix) with ESMTP id 1F55E2700EE; Fri, 19 Nov 2010 16:58:23 +0100 (CET) Date: Fri, 19 Nov 2010 16:58:04 +0100 From: Michal Nazarewicz Subject: [RFCv6 06/13] mm: cma: Best-fit algorithm added In-reply-to: To: mina86@mina86.com Cc: Andrew Morton , Ankita Garg , Bryan Huntsman , Daniel Walker , FUJITA Tomonori , Hans Verkuil , Johan Mossberg , Jonathan Corbet , KAMEZAWA Hiroyuki , Konrad Rzeszutek Wilk , Marcus LORENTZON , Marek Szyprowski , Mark Brown , Mel Gorman , Pawel Osciak , Russell King , Vaidyanathan Srinivasan , Zach Pfeffer , dipankar@in.ibm.com, linux-arm-kernel@lists.infradead.org, linux-kernel@vger.kernel.org, linux-media@vger.kernel.org, linux-mm@kvack.org Message-id: MIME-version: 1.0 X-Mailer: git-send-email 1.7.2.3 Content-type: TEXT/PLAIN Content-transfer-encoding: 7BIT References: Sender: linux-media-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-media@vger.kernel.org X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-4.2.3 (demeter1.kernel.org [140.211.167.41]); Fri, 19 Nov 2010 16:03:10 +0000 (UTC) diff --git a/mm/Kconfig b/mm/Kconfig index a5480ea..5ad2471 100644 --- a/mm/Kconfig +++ b/mm/Kconfig @@ -332,10 +332,13 @@ config CLEANCACHE If unsure, say Y to enable cleancache +config CMA_HAS_ALLOCATOR + bool + config CMA bool "Contiguous Memory Allocator framework" # Currently there is only one allocator so force it on - select CMA_GENERIC_ALLOCATOR + select CMA_GENERIC_ALLOCATOR if !CMA_HAS_ALLOCATOR help This enables the Contiguous Memory Allocator framework which allows drivers to allocate big physically-contiguous blocks of @@ -391,3 +394,14 @@ config CMA_GENERIC_ALLOCATOR implementations: the first-fit, bitmap-based algorithm or a best-fit, red-black tree-based algorithm. The algorithm can be changed under "Library routines". + +config CMA_BEST_FIT + bool "CMA best-fit allocator" + depends on CMA + select CMA_HAS_ALLOCATOR + help + This is a best-fit algorithm running in O(n log n) time where + n is the number of existing holes (which is never greater then + the number of allocated regions and usually much smaller). It + allocates area from the smallest hole that is big enough for + allocation in question. diff --git a/mm/Makefile b/mm/Makefile index c6a84f1..2cb2569 100644 --- a/mm/Makefile +++ b/mm/Makefile @@ -44,3 +44,4 @@ obj-$(CONFIG_DEBUG_KMEMLEAK) += kmemleak.o obj-$(CONFIG_DEBUG_KMEMLEAK_TEST) += kmemleak-test.o obj-$(CONFIG_CLEANCACHE) += cleancache.o obj-$(CONFIG_CMA) += cma.o +obj-$(CONFIG_CMA_BEST_FIT) += cma-best-fit.o diff --git a/mm/cma-best-fit.c b/mm/cma-best-fit.c new file mode 100644 index 0000000..5ed1168 --- /dev/null +++ b/mm/cma-best-fit.c @@ -0,0 +1,372 @@ +/* + * Contiguous Memory Allocator framework: Best Fit allocator + * Copyright (c) 2010 by Samsung Electronics. + * Written by Michal Nazarewicz (m.nazarewicz@samsung.com) + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation; either version 2 of the + * License or (at your optional) any later version of the license. + */ + +#define pr_fmt(fmt) "cma: bf: " fmt + +#ifdef CONFIG_CMA_DEBUG +# define DEBUG +#endif + +#include /* Error numbers */ +#include /* kmalloc() */ + +#include /* CMA structures */ + + +/************************* Data Types *************************/ + +struct cma_bf_node { + unsigned long v; + struct rb_node n; +}; + +union cma_bf_item { + struct cma chunk; + struct { + struct cma_bf_node start, size; + }; +}; + +struct cma_bf_private { + struct rb_root by_start_root; + struct rb_root by_size_root; + bool warned; +}; + + +/************************* Basic Tree Manipulation *************************/ + +static int cma_bf_node_add(struct cma_bf_node *node, struct rb_root *root, + bool unique) +{ + struct rb_node **link = &root->rb_node, *parent = NULL; + const unsigned long v = node->v; + + while (*link) { + struct cma_bf_node *n; + parent = *link; + n = rb_entry(parent, struct cma_bf_node, n); + + if (unlikely(unique && v == n->v)) + return -EBUSY; + + link = v <= n->v ? &parent->rb_left : &parent->rb_right; + } + + rb_link_node(&node->n, parent, link); + rb_insert_color(&node->n, root); + + return 0; +} + +static void cma_bf_node_del(struct cma_bf_node *node, struct rb_root *root) +{ + rb_erase(&node->n, root); +} + +static int cma_bf_item_add_by_start(union cma_bf_item *item, + struct cma_bf_private *prv) +{ + int ret = cma_bf_node_add(&item->start, &prv->by_start_root, true); + if (WARN_ON(ret && !prv->warned)) + prv->warned = true; + return ret; +} + +static void cma_bf_item_del_by_start(union cma_bf_item *item, + struct cma_bf_private *prv) +{ + cma_bf_node_del(&item->start, &prv->by_start_root); +} + +static void cma_bf_item_add_by_size(union cma_bf_item *item, + struct cma_bf_private *prv) +{ + cma_bf_node_add(&item->size, &prv->by_size_root, false); +} + +static void cma_bf_item_del_by_size(union cma_bf_item *item, + struct cma_bf_private *prv) +{ + cma_bf_node_del(&item->size, &prv->by_size_root); +} + + +/************************* Device API *************************/ + +static int cma_bf_init(struct cma_region *reg) +{ + struct cma_bf_private *prv; + union cma_bf_item *item; + + prv = kzalloc(sizeof *prv, GFP_KERNEL); + if (unlikely(!prv)) + return -ENOMEM; + + item = kzalloc(sizeof *item, GFP_KERNEL); + if (unlikely(!item)) { + kfree(prv); + return -ENOMEM; + } + + item->start.v = reg->start; + item->size.v = reg->size; + + rb_root_init(&prv->by_start_root, &item->start.n); + rb_root_init(&prv->by_size_root, &item->size.n); + prv->warned = false; + + reg->private_data = prv; + return 0; +} + +static void cma_bf_cleanup(struct cma_region *reg) +{ + struct cma_bf_private *prv = reg->private_data; + union cma_bf_item *item = + rb_entry(prv->by_start_root.rb_node, + union cma_bf_item, start.n); + + /* There should be only one item. */ + WARN_ON(!prv->warned && + (!item || + item->start.n.rb_left || item->start.n.rb_right || + item->size.n.rb_left || item->size.n.rb_right)); + + kfree(item); + kfree(prv); +} + +struct cma *cma_bf_alloc(struct cma_region *reg, + size_t size, unsigned long alignment) +{ + struct cma_bf_private *prv = reg->private_data; + struct rb_node *node = prv->by_size_root.rb_node; + union cma_bf_item *hole = NULL, *item; + unsigned long start; + int ret; + + /* First find hole that is large enough */ + while (node) { + union cma_bf_item *item = + rb_entry(node, union cma_bf_item, size.n); + + if (item->size.v < size) { + node = node->rb_right; + } else if (item->size.v >= size) { + node = node->rb_left; + hole = item; + } + } + if (!hole) + return ERR_PTR(-ENOMEM); + + /* Now look for items which can satisfy alignment requirements */ + for (;;) { + unsigned long end = hole->start.v + hole->size.v; + start = ALIGN(hole->start.v, alignment); + if (start < end && end - start >= size) + break; + + node = rb_next(node); + if (!node) + return ERR_PTR(-ENOMEM); + + hole = rb_entry(node, union cma_bf_item, size.n); + } + + /* And finally, take part of the hole */ + + /* + * There are three cases: + * 1. the chunk takes the whole hole, + * 2. the chunk is at the beginning or at the end of the hole, or + * 3. the chunk is in the middle of the hole. + */ + + /* Case 1, the whole hole */ + if (size == hole->size.v) { + ret = __cma_grab(reg, start, size); + if (ret) + return ERR_PTR(ret); + + cma_bf_item_del_by_start(hole, prv); + cma_bf_item_del_by_size(hole, prv); + + hole->chunk.phys = start; + hole->chunk.size = size; + return &hole->chunk; + } + + /* Allocate (so we can test early if ther's enough memory) */ + item = kmalloc(sizeof *item, GFP_KERNEL); + if (unlikely(!item)) + return ERR_PTR(-ENOMEM); + + /* Case 3, in the middle */ + if (start != hole->start.v && + start + size != hole->start.v + hole->size.v) { + union cma_bf_item *tail; + + /* + * Space between the end of the chunk and the end of + * the region, ie. space left after the end of the + * chunk. If this is dividable by alignment we can + * move the chunk to the end of the hole. + */ + unsigned long left = + hole->start.v + hole->size.v - (start + size); + if ((left & (alignment - 1)) == 0) { + start += left; + /* And so, we have reduced problem to case 2. */ + goto case_2; + } + + /* + * We are going to add a hole at the end. This way, + * we will reduce the problem to case 2 -- the chunk + * will be at the end of a reduced hole. + */ + tail = kmalloc(sizeof *tail, GFP_KERNEL); + if (unlikely(!tail)) { + kfree(item); + return ERR_PTR(-ENOMEM); + } + + tail->start.v = start + size; + tail->size.v = + hole->start.v + hole->size.v - tail->start.v; + + if (cma_bf_item_add_by_start(tail, prv)) + /* + * Things are broken beyond repair... Abort + * inserting the hole but continue with the + * item. We will loose some memory but we're + * screwed anyway. + */ + kfree(tail); + else + cma_bf_item_add_by_size(tail, prv); + + /* + * It's important that we first insert the new hole in + * the tree sorted by size and later reduce the size + * of the old hole. We will update the position of + * the old hole in the rb tree in code that handles + * case 2. + */ + hole->size.v = tail->start.v - hole->start.v; + + /* Go to case 2 */ + } + + /* Case 2, at the beginning or at the end */ +case_2: + /* No need to update the tree; order preserved. */ + if (start == hole->start.v) + hole->start.v += size; + + /* Alter hole's size */ + hole->size.v -= size; + cma_bf_item_del_by_size(hole, prv); + cma_bf_item_add_by_size(hole, prv); + + item->chunk.phys = start; + item->chunk.size = size; + return &item->chunk; +} + +static void cma_bf_free(struct cma_chunk *chunk) +{ + struct cma_bf_private *prv = reg->private_data; + union cma_bf_item *prev; + struct rb_node *node; + int twice; + + { + unsigned long start = item->chunk.phys; + unsigned long size = item->chunk.size; + item->start.v = start; + item->size.v = size; + } + + /* Add new hole */ + if (cma_bf_item_add_by_start(item, prv)) { + /* + * We're screwed... Just free the item and forget + * about it. Things are broken beyond repair so no + * sense in trying to recover. + */ + kfree(item); + return; + } + + cma_bf_item_add_by_size(item, prv); + + /* Merge with prev or next sibling */ + twice = 2; + node = rb_prev(&item->start.n); + if (unlikely(!node)) + goto next; + prev = rb_entry(node, union cma_bf_item, start.n); + + for (;;) { + if (prev->start.v + prev->size.v == item->start.v) { + /* Remove previous hole from trees */ + cma_bf_item_del_by_start(prev, prv); + cma_bf_item_del_by_size(prev, prv); + + /* Alter this hole */ + item->start.v = prev->start.v; + item->size.v += prev->size.v; + cma_bf_item_del_by_size(item, prv); + cma_bf_item_del_by_size(item, prv); + /* + * No need to update the by start trees as we + * do not break sequence order. + */ + + /* Free prev hole */ + kfree(prev); + } + +next: + if (!--twice) + break; + + node = rb_next(&item->start.n); + if (unlikely(!node)) + break; + prev = item; + item = rb_entry(node, union cma_bf_item, start.n); + } +} + +{ + __cma_ungrab(chunk->reg, chunk->phys, chunk->size); + __cma_bf_free(chunk->reg, + container_of(chunk, union cma_bf_item, chunk)); +} + +/************************* Register *************************/ + +static int cma_bf_module_init(void) +{ + static struct cma_allocator alloc = { + .name = "bf", + .init = cma_bf_init, + .cleanup = cma_bf_cleanup, + .alloc = cma_bf_alloc, + .free = cma_bf_free, + }; + return cma_allocator_register(&alloc); +} +module_init(cma_bf_module_init);