diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Makefile | 3 | ||||
| -rw-r--r-- | lib/argv_split.c | 4 | ||||
| -rw-r--r-- | lib/bust_spinlocks.c | 6 | ||||
| -rw-r--r-- | lib/idr.c | 3 | ||||
| -rw-r--r-- | lib/iomap.c | 2 | ||||
| -rw-r--r-- | lib/ioremap.c | 1 | ||||
| -rw-r--r-- | lib/percpu_counter.c | 48 | ||||
| -rw-r--r-- | lib/proportions.c | 384 | ||||
| -rw-r--r-- | lib/radix-tree.c | 16 | ||||
| -rw-r--r-- | lib/sort.c | 2 |
10 files changed, 445 insertions, 24 deletions
diff --git a/lib/Makefile b/lib/Makefile index 6c4ea33..c5f215d 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -5,7 +5,8 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ rbtree.o radix-tree.o dump_stack.o \ idr.o int_sqrt.o bitmap.o extable.o prio_tree.o \ - sha1.o irq_regs.o reciprocal_div.o argv_split.o + sha1.o irq_regs.o reciprocal_div.o argv_split.o \ + proportions.o lib-$(CONFIG_MMU) += ioremap.o lib-$(CONFIG_SMP) += cpumask.o diff --git a/lib/argv_split.c b/lib/argv_split.c index 4096ed4..fad6ce4 100644 --- a/lib/argv_split.c +++ b/lib/argv_split.c @@ -75,7 +75,9 @@ char **argv_split(gfp_t gfp, const char *str, int *argcp) if (argv == NULL) goto out; - *argcp = argc; + if (argcp) + *argcp = argc; + argvp = argv; while (*str) { diff --git a/lib/bust_spinlocks.c b/lib/bust_spinlocks.c index accb356..486da62 100644 --- a/lib/bust_spinlocks.c +++ b/lib/bust_spinlocks.c @@ -17,13 +17,13 @@ void __attribute__((weak)) bust_spinlocks(int yes) { if (yes) { - oops_in_progress = 1; + ++oops_in_progress; } else { #ifdef CONFIG_VT unblank_screen(); #endif - oops_in_progress = 0; - wake_up_klogd(); + if (--oops_in_progress == 0) + wake_up_klogd(); } } @@ -580,8 +580,7 @@ void *idr_replace(struct idr *idp, void *ptr, int id) } EXPORT_SYMBOL(idr_replace); -static void idr_cache_ctor(void * idr_layer, struct kmem_cache *idr_layer_cache, - unsigned long flags) +static void idr_cache_ctor(struct kmem_cache *idr_layer_cache, void *idr_layer) { memset(idr_layer, 0, sizeof(struct idr_layer)); } diff --git a/lib/iomap.c b/lib/iomap.c index 864f2ec..72c4268 100644 --- a/lib/iomap.c +++ b/lib/iomap.c @@ -40,7 +40,7 @@ static void bad_io_access(unsigned long port, const char *access) static int count = 10; if (count) { count--; - printk(KERN_ERR "Bad IO access at port %lx (%s)\n", port, access); + printk(KERN_ERR "Bad IO access at port %#lx (%s)\n", port, access); WARN_ON(1); } } diff --git a/lib/ioremap.c b/lib/ioremap.c index 7605214..14c6078 100644 --- a/lib/ioremap.c +++ b/lib/ioremap.c @@ -8,6 +8,7 @@ #include <linux/vmalloc.h> #include <linux/mm.h> #include <linux/sched.h> +#include <linux/io.h> #include <asm/cacheflush.h> #include <asm/pgtable.h> diff --git a/lib/percpu_counter.c b/lib/percpu_counter.c index cf22c61..9659eab 100644 --- a/lib/percpu_counter.c +++ b/lib/percpu_counter.c @@ -14,15 +14,29 @@ static LIST_HEAD(percpu_counters); static DEFINE_MUTEX(percpu_counters_lock); #endif -void percpu_counter_mod(struct percpu_counter *fbc, s32 amount) +void percpu_counter_set(struct percpu_counter *fbc, s64 amount) { - long count; + int cpu; + + spin_lock(&fbc->lock); + for_each_possible_cpu(cpu) { + s32 *pcount = per_cpu_ptr(fbc->counters, cpu); + *pcount = 0; + } + fbc->count = amount; + spin_unlock(&fbc->lock); +} +EXPORT_SYMBOL(percpu_counter_set); + +void __percpu_counter_add(struct percpu_counter *fbc, s64 amount, s32 batch) +{ + s64 count; s32 *pcount; int cpu = get_cpu(); pcount = per_cpu_ptr(fbc->counters, cpu); count = *pcount + amount; - if (count >= FBC_BATCH || count <= -FBC_BATCH) { + if (count >= batch || count <= -batch) { spin_lock(&fbc->lock); fbc->count += count; *pcount = 0; @@ -32,13 +46,13 @@ void percpu_counter_mod(struct percpu_counter *fbc, s32 amount) } put_cpu(); } -EXPORT_SYMBOL(percpu_counter_mod); +EXPORT_SYMBOL(__percpu_counter_add); /* * Add up all the per-cpu counts, return the result. This is a more accurate * but much slower version of percpu_counter_read_positive() */ -s64 percpu_counter_sum(struct percpu_counter *fbc) +s64 __percpu_counter_sum(struct percpu_counter *fbc) { s64 ret; int cpu; @@ -50,25 +64,43 @@ s64 percpu_counter_sum(struct percpu_counter *fbc) ret += *pcount; } spin_unlock(&fbc->lock); - return ret < 0 ? 0 : ret; + return ret; } -EXPORT_SYMBOL(percpu_counter_sum); +EXPORT_SYMBOL(__percpu_counter_sum); + +static struct lock_class_key percpu_counter_irqsafe; -void percpu_counter_init(struct percpu_counter *fbc, s64 amount) +int percpu_counter_init(struct percpu_counter *fbc, s64 amount) { spin_lock_init(&fbc->lock); fbc->count = amount; fbc->counters = alloc_percpu(s32); + if (!fbc->counters) + return -ENOMEM; #ifdef CONFIG_HOTPLUG_CPU mutex_lock(&percpu_counters_lock); list_add(&fbc->list, &percpu_counters); mutex_unlock(&percpu_counters_lock); #endif + return 0; } EXPORT_SYMBOL(percpu_counter_init); +int percpu_counter_init_irq(struct percpu_counter *fbc, s64 amount) +{ + int err; + + err = percpu_counter_init(fbc, amount); + if (!err) + lockdep_set_class(&fbc->lock, &percpu_counter_irqsafe); + return err; +} + void percpu_counter_destroy(struct percpu_counter *fbc) { + if (!fbc->counters) + return; + free_percpu(fbc->counters); #ifdef CONFIG_HOTPLUG_CPU mutex_lock(&percpu_counters_lock); diff --git a/lib/proportions.c b/lib/proportions.c new file mode 100644 index 0000000..332d8c5 --- /dev/null +++ b/lib/proportions.c @@ -0,0 +1,384 @@ +/* + * Floating proportions + * + * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com> + * + * Description: + * + * The floating proportion is a time derivative with an exponentially decaying + * history: + * + * p_{j} = \Sum_{i=0} (dx_{j}/dt_{-i}) / 2^(1+i) + * + * Where j is an element from {prop_local}, x_{j} is j's number of events, + * and i the time period over which the differential is taken. So d/dt_{-i} is + * the differential over the i-th last period. + * + * The decaying history gives smooth transitions. The time differential carries + * the notion of speed. + * + * The denominator is 2^(1+i) because we want the series to be normalised, ie. + * + * \Sum_{i=0} 1/2^(1+i) = 1 + * + * Further more, if we measure time (t) in the same events as x; so that: + * + * t = \Sum_{j} x_{j} + * + * we get that: + * + * \Sum_{j} p_{j} = 1 + * + * Writing this in an iterative fashion we get (dropping the 'd's): + * + * if (++x_{j}, ++t > period) + * t /= 2; + * for_each (j) + * x_{j} /= 2; + * + * so that: + * + * p_{j} = x_{j} / t; + * + * We optimize away the '/= 2' for the global time delta by noting that: + * + * if (++t > period) t /= 2: + * + * Can be approximated by: + * + * period/2 + (++t % period/2) + * + * [ Furthermore, when we choose period to be 2^n it can be written in terms of + * binary operations and wraparound artefacts disappear. ] + * + * Also note that this yields a natural counter of the elapsed periods: + * + * c = t / (period/2) + * + * [ Its monotonic increasing property can be applied to mitigate the wrap- + * around issue. ] + * + * This allows us to do away with the loop over all prop_locals on each period + * expiration. By remembering the period count under which it was last accessed + * as c_{j}, we can obtain the number of 'missed' cycles from: + * + * c - c_{j} + * + * We can then lazily catch up to the global period count every time we are + * going to use x_{j}, by doing: + * + * x_{j} /= 2^(c - c_{j}), c_{j} = c + */ + +#include <linux/proportions.h> +#include <linux/rcupdate.h> + +/* + * Limit the time part in order to ensure there are some bits left for the + * cycle counter. + */ +#define PROP_MAX_SHIFT (3*BITS_PER_LONG/4) + +int prop_descriptor_init(struct prop_descriptor *pd, int shift) +{ + int err; + + if (shift > PROP_MAX_SHIFT) + shift = PROP_MAX_SHIFT; + + pd->index = 0; + pd->pg[0].shift = shift; + mutex_init(&pd->mutex); + err = percpu_counter_init_irq(&pd->pg[0].events, 0); + if (err) + goto out; + + err = percpu_counter_init_irq(&pd->pg[1].events, 0); + if (err) + percpu_counter_destroy(&pd->pg[0].events); + +out: + return err; +} + +/* + * We have two copies, and flip between them to make it seem like an atomic + * update. The update is not really atomic wrt the events counter, but + * it is internally consistent with the bit layout depending on shift. + * + * We copy the events count, move the bits around and flip the index. + */ +void prop_change_shift(struct prop_descriptor *pd, int shift) +{ + int index; + int offset; + u64 events; + unsigned long flags; + + if (shift > PROP_MAX_SHIFT) + shift = PROP_MAX_SHIFT; + + mutex_lock(&pd->mutex); + + index = pd->index ^ 1; + offset = pd->pg[pd->index].shift - shift; + if (!offset) + goto out; + + pd->pg[index].shift = shift; + + local_irq_save(flags); + events = percpu_counter_sum(&pd->pg[pd->index].events); + if (offset < 0) + events <<= -offset; + else + events >>= offset; + percpu_counter_set(&pd->pg[index].events, events); + + /* + * ensure the new pg is fully written before the switch + */ + smp_wmb(); + pd->index = index; + local_irq_restore(flags); + + synchronize_rcu(); + +out: + mutex_unlock(&pd->mutex); +} + +/* + * wrap the access to the data in an rcu_read_lock() section; + * this is used to track the active references. + */ +static struct prop_global *prop_get_global(struct prop_descriptor *pd) +{ + int index; + + rcu_read_lock(); + index = pd->index; + /* + * match the wmb from vcd_flip() + */ + smp_rmb(); + return &pd->pg[index]; +} + +static void prop_put_global(struct prop_descriptor *pd, struct prop_global *pg) +{ + rcu_read_unlock(); +} + +static void +prop_adjust_shift(int *pl_shift, unsigned long *pl_period, int new_shift) +{ + int offset = *pl_shift - new_shift; + + if (!offset) + return; + + if (offset < 0) + *pl_period <<= -offset; + else + *pl_period >>= offset; + + *pl_shift = new_shift; +} + +/* + * PERCPU + */ + +int prop_local_init_percpu(struct prop_local_percpu *pl) +{ + spin_lock_init(&pl->lock); + pl->shift = 0; + pl->period = 0; + return percpu_counter_init_irq(&pl->events, 0); +} + +void prop_local_destroy_percpu(struct prop_local_percpu *pl) +{ + percpu_counter_destroy(&pl->events); +} + +/* + * Catch up with missed period expirations. + * + * until (c_{j} == c) + * x_{j} -= x_{j}/2; + * c_{j}++; + */ +static +void prop_norm_percpu(struct prop_global *pg, struct prop_local_percpu *pl) +{ + unsigned long period = 1UL << (pg->shift - 1); + unsigned long period_mask = ~(period - 1); + unsigned long global_period; + unsigned long flags; + + global_period = percpu_counter_read(&pg->events); + global_period &= period_mask; + + /* + * Fast path - check if the local and global period count still match + * outside of the lock. + */ + if (pl->period == global_period) + return; + + spin_lock_irqsave(&pl->lock, flags); + prop_adjust_shift(&pl->shift, &pl->period, pg->shift); + /* + * For each missed period, we half the local counter. + * basically: + * pl->events >> (global_period - pl->period); + * + * but since the distributed nature of percpu counters make division + * rather hard, use a regular subtraction loop. This is safe, because + * the events will only every be incremented, hence the subtraction + * can never result in a negative number. + */ + while (pl->period != global_period) { + unsigned long val = percpu_counter_read(&pl->events); + unsigned long half = (val + 1) >> 1; + + /* + * Half of zero won't be much less, break out. + * This limits the loop to shift iterations, even + * if we missed a million. + */ + if (!val) + break; + + percpu_counter_add(&pl->events, -half); + pl->period += period; + } + pl->period = global_period; + spin_unlock_irqrestore(&pl->lock, flags); +} + +/* + * ++x_{j}, ++t + */ +void __prop_inc_percpu(struct prop_descriptor *pd, struct prop_local_percpu *pl) +{ + struct prop_global *pg = prop_get_global(pd); + + prop_norm_percpu(pg, pl); + percpu_counter_add(&pl->events, 1); + percpu_counter_add(&pg->events, 1); + prop_put_global(pd, pg); +} + +/* + * Obtain a fraction of this proportion + * + * p_{j} = x_{j} / (period/2 + t % period/2) + */ +void prop_fraction_percpu(struct prop_descriptor *pd, + struct prop_local_percpu *pl, + long *numerator, long *denominator) +{ + struct prop_global *pg = prop_get_global(pd); + unsigned long period_2 = 1UL << (pg->shift - 1); + unsigned long counter_mask = period_2 - 1; + unsigned long global_count; + + prop_norm_percpu(pg, pl); + *numerator = percpu_counter_read_positive(&pl->events); + + global_count = percpu_counter_read(&pg->events); + *denominator = period_2 + (global_count & counter_mask); + + prop_put_global(pd, pg); +} + +/* + * SINGLE + */ + +int prop_local_init_single(struct prop_local_single *pl) +{ + spin_lock_init(&pl->lock); + pl->shift = 0; + pl->period = 0; + pl->events = 0; + return 0; +} + +void prop_local_destroy_single(struct prop_local_single *pl) +{ +} + +/* + * Catch up with missed period expirations. + */ +static +void prop_norm_single(struct prop_global *pg, struct prop_local_single *pl) +{ + unsigned long period = 1UL << (pg->shift - 1); + unsigned long period_mask = ~(period - 1); + unsigned long global_period; + unsigned long flags; + + global_period = percpu_counter_read(&pg->events); + global_period &= period_mask; + + /* + * Fast path - check if the local and global period count still match + * outside of the lock. + */ + if (pl->period == global_period) + return; + + spin_lock_irqsave(&pl->lock, flags); + prop_adjust_shift(&pl->shift, &pl->period, pg->shift); + /* + * For each missed period, we half the local counter. + */ + period = (global_period - pl->period) >> (pg->shift - 1); + if (likely(period < BITS_PER_LONG)) + pl->events >>= period; + else + pl->events = 0; + pl->period = global_period; + spin_unlock_irqrestore(&pl->lock, flags); +} + +/* + * ++x_{j}, ++t + */ +void __prop_inc_single(struct prop_descriptor *pd, struct prop_local_single *pl) +{ + struct prop_global *pg = prop_get_global(pd); + + prop_norm_single(pg, pl); + pl->events++; + percpu_counter_add(&pg->events, 1); + prop_put_global(pd, pg); +} + +/* + * Obtain a fraction of this proportion + * + * p_{j} = x_{j} / (period/2 + t % period/2) + */ +void prop_fraction_single(struct prop_descriptor *pd, + struct prop_local_single *pl, + long *numerator, long *denominator) +{ + struct prop_global *pg = prop_get_global(pd); + unsigned long period_2 = 1UL << (pg->shift - 1); + unsigned long counter_mask = period_2 - 1; + unsigned long global_count; + + prop_norm_single(pg, pl); + *numerator = pl->events; + + global_count = percpu_counter_read(&pg->events); + *denominator = period_2 + (global_count & counter_mask); + + prop_put_global(pd, pg); +} diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 6b26f9d..48c250f 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1042,19 +1042,21 @@ int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag) EXPORT_SYMBOL(radix_tree_tagged); static void -radix_tree_node_ctor(void *node, struct kmem_cache *cachep, unsigned long flags) +radix_tree_node_ctor(struct kmem_cache *cachep, void *node) { memset(node, 0, sizeof(struct radix_tree_node)); } static __init unsigned long __maxindex(unsigned int height) { - unsigned int tmp = height * RADIX_TREE_MAP_SHIFT; - unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1; - - if (tmp >= RADIX_TREE_INDEX_BITS) - index = ~0UL; - return index; + unsigned int width = height * RADIX_TREE_MAP_SHIFT; + int shift = RADIX_TREE_INDEX_BITS - width; + + if (shift < 0) + return ~0UL; + if (shift >= BITS_PER_LONG) + return 0UL; + return ~0UL >> shift; } static __init void radix_tree_init_maxindex(void) @@ -67,7 +67,7 @@ void sort(void *base, size_t num, size_t size, } /* sort */ - for (i = n - size; i >= 0; i -= size) { + for (i = n - size; i > 0; i -= size) { swap(base, base + i, size); for (r = 0; r * 2 + size < i; r = c) { c = r * 2 + size; |
