tmpfs: Quick token library to allow scalable retrieval of tokens from token jar
PATCH 1/2 tmpfs: Quick token library to allow scalable retrieval of tokens from token jar
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, and allows better scaling on system with many cpus.
include/linux/qtoken.h | 40 ++++++++ lib/Makefile | 2 +- lib/qtoken.c | 235 ++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 276 insertions(+), 1 deletions(-)
include/linux/qtoken.h new file +40 -0
@@ -0,0 +1,40 @@ +/* +* 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 <[email protected]> +* +* 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_HIGHMARK 2 +#define QTOKEN_POOL_HIGHMARK (2 * QTOKEN_CACHE_HIGHMARK) + +struct qtoken { +long pool;/* pool of free tokens */ +long total;/* total num of tokens */ +#ifdef CONFIG_SMP +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,long tokens); +extern int qtoken_get (struct qtoken *token_jar,long tkn,long reserve); +extern int qtoken_init (struct qtoken *token_jar,long total_tokens, +long init_cache_sz); +extern void qtoken_put (struct qtoken *token_jar); +extern long qtoken_avail (struct qtoken *token_jar); +extern int qtoken_resize (struct qtoken *token_jar,long new_total_tokens); +extern long qtoken_total (struct qtoken *token_jar); + +#endif /* _QTOKEN_H */
lib/Makefile +1 -1
@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ 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
lib/qtoken.c new file +235 -0
235 lines not on this page · raw message
Andrew Morton
maintainerQuoted 5 lines · On Tue, 18 May 2010 16:34:28 -0700 tim <[email protected]> wrote:
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, and allows better scaling on system with many cpus.
A few things...
Quoted 21 lines
include/linux/qtoken.h new file +15
-0@@ -0,0 +1,40 @@ +/* +* 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 <[email protected]> +* +* 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
include/linux/qtoken.h line 25
Quoted 10 lines
include/linux/qtoken.h new file +10
-0+#define _QTOKEN_H + +#define QTOKEN_CACHE_HIGHMARK 2 +#define QTOKEN_POOL_HIGHMARK (2 * QTOKEN_CACHE_HIGHMARK) + +struct qtoken { +long pool;/* pool of free tokens */ +long total;/* total num of tokens */ +#ifdef CONFIG_SMP +long init_cache_sz;/* initial cache size */
I don't think that it si meaningful for any of these things to have negative values, so an unsigned type would be more appropriate.
Did they really need to be long'? Plain old unsigned' might be more efficient, perhaps.
include/linux/qtoken.h line 27
Quoted 2 lines
include/linux/qtoken.h new file +2
-0+spinlock_t lock;/* lock on token jar */ +atomic_long_t __percpu *cache;/* per cpu cache of tokens */
Why are these long? Bear in mind that `long' is only 32-bit on 32-bit..
Quoted 35 lines
include/linux/qtoken.h new file +13
-0+#endif +}; + +extern void qtoken_return (struct qtoken *token_jar,long tokens); +extern int qtoken_get (struct qtoken *token_jar,long tkn,long reserve); +extern int qtoken_init (struct qtoken *token_jar,long total_tokens, +long init_cache_sz); +extern void qtoken_put (struct qtoken *token_jar); +extern long qtoken_avail (struct qtoken *token_jar); +extern int qtoken_resize (struct qtoken *token_jar,long new_total_tokens); +extern long qtoken_total (struct qtoken *token_jar); + +#endif /* _QTOKEN_H */ lib/Makefile +1
-1@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ 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.olib/qtoken.c new file +3
-0@@ -0,0 +1,235 @@ +/* +* qtoken.c: Library of functions to implement quick token +* retrieval from a jar of tokens with per cpu cache.
lib/qtoken.c line 13
Quoted 10 lines
lib/qtoken.c new file +10
-0+* +* Copyright (C) 2010 Intel Corporation +* Author: Tim Chen <[email protected]> +* +* 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. +* +*/
It would be nice to have some description of what this thing actually does and how it does it. And under which circumstances one should use it, and how one should use it. In the changelog or, better, in .the .c file
lib/qtoken.c line 21
Quoted 7 lines
lib/qtoken.c new file +7
-0+#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/init.h> +#include <linux/cpumask.h> +#include <linux/qtoken.h> + +void qtoken_return (struct qtoken *token_jar,long tokens)
Please document at least all the interface functions.
kerneldoc is suitable, but avoid falling into the trap of just lamely describing the function arguments without actually telling anyone anything interesting or relevant.
lib/qtoken.c line 33
Quoted 12 lines
lib/qtoken.c new file +12
-0+{ +#ifdef CONFIG_SMP +long cnt; +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 (likely ((cnt+tokens) <= +QTOKEN_CACHE_HIGHMARK *token_jar->init_cache_sz)) {
It's kernel-conventional to put spaces around arithmetic operators. (Many instances).
lib/qtoken.c line 37
Quoted 4 lines
lib/qtoken.c new file +4
-0+/* Add freed tokens to local cache unless cache was +* reaped and disabled, return tokens to pool +* for that case +*/
More typical comment layout is like this (many instances):
/*
* Add freed tokens to local cache unless cache was
* reaped and disabled, return tokens to pool
* for that case
*/
lib/qtoken.c line 42
Quoted 5 lines
lib/qtoken.c new file +5
-0+if (!atomic_long_add_unless ( + cache, tokens,-1 )) { +spin_lock (&token_jar->lock); + token_jar->pool += tokens; +spin_unlock (&token_jar->lock);
It internally calls spin_lock(), so this whole facility cannot be used from interrupt context, unless one jumps through obscure hoops.
This might be a significant restriction. We should think about this and it should be documented and justified. Or fixed.
lib/qtoken.c line 52
Quoted 10 lines
lib/qtoken.c new file +10
-0+ } + }else { +spin_lock (&token_jar->lock); +/* If cache has not been reaped and set to -1, +* set cache to init cache size +*/ +if (atomic_long_add_unless ( + cache, token_jar->init_cache_sz-cnt,-1 )) { +long excess = cnt + tokens - + token_jar->init_cache_sz;
In several places this code does strange contortions to avoid overflowing 80-cols. It would be better to let it overflow rather than doing things like the above.
There are often tasteful fixes. In this case,
long extra; extra = cnt + tokens - token_jar->init_cache_sz;
("excess" would have overflowed ;))
Please have a think about it..
lib/qtoken.c line 61
Quoted 8 lines
lib/qtoken.c new file +8
-0+ token_jar->pool += excess; + }else + token_jar->pool += tokens; +spin_unlock (&token_jar->lock); + } + }else { +/* local cache reaped and disabled, */ +/* return pages to global pool */
This reference to "pages" assumes a particular application.
lib/qtoken.c line 71
Quoted 10 lines
lib/qtoken.c new file +10
-0+spin_lock (&token_jar->lock); + token_jar->pool += tokens; + spin_unlock(&token_jar->lock); + } +put_cpu (); +#else + token_jar->pool += tokens; +#endif +} +EXPORT_SYMBOL (qtoken_return);
Can we do something to reduce the amount of `#ifdef CONFIG_SMP' in here?
Quoted 8 lines
lib/qtoken.c new file +8
-0+#ifdef CONFIG_SMP +static void qtoken_reap_cache (struct qtoken *token_jar) +{ +long cnt; +int i; + +/* Need to have already acquired lock before here */ +/* Reap cache into pool and disable local cache */
lib/qtoken.c line 90
Quoted 10 lines
lib/qtoken.c new file +10
-0+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; + } +} +#endif
What happens if num_possible_cpus() is much larger than num_online_cpus()?
Have you though about making this code cpu-hotplug-aware?
Quoted 6 lines
lib/qtoken.c new file +6
-0+static int qtoken_from_pool (struct qtoken *token_jar,unsigned tkn, +unsigned reserve) +{ +int allocated =0 ; + +#ifdef CONFIG_SMP
lib/qtoken.c line 107
Quoted 10 lines
lib/qtoken.c new file +10
-0+/* Need to have acquired lock of token pool before coming here */ +if (token_jar->pool < (reserve+tkn)) +qtoken_reap_cache (token_jar); +#endif +if (token_jar->pool >= (reserve+tkn)) { + token_jar->pool -= tkn; + allocated =1 ; + } +return allocated; +}
Sometimes the code uses "token" and sometimes it uses "tkn". "tkn" is plain ugly - "token" is better.
Quoted 4 lines
lib/qtoken.c new file +4
-0+int qtoken_get (struct qtoken *token_jar,long tkn,long reserve) +{ +int allocated =0 ; +#ifdef CONFIG_SMP
lib/qtoken.c line 122
Quoted 10 lines
lib/qtoken.c new file +10
-0+int cpu; +long cnt; +atomic_long_t *cache; + +if (tkn <=0 ) +return 0 ; + cpu =get_cpu (); + cache =per_cpu_ptr (token_jar->cache, cpu); + cnt =atomic_long_read (cache); +/* Need to reserve tokens after allocation */
As often happens, the comment explains the "what", but leaves the reader wondering "why".
Quoted 48 lines
lib/qtoken.c new file +48
-0+if ((cnt > reserve) && (cnt >= tkn)) { +if (atomic_long_add_unless (cache, -tkn,-1 )) + allocated =1 ; +else { +/* cache has been reaped, get token from pool */ +spin_lock (&token_jar->lock); + allocated =qtoken_from_pool (token_jar, tkn, reserve); +spin_unlock (&token_jar->lock); + } + }else { +/* cache low, allocate from pool */ +spin_lock (&token_jar->lock); +if ((token_jar->pool - tkn) > (QTOKEN_POOL_HIGHMARK * + token_jar->init_cache_sz *num_possible_cpus ())) { +/* abundant tokens in pool */ +/* allocate token and replenish cache */ + token_jar->pool -= tkn; + allocated = tkn; + token_jar->pool -= token_jar->init_cache_sz; + 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, tkn, reserve); +spin_unlock (&token_jar->lock); + } +put_cpu (); +#else + allocated =qtoken_from_pool (token_jar, tkn, reserve); +#endif +return allocated; +} +EXPORT_SYMBOL (qtoken_get); + +int qtoken_init (struct qtoken *token_jar,long total_tokens,long cache_size) +{ +#ifdef CONFIG_SMP +int i; + + token_jar->cache =alloc_percpu (atomic_long_t); +if (!token_jar->cache) +return 0 ; +spin_lock_init (&token_jar->lock); +for_each_possible_cpu (i) { +atomic_long_t *cache;
lib/qtoken.c line 180
Quoted 10 lines
lib/qtoken.c new file +10
-0+ + cache =per_cpu_ptr (token_jar->cache, i); + atomic_long_set(cache, -1); + } + token_jar->init_cache_sz = cache_size; +#endif + token_jar->total = token_jar->pool = total_tokens; +return 1 ; +} +EXPORT_SYMBOL (qtoken_init);
This (undocumented) interface function returns 0 on failure and 1 on success. This is very atypical. The expected interface would be 0 on success and a -ve errno (in this case -ENOMEM) on failure.
lib/qtoken.c line 191
Quoted 10 lines
lib/qtoken.c new file +10
-0+void qtoken_put (struct qtoken *token_jar) +{ +#ifdef CONFIG_SMP +if (token_jar->cache) +free_percpu (token_jar->cache); +#endif + token_jar->pool =0 ; + token_jar->total =0 ; +} +EXPORT_SYMBOL (qtoken_put);
One expects a kernel function called "foo_put()" to decrease the refcount on a foo, and to free it if the refcount went to zero. But that isn't what this (undocumented) function appears to be doing. Perhaps qtoken_free() would be a more appropriate name?
Quoted 8 lines
lib/qtoken.c new file +8
-0+/* This function should be called sparingly, it is +* expensive to get a total count of free tokens. +*/ +long qtoken_avail (struct qtoken *token_jar) +{ +long cnt; + +#ifdef CONFIG_SMP
lib/qtoken.c line 210
Quoted 10 lines
lib/qtoken.c new file +10
-0+spin_lock (&token_jar->lock); +qtoken_reap_cache (token_jar); + cnt = token_jar->pool; +spin_unlock (&token_jar->lock); +#else + cnt = token_jar->pool; +#endif +return cnt; +} +EXPORT_SYMBOL (qtoken_avail);
Perhaps it was inappropriate to run qtoken_reap_cache() in this function.
Quoted 8 lines
lib/qtoken.c new file +8
-0+int qtoken_resize (struct qtoken *token_jar,long new_total_tokens) +{ +long in_use; + +#ifdef CONFIG_SMP +spin_lock (&token_jar->lock); +qtoken_reap_cache (token_jar); +#endif
lib/qtoken.c line 229
Quoted 10 lines
lib/qtoken.c new file +10
-0+ in_use = token_jar->total - token_jar->pool; +if (in_use > new_total_tokens) +return 0 ; + token_jar->total = new_total_tokens - in_use; +#ifdef CONFIG_SMP +spin_unlock (&token_jar->lock); +#endif +return 1 ; +} +EXPORT_SYMBOL (qtoken_resize);
This code will get an unused-variable warning on CONFIG_SMP=n. Please do a uniprocessor test build, get it clean.
Quoted 5 lines
lib/qtoken.c new file +5
-0+long qtoken_total (struct qtoken *token_jar) +{ +return token_jar->total; +} +EXPORT_SYMBOL (qtoken_total);
Andrew,
I've fixed the issues that you brought up for this patch series. I have sent out version 2 patches in separate mails.
I've followed up on one of your comments below to explain why I'm doing things done differently from your suggestions.
Quoted 10 lines · Andrew Morton
include/linux/qtoken.h line 25
Quoted 6 lines
include/linux/qtoken.h new file +6
-0+ +struct qtoken { +long pool;/* pool of free tokens */ +long total;/* total num of tokens */ +#ifdef CONFIG_SMP +long init_cache_sz;/* initial cache size */ I don't think that it si meaningful for any of these things to have negative values, so an unsigned type would be more appropriate.
Quoted 2 lines
Did they really need to be
long'? Plain oldunsigned' might be more efficient, perhaps.
I've changed "pool" and "total" to unsigned long. However, since tmpfs uses unsigned long for the free blocks, I have to use unsigned long instead of unsigned for the token jar to maintain compatibility with tmpfs.
Thank you for your review.
Regards,
Tim Chen