The patch titled
tmpfs: quick token library to allow scalable retrieval of tokens from token jar
has been added to the -mm tree. Its filename is
tmpfs-quick-token-library-to-allow-scalable-retrieval-of-tokens-from-token-jar.patch
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/SubmitChecklist when testing your code ***
See http://userweb.kernel.org/~akpm/stuff/added-to-mm.txt to find
out what to do about this
The current -mm tree may be found at http://userweb.kernel.org/~akpm/mmotm/
------------------------------------------------------
Subject: tmpfs: quick token library to allow scalable retrieval of tokens from token jar
From: Tim Chen <tim.c.chen@xxxxxxxxxxxxxxx>
We created a token jar library implementing per cpu cache of tokens to
avoid lock contentions whenever we retrieve or return a token to a token
jar. Using this library with tmpfs, we find Aim7 fserver throughput
improved 270% on a 4 socket, 32 cores NHM-EX system.
In current implementation of tmpfs, whenever we get a new page, stat_lock
in shmem_sb_info needs to be acquired. This causes a lot of lock
contentions when multiple threads are using tmpfs simultaneously, which
makes system with large number of cpus scale poorly. Almost 75% of cpu
time was spent contending on stat_lock when we ran Aim7 fserver load with
128 threads on a 4 socket, 32 cores NHM-EX system.
The first patch in the series implements the quick token jar. The second
patch update the shmem code of tmpfs to use this library to improve tmpfs
performance.
This patch:
Creates a quick token (qtoken) library to maintain local caches of tokens.
This avoids lock contention when a token is retrieved or returned to the
token jar to improve scalability performance on system with many cpus.
Signed-off-by: Tim Chen <tim.c.chen@xxxxxxxxxxxxxxx>
Cc: Andi Kleen <ak@xxxxxxxxxxxxxxx>
Cc: Hugh Dickins <hughd@xxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
include/linux/qtoken.h | 41 +++
lib/Makefile | 2
lib/qtoken.c | 447 +++++++++++++++++++++++++++++++++++++++
3 files changed, 489 insertions(+), 1 deletion(-)
diff -puN /dev/null include/linux/qtoken.h
--- /dev/null
+++ a/include/linux/qtoken.h
@@ -0,0 +1,41 @@
+/*
+ * qtoken.h: Structure and function prototypes to implement quick token
+ * retrieval from a jar of tokens with per cpu cache.
+ *
+ * Copyright (C) 2010 Intel Corporation
+ * Author: Tim Chen <tim.c.chen@xxxxxxxxxxxxxxx>
+ *
+ * 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; version 2
+ * of the License.
+ *
+ */
+
+#ifndef _QTOKEN_H
+#define _QTOKEN_H
+
+#define QTOKEN_CACHE_HIGH 2
+#define QTOKEN_POOL_HIGH (2 * QTOKEN_CACHE_HIGH)
+
+struct qtoken {
+ unsigned long pool; /* pool of free tokens */
+ unsigned long total; /* total num of tokens */
+#ifdef CONFIG_SMP
+ unsigned long init_cache_sz; /* initial cache size */
+ spinlock_t lock; /* lock on token jar */
+ atomic_long_t __percpu *cache; /* per cpu cache of tokens */
+#endif
+};
+
+extern void qtoken_return(struct qtoken *token_jar, unsigned long tokens);
+extern int qtoken_get(struct qtoken *token_jar, unsigned long tokens,
+ unsigned long reserve);
+extern int qtoken_init(struct qtoken *token_jar, unsigned long total_tokens,
+ unsigned long init_cache_sz);
+extern void qtoken_free(struct qtoken *token_jar);
+extern unsigned long qtoken_avail(struct qtoken *token_jar);
+extern int qtoken_resize(struct qtoken *token_jar, unsigned long new_size);
+extern unsigned long qtoken_total(struct qtoken *token_jar);
+
+#endif /* _QTOKEN_H */
diff -puN lib/Makefile~tmpfs-quick-token-library-to-allow-scalable-retrieval-of-tokens-from-token-jar lib/Makefile
--- a/lib/Makefile~tmpfs-quick-token-library-to-allow-scalable-retrieval-of-tokens-from-token-jar
+++ a/lib/Makefile
@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmd
idr.o int_sqrt.o extable.o prio_tree.o \
sha1.o irq_regs.o reciprocal_div.o argv_split.o \
proportions.o prio_heap.o ratelimit.o show_mem.o \
- is_single_threaded.o plist.o decompress.o flex_array.o
+ is_single_threaded.o plist.o decompress.o flex_array.o qtoken.o
lib-$(CONFIG_MMU) += ioremap.o
lib-$(CONFIG_SMP) += cpumask.o
diff -puN /dev/null lib/qtoken.c
--- /dev/null
+++ a/lib/qtoken.c
@@ -0,0 +1,447 @@
+/*
+ * qtoken.c: Library of functions to implement quick token
+ * retrieval from a jar of tokens with per cpu cache.
+ *
+ * Copyright (C) 2010 Intel Corporation
+ * Author: Tim Chen <tim.c.chen@xxxxxxxxxxxxxxx>
+ *
+ * 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; version 2
+ * of the License.
+ *
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/init.h>
+#include <linux/cpumask.h>
+#include <linux/qtoken.h>
+
+/*
+ * This library is useful when we have a large number of threads
+ * running concurrently on many cpus trying to access tokens in a token jar
+ * at the same time.
+ *
+ * The token jar is implemented with per cpu cache of tokens.
+ * This library allows tokens to be obtained from or returned quickly to
+ * the local cpu cache without any lock acquisition most of the time.
+ * We only need to lock and modify tokens in the common pool for the
+ * following cases:
+ *
+ * 1) Not enough tokens are in our local cache and we need to get tokens
+ * from the common pool
+ * 2) We have too many tokens in local cache and need to return
+ * some tokens to the common pool
+ * 3) We want to resize the token jar and need to freeze the free tokens
+ *
+ * The local token cache is disabled by setting it to -1 and tokens
+ * reaped into the common pool when we find the common pool low in tokens.
+ * The token jar should be initialized with a cache size large enough
+ * to avoid touching the common pool's tokens frequently.
+ *
+ * It is possible to implement the token jar with just a single
+ * atomic variable for all free tokens. However, this approach is
+ * not used here to prevent excessive cache line bouncing which causes poor
+ * performance when token jar is accessed by large number of simultaneous
+ * threads.
+ */
+
+#ifdef CONFIG_SMP
+/**
+ * qtoken_return - return tokens to token jar
+ *
+ * @token_jar: pointer to token jar
+ * @tokens: the number of tokens to return to token jar
+ *
+ * @tokens are returned to the cache in current cpu, unless
+ * the cache is disabled (i.e. value -1). For this case,
+ * @tokens are returned to common pool.
+ * If the number of tokens in current cpu's cache exceed
+ * a a highmark, we will return the extra tokens into the
+ * common pool.
+ */
+void qtoken_return(struct qtoken *token_jar, unsigned long tokens)
+{
+ long cnt;
+ unsigned long flags;
+ int cpu;
+ atomic_long_t *cache;
+
+ cpu = get_cpu();
+ cache = per_cpu_ptr(token_jar->cache, cpu);
+ cnt = atomic_long_read(cache);
+ if (cnt >= 0) {
+ if ((cnt + tokens) <= QTOKEN_CACHE_HIGH * token_jar->init_cache_sz) {
+ if (!atomic_long_add_unless(cache, tokens, -1)) {
+ spin_lock_irqsave(&token_jar->lock, flags);
+ token_jar->pool += tokens;
+ spin_unlock_irqrestore(&token_jar->lock, flags);
+ }
+ } else {
+ spin_lock_irqsave(&token_jar->lock, flags);
+ if (atomic_long_add_unless(cache, token_jar->init_cache_sz - cnt, -1)) {
+ int extra;
+
+ extra = cnt + tokens - token_jar->init_cache_sz;
+
+ token_jar->pool += extra;
+ } else
+ token_jar->pool += tokens;
+ spin_unlock_irqrestore(&token_jar->lock, flags);
+ }
+ } else {
+ spin_lock_irqsave(&token_jar->lock, flags);
+ token_jar->pool += tokens;
+ spin_unlock_irqrestore(&token_jar->lock, flags);
+ }
+ put_cpu();
+}
+EXPORT_SYMBOL(qtoken_return);
+
+/**
+ * qtoken_reap cache: Move tokens from cache into common pool in token jar
+ *
+ * @token_jar: pointer to token jar
+ *
+ * The tokens in each cpu's cache are reaped and and placed in
+ * common pool. The cache of each cpu is disabled (set to -1).
+ */
+static void qtoken_reap_cache(struct qtoken *token_jar)
+{
+ long cnt;
+ int i;
+
+ for_each_possible_cpu(i) {
+ atomic_long_t *cache;
+
+ cache = per_cpu_ptr(token_jar->cache, i);
+ cnt = atomic_long_xchg(cache, -1);
+ if (cnt > 0)
+ token_jar->pool += cnt;
+ }
+}
+
+/**
+ * qtoken_from pool: Get tokens from common pool in token jar
+ *
+ * @token_jar: pointer to struct qtoken
+ * @tokens: the number of tokens to acquire from token jar
+ * @reserve: number of tokens to reserve in token jar after getting tokens
+ *
+ * Get @tokens from the token jar's common pool but keep @reserve tokens.
+ * We will fail the operation if we cannot keep @reserve tokens in token jar.
+ *
+ * Return 0 if operations succeeds and -ENOSPC if operation fails.
+ */
+static int qtoken_from_pool(struct qtoken *token_jar, unsigned long tokens,
+ unsigned long reserve)
+{
+ int allocated = -ENOSPC;
+
+ /* We should have acquired lock of token pool before coming here */
+ if (token_jar->pool < (reserve + tokens))
+ qtoken_reap_cache(token_jar);
+ if (token_jar->pool >= (reserve + tokens)) {
+ token_jar->pool -= tokens;
+ allocated = 0;
+ }
+ return allocated;
+}
+
+/**
+ * qtoken_get: Get tokens from token jar
+ *
+ * @token_jar: pointer to struct qtoken
+ * @tokens: the number of tokens to acquire from token jar
+ * @reserve: number of tokens to reserve in token jar after getting tokens
+ *
+ * Get @tokens from the token jar but leave @reserve tokens in jar.
+ * Some application may come back quickly to get the reserved tokens
+ * and they do not want the get operation to succeed if it cannot succeed
+ * later. We fail the operation if we cannot keep @reserve tokens in token jar.
+ *
+ * Return 0 if operation succeeds, non zero error code if operation fails
+ */
+int qtoken_get(struct qtoken *token_jar, unsigned long token, unsigned long reserve)
+{
+ int allocated = -ENOSPC;
+ int from_cache = 0;
+ int cpu;
+ long cnt;
+ unsigned long flags;
+ atomic_long_t *cache;
+
+ cpu = get_cpu();
+ cache = per_cpu_ptr(token_jar->cache, cpu);
+ cnt = atomic_long_read(cache);
+ if ((cnt > 0) && (cnt > token)) {
+ /* check cache's reserve first to avoid reading pool var */
+ if (cnt >= (token + reserve))
+ from_cache = 1;
+ else if ((cnt + token_jar->pool) >= (token + reserve))
+ from_cache = 1;
+ }
+ if (from_cache) {
+ if (atomic_long_add_unless(cache, -(long)token, -1))
+ allocated = 0;
+ else {
+ /* cache disabled, get token from pool */
+ spin_lock_irqsave(&token_jar->lock, flags);
+ allocated = qtoken_from_pool(token_jar, token, reserve);
+ spin_unlock_irqrestore(&token_jar->lock, flags);
+ }
+ } else {
+ unsigned long pool_high_mark;
+
+ spin_lock_irqsave(&token_jar->lock, flags);
+ pool_high_mark = QTOKEN_POOL_HIGH * token_jar->init_cache_sz
+ * num_online_cpus();
+ if (token_jar->pool > pool_high_mark + token) {
+ /* plenty of tokens, replenish cache */
+ token_jar->pool -= token + token_jar->init_cache_sz;
+ allocated = 0;
+ cnt = atomic_long_read(cache);
+ if (cnt < 0)
+ cnt = token_jar->init_cache_sz;
+ else
+ cnt += token_jar->init_cache_sz;
+ atomic_long_set(cache, cnt);
+ } else
+ allocated = qtoken_from_pool(token_jar, token, reserve);
+ spin_unlock_irqrestore(&token_jar->lock, flags);
+ }
+ put_cpu();
+ return allocated;
+}
+EXPORT_SYMBOL(qtoken_get);
+
+/**
+ * qtoken_init: Init token jar
+ *
+ * @token_jar: pointer to token jar
+ * @total_tokens: the total number of tokens that the token jar holds
+ * @cache_size: the initial size of per cpu cache of tokens
+ *
+ * Initialize the token jar structure, and allocate per cpu cache of
+ * tokens in the token jar.
+ *
+ * Returns 0 if initialization successful and non-zero error code otherwise.
+ */
+int qtoken_init(struct qtoken *token_jar, unsigned long total_tokens, unsigned long cache_size)
+{
+ int i;
+
+ token_jar->cache = alloc_percpu(atomic_long_t);
+ if (!token_jar->cache)
+ return -ENOMEM;
+ spin_lock_init(&token_jar->lock);
+ for_each_possible_cpu(i) {
+ atomic_long_t *cache;
+
+ cache = per_cpu_ptr(token_jar->cache, i);
+ atomic_long_set(cache, -1);
+ }
+ token_jar->init_cache_sz = cache_size;
+ token_jar->total = token_jar->pool = total_tokens;
+ return 0;
+}
+EXPORT_SYMBOL(qtoken_init);
+
+/**
+ * qtoken_free: Free token jar
+ *
+ * @token_jar: pointer to token jar
+ *
+ * Free memory for per cpu cache used in token jar and
+ * clear the token counts.
+ */
+void qtoken_free(struct qtoken *token_jar)
+{
+ if (token_jar->cache)
+ free_percpu(token_jar->cache);
+ token_jar->pool = 0;
+ token_jar->total = 0;
+}
+EXPORT_SYMBOL(qtoken_free);
+
+/**
+ * qtoken_avail: Calculates token available in token jar
+ *
+ * @token_jar: pointer to token jar
+ *
+ * Get a count of all free tokens in the token jar.
+ */
+unsigned long qtoken_avail(struct qtoken *token_jar)
+{
+ int i;
+ long cnt;
+ unsigned long cnt_total;
+ unsigned long flags;
+
+ spin_lock_irqsave(&token_jar->lock, flags);
+ cnt_total = token_jar->pool;
+ for_each_possible_cpu(i) {
+ atomic_long_t *cache;
+
+ cache = per_cpu_ptr(token_jar->cache, i);
+ cnt = atomic_long_read(cache);
+ if (cnt > 0)
+ cnt_total += cnt;
+ }
+ spin_unlock_irqrestore(&token_jar->lock, flags);
+ return cnt_total;
+}
+EXPORT_SYMBOL(qtoken_avail);
+
+/**
+ * qtoken_resize: Resize the total number of tokens in token jar
+ *
+ * @token_jar: pointer to token jar
+ * @new_size: new total number of tokens in token jar
+ * Returns 0 if token jar resize successful, non zero error code otherwise
+ *
+ * We will resize the token jar and return 0 if the new total number of tokens
+ * is greater than the existing tokens in use. Otherwise, we will fail the
+ * operation and return an error code.
+ */
+int qtoken_resize(struct qtoken *token_jar, unsigned long new_size)
+{
+ unsigned long in_use;
+ unsigned long flags;
+
+ spin_lock_irqsave(&token_jar->lock, flags);
+ qtoken_reap_cache(token_jar);
+ in_use = token_jar->total - token_jar->pool;
+ if (in_use > new_size)
+ return -EBUSY;
+ token_jar->pool = new_size - in_use;
+ token_jar->total = new_size;
+ spin_unlock_irqrestore(&token_jar->lock, flags);
+ return 0;
+}
+EXPORT_SYMBOL(qtoken_resize);
+
+#else /* !CONFIG_SMP */
+
+/**
+ * qtoken_return - return tokens to token jar
+ *
+ * @token_jar: pointer to token jar
+ * @tokens: the number of tokens to return to token jar
+ */
+void qtoken_return(struct qtoken *token_jar, unsigned long tokens)
+{
+ token_jar->pool += tokens;
+}
+EXPORT_SYMBOL(qtoken_return);
+
+/**
+ * qtoken_get: Get tokens from token jar
+ *
+ * @token_jar: pointer to struct qtoken
+ * @tokens: the number of tokens to acquire from token jar
+ * @reserve: number of tokens to reserve in token jar after getting tokens
+ *
+ * Get @tokens from the token jar's but leave @reserve tokens in jar.
+ * Some application may come back quickly to get the reserved tokens
+ * and they do not want the get operation to succeed if it cannot succeed
+ * later. We fail the operation if we cannot keep @reserve tokens in token jar.
+ *
+ * Return 0 if operation succeeds, non zero error code if operation fails
+ */
+int qtoken_get(struct qtoken *token_jar, unsigned long token, unsigned long reserve)
+{
+ int allocated = -ENOSPC;
+
+ if (token_jar->pool >= (reserve + token)) {
+ token_jar->pool -= token;
+ allocated = 0;
+ }
+
+ return allocated;
+}
+EXPORT_SYMBOL(qtoken_get);
+
+/**
+ * qtoken_init: Init token jar
+ *
+ * @token_jar: pointer to token jar
+ * @total_tokens: the total number of tokens that the token jar holds
+ * @cache_size: the initial size of per cpu cache of tokens
+ *
+ * Initialize the token jar structure, and allocate per cpu cache of
+ * tokens for the token jar.
+ *
+ * Returns 0 if initialization is successful and non-zero error code otherwise.
+ */
+int qtoken_init(struct qtoken *token_jar, unsigned long total_tokens, unsigned long cache_size)
+{
+ token_jar->total = token_jar->pool = total_tokens;
+ return 0;
+}
+EXPORT_SYMBOL(qtoken_init);
+
+/**
+ * qtoken_free: Free token jar
+ *
+ * @token_jar: pointer to token jar
+ *
+ * Clear the token counts.
+ */
+void qtoken_free(struct qtoken *token_jar)
+{
+ token_jar->pool = 0;
+ token_jar->total = 0;
+}
+EXPORT_SYMBOL(qtoken_free);
+
+/**
+ * qtoken_avail: Calculate the tokens available in token jar
+ *
+ * @token_jar: pointer to token jar
+ *
+ */
+unsigned long qtoken_avail(struct qtoken *token_jar)
+{
+ return token_jar->pool;
+}
+EXPORT_SYMBOL(qtoken_avail);
+
+/**
+ * qtoken_resize: Resize the total number of tokens in token jar
+ *
+ * @token_jar: pointer to token jar
+ * @new_size: new total number of tokens in token jar
+ * Returns 0 if token jar resize successful, non zero error code otherwise
+ *
+ * We will resize the token jar if the new total number of tokens is greater
+ * than the existing tokens in use. Otherwise, we will fail the operation.
+ */
+int qtoken_resize(struct qtoken *token_jar, unsigned long new_size)
+{
+ unsigned long in_use;
+
+ in_use = token_jar->total - token_jar->pool;
+ if (in_use > new_size)
+ return -EBUSY;
+ token_jar->pool = new_size - in_use;
+ token_jar->total = new_size;
+ return 0;
+}
+EXPORT_SYMBOL(qtoken_resize);
+
+#endif /* CONFIG_SMP */
+
+/**
+ * qtoken_total: Return the total number of tokens configured for token jar
+ *
+ * @token_jar: pointer to token jar
+ *
+ * Returns total number of tokens configured for token jar
+ */
+unsigned long qtoken_total(struct qtoken *token_jar)
+{
+ return token_jar->total;
+}
+EXPORT_SYMBOL(qtoken_total);
_
Patches currently in -mm which might be from tim.c.chen@xxxxxxxxxxxxxxx are
tmpfs-quick-token-library-to-allow-scalable-retrieval-of-tokens-from-token-jar.patch
tmpfs-quick-token-library-to-allow-scalable-retrieval-of-tokens-from-token-jar-fix.patch
tmpfs-make-tmpfs-scalable-with-caches-for-free-blocks.patch
--
To unsubscribe from this list: send the line "unsubscribe mm-commits" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
