From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933614AbcLHBYh (ORCPT ); Wed, 7 Dec 2016 20:24:37 -0500 Received: from mail-wj0-f169.google.com ([209.85.210.169]:35647 "EHLO mail-wj0-f169.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932400AbcLHBYf (ORCPT ); Wed, 7 Dec 2016 20:24:35 -0500 From: Rasmus Villemoes To: Tejun Heo , Andrew Morton Cc: linux-kernel@vger.kernel.org, Lai Jiangshan , Jens Axboe , Greg Kroah-Hartman , Rasmus Villemoes Subject: [RFC 04/10] lib/tida.c: a very simple integer id allocator Date: Thu, 8 Dec 2016 02:22:59 +0100 Message-Id: <1481160187-9652-5-git-send-email-linux@rasmusvillemoes.dk> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1481160187-9652-1-git-send-email-linux@rasmusvillemoes.dk> References: <1481160187-9652-1-git-send-email-linux@rasmusvillemoes.dk> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org The idr-based id allocator ida has a rather large memory footprint (despite claims to the contrary). For example, on my laptop, each of the six idas associated to the workqueues uses more than 16 KB of memory (most of which sits unused in the embedded idr structure), even though _combined_ they have only handed out a little over 100 ids in their lifetime. That's about 1KB of overhead per id, which is rather far from "each id only occupies a bit". This introduces tida (t for tiny, trivial, whatever). Initially we only support allocating the smallest available id, but this can already replace many uses of ida throughout the tree. It shouldn't be that hard to implement e.g. tida_get_min() or tida_get_exact() which might make this capable of replacing more ida instances. Signed-off-by: Rasmus Villemoes --- include/linux/tida.h | 26 +++++++++++++ lib/Makefile | 2 +- lib/tida.c | 103 +++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 130 insertions(+), 1 deletion(-) create mode 100644 include/linux/tida.h create mode 100644 lib/tida.c diff --git a/include/linux/tida.h b/include/linux/tida.h new file mode 100644 index 000000000000..9aa3ad96a632 --- /dev/null +++ b/include/linux/tida.h @@ -0,0 +1,26 @@ +#ifndef __LINUX_TIDA_H__ +#define __LINUX_TIDA_H__ + +#include +#include + +struct tida { + unsigned long *bits; + unsigned long alloc; + spinlock_t lock; + int hint; +}; + +#define TIDA_INIT(name) \ + { .lock = __SPIN_LOCK_UNLOCKED(name.lock), } + +#define DEFINE_TIDA(name) struct tida name = TIDA_INIT(name) + +void tida_init(struct tida *tida); +void tida_destroy(struct tida *tida); + +int tida_get(struct tida *tida, gfp_t gfp); +void tida_put(struct tida *tida, int id); + + +#endif /* __LINUX_TIDA_H__ */ diff --git a/lib/Makefile b/lib/Makefile index 50144a3aeebd..e6f5b9896bbd 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -18,7 +18,7 @@ KCOV_INSTRUMENT_dynamic_debug.o := n lib-y := ctype.o string.o vsprintf.o cmdline.o \ rbtree.o radix-tree.o dump_stack.o timerqueue.o\ - idr.o int_sqrt.o extable.o \ + idr.o int_sqrt.o extable.o tida.o \ sha1.o chacha20.o md5.o irq_regs.o argv_split.o \ flex_proportions.o ratelimit.o show_mem.o \ is_single_threaded.o plist.o decompress.o kobject_uevent.o \ diff --git a/lib/tida.c b/lib/tida.c new file mode 100644 index 000000000000..1ea0deb6fa64 --- /dev/null +++ b/lib/tida.c @@ -0,0 +1,103 @@ +#include +#include +#include +#include +#include +#include +#include + +/* + * An extremely simple integer id allocator with small memory + * footprint, mostly useful for cases where up to a few hundred ids + * get allocated. + * + * Note that the backing bitmap is never shrunk. + */ + +/* + * Invariant: + * + * 0 <= tida->hint + * <= find_next_zero_bit(tida->bits, tida->alloc, 0) + * <= tida->alloc. + */ + +static int +tida_expand(struct tida *tida, gfp_t gfp, unsigned long *flags) + __releases(tida->lock) + __acquires(tida->lock) +{ + unsigned long newalloc, oldalloc = tida->alloc; + unsigned long *bits; + + newalloc = oldalloc ? 2 * oldalloc : BITS_PER_LONG; + + spin_unlock_irqrestore(&tida->lock, *flags); + bits = kcalloc(BITS_TO_LONGS(newalloc), sizeof(*bits), gfp); + spin_lock_irqsave(&tida->lock, *flags); + + if (!bits) + return -ENOMEM; + + if (tida->alloc < newalloc) { + memcpy(bits, tida->bits, tida->alloc/8); + tida->alloc = newalloc; + swap(tida->bits, bits); + } + kfree(bits); + + return 0; +} + +int +tida_get(struct tida *tida, gfp_t gfp) +{ + unsigned long flags; + int ret; + + spin_lock_irqsave(&tida->lock, flags); + while (1) { + /* find_next_zero_bit is fine with a NULL bitmap as long as size is 0 */ + ret = find_next_zero_bit(tida->bits, tida->alloc, tida->hint); + if (ret < tida->alloc) + break; + ret = tida_expand(tida, gfp, &flags); + if (ret < 0) + goto out; + } + + __set_bit(ret, tida->bits); + tida->hint = ret+1; +out: + spin_unlock_irqrestore(&tida->lock, flags); + return ret; +} +EXPORT_SYMBOL_GPL(tida_get); + +void +tida_put(struct tida *tida, int id) +{ + unsigned long flags; + + spin_lock_irqsave(&tida->lock, flags); + __clear_bit(id, tida->bits); + if (id < tida->hint) + tida->hint = id; + spin_unlock_irqrestore(&tida->lock, flags); +} +EXPORT_SYMBOL_GPL(tida_put); + +void +tida_init(struct tida *tida) +{ + memset(tida, 0, sizeof(*tida)); + spin_lock_init(&tida->lock); +} +EXPORT_SYMBOL_GPL(tida_init); + +void +tida_destroy(struct tida *tida) +{ + kfree(tida->bits); +} +EXPORT_SYMBOL_GPL(tida_destroy); -- 2.1.4