diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Kconfig | 13 | ||||
| -rw-r--r-- | lib/Kconfig.debug | 13 | ||||
| -rw-r--r-- | lib/Makefile | 1 | ||||
| -rw-r--r-- | lib/audit.c | 15 | ||||
| -rw-r--r-- | lib/clz_ctz.c | 7 | ||||
| -rw-r--r-- | lib/compat_audit.c | 50 | ||||
| -rw-r--r-- | lib/decompress.c | 3 | ||||
| -rw-r--r-- | lib/decompress_inflate.c | 1 | ||||
| -rw-r--r-- | lib/devres.c | 26 | ||||
| -rw-r--r-- | lib/dump_stack.c | 4 | ||||
| -rw-r--r-- | lib/idr.c | 24 | ||||
| -rw-r--r-- | lib/iomap.c | 4 | ||||
| -rw-r--r-- | lib/kobject_uevent.c | 48 | ||||
| -rw-r--r-- | lib/nlattr.c | 10 | ||||
| -rw-r--r-- | lib/percpu_counter.c | 2 | ||||
| -rw-r--r-- | lib/radix-tree.c | 385 | ||||
| -rw-r--r-- | lib/random32.c | 76 | ||||
| -rw-r--r-- | lib/smp_processor_id.c | 18 | ||||
| -rw-r--r-- | lib/syscall.c | 1 | ||||
| -rw-r--r-- | lib/vsprintf.c | 45 |
20 files changed, 410 insertions, 336 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index 991c98bc4a3..4771fb3f4da 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -182,6 +182,15 @@ config AUDIT_GENERIC depends on AUDIT && !AUDIT_ARCH default y +config AUDIT_ARCH_COMPAT_GENERIC + bool + default n + +config AUDIT_COMPAT_GENERIC + bool + depends on AUDIT_GENERIC && AUDIT_ARCH_COMPAT_GENERIC && COMPAT + default y + config RANDOM32_SELFTEST bool "PRNG perform self test on init" default n @@ -342,9 +351,9 @@ config HAS_IOMEM select GENERIC_IO default y -config HAS_IOPORT +config HAS_IOPORT_MAP boolean - depends on HAS_IOMEM && !NO_IOPORT + depends on HAS_IOMEM && !NO_IOPORT_MAP default y config HAS_DMA diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index fc77167a7e4..99c8bfee1b0 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -505,8 +505,7 @@ config DEBUG_VM_RB bool "Debug VM red-black trees" depends on DEBUG_VM help - Enable this to turn on more extended checks in the virtual-memory - system that may impact performance. + Enable VM red-black tree debugging information and extra validations. If unsure, say N. @@ -1045,16 +1044,6 @@ config DEBUG_BUGVERBOSE of the BUG call as well as the EIP and oops trace. This aids debugging but costs about 70-100K of memory. -config DEBUG_WRITECOUNT - bool "Debug filesystem writers count" - depends on DEBUG_KERNEL - help - Enable this to catch wrong use of the writers count in struct - vfsmount. This will increase the size of each file struct by - 32 bits. - - If unsure, say N. - config DEBUG_LIST bool "Debug linked list manipulation" depends on DEBUG_KERNEL diff --git a/lib/Makefile b/lib/Makefile index 48140e3ba73..0cd7b68e138 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -96,6 +96,7 @@ obj-$(CONFIG_TEXTSEARCH_BM) += ts_bm.o obj-$(CONFIG_TEXTSEARCH_FSM) += ts_fsm.o obj-$(CONFIG_SMP) += percpu_counter.o obj-$(CONFIG_AUDIT_GENERIC) += audit.o +obj-$(CONFIG_AUDIT_COMPAT_GENERIC) += compat_audit.o obj-$(CONFIG_SWIOTLB) += swiotlb.o obj-$(CONFIG_IOMMU_HELPER) += iommu-helper.o diff --git a/lib/audit.c b/lib/audit.c index 76bbed4a20e..1d726a22565 100644 --- a/lib/audit.c +++ b/lib/audit.c @@ -30,11 +30,17 @@ static unsigned signal_class[] = { int audit_classify_arch(int arch) { - return 0; + if (audit_is_compat(arch)) + return 1; + else + return 0; } int audit_classify_syscall(int abi, unsigned syscall) { + if (audit_is_compat(abi)) + return audit_classify_compat_syscall(abi, syscall); + switch(syscall) { #ifdef __NR_open case __NR_open: @@ -57,6 +63,13 @@ int audit_classify_syscall(int abi, unsigned syscall) static int __init audit_classes_init(void) { +#ifdef CONFIG_AUDIT_COMPAT_GENERIC + audit_register_class(AUDIT_CLASS_WRITE_32, compat_write_class); + audit_register_class(AUDIT_CLASS_READ_32, compat_read_class); + audit_register_class(AUDIT_CLASS_DIR_WRITE_32, compat_dir_class); + audit_register_class(AUDIT_CLASS_CHATTR_32, compat_chattr_class); + audit_register_class(AUDIT_CLASS_SIGNAL_32, compat_signal_class); +#endif audit_register_class(AUDIT_CLASS_WRITE, write_class); audit_register_class(AUDIT_CLASS_READ, read_class); audit_register_class(AUDIT_CLASS_DIR_WRITE, dir_class); diff --git a/lib/clz_ctz.c b/lib/clz_ctz.c index a8f8379eb49..2e11e48446a 100644 --- a/lib/clz_ctz.c +++ b/lib/clz_ctz.c @@ -6,6 +6,9 @@ * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License version 2 as * published by the Free Software Foundation. + * The functions in this file aren't called directly, but are required by + * GCC builtins such as __builtin_ctz, and therefore they can't be removed + * despite appearing unreferenced in kernel source. * * __c[lt]z[sd]i2 can be overridden by linking arch-specific versions. */ @@ -13,18 +16,22 @@ #include <linux/export.h> #include <linux/kernel.h> +int __weak __ctzsi2(int val); int __weak __ctzsi2(int val) { return __ffs(val); } EXPORT_SYMBOL(__ctzsi2); +int __weak __clzsi2(int val); int __weak __clzsi2(int val) { return 32 - fls(val); } EXPORT_SYMBOL(__clzsi2); +int __weak __clzdi2(long val); +int __weak __ctzdi2(long val); #if BITS_PER_LONG == 32 int __weak __clzdi2(long val) diff --git a/lib/compat_audit.c b/lib/compat_audit.c new file mode 100644 index 00000000000..873f75b640a --- /dev/null +++ b/lib/compat_audit.c @@ -0,0 +1,50 @@ +#include <linux/init.h> +#include <linux/types.h> +#include <asm/unistd32.h> + +unsigned compat_dir_class[] = { +#include <asm-generic/audit_dir_write.h> +~0U +}; + +unsigned compat_read_class[] = { +#include <asm-generic/audit_read.h> +~0U +}; + +unsigned compat_write_class[] = { +#include <asm-generic/audit_write.h> +~0U +}; + +unsigned compat_chattr_class[] = { +#include <asm-generic/audit_change_attr.h> +~0U +}; + +unsigned compat_signal_class[] = { +#include <asm-generic/audit_signal.h> +~0U +}; + +int audit_classify_compat_syscall(int abi, unsigned syscall) +{ + switch (syscall) { +#ifdef __NR_open + case __NR_open: + return 2; +#endif +#ifdef __NR_openat + case __NR_openat: + return 3; +#endif +#ifdef __NR_socketcall + case __NR_socketcall: + return 4; +#endif + case __NR_execve: + return 5; + default: + return 1; + } +} diff --git a/lib/decompress.c b/lib/decompress.c index 4d1cd0397aa..86069d74c06 100644 --- a/lib/decompress.c +++ b/lib/decompress.c @@ -16,6 +16,7 @@ #include <linux/types.h> #include <linux/string.h> #include <linux/init.h> +#include <linux/printk.h> #ifndef CONFIG_DECOMPRESS_GZIP # define gunzip NULL @@ -61,6 +62,8 @@ decompress_fn __init decompress_method(const unsigned char *inbuf, int len, if (len < 2) return NULL; /* Need at least this much... */ + pr_debug("Compressed data magic: %#.2x %#.2x\n", inbuf[0], inbuf[1]); + for (cf = compressed_formats; cf->name; cf++) { if (!memcmp(inbuf, cf->magic, 2)) break; diff --git a/lib/decompress_inflate.c b/lib/decompress_inflate.c index d619b28c456..0edfd742a15 100644 --- a/lib/decompress_inflate.c +++ b/lib/decompress_inflate.c @@ -19,6 +19,7 @@ #include "zlib_inflate/inflate.h" #include "zlib_inflate/infutil.h" +#include <linux/decompress/inflate.h> #endif /* STATIC */ diff --git a/lib/devres.c b/lib/devres.c index 823533138fa..f562bf6ff71 100644 --- a/lib/devres.c +++ b/lib/devres.c @@ -81,11 +81,13 @@ EXPORT_SYMBOL(devm_ioremap_nocache); void devm_iounmap(struct device *dev, void __iomem *addr) { WARN_ON(devres_destroy(dev, devm_ioremap_release, devm_ioremap_match, - (void *)addr)); + (__force void *)addr)); iounmap(addr); } EXPORT_SYMBOL(devm_iounmap); +#define IOMEM_ERR_PTR(err) (__force void __iomem *)ERR_PTR(err) + /** * devm_ioremap_resource() - check, request region, and ioremap resource * @dev: generic device to handle the resource for @@ -114,7 +116,7 @@ void __iomem *devm_ioremap_resource(struct device *dev, struct resource *res) if (!res || resource_type(res) != IORESOURCE_MEM) { dev_err(dev, "invalid resource\n"); - return ERR_PTR(-EINVAL); + return IOMEM_ERR_PTR(-EINVAL); } size = resource_size(res); @@ -122,7 +124,7 @@ void __iomem *devm_ioremap_resource(struct device *dev, struct resource *res) if (!devm_request_mem_region(dev, res->start, size, name)) { dev_err(dev, "can't request region for resource %pR\n", res); - return ERR_PTR(-EBUSY); + return IOMEM_ERR_PTR(-EBUSY); } if (res->flags & IORESOURCE_CACHEABLE) @@ -133,7 +135,7 @@ void __iomem *devm_ioremap_resource(struct device *dev, struct resource *res) if (!dest_ptr) { dev_err(dev, "ioremap failed for resource %pR\n", res); devm_release_mem_region(dev, res->start, size); - dest_ptr = ERR_PTR(-ENOMEM); + dest_ptr = IOMEM_ERR_PTR(-ENOMEM); } return dest_ptr; @@ -155,12 +157,12 @@ EXPORT_SYMBOL(devm_ioremap_resource); * if (!base) * return -EADDRNOTAVAIL; */ -void __iomem *devm_request_and_ioremap(struct device *device, +void __iomem *devm_request_and_ioremap(struct device *dev, struct resource *res) { void __iomem *dest_ptr; - dest_ptr = devm_ioremap_resource(device, res); + dest_ptr = devm_ioremap_resource(dev, res); if (IS_ERR(dest_ptr)) return NULL; @@ -168,7 +170,7 @@ void __iomem *devm_request_and_ioremap(struct device *device, } EXPORT_SYMBOL(devm_request_and_ioremap); -#ifdef CONFIG_HAS_IOPORT +#ifdef CONFIG_HAS_IOPORT_MAP /* * Generic iomap devres */ @@ -192,7 +194,7 @@ static int devm_ioport_map_match(struct device *dev, void *res, * Managed ioport_map(). Map is automatically unmapped on driver * detach. */ -void __iomem * devm_ioport_map(struct device *dev, unsigned long port, +void __iomem *devm_ioport_map(struct device *dev, unsigned long port, unsigned int nr) { void __iomem **ptr, *addr; @@ -224,10 +226,10 @@ void devm_ioport_unmap(struct device *dev, void __iomem *addr) { ioport_unmap(addr); WARN_ON(devres_destroy(dev, devm_ioport_map_release, - devm_ioport_map_match, (void *)addr)); + devm_ioport_map_match, (__force void *)addr)); } EXPORT_SYMBOL(devm_ioport_unmap); -#endif /* CONFIG_HAS_IOPORT */ +#endif /* CONFIG_HAS_IOPORT_MAP */ #ifdef CONFIG_PCI /* @@ -263,7 +265,7 @@ static void pcim_iomap_release(struct device *gendev, void *res) * be safely called without context and guaranteed to succed once * allocated. */ -void __iomem * const * pcim_iomap_table(struct pci_dev *pdev) +void __iomem * const *pcim_iomap_table(struct pci_dev *pdev) { struct pcim_iomap_devres *dr, *new_dr; @@ -288,7 +290,7 @@ EXPORT_SYMBOL(pcim_iomap_table); * Managed pci_iomap(). Map is automatically unmapped on driver * detach. */ -void __iomem * pcim_iomap(struct pci_dev *pdev, int bar, unsigned long maxlen) +void __iomem *pcim_iomap(struct pci_dev *pdev, int bar, unsigned long maxlen) { void __iomem **tbl; diff --git a/lib/dump_stack.c b/lib/dump_stack.c index f23b63f0a1c..6745c6230db 100644 --- a/lib/dump_stack.c +++ b/lib/dump_stack.c @@ -23,7 +23,7 @@ static void __dump_stack(void) #ifdef CONFIG_SMP static atomic_t dump_lock = ATOMIC_INIT(-1); -asmlinkage void dump_stack(void) +asmlinkage __visible void dump_stack(void) { int was_locked; int old; @@ -55,7 +55,7 @@ retry: preempt_enable(); } #else -asmlinkage void dump_stack(void) +asmlinkage __visible void dump_stack(void) { __dump_stack(); } diff --git a/lib/idr.c b/lib/idr.c index 1ba4956bfbf..2642fa8e424 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -196,7 +196,7 @@ static void idr_mark_full(struct idr_layer **pa, int id) } } -int __idr_pre_get(struct idr *idp, gfp_t gfp_mask) +static int __idr_pre_get(struct idr *idp, gfp_t gfp_mask) { while (idp->id_free_cnt < MAX_IDR_FREE) { struct idr_layer *new; @@ -207,7 +207,6 @@ int __idr_pre_get(struct idr *idp, gfp_t gfp_mask) } return 1; } -EXPORT_SYMBOL(__idr_pre_get); /** * sub_alloc - try to allocate an id without growing the tree depth @@ -374,20 +373,6 @@ static void idr_fill_slot(struct idr *idr, void *ptr, int id, idr_mark_full(pa, id); } -int __idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id) -{ - struct idr_layer *pa[MAX_IDR_LEVEL + 1]; - int rv; - - rv = idr_get_empty_slot(idp, starting_id, pa, 0, idp); - if (rv < 0) - return rv == -ENOMEM ? -EAGAIN : rv; - - idr_fill_slot(idp, ptr, rv, pa); - *id = rv; - return 0; -} -EXPORT_SYMBOL(__idr_get_new_above); /** * idr_preload - preload for idr_alloc() @@ -548,7 +533,7 @@ static void sub_remove(struct idr *idp, int shift, int id) n = id & IDR_MASK; if (likely(p != NULL && test_bit(n, p->bitmap))) { __clear_bit(n, p->bitmap); - rcu_assign_pointer(p->ary[n], NULL); + RCU_INIT_POINTER(p->ary[n], NULL); to_free = NULL; while(*paa && ! --((**paa)->count)){ if (to_free) @@ -607,7 +592,7 @@ void idr_remove(struct idr *idp, int id) } EXPORT_SYMBOL(idr_remove); -void __idr_remove_all(struct idr *idp) +static void __idr_remove_all(struct idr *idp) { int n, id, max; int bt_mask; @@ -617,7 +602,7 @@ void __idr_remove_all(struct idr *idp) n = idp->layers * IDR_BITS; p = idp->top; - rcu_assign_pointer(idp->top, NULL); + RCU_INIT_POINTER(idp->top, NULL); max = idr_max(idp->layers); id = 0; @@ -640,7 +625,6 @@ void __idr_remove_all(struct idr *idp) } idp->layers = 0; } -EXPORT_SYMBOL(__idr_remove_all); /** * idr_destroy - release all cached layers within an idr tree diff --git a/lib/iomap.c b/lib/iomap.c index 2c08f36862e..fc3dcb4b238 100644 --- a/lib/iomap.c +++ b/lib/iomap.c @@ -224,7 +224,7 @@ EXPORT_SYMBOL(iowrite8_rep); EXPORT_SYMBOL(iowrite16_rep); EXPORT_SYMBOL(iowrite32_rep); -#ifdef CONFIG_HAS_IOPORT +#ifdef CONFIG_HAS_IOPORT_MAP /* Create a virtual mapping cookie for an IO port range */ void __iomem *ioport_map(unsigned long port, unsigned int nr) { @@ -239,7 +239,7 @@ void ioport_unmap(void __iomem *addr) } EXPORT_SYMBOL(ioport_map); EXPORT_SYMBOL(ioport_unmap); -#endif /* CONFIG_HAS_IOPORT */ +#endif /* CONFIG_HAS_IOPORT_MAP */ #ifdef CONFIG_PCI /* Hide the details if this is a MMIO or PIO address space and just do what diff --git a/lib/kobject_uevent.c b/lib/kobject_uevent.c index 5f72767ddd9..9ebf9e20de5 100644 --- a/lib/kobject_uevent.c +++ b/lib/kobject_uevent.c @@ -29,7 +29,9 @@ u64 uevent_seqnum; +#ifdef CONFIG_UEVENT_HELPER char uevent_helper[UEVENT_HELPER_PATH_LEN] = CONFIG_UEVENT_HELPER_PATH; +#endif #ifdef CONFIG_NET struct uevent_sock { struct list_head list; @@ -109,6 +111,7 @@ static int kobj_bcast_filter(struct sock *dsk, struct sk_buff *skb, void *data) } #endif +#ifdef CONFIG_UEVENT_HELPER static int kobj_usermode_filter(struct kobject *kobj) { const struct kobj_ns_type_operations *ops; @@ -124,6 +127,31 @@ static int kobj_usermode_filter(struct kobject *kobj) return 0; } +static int init_uevent_argv(struct kobj_uevent_env *env, const char *subsystem) +{ + int len; + + len = strlcpy(&env->buf[env->buflen], subsystem, + sizeof(env->buf) - env->buflen); + if (len >= (sizeof(env->buf) - env->buflen)) { + WARN(1, KERN_ERR "init_uevent_argv: buffer size too small\n"); + return -ENOMEM; + } + + env->argv[0] = uevent_helper; + env->argv[1] = &env->buf[env->buflen]; + env->argv[2] = NULL; + + env->buflen += len + 1; + return 0; +} + +static void cleanup_uevent_env(struct subprocess_info *info) +{ + kfree(info->data); +} +#endif + /** * kobject_uevent_env - send an uevent with environmental data * @@ -299,13 +327,11 @@ int kobject_uevent_env(struct kobject *kobj, enum kobject_action action, #endif mutex_unlock(&uevent_sock_mutex); +#ifdef CONFIG_UEVENT_HELPER /* call uevent_helper, usually only enabled during early boot */ if (uevent_helper[0] && !kobj_usermode_filter(kobj)) { - char *argv [3]; + struct subprocess_info *info; - argv [0] = uevent_helper; - argv [1] = (char *)subsystem; - argv [2] = NULL; retval = add_uevent_var(env, "HOME=/"); if (retval) goto exit; @@ -313,10 +339,20 @@ int kobject_uevent_env(struct kobject *kobj, enum kobject_action action, "PATH=/sbin:/bin:/usr/sbin:/usr/bin"); if (retval) goto exit; + retval = init_uevent_argv(env, subsystem); + if (retval) + goto exit; - retval = call_usermodehelper(argv[0], argv, - env->envp, UMH_WAIT_EXEC); + retval = -ENOMEM; + info = call_usermodehelper_setup(env->argv[0], env->argv, + env->envp, GFP_KERNEL, + NULL, cleanup_uevent_env, env); + if (info) { + retval = call_usermodehelper_exec(info, UMH_NO_WAIT); + env = NULL; /* freed by cleanup_uevent_env */ + } } +#endif exit: kfree(devpath); diff --git a/lib/nlattr.c b/lib/nlattr.c index 18eca7809b0..fc6754720ce 100644 --- a/lib/nlattr.c +++ b/lib/nlattr.c @@ -303,9 +303,15 @@ int nla_memcmp(const struct nlattr *nla, const void *data, */ int nla_strcmp(const struct nlattr *nla, const char *str) { - int len = strlen(str) + 1; - int d = nla_len(nla) - len; + int len = strlen(str); + char *buf = nla_data(nla); + int attrlen = nla_len(nla); + int d; + if (attrlen > 0 && buf[attrlen - 1] == '\0') + attrlen--; + + d = attrlen - len; if (d == 0) d = memcmp(nla_data(nla), str, len); diff --git a/lib/percpu_counter.c b/lib/percpu_counter.c index 8280a5dd172..7dd33577b90 100644 --- a/lib/percpu_counter.c +++ b/lib/percpu_counter.c @@ -169,7 +169,7 @@ static int percpu_counter_hotcpu_callback(struct notifier_block *nb, struct percpu_counter *fbc; compute_batch_value(); - if (action != CPU_DEAD) + if (action != CPU_DEAD && action != CPU_DEAD_FROZEN) return NOTIFY_OK; cpu = (unsigned long)hcpu; diff --git a/lib/radix-tree.c b/lib/radix-tree.c index bd4a8dfdf0b..9599aa72d7a 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -35,33 +35,6 @@ #include <linux/hardirq.h> /* in_interrupt() */ -#ifdef __KERNEL__ -#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) -#else -#define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ -#endif - -#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) -#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) - -#define RADIX_TREE_TAG_LONGS \ - ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG) - -struct radix_tree_node { - unsigned int height; /* Height from the bottom */ - unsigned int count; - union { - struct radix_tree_node *parent; /* Used when ascending tree */ - struct rcu_head rcu_head; /* Used when freeing node */ - }; - void __rcu *slots[RADIX_TREE_MAP_SIZE]; - unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; -}; - -#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) -#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \ - RADIX_TREE_MAP_SHIFT)) - /* * The height_to_maxindex array needs to be one deeper than the maximum * path as height 0 holds only 1 entry. @@ -369,7 +342,8 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) /* Increase the height. */ newheight = root->height+1; - node->height = newheight; + BUG_ON(newheight & ~RADIX_TREE_HEIGHT_MASK); + node->path = newheight; node->count = 1; node->parent = NULL; slot = root->rnode; @@ -387,23 +361,28 @@ out: } /** - * radix_tree_insert - insert into a radix tree + * __radix_tree_create - create a slot in a radix tree * @root: radix tree root * @index: index key - * @item: item to insert + * @nodep: returns node + * @slotp: returns slot * - * Insert an item into the radix tree at position @index. + * Create, if necessary, and return the node and slot for an item + * at position @index in the radix tree @root. + * + * Until there is more than one item in the tree, no nodes are + * allocated and @root->rnode is used as a direct slot instead of + * pointing to a node, in which case *@nodep will be NULL. + * + * Returns -ENOMEM, or 0 for success. */ -int radix_tree_insert(struct radix_tree_root *root, - unsigned long index, void *item) +int __radix_tree_create(struct radix_tree_root *root, unsigned long index, + struct radix_tree_node **nodep, void ***slotp) { struct radix_tree_node *node = NULL, *slot; - unsigned int height, shift; - int offset; + unsigned int height, shift, offset; int error; - BUG_ON(radix_tree_is_indirect_ptr(item)); - /* Make sure the tree is high enough. */ if (index > radix_tree_maxindex(root->height)) { error = radix_tree_extend(root, index); @@ -422,11 +401,12 @@ int radix_tree_insert(struct radix_tree_root *root, /* Have to add a child node. */ if (!(slot = radix_tree_node_alloc(root))) return -ENOMEM; - slot->height = height; + slot->path = height; slot->parent = node; if (node) { rcu_assign_pointer(node->slots[offset], slot); node->count++; + slot->path |= offset << RADIX_TREE_HEIGHT_SHIFT; } else rcu_assign_pointer(root->rnode, ptr_to_indirect(slot)); } @@ -439,16 +419,42 @@ int radix_tree_insert(struct radix_tree_root *root, height--; } - if (slot != NULL) + if (nodep) + *nodep = node; + if (slotp) + *slotp = node ? node->slots + offset : (void **)&root->rnode; + return 0; +} + +/** + * radix_tree_insert - insert into a radix tree + * @root: radix tree root + * @index: index key + * @item: item to insert + * + * Insert an item into the radix tree at position @index. + */ +int radix_tree_insert(struct radix_tree_root *root, + unsigned long index, void *item) +{ + struct radix_tree_node *node; + void **slot; + int error; + + BUG_ON(radix_tree_is_indirect_ptr(item)); + + error = __radix_tree_create(root, index, &node, &slot); + if (error) + return error; + if (*slot != NULL) return -EEXIST; + rcu_assign_pointer(*slot, item); if (node) { node->count++; - rcu_assign_pointer(node->slots[offset], item); - BUG_ON(tag_get(node, 0, offset)); - BUG_ON(tag_get(node, 1, offset)); + BUG_ON(tag_get(node, 0, index & RADIX_TREE_MAP_MASK)); + BUG_ON(tag_get(node, 1, index & RADIX_TREE_MAP_MASK)); } else { - rcu_assign_pointer(root->rnode, item); BUG_ON(root_tag_get(root, 0)); BUG_ON(root_tag_get(root, 1)); } @@ -457,15 +463,26 @@ int radix_tree_insert(struct radix_tree_root *root, } EXPORT_SYMBOL(radix_tree_insert); -/* - * is_slot == 1 : search for the slot. - * is_slot == 0 : search for the node. +/** + * __radix_tree_lookup - lookup an item in a radix tree + * @root: radix tree root + * @index: index key + * @nodep: returns node + * @slotp: returns slot + * + * Lookup and return the item at position @index in the radix + * tree @root. + * + * Until there is more than one item in the tree, no nodes are + * allocated and @root->rnode is used as a direct slot instead of + * pointing to a node, in which case *@nodep will be NULL. */ -static void *radix_tree_lookup_element(struct radix_tree_root *root, - unsigned long index, int is_slot) +void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index, + struct radix_tree_node **nodep, void ***slotp) { + struct radix_tree_node *node, *parent; unsigned int height, shift; - struct radix_tree_node *node, **slot; + void **slot; node = rcu_dereference_raw(root->rnode); if (node == NULL) @@ -474,19 +491,24 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root, if (!radix_tree_is_indirect_ptr(node)) { if (index > 0) return NULL; - return is_slot ? (void *)&root->rnode : node; + + if (nodep) + *nodep = NULL; + if (slotp) + *slotp = (void **)&root->rnode; + return node; } node = indirect_to_ptr(node); - height = node->height; + height = node->path & RADIX_TREE_HEIGHT_MASK; if (index > radix_tree_maxindex(height)) return NULL; shift = (height-1) * RADIX_TREE_MAP_SHIFT; do { - slot = (struct radix_tree_node **) - (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); + parent = node; + slot = node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK); node = rcu_dereference_raw(*slot); if (node == NULL) return NULL; @@ -495,7 +517,11 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root, height--; } while (height > 0); - return is_slot ? (void *)slot : indirect_to_ptr(node); + if (nodep) + *nodep = parent; + if (slotp) + *slotp = slot; + return node; } /** @@ -513,7 +539,11 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root, */ void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) { - return (void **)radix_tree_lookup_element(root, index, 1); + void **slot; + + if (!__radix_tree_lookup(root, index, NULL, &slot)) + return NULL; + return slot; } EXPORT_SYMBOL(radix_tree_lookup_slot); @@ -531,7 +561,7 @@ EXPORT_SYMBOL(radix_tree_lookup_slot); */ void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) { - return radix_tree_lookup_element(root, index, 0); + return __radix_tree_lookup(root, index, NULL, NULL); } EXPORT_SYMBOL(radix_tree_lookup); @@ -676,7 +706,7 @@ int radix_tree_tag_get(struct radix_tree_root *root, return (index == 0); node = indirect_to_ptr(node); - height = node->height; + height = node->path & RADIX_TREE_HEIGHT_MASK; if (index > radix_tree_maxindex(height)) return 0; @@ -713,7 +743,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root, { unsigned shift, tag = flags & RADIX_TREE_ITER_TAG_MASK; struct radix_tree_node *rnode, *node; - unsigned long index, offset; + unsigned long index, offset, height; if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag)) return NULL; @@ -744,7 +774,8 @@ void **radix_tree_next_chunk(struct radix_tree_root *root, return NULL; restart: - shift = (rnode->height - 1) * RADIX_TREE_MAP_SHIFT; + height = rnode->path & RADIX_TREE_HEIGHT_MASK; + shift = (height - 1) * RADIX_TREE_MAP_SHIFT; offset = index >> shift; /* Index outside of the tree */ @@ -946,81 +977,6 @@ next: } EXPORT_SYMBOL(radix_tree_range_tag_if_tagged); - -/** - * radix_tree_next_hole - find the next hole (not-present entry) - * @root: tree root - * @index: index key - * @max_scan: maximum range to search - * - * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest - * indexed hole. - * - * Returns: the index of the hole if found, otherwise returns an index - * outside of the set specified (in which case 'return - index >= max_scan' - * will be true). In rare cases of index wrap-around, 0 will be returned. - * - * radix_tree_next_hole may be called under rcu_read_lock. However, like - * radix_tree_gang_lookup, this will not atomically search a snapshot of - * the tree at a single point in time. For example, if a hole is created - * at index 5, then subsequently a hole is created at index 10, - * radix_tree_next_hole covering both indexes may return 10 if called - * under rcu_read_lock. - */ -unsigned long radix_tree_next_hole(struct radix_tree_root *root, - unsigned long index, unsigned long max_scan) -{ - unsigned long i; - - for (i = 0; i < max_scan; i++) { - if (!radix_tree_lookup(root, index)) - break; - index++; - if (index == 0) - break; - } - - return index; -} -EXPORT_SYMBOL(radix_tree_next_hole); - -/** - * radix_tree_prev_hole - find the prev hole (not-present entry) - * @root: tree root - * @index: index key - * @max_scan: maximum range to search - * - * Search backwards in the range [max(index-max_scan+1, 0), index] - * for the first hole. - * - * Returns: the index of the hole if found, otherwise returns an index - * outside of the set specified (in which case 'index - return >= max_scan' - * will be true). In rare cases of wrap-around, ULONG_MAX will be returned. - * - * radix_tree_next_hole may be called under rcu_read_lock. However, like - * radix_tree_gang_lookup, this will not atomically search a snapshot of - * the tree at a single point in time. For example, if a hole is created - * at index 10, then subsequently a hole is created at index 5, - * radix_tree_prev_hole covering both indexes may return 5 if called under - * rcu_read_lock. - */ -unsigned long radix_tree_prev_hole(struct radix_tree_root *root, - unsigned long index, unsigned long max_scan) -{ - unsigned long i; - - for (i = 0; i < max_scan; i++) { - if (!radix_tree_lookup(root, index)) - break; - index--; - if (index == ULONG_MAX) - break; - } - - return index; -} -EXPORT_SYMBOL(radix_tree_prev_hole); - /** * radix_tree_gang_lookup - perform multiple lookup on a radix tree * @root: radix tree root @@ -1189,7 +1145,7 @@ static unsigned long __locate(struct radix_tree_node *slot, void *item, unsigned int shift, height; unsigned long i; - height = slot->height; + height = slot->path & RADIX_TREE_HEIGHT_MASK; shift = (height-1) * RADIX_TREE_MAP_SHIFT; for ( ; height > 1; height--) { @@ -1252,7 +1208,8 @@ unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) } node = indirect_to_ptr(node); - max_index = radix_tree_maxindex(node->height); + max_index = radix_tree_maxindex(node->path & + RADIX_TREE_HEIGHT_MASK); if (cur_index > max_index) { rcu_read_unlock(); break; @@ -1337,48 +1294,90 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) } /** - * radix_tree_delete - delete an item from a radix tree + * __radix_tree_delete_node - try to free node after clearing a slot * @root: radix tree root * @index: index key + * @node: node containing @index * - * Remove the item at @index from the radix tree rooted at @root. + * After clearing the slot at @index in @node from radix tree + * rooted at @root, call this function to attempt freeing the + * node and shrinking the tree. * - * Returns the address of the deleted item, or NULL if it was not present. + * Returns %true if @node was freed, %false otherwise. */ -void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) +bool __radix_tree_delete_node(struct radix_tree_root *root, + struct radix_tree_node *node) { - struct radix_tree_node *node = NULL; - struct radix_tree_node *slot = NULL; - struct radix_tree_node *to_free; - unsigned int height, shift; + bool deleted = false; + + do { + struct radix_tree_node *parent; + + if (node->count) { + if (node == indirect_to_ptr(root->rnode)) { + radix_tree_shrink(root); + if (root->height == 0) + deleted = true; + } + return deleted; + } + + parent = node->parent; + if (parent) { + unsigned int offset; + + offset = node->path >> RADIX_TREE_HEIGHT_SHIFT; + parent->slots[offset] = NULL; + parent->count--; + } else { + root_tag_clear_all(root); + root->height = 0; + root->rnode = NULL; + } + + radix_tree_node_free(node); + deleted = true; + + node = parent; + } while (node); + + return deleted; +} + +/** + * radix_tree_delete_item - delete an item from a radix tree + * @root: radix tree root + * @index: index key + * @item: expected item + * + * Remove @item at @index from the radix tree rooted at @root. + * + * Returns the address of the deleted item, or NULL if it was not present + * or the entry at the given @index was not @item. + */ +void *radix_tree_delete_item(struct radix_tree_root *root, + unsigned long index, void *item) +{ + struct radix_tree_node *node; + unsigned int offset; + void **slot; + void *entry; int tag; - int uninitialized_var(offset); - height = root->height; - if (index > radix_tree_maxindex(height)) - goto out; + entry = __radix_tree_lookup(root, index, &node, &slot); + if (!entry) + return NULL; - slot = root->rnode; - if (height == 0) { + if (item && entry != item) + return NULL; + + if (!node) { root_tag_clear_all(root); root->rnode = NULL; - goto out; + return entry; } - slot = indirect_to_ptr(slot); - shift = height * RADIX_TREE_MAP_SHIFT; - do { - if (slot == NULL) - goto out; - - shift -= RADIX_TREE_MAP_SHIFT; - offset = (index >> shift) & RADIX_TREE_MAP_MASK; - node = slot; - slot = slot->slots[offset]; - } while (shift); - - if (slot == NULL) - goto out; + offset = index & RADIX_TREE_MAP_MASK; /* * Clear all tags associated with the item to be deleted. @@ -1389,40 +1388,27 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) radix_tree_tag_clear(root, index, tag); } - to_free = NULL; - /* Now free the nodes we do not need anymore */ - while (node) { - node->slots[offset] = NULL; - node->count--; - /* - * Queue the node for deferred freeing after the - * last reference to it disappears (set NULL, above). - */ - if (to_free) - radix_tree_node_free(to_free); - - if (node->count) { - if (node == indirect_to_ptr(root->rnode)) - radix_tree_shrink(root); - goto out; - } + node->slots[offset] = NULL; + node->count--; - /* Node with zero slots in use so free it */ - to_free = node; + __radix_tree_delete_node(root, node); - index >>= RADIX_TREE_MAP_SHIFT; - offset = index & RADIX_TREE_MAP_MASK; - node = node->parent; - } - - root_tag_clear_all(root); - root->height = 0; - root->rnode = NULL; - if (to_free) - radix_tree_node_free(to_free); + return entry; +} +EXPORT_SYMBOL(radix_tree_delete_item); -out: - return slot; +/** + * radix_tree_delete - delete an item from a radix tree + * @root: radix tree root + * @index: index key + * + * Remove the item at @index from the radix tree rooted at @root. + * + * Returns the address of the deleted item, or NULL if it was not present. + */ +void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) +{ + return radix_tree_delete_item(root, index, NULL); } EXPORT_SYMBOL(radix_tree_delete); @@ -1438,9 +1424,12 @@ 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) +radix_tree_node_ctor(void *arg) { - memset(node, 0, sizeof(struct radix_tree_node)); + struct radix_tree_node *node = arg; + + memset(node, 0, sizeof(*node)); + INIT_LIST_HEAD(&node->private_list); } static __init unsigned long __maxindex(unsigned int height) diff --git a/lib/random32.c b/lib/random32.c index 61489677870..fa5da61ce7a 100644 --- a/lib/random32.c +++ b/lib/random32.c @@ -1,37 +1,35 @@ /* - This is a maximally equidistributed combined Tausworthe generator - based on code from GNU Scientific Library 1.5 (30 Jun 2004) - - lfsr113 version: - - x_n = (s1_n ^ s2_n ^ s3_n ^ s4_n) - - s1_{n+1} = (((s1_n & 4294967294) << 18) ^ (((s1_n << 6) ^ s1_n) >> 13)) - s2_{n+1} = (((s2_n & 4294967288) << 2) ^ (((s2_n << 2) ^ s2_n) >> 27)) - s3_{n+1} = (((s3_n & 4294967280) << 7) ^ (((s3_n << 13) ^ s3_n) >> 21)) - s4_{n+1} = (((s4_n & 4294967168) << 13) ^ (((s4_n << 3) ^ s4_n) >> 12)) - - The period of this generator is about 2^113 (see erratum paper). - - From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe - Generators", Mathematics of Computation, 65, 213 (1996), 203--213: - http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps - ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps - - There is an erratum in the paper "Tables of Maximally - Equidistributed Combined LFSR Generators", Mathematics of - Computation, 68, 225 (1999), 261--269: - http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps - - ... the k_j most significant bits of z_j must be non- - zero, for each j. (Note: this restriction also applies to the - computer code given in [4], but was mistakenly not mentioned in - that paper.) - - This affects the seeding procedure by imposing the requirement - s1 > 1, s2 > 7, s3 > 15, s4 > 127. - -*/ + * This is a maximally equidistributed combined Tausworthe generator + * based on code from GNU Scientific Library 1.5 (30 Jun 2004) + * + * lfsr113 version: + * + * x_n = (s1_n ^ s2_n ^ s3_n ^ s4_n) + * + * s1_{n+1} = (((s1_n & 4294967294) << 18) ^ (((s1_n << 6) ^ s1_n) >> 13)) + * s2_{n+1} = (((s2_n & 4294967288) << 2) ^ (((s2_n << 2) ^ s2_n) >> 27)) + * s3_{n+1} = (((s3_n & 4294967280) << 7) ^ (((s3_n << 13) ^ s3_n) >> 21)) + * s4_{n+1} = (((s4_n & 4294967168) << 13) ^ (((s4_n << 3) ^ s4_n) >> 12)) + * + * The period of this generator is about 2^113 (see erratum paper). + * + * From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe + * Generators", Mathematics of Computation, 65, 213 (1996), 203--213: + * http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps + * ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps + * + * There is an erratum in the paper "Tables of Maximally Equidistributed + * Combined LFSR Generators", Mathematics of Computation, 68, 225 (1999), + * 261--269: http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps + * + * ... the k_j most significant bits of z_j must be non-zero, + * for each j. (Note: this restriction also applies to the + * computer code given in [4], but was mistakenly not mentioned + * in that paper.) + * + * This affects the seeding procedure by imposing the requirement + * s1 > 1, s2 > 7, s3 > 15, s4 > 127. + */ #include <linux/types.h> #include <linux/percpu.h> @@ -75,15 +73,17 @@ EXPORT_SYMBOL(prandom_u32_state); */ u32 prandom_u32(void) { - unsigned long r; struct rnd_state *state = &get_cpu_var(net_rand_state); - r = prandom_u32_state(state); + u32 res; + + res = prandom_u32_state(state); put_cpu_var(state); - return r; + + return res; } EXPORT_SYMBOL(prandom_u32); -/* +/** * prandom_bytes_state - get the requested number of pseudo-random bytes * * @state: pointer to state structure holding seeded state. @@ -204,6 +204,7 @@ static int __init prandom_init(void) prandom_seed_very_weak(state, (i + jiffies) ^ random_get_entropy()); prandom_warmup(state); } + return 0; } core_initcall(prandom_init); @@ -259,6 +260,7 @@ static void __prandom_reseed(bool late) if (latch && !late) goto out; + latch = true; for_each_possible_cpu(i) { diff --git a/lib/smp_processor_id.c b/lib/smp_processor_id.c index 04abe53f12a..1afec32de6f 100644 --- a/lib/smp_processor_id.c +++ b/lib/smp_processor_id.c @@ -7,7 +7,8 @@ #include <linux/kallsyms.h> #include <linux/sched.h> -notrace unsigned int debug_smp_processor_id(void) +notrace static unsigned int check_preemption_disabled(const char *what1, + const char *what2) { int this_cpu = raw_smp_processor_id(); @@ -38,9 +39,9 @@ notrace unsigned int debug_smp_processor_id(void) if (!printk_ratelimit()) goto out_enable; - printk(KERN_ERR "BUG: using smp_processor_id() in preemptible [%08x] " - "code: %s/%d\n", - preempt_count() - 1, current->comm, current->pid); + printk(KERN_ERR "BUG: using %s%s() in preemptible [%08x] code: %s/%d\n", + what1, what2, preempt_count() - 1, current->comm, current->pid); + print_symbol("caller is %s\n", (long)__builtin_return_address(0)); dump_stack(); @@ -50,5 +51,14 @@ out: return this_cpu; } +notrace unsigned int debug_smp_processor_id(void) +{ + return check_preemption_disabled("smp_processor_id", ""); +} EXPORT_SYMBOL(debug_smp_processor_id); +notrace void __this_cpu_preempt_check(const char *op) +{ + check_preemption_disabled("__this_cpu_", op); +} +EXPORT_SYMBOL(__this_cpu_preempt_check); diff --git a/lib/syscall.c b/lib/syscall.c index 58710eefeac..e30e0393248 100644 --- a/lib/syscall.c +++ b/lib/syscall.c @@ -72,4 +72,3 @@ int task_current_syscall(struct task_struct *target, long *callno, return 0; } -EXPORT_SYMBOL_GPL(task_current_syscall); diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 5e2cf6f342f..0648291cdaf 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -364,7 +364,6 @@ enum format_type { FORMAT_TYPE_SHORT, FORMAT_TYPE_UINT, FORMAT_TYPE_INT, - FORMAT_TYPE_NRCHARS, FORMAT_TYPE_SIZE_T, FORMAT_TYPE_PTRDIFF }; @@ -1538,10 +1537,6 @@ qualifier: return fmt - start; /* skip alnum */ - case 'n': - spec->type = FORMAT_TYPE_NRCHARS; - return ++fmt - start; - case '%': spec->type = FORMAT_TYPE_PERCENT_CHAR; return ++fmt - start; @@ -1564,6 +1559,15 @@ qualifier: case 'u': break; + case 'n': + /* + * Since %n poses a greater security risk than utility, treat + * it as an invalid format specifier. Warn about its use so + * that new instances don't get added. + */ + WARN_ONCE(1, "Please remove ignored %%n in '%s'\n", fmt); + /* Fall-through */ + default: spec->type = FORMAT_TYPE_INVALID; return fmt - start; @@ -1737,20 +1741,6 @@ int vsnprintf(char *buf, size_t size, const char *fmt, va_list args) ++str; break; - case FORMAT_TYPE_NRCHARS: { - /* - * Since %n poses a greater security risk than - * utility, ignore %n and skip its argument. - */ - void *skip_arg; - - WARN_ONCE(1, "Please remove ignored %%n in '%s'\n", - old_fmt); - - skip_arg = va_arg(args, void *); - break; - } - default: switch (spec.type) { case FORMAT_TYPE_LONG_LONG: @@ -2025,19 +2015,6 @@ do { \ fmt++; break; - case FORMAT_TYPE_NRCHARS: { - /* skip %n 's argument */ - u8 qualifier = spec.qualifier; - void *skip_arg; - if (qualifier == 'l') - skip_arg = va_arg(args, long *); - else if (_tolower(qualifier) == 'z') - skip_arg = va_arg(args, size_t *); - else - skip_arg = va_arg(args, int *); - break; - } - default: switch (spec.type) { @@ -2196,10 +2173,6 @@ int bstr_printf(char *buf, size_t size, const char *fmt, const u32 *bin_buf) ++str; break; - case FORMAT_TYPE_NRCHARS: - /* skip */ - break; - default: { unsigned long long num; |