diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Kconfig.debug | 13 | ||||
| -rw-r--r-- | lib/Makefile | 2 | ||||
| -rw-r--r-- | lib/bug.c | 5 | ||||
| -rw-r--r-- | lib/check_signature.c | 26 | ||||
| -rw-r--r-- | lib/idr.c | 434 | ||||
| -rw-r--r-- | lib/kobject.c | 19 | ||||
| -rw-r--r-- | lib/percpu_counter.c | 68 | ||||
| -rw-r--r-- | lib/radix-tree.c | 1 | ||||
| -rw-r--r-- | lib/vsprintf.c | 173 |
9 files changed, 677 insertions, 64 deletions
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index fab32a28637..640844024ff 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -152,6 +152,19 @@ config DEBUG_SLAB_LEAK bool "Memory leak debugging" depends on DEBUG_SLAB +config SLUB_DEBUG_ON + bool "SLUB debugging on by default" + depends on SLUB && SLUB_DEBUG + default n + help + Boot with debugging on by default. SLUB boots by default with + the runtime debug capabilities switched off. Enabling this is + equivalent to specifying the "slub_debug" parameter on boot. + There is no support for more fine grained debug control like + possible with slub_debug=xxx. SLUB debugging may be switched + off in a kernel built with CONFIG_SLUB_DEBUG_ON by specifying + "slub_debug=-". + config DEBUG_PREEMPT bool "Debug preemptible kernel" depends on DEBUG_KERNEL && PREEMPT && TRACE_IRQFLAGS_SUPPORT diff --git a/lib/Makefile b/lib/Makefile index d1b366bdf86..d7a93ff7f5a 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -13,7 +13,7 @@ lib-$(CONFIG_SMP) += cpumask.o lib-y += kobject.o kref.o kobject_uevent.o klist.o obj-y += div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ - bust_spinlocks.o hexdump.o + bust_spinlocks.o hexdump.o check_signature.o ifeq ($(CONFIG_DEBUG_KOBJECT),y) CFLAGS_kobject.o += -DDEBUG diff --git a/lib/bug.c b/lib/bug.c index 014b582c5c4..530f38f5578 100644 --- a/lib/bug.c +++ b/lib/bug.c @@ -38,6 +38,7 @@ #include <linux/list.h> #include <linux/module.h> #include <linux/bug.h> +#include <linux/sched.h> extern const struct bug_entry __start___bug_table[], __stop___bug_table[]; @@ -112,7 +113,7 @@ const struct bug_entry *find_bug(unsigned long bugaddr) return module_find_bug(bugaddr); } -enum bug_trap_type report_bug(unsigned long bugaddr) +enum bug_trap_type report_bug(unsigned long bugaddr, struct pt_regs *regs) { const struct bug_entry *bug; const char *file; @@ -147,7 +148,7 @@ enum bug_trap_type report_bug(unsigned long bugaddr) "[verbose debug info unavailable]\n", (void *)bugaddr); - dump_stack(); + show_regs(regs); return BUG_TRAP_TYPE_WARN; } diff --git a/lib/check_signature.c b/lib/check_signature.c new file mode 100644 index 00000000000..fd6af199247 --- /dev/null +++ b/lib/check_signature.c @@ -0,0 +1,26 @@ +#include <linux/io.h> +#include <linux/module.h> + +/** + * check_signature - find BIOS signatures + * @io_addr: mmio address to check + * @signature: signature block + * @length: length of signature + * + * Perform a signature comparison with the mmio address io_addr. This + * address should have been obtained by ioremap. + * Returns 1 on a match. + */ + +int check_signature(const volatile void __iomem *io_addr, + const unsigned char *signature, int length) +{ + while (length--) { + if (readb(io_addr) != *signature) + return 0; + io_addr++; + signature++; + } + return 1; +} +EXPORT_SYMBOL(check_signature); diff --git a/lib/idr.c b/lib/idr.c index 305117ca2d4..5ca67b3cfd3 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -70,6 +70,26 @@ static void free_layer(struct idr *idp, struct idr_layer *p) spin_unlock_irqrestore(&idp->lock, flags); } +static void idr_mark_full(struct idr_layer **pa, int id) +{ + struct idr_layer *p = pa[0]; + int l = 0; + + __set_bit(id & IDR_MASK, &p->bitmap); + /* + * If this layer is full mark the bit in the layer above to + * show that this part of the radix tree is full. This may + * complete the layer above and require walking up the radix + * tree. + */ + while (p->bitmap == IDR_FULL) { + if (!(p = pa[++l])) + break; + id = id >> IDR_BITS; + __set_bit((id & IDR_MASK), &p->bitmap); + } +} + /** * idr_pre_get - reserver resources for idr allocation * @idp: idr handle @@ -95,15 +115,15 @@ int idr_pre_get(struct idr *idp, gfp_t gfp_mask) } EXPORT_SYMBOL(idr_pre_get); -static int sub_alloc(struct idr *idp, void *ptr, int *starting_id) +static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) { int n, m, sh; struct idr_layer *p, *new; - struct idr_layer *pa[MAX_LEVEL]; - int l, id; + int l, id, oid; long bm; id = *starting_id; + restart: p = idp->top; l = idp->layers; pa[l--] = NULL; @@ -117,12 +137,23 @@ static int sub_alloc(struct idr *idp, void *ptr, int *starting_id) if (m == IDR_SIZE) { /* no space available go back to previous layer. */ l++; + oid = id; id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; + + /* if already at the top layer, we need to grow */ if (!(p = pa[l])) { *starting_id = id; return -2; } - continue; + + /* If we need to go up one layer, continue the + * loop; otherwise, restart from the top. + */ + sh = IDR_BITS * (l + 1); + if (oid >> sh == id >> sh) + continue; + else + goto restart; } if (m != n) { sh = IDR_BITS*l; @@ -144,30 +175,13 @@ static int sub_alloc(struct idr *idp, void *ptr, int *starting_id) pa[l--] = p; p = p->ary[m]; } - /* - * We have reached the leaf node, plant the - * users pointer and return the raw id. - */ - p->ary[m] = (struct idr_layer *)ptr; - __set_bit(m, &p->bitmap); - p->count++; - /* - * If this layer is full mark the bit in the layer above - * to show that this part of the radix tree is full. - * This may complete the layer above and require walking - * up the radix tree. - */ - n = id; - while (p->bitmap == IDR_FULL) { - if (!(p = pa[++l])) - break; - n = n >> IDR_BITS; - __set_bit((n & IDR_MASK), &p->bitmap); - } - return(id); + + pa[l] = p; + return id; } -static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id) +static int idr_get_empty_slot(struct idr *idp, int starting_id, + struct idr_layer **pa) { struct idr_layer *p, *new; int layers, v, id; @@ -213,12 +227,31 @@ build_up: } idp->top = p; idp->layers = layers; - v = sub_alloc(idp, ptr, &id); + v = sub_alloc(idp, &id, pa); if (v == -2) goto build_up; return(v); } +static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id) +{ + struct idr_layer *pa[MAX_LEVEL]; + int id; + + id = idr_get_empty_slot(idp, starting_id, pa); + if (id >= 0) { + /* + * Successfully found an empty slot. Install the user + * pointer and mark the slot full. + */ + pa[0]->ary[id & IDR_MASK] = (struct idr_layer *)ptr; + pa[0]->count++; + idr_mark_full(pa, id); + } + + return id; +} + /** * idr_get_new_above - allocate new idr entry above or equal to a start id * @idp: idr handle @@ -358,6 +391,53 @@ void idr_remove(struct idr *idp, int id) EXPORT_SYMBOL(idr_remove); /** + * idr_remove_all - remove all ids from the given idr tree + * @idp: idr handle + * + * idr_destroy() only frees up unused, cached idp_layers, but this + * function will remove all id mappings and leave all idp_layers + * unused. + * + * A typical clean-up sequence for objects stored in an idr tree, will + * use idr_for_each() to free all objects, if necessay, then + * idr_remove_all() to remove all ids, and idr_destroy() to free + * up the cached idr_layers. + */ +void idr_remove_all(struct idr *idp) +{ + int n, id, max, error = 0; + struct idr_layer *p; + struct idr_layer *pa[MAX_LEVEL]; + struct idr_layer **paa = &pa[0]; + + n = idp->layers * IDR_BITS; + p = idp->top; + max = 1 << n; + + id = 0; + while (id < max && !error) { + while (n > IDR_BITS && p) { + n -= IDR_BITS; + *paa++ = p; + p = p->ary[(id >> n) & IDR_MASK]; + } + + id += 1 << n; + while (n < fls(id)) { + if (p) { + memset(p, 0, sizeof *p); + free_layer(idp, p); + } + n += IDR_BITS; + p = *--paa; + } + } + idp->top = NULL; + idp->layers = 0; +} +EXPORT_SYMBOL(idr_remove_all); + +/** * idr_destroy - release all cached layers within an idr tree * idp: idr handle */ @@ -404,6 +484,61 @@ void *idr_find(struct idr *idp, int id) EXPORT_SYMBOL(idr_find); /** + * idr_for_each - iterate through all stored pointers + * @idp: idr handle + * @fn: function to be called for each pointer + * @data: data passed back to callback function + * + * Iterate over the pointers registered with the given idr. The + * callback function will be called for each pointer currently + * registered, passing the id, the pointer and the data pointer passed + * to this function. It is not safe to modify the idr tree while in + * the callback, so functions such as idr_get_new and idr_remove are + * not allowed. + * + * We check the return of @fn each time. If it returns anything other + * than 0, we break out and return that value. + * + * The caller must serialize idr_for_each() vs idr_get_new() and idr_remove(). + */ +int idr_for_each(struct idr *idp, + int (*fn)(int id, void *p, void *data), void *data) +{ + int n, id, max, error = 0; + struct idr_layer *p; + struct idr_layer *pa[MAX_LEVEL]; + struct idr_layer **paa = &pa[0]; + + n = idp->layers * IDR_BITS; + p = idp->top; + max = 1 << n; + + id = 0; + while (id < max) { + while (n > 0 && p) { + n -= IDR_BITS; + *paa++ = p; + p = p->ary[(id >> n) & IDR_MASK]; + } + + if (p) { + error = fn(id, (void *)p, data); + if (error) + break; + } + + id += 1 << n; + while (n < fls(id)) { + n += IDR_BITS; + p = *--paa; + } + } + + return error; +} +EXPORT_SYMBOL(idr_for_each); + +/** * idr_replace - replace pointer for given id * @idp: idr handle * @ptr: pointer you want associated with the id @@ -473,3 +608,248 @@ void idr_init(struct idr *idp) spin_lock_init(&idp->lock); } EXPORT_SYMBOL(idr_init); + + +/* + * IDA - IDR based ID allocator + * + * this is id allocator without id -> pointer translation. Memory + * usage is much lower than full blown idr because each id only + * occupies a bit. ida uses a custom leaf node which contains + * IDA_BITMAP_BITS slots. + * + * 2007-04-25 written by Tejun Heo <htejun@gmail.com> + */ + +static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap) +{ + unsigned long flags; + + if (!ida->free_bitmap) { + spin_lock_irqsave(&ida->idr.lock, flags); + if (!ida->free_bitmap) { + ida->free_bitmap = bitmap; + bitmap = NULL; + } + spin_unlock_irqrestore(&ida->idr.lock, flags); + } + + kfree(bitmap); +} + +/** + * ida_pre_get - reserve resources for ida allocation + * @ida: ida handle + * @gfp_mask: memory allocation flag + * + * This function should be called prior to locking and calling the + * following function. It preallocates enough memory to satisfy the + * worst possible allocation. + * + * If the system is REALLY out of memory this function returns 0, + * otherwise 1. + */ +int ida_pre_get(struct ida *ida, gfp_t gfp_mask) +{ + /* allocate idr_layers */ + if (!idr_pre_get(&ida->idr, gfp_mask)) + return 0; + + /* allocate free_bitmap */ + if (!ida->free_bitmap) { + struct ida_bitmap *bitmap; + + bitmap = kmalloc(sizeof(struct ida_bitmap), gfp_mask); + if (!bitmap) + return 0; + + free_bitmap(ida, bitmap); + } + + return 1; +} +EXPORT_SYMBOL(ida_pre_get); + +/** + * ida_get_new_above - allocate new ID above or equal to a start id + * @ida: ida handle + * @staring_id: id to start search at + * @p_id: pointer to the allocated handle + * + * Allocate new ID above or equal to @ida. It should be called with + * any required locks. + * + * If memory is required, it will return -EAGAIN, you should unlock + * and go back to the ida_pre_get() call. If the ida is full, it will + * return -ENOSPC. + * + * @p_id returns a value in the range 0 ... 0x7fffffff. + */ +int ida_get_new_above(struct ida *ida, int starting_id, int *p_id) +{ + struct idr_layer *pa[MAX_LEVEL]; + struct ida_bitmap *bitmap; + unsigned long flags; + int idr_id = starting_id / IDA_BITMAP_BITS; + int offset = starting_id % IDA_BITMAP_BITS; + int t, id; + + restart: + /* get vacant slot */ + t = idr_get_empty_slot(&ida->idr, idr_id, pa); + if (t < 0) { + if (t == -1) + return -EAGAIN; + else /* will be -3 */ + return -ENOSPC; + } + + if (t * IDA_BITMAP_BITS >= MAX_ID_BIT) + return -ENOSPC; + + if (t != idr_id) + offset = 0; + idr_id = t; + + /* if bitmap isn't there, create a new one */ + bitmap = (void *)pa[0]->ary[idr_id & IDR_MASK]; + if (!bitmap) { + spin_lock_irqsave(&ida->idr.lock, flags); + bitmap = ida->free_bitmap; + ida->free_bitmap = NULL; + spin_unlock_irqrestore(&ida->idr.lock, flags); + + if (!bitmap) + return -EAGAIN; + + memset(bitmap, 0, sizeof(struct ida_bitmap)); + pa[0]->ary[idr_id & IDR_MASK] = (void *)bitmap; + pa[0]->count++; + } + + /* lookup for empty slot */ + t = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, offset); + if (t == IDA_BITMAP_BITS) { + /* no empty slot after offset, continue to the next chunk */ + idr_id++; + offset = 0; + goto restart; + } + + id = idr_id * IDA_BITMAP_BITS + t; + if (id >= MAX_ID_BIT) + return -ENOSPC; + + __set_bit(t, bitmap->bitmap); + if (++bitmap->nr_busy == IDA_BITMAP_BITS) + idr_mark_full(pa, idr_id); + + *p_id = id; + + /* Each leaf node can handle nearly a thousand slots and the + * whole idea of ida is to have small memory foot print. + * Throw away extra resources one by one after each successful + * allocation. + */ + if (ida->idr.id_free_cnt || ida->free_bitmap) { + struct idr_layer *p = alloc_layer(&ida->idr); + if (p) + kmem_cache_free(idr_layer_cache, p); + } + + return 0; +} +EXPORT_SYMBOL(ida_get_new_above); + +/** + * ida_get_new - allocate new ID + * @ida: idr handle + * @p_id: pointer to the allocated handle + * + * Allocate new ID. It should be called with any required locks. + * + * If memory is required, it will return -EAGAIN, you should unlock + * and go back to the idr_pre_get() call. If the idr is full, it will + * return -ENOSPC. + * + * @id returns a value in the range 0 ... 0x7fffffff. + */ +int ida_get_new(struct ida *ida, int *p_id) +{ + return ida_get_new_above(ida, 0, p_id); +} +EXPORT_SYMBOL(ida_get_new); + +/** + * ida_remove - remove the given ID + * @ida: ida handle + * @id: ID to free + */ +void ida_remove(struct ida *ida, int id) +{ + struct idr_layer *p = ida->idr.top; + int shift = (ida->idr.layers - 1) * IDR_BITS; + int idr_id = id / IDA_BITMAP_BITS; + int offset = id % IDA_BITMAP_BITS; + int n; + struct ida_bitmap *bitmap; + + /* clear full bits while looking up the leaf idr_layer */ + while ((shift > 0) && p) { + n = (idr_id >> shift) & IDR_MASK; + __clear_bit(n, &p->bitmap); + p = p->ary[n]; + shift -= IDR_BITS; + } + + if (p == NULL) + goto err; + + n = idr_id & IDR_MASK; + __clear_bit(n, &p->bitmap); + + bitmap = (void *)p->ary[n]; + if (!test_bit(offset, bitmap->bitmap)) + goto err; + + /* update bitmap and remove it if empty */ + __clear_bit(offset, bitmap->bitmap); + if (--bitmap->nr_busy == 0) { + __set_bit(n, &p->bitmap); /* to please idr_remove() */ + idr_remove(&ida->idr, idr_id); + free_bitmap(ida, bitmap); + } + + return; + + err: + printk(KERN_WARNING + "ida_remove called for id=%d which is not allocated.\n", id); +} +EXPORT_SYMBOL(ida_remove); + +/** + * ida_destroy - release all cached layers within an ida tree + * ida: ida handle + */ +void ida_destroy(struct ida *ida) +{ + idr_destroy(&ida->idr); + kfree(ida->free_bitmap); +} +EXPORT_SYMBOL(ida_destroy); + +/** + * ida_init - initialize ida handle + * @ida: ida handle + * + * This function is use to set up the handle (@ida) that you will pass + * to the rest of the functions. + */ +void ida_init(struct ida *ida) +{ + memset(ida, 0, sizeof(struct ida)); + idr_init(&ida->idr); + +} +EXPORT_SYMBOL(ida_init); diff --git a/lib/kobject.c b/lib/kobject.c index ac1520651b9..4b08e0ff95c 100644 --- a/lib/kobject.c +++ b/lib/kobject.c @@ -44,7 +44,7 @@ static int populate_dir(struct kobject * kobj) return error; } -static int create_dir(struct kobject * kobj, struct dentry *shadow_parent) +static int create_dir(struct kobject *kobj, struct sysfs_dirent *shadow_parent) { int error = 0; if (kobject_name(kobj)) { @@ -162,7 +162,7 @@ static void unlink(struct kobject * kobj) * @shadow_parent: sysfs directory to add to. */ -int kobject_shadow_add(struct kobject * kobj, struct dentry *shadow_parent) +int kobject_shadow_add(struct kobject *kobj, struct sysfs_dirent *shadow_parent) { int error = 0; struct kobject * parent; @@ -338,7 +338,7 @@ int kobject_rename(struct kobject * kobj, const char *new_name) /* Note : if we want to send the new name alone, not the full path, * we could probably use kobject_name(kobj); */ - error = sysfs_rename_dir(kobj, kobj->parent->dentry, new_name); + error = sysfs_rename_dir(kobj, kobj->parent->sd, new_name); /* This function is mostly/only used for network interface. * Some hotplug package track interfaces by their name and @@ -361,8 +361,8 @@ out: * @new_name: object's new name */ -int kobject_shadow_rename(struct kobject * kobj, struct dentry *new_parent, - const char *new_name) +int kobject_shadow_rename(struct kobject *kobj, + struct sysfs_dirent *new_parent, const char *new_name) { int error = 0; @@ -597,10 +597,17 @@ int kset_add(struct kset * k) int kset_register(struct kset * k) { + int err; + if (!k) return -EINVAL; + kset_init(k); - return kset_add(k); + err = kset_add(k); + if (err) + return err; + kobject_uevent(&k->kobj, KOBJ_ADD); + return 0; } diff --git a/lib/percpu_counter.c b/lib/percpu_counter.c index 850449080e1..cf22c617baa 100644 --- a/lib/percpu_counter.c +++ b/lib/percpu_counter.c @@ -3,8 +3,17 @@ */ #include <linux/percpu_counter.h> +#include <linux/notifier.h> +#include <linux/mutex.h> +#include <linux/init.h> +#include <linux/cpu.h> #include <linux/module.h> +#ifdef CONFIG_HOTPLUG_CPU +static LIST_HEAD(percpu_counters); +static DEFINE_MUTEX(percpu_counters_lock); +#endif + void percpu_counter_mod(struct percpu_counter *fbc, s32 amount) { long count; @@ -36,7 +45,7 @@ s64 percpu_counter_sum(struct percpu_counter *fbc) spin_lock(&fbc->lock); ret = fbc->count; - for_each_possible_cpu(cpu) { + for_each_online_cpu(cpu) { s32 *pcount = per_cpu_ptr(fbc->counters, cpu); ret += *pcount; } @@ -44,3 +53,60 @@ s64 percpu_counter_sum(struct percpu_counter *fbc) return ret < 0 ? 0 : ret; } EXPORT_SYMBOL(percpu_counter_sum); + +void percpu_counter_init(struct percpu_counter *fbc, s64 amount) +{ + spin_lock_init(&fbc->lock); + fbc->count = amount; + fbc->counters = alloc_percpu(s32); +#ifdef CONFIG_HOTPLUG_CPU + mutex_lock(&percpu_counters_lock); + list_add(&fbc->list, &percpu_counters); + mutex_unlock(&percpu_counters_lock); +#endif +} +EXPORT_SYMBOL(percpu_counter_init); + +void percpu_counter_destroy(struct percpu_counter *fbc) +{ + free_percpu(fbc->counters); +#ifdef CONFIG_HOTPLUG_CPU + mutex_lock(&percpu_counters_lock); + list_del(&fbc->list); + mutex_unlock(&percpu_counters_lock); +#endif +} +EXPORT_SYMBOL(percpu_counter_destroy); + +#ifdef CONFIG_HOTPLUG_CPU +static int __cpuinit percpu_counter_hotcpu_callback(struct notifier_block *nb, + unsigned long action, void *hcpu) +{ + unsigned int cpu; + struct percpu_counter *fbc; + + if (action != CPU_DEAD) + return NOTIFY_OK; + + cpu = (unsigned long)hcpu; + mutex_lock(&percpu_counters_lock); + list_for_each_entry(fbc, &percpu_counters, list) { + s32 *pcount; + + spin_lock(&fbc->lock); + pcount = per_cpu_ptr(fbc->counters, cpu); + fbc->count += *pcount; + *pcount = 0; + spin_unlock(&fbc->lock); + } + mutex_unlock(&percpu_counters_lock); + return NOTIFY_OK; +} + +static int __init percpu_counter_startup(void) +{ + hotcpu_notifier(percpu_counter_hotcpu_callback, 0); + return 0; +} +module_init(percpu_counter_startup); +#endif diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 402eb4eb6b2..9927cca14cb 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -151,6 +151,7 @@ int radix_tree_preload(gfp_t gfp_mask) out: return ret; } +EXPORT_SYMBOL(radix_tree_preload); static inline void tag_set(struct radix_tree_node *node, unsigned int tag, int offset) diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 01729024126..6b6734df6d2 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -135,6 +135,103 @@ static int skip_atoi(const char **s) return i; } +/* Decimal conversion is by far the most typical, and is used + * for /proc and /sys data. This directly impacts e.g. top performance + * with many processes running. We optimize it for speed + * using code from + * http://www.cs.uiowa.edu/~jones/bcd/decimal.html + * (with permission from the author, Douglas W. Jones). */ + +/* Formats correctly any integer in [0,99999]. + * Outputs from one to five digits depending on input. + * On i386 gcc 4.1.2 -O2: ~250 bytes of code. */ +static char* put_dec_trunc(char *buf, unsigned q) +{ + unsigned d3, d2, d1, d0; + d1 = (q>>4) & 0xf; + d2 = (q>>8) & 0xf; + d3 = (q>>12); + + d0 = 6*(d3 + d2 + d1) + (q & 0xf); + q = (d0 * 0xcd) >> 11; + d0 = d0 - 10*q; + *buf++ = d0 + '0'; /* least significant digit */ + d1 = q + 9*d3 + 5*d2 + d1; + if (d1 != 0) { + q = (d1 * 0xcd) >> 11; + d1 = d1 - 10*q; + *buf++ = d1 + '0'; /* next digit */ + + d2 = q + 2*d2; + if ((d2 != 0) || (d3 != 0)) { + q = (d2 * 0xd) >> 7; + d2 = d2 - 10*q; + *buf++ = d2 + '0'; /* next digit */ + + d3 = q + 4*d3; + if (d3 != 0) { + q = (d3 * 0xcd) >> 11; + d3 = d3 - 10*q; + *buf++ = d3 + '0'; /* next digit */ + if (q != 0) + *buf++ = q + '0'; /* most sign. digit */ + } + } + } + return buf; +} +/* Same with if's removed. Always emits five digits */ +static char* put_dec_full(char *buf, unsigned q) +{ + /* BTW, if q is in [0,9999], 8-bit ints will be enough, */ + /* but anyway, gcc produces better code with full-sized ints */ + unsigned d3, d2, d1, d0; + d1 = (q>>4) & 0xf; + d2 = (q>>8) & 0xf; + d3 = (q>>12); + + /* Possible ways to approx. divide by 10 */ + /* gcc -O2 replaces multiply with shifts and adds */ + // (x * 0xcd) >> 11: 11001101 - shorter code than * 0x67 (on i386) + // (x * 0x67) >> 10: 1100111 + // (x * 0x34) >> 9: 110100 - same + // (x * 0x1a) >> 8: 11010 - same + // (x * 0x0d) >> 7: 1101 - same, shortest code (on i386) + + d0 = 6*(d3 + d2 + d1) + (q & 0xf); + q = (d0 * 0xcd) >> 11; + d0 = d0 - 10*q; + *buf++ = d0 + '0'; + d1 = q + 9*d3 + 5*d2 + d1; + q = (d1 * 0xcd) >> 11; + d1 = d1 - 10*q; + *buf++ = d1 + '0'; + + d2 = q + 2*d2; + q = (d2 * 0xd) >> 7; + d2 = d2 - 10*q; + *buf++ = d2 + '0'; + + d3 = q + 4*d3; + q = (d3 * 0xcd) >> 11; /* - shorter code */ + /* q = (d3 * 0x67) >> 10; - would also work */ + d3 = d3 - 10*q; + *buf++ = d3 + '0'; + *buf++ = q + '0'; + return buf; +} +/* No inlining helps gcc to use registers better */ +static noinline char* put_dec(char *buf, unsigned long long num) +{ + while (1) { + unsigned rem; + if (num < 100000) + return put_dec_trunc(buf, num); + rem = do_div(num, 100000); + buf = put_dec_full(buf, rem); + } +} + #define ZEROPAD 1 /* pad with zero */ #define SIGN 2 /* unsigned/signed long */ #define PLUS 4 /* show plus */ @@ -143,12 +240,14 @@ static int skip_atoi(const char **s) #define SPECIAL 32 /* 0x */ #define LARGE 64 /* use 'ABCDEF' instead of 'abcdef' */ -static char * number(char * buf, char * end, unsigned long long num, int base, int size, int precision, int type) +static char *number(char *buf, char *end, unsigned long long num, int base, int size, int precision, int type) { - char c,sign,tmp[66]; + char sign,tmp[66]; const char *digits; - static const char small_digits[] = "0123456789abcdefghijklmnopqrstuvwxyz"; - static const char large_digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + /* we are called with base 8, 10 or 16, only, thus don't need "g..." */ + static const char small_digits[] = "0123456789abcdefx"; /* "ghijklmnopqrstuvwxyz"; */ + static const char large_digits[] = "0123456789ABCDEFX"; /* "GHIJKLMNOPQRSTUVWXYZ"; */ + int need_pfx = ((type & SPECIAL) && base != 10); int i; digits = (type & LARGE) ? large_digits : small_digits; @@ -156,7 +255,6 @@ static char * number(char * buf, char * end, unsigned long long num, int base, i type &= ~ZEROPAD; if (base < 2 || base > 36) return NULL; - c = (type & ZEROPAD) ? '0' : ' '; sign = 0; if (type & SIGN) { if ((signed long long) num < 0) { @@ -171,64 +269,85 @@ static char * number(char * buf, char * end, unsigned long long num, int base, i size--; } } - if (type & SPECIAL) { + if (need_pfx) { + size--; if (base == 16) - size -= 2; - else if (base == 8) size--; } + + /* generate full string in tmp[], in reverse order */ i = 0; if (num == 0) - tmp[i++]='0'; - else while (num != 0) + tmp[i++] = '0'; + /* Generic code, for any base: + else do { tmp[i++] = digits[do_div(num,base)]; + } while (num != 0); + */ + else if (base != 10) { /* 8 or 16 */ + int mask = base - 1; + int shift = 3; + if (base == 16) shift = 4; + do { + tmp[i++] = digits[((unsigned char)num) & mask]; + num >>= shift; + } while (num); + } else { /* base 10 */ + i = put_dec(tmp, num) - tmp; + } + + /* printing 100 using %2d gives "100", not "00" */ if (i > precision) precision = i; + /* leading space padding */ size -= precision; - if (!(type&(ZEROPAD+LEFT))) { - while(size-->0) { + if (!(type & (ZEROPAD+LEFT))) { + while(--size >= 0) { if (buf < end) *buf = ' '; ++buf; } } + /* sign */ if (sign) { if (buf < end) *buf = sign; ++buf; } - if (type & SPECIAL) { - if (base==8) { - if (buf < end) - *buf = '0'; - ++buf; - } else if (base==16) { - if (buf < end) - *buf = '0'; - ++buf; + /* "0x" / "0" prefix */ + if (need_pfx) { + if (buf < end) + *buf = '0'; + ++buf; + if (base == 16) { if (buf < end) - *buf = digits[33]; + *buf = digits[16]; /* for arbitrary base: digits[33]; */ ++buf; } } + /* zero or space padding */ if (!(type & LEFT)) { - while (size-- > 0) { + char c = (type & ZEROPAD) ? '0' : ' '; + while (--size >= 0) { if (buf < end) *buf = c; ++buf; } } - while (i < precision--) { + /* hmm even more zero padding? */ + while (i <= --precision) { if (buf < end) *buf = '0'; ++buf; } - while (i-- > 0) { + /* actual digits of result */ + while (--i >= 0) { if (buf < end) *buf = tmp[i]; ++buf; } - while (size-- > 0) { + /* trailing space padding */ + while (--size >= 0) { if (buf < end) *buf = ' '; ++buf; @@ -276,7 +395,7 @@ int vsnprintf(char *buf, size_t size, const char *fmt, va_list args) used for unknown buffer sizes. */ if (unlikely((int) size < 0)) { /* There can be only one.. */ - static int warn = 1; + static char warn = 1; WARN_ON(warn); warn = 0; return 0; |