aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig.debug20
-rw-r--r--lib/Makefile6
-rw-r--r--lib/argv_split.c4
-rw-r--r--lib/bust_spinlocks.c6
-rw-r--r--lib/idr.c5
-rw-r--r--lib/iomap.c2
-rw-r--r--lib/ioremap.c1
-rw-r--r--lib/kobject.c135
-rw-r--r--lib/kobject_uevent.c221
-rw-r--r--lib/percpu_counter.c48
-rw-r--r--lib/proportions.c384
-rw-r--r--lib/radix-tree.c148
-rw-r--r--lib/sort.c2
-rw-r--r--lib/swiotlb.c20
-rw-r--r--lib/zlib_inflate/Makefile2
-rw-r--r--lib/zlib_inflate/inffast.c18
-rw-r--r--lib/zlib_inflate/inflate.c8
-rw-r--r--lib/zlib_inflate/inflate_syms.c1
-rw-r--r--lib/zlib_inflate/infutil.c49
19 files changed, 807 insertions, 273 deletions
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index cdc9b099e62..7d16e643330 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -167,7 +167,7 @@ config SLUB_DEBUG_ON
config DEBUG_PREEMPT
bool "Debug preemptible kernel"
- depends on DEBUG_KERNEL && PREEMPT && TRACE_IRQFLAGS_SUPPORT
+ depends on DEBUG_KERNEL && PREEMPT && (TRACE_IRQFLAGS_SUPPORT || PPC64)
default y
help
If you say Y here then the kernel will use a debug variant of the
@@ -413,6 +413,24 @@ config FORCED_INLINING
become the default in the future, until then this option is there to
test gcc for this.
+config BOOT_PRINTK_DELAY
+ bool "Delay each boot printk message by N milliseconds"
+ depends on DEBUG_KERNEL && PRINTK && GENERIC_CALIBRATE_DELAY
+ help
+ This build option allows you to read kernel boot messages
+ by inserting a short delay after each one. The delay is
+ specified in milliseconds on the kernel command line,
+ using "boot_delay=N".
+
+ It is likely that you would also need to use "lpj=M" to preset
+ the "loops per jiffie" value.
+ See a previous boot log for the "lpj" value to use for your
+ system, and then set "lpj=M" before setting "boot_delay=N".
+ NOTE: Using this option may adversely affect SMP systems.
+ I.e., processors other than the first one may not boot up.
+ BOOT_PRINTK_DELAY also may cause DETECT_SOFTLOCKUP to detect
+ what it believes to be lockup conditions.
+
config RCU_TORTURE_TEST
tristate "torture tests for RCU"
depends on DEBUG_KERNEL
diff --git a/lib/Makefile b/lib/Makefile
index 4f3f3e25650..c5f215d509d 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -5,12 +5,13 @@
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
-lib-y += kobject.o kref.o kobject_uevent.o klist.o
+lib-y += kobject.o kref.o klist.o
obj-y += div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
bust_spinlocks.o hexdump.o kasprintf.o
@@ -20,6 +21,7 @@ CFLAGS_kobject.o += -DDEBUG
CFLAGS_kobject_uevent.o += -DDEBUG
endif
+lib-$(CONFIG_HOTPLUG) += kobject_uevent.o
obj-$(CONFIG_GENERIC_IOMAP) += iomap.o
obj-$(CONFIG_HAS_IOMEM) += iomap_copy.o devres.o
obj-$(CONFIG_CHECK_SIGNATURE) += check_signature.o
diff --git a/lib/argv_split.c b/lib/argv_split.c
index 4096ed42f49..fad6ce4f7b5 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 accb3565816..486da62b2b0 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();
}
}
diff --git a/lib/idr.c b/lib/idr.c
index d0f1acdbfa3..afbb0b1023d 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -120,7 +120,7 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa)
int n, m, sh;
struct idr_layer *p, *new;
int l, id, oid;
- long bm;
+ unsigned long bm;
id = *starting_id;
restart:
@@ -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 864f2ec1966..72c42687ba1 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 760521417b6..14c6078f17a 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/kobject.c b/lib/kobject.c
index 4b08e0ff95c..03d40360ff1 100644
--- a/lib/kobject.c
+++ b/lib/kobject.c
@@ -2,6 +2,8 @@
* kobject.c - library routines for handling generic kernel objects
*
* Copyright (c) 2002-2003 Patrick Mochel <mochel@osdl.org>
+ * Copyright (c) 2006-2007 Greg Kroah-Hartman <greg@kroah.com>
+ * Copyright (c) 2006-2007 Novell Inc.
*
* This file is released under the GPLv2.
*
@@ -44,11 +46,11 @@ static int populate_dir(struct kobject * kobj)
return error;
}
-static int create_dir(struct kobject *kobj, struct sysfs_dirent *shadow_parent)
+static int create_dir(struct kobject * kobj)
{
int error = 0;
if (kobject_name(kobj)) {
- error = sysfs_create_dir(kobj, shadow_parent);
+ error = sysfs_create_dir(kobj);
if (!error) {
if ((error = populate_dir(kobj)))
sysfs_remove_dir(kobj);
@@ -131,7 +133,6 @@ void kobject_init(struct kobject * kobj)
return;
kref_init(&kobj->kref);
INIT_LIST_HEAD(&kobj->entry);
- init_waitqueue_head(&kobj->poll);
kobj->kset = kset_get(kobj->kset);
}
@@ -157,12 +158,11 @@ static void unlink(struct kobject * kobj)
}
/**
- * kobject_shadow_add - add an object to the hierarchy.
+ * kobject_add - add an object to the hierarchy.
* @kobj: object.
- * @shadow_parent: sysfs directory to add to.
*/
-int kobject_shadow_add(struct kobject *kobj, struct sysfs_dirent *shadow_parent)
+int kobject_add(struct kobject * kobj)
{
int error = 0;
struct kobject * parent;
@@ -170,7 +170,7 @@ int kobject_shadow_add(struct kobject *kobj, struct sysfs_dirent *shadow_parent)
if (!(kobj = kobject_get(kobj)))
return -ENOENT;
if (!kobj->k_name)
- kobj->k_name = kobj->name;
+ kobject_set_name(kobj, "NO_NAME");
if (!*kobj->k_name) {
pr_debug("kobject attempted to be registered with no name!\n");
WARN_ON(1);
@@ -181,7 +181,7 @@ int kobject_shadow_add(struct kobject *kobj, struct sysfs_dirent *shadow_parent)
pr_debug("kobject %s: registering. parent: %s, set: %s\n",
kobject_name(kobj), parent ? kobject_name(parent) : "<NULL>",
- kobj->kset ? kobj->kset->kobj.name : "<NULL>" );
+ kobj->kset ? kobject_name(&kobj->kset->kobj) : "<NULL>" );
if (kobj->kset) {
spin_lock(&kobj->kset->list_lock);
@@ -194,7 +194,7 @@ int kobject_shadow_add(struct kobject *kobj, struct sysfs_dirent *shadow_parent)
kobj->parent = parent;
}
- error = create_dir(kobj, shadow_parent);
+ error = create_dir(kobj);
if (error) {
/* unlink does the kobject_put() for us */
unlink(kobj);
@@ -216,16 +216,6 @@ int kobject_shadow_add(struct kobject *kobj, struct sysfs_dirent *shadow_parent)
}
/**
- * kobject_add - add an object to the hierarchy.
- * @kobj: object.
- */
-int kobject_add(struct kobject * kobj)
-{
- return kobject_shadow_add(kobj, NULL);
-}
-
-
-/**
* kobject_register - initialize and add an object.
* @kobj: object in question.
*/
@@ -255,54 +245,50 @@ int kobject_register(struct kobject * kobj)
int kobject_set_name(struct kobject * kobj, const char * fmt, ...)
{
int error = 0;
- int limit = KOBJ_NAME_LEN;
+ int limit;
int need;
va_list args;
- char * name;
+ char *name;
- /*
- * First, try the static array
- */
- va_start(args,fmt);
- need = vsnprintf(kobj->name,limit,fmt,args);
+ /* find out how big a buffer we need */
+ name = kmalloc(1024, GFP_KERNEL);
+ if (!name) {
+ error = -ENOMEM;
+ goto done;
+ }
+ va_start(args, fmt);
+ need = vsnprintf(name, 1024, fmt, args);
va_end(args);
- if (need < limit)
- name = kobj->name;
- else {
- /*
- * Need more space? Allocate it and try again
- */
- limit = need + 1;
- name = kmalloc(limit,GFP_KERNEL);
- if (!name) {
- error = -ENOMEM;
- goto Done;
- }
- va_start(args,fmt);
- need = vsnprintf(name,limit,fmt,args);
- va_end(args);
-
- /* Still? Give up. */
- if (need >= limit) {
- kfree(name);
- error = -EFAULT;
- goto Done;
- }
+ kfree(name);
+
+ /* Allocate the new space and copy the string in */
+ limit = need + 1;
+ name = kmalloc(limit, GFP_KERNEL);
+ if (!name) {
+ error = -ENOMEM;
+ goto done;
+ }
+ va_start(args, fmt);
+ need = vsnprintf(name, limit, fmt, args);
+ va_end(args);
+
+ /* something wrong with the string we copied? */
+ if (need >= limit) {
+ kfree(name);
+ error = -EFAULT;
+ goto done;
}
/* Free the old name, if necessary. */
- if (kobj->k_name && kobj->k_name != kobj->name)
- kfree(kobj->k_name);
+ kfree(kobj->k_name);
/* Now, set the new name */
kobj->k_name = name;
- Done:
+done:
return error;
}
-
EXPORT_SYMBOL(kobject_set_name);
-
/**
* kobject_rename - change the name of an object
* @kobj: object in question.
@@ -338,7 +324,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->sd, new_name);
+ error = sysfs_rename_dir(kobj, new_name);
/* This function is mostly/only used for network interface.
* Some hotplug package track interfaces by their name and
@@ -355,27 +341,6 @@ out:
}
/**
- * kobject_rename - change the name of an object
- * @kobj: object in question.
- * @new_parent: object's new parent
- * @new_name: object's new name
- */
-
-int kobject_shadow_rename(struct kobject *kobj,
- struct sysfs_dirent *new_parent, const char *new_name)
-{
- int error = 0;
-
- kobj = kobject_get(kobj);
- if (!kobj)
- return -EINVAL;
- error = sysfs_rename_dir(kobj, new_parent, new_name);
- kobject_put(kobj);
-
- return error;
-}
-
-/**
* kobject_move - move object to another parent
* @kobj: object in question.
* @new_parent: object's new parent (can be NULL)
@@ -477,13 +442,16 @@ void kobject_cleanup(struct kobject * kobj)
struct kobj_type * t = get_ktype(kobj);
struct kset * s = kobj->kset;
struct kobject * parent = kobj->parent;
+ const char *name = kobj->k_name;
pr_debug("kobject %s: cleaning up\n",kobject_name(kobj));
- if (kobj->k_name != kobj->name)
- kfree(kobj->k_name);
- kobj->k_name = NULL;
- if (t && t->release)
+ if (t && t->release) {
t->release(kobj);
+ /* If we have a release function, we can guess that this was
+ * not a statically allocated kobject, so we should be safe to
+ * free the name */
+ kfree(name);
+ }
if (s)
kset_put(s);
kobject_put(parent);
@@ -651,11 +619,6 @@ struct kobject * kset_find_obj(struct kset * kset, const char * name)
return ret;
}
-void subsystem_init(struct kset *s)
-{
- kset_init(s);
-}
-
int subsystem_register(struct kset *s)
{
return kset_register(s);
@@ -679,9 +642,9 @@ int subsys_create_file(struct kset *s, struct subsys_attribute *a)
if (!s || !a)
return -EINVAL;
- if (subsys_get(s)) {
+ if (kset_get(s)) {
error = sysfs_create_file(&s->kobj, &a->attr);
- subsys_put(s);
+ kset_put(s);
}
return error;
}
diff --git a/lib/kobject_uevent.c b/lib/kobject_uevent.c
index df02814699d..2e4eae5b082 100644
--- a/lib/kobject_uevent.c
+++ b/lib/kobject_uevent.c
@@ -22,31 +22,62 @@
#include <linux/kobject.h>
#include <net/sock.h>
-#define BUFFER_SIZE 2048 /* buffer for the variables */
-#define NUM_ENVP 32 /* number of env pointers */
-/* the strings here must match the enum in include/linux/kobject.h */
-const char *kobject_actions[] = {
- "add",
- "remove",
- "change",
- "move",
- "online",
- "offline",
-};
-
-#if defined(CONFIG_HOTPLUG)
u64 uevent_seqnum;
-char uevent_helper[UEVENT_HELPER_PATH_LEN] = "/sbin/hotplug";
+char uevent_helper[UEVENT_HELPER_PATH_LEN] = CONFIG_UEVENT_HELPER_PATH;
static DEFINE_SPINLOCK(sequence_lock);
#if defined(CONFIG_NET)
static struct sock *uevent_sock;
#endif
+/* the strings here must match the enum in include/linux/kobject.h */
+static const char *kobject_actions[] = {
+ [KOBJ_ADD] = "add",
+ [KOBJ_REMOVE] = "remove",
+ [KOBJ_CHANGE] = "change",
+ [KOBJ_MOVE] = "move",
+ [KOBJ_ONLINE] = "online",
+ [KOBJ_OFFLINE] = "offline",
+};
+
+/**
+ * kobject_action_type - translate action string to numeric type
+ *
+ * @buf: buffer containing the action string, newline is ignored
+ * @len: length of buffer
+ * @type: pointer to the location to store the action type
+ *
+ * Returns 0 if the action string was recognized.
+ */
+int kobject_action_type(const char *buf, size_t count,
+ enum kobject_action *type)
+{
+ enum kobject_action action;
+ int ret = -EINVAL;
+
+ if (count && buf[count-1] == '\n')
+ count--;
+
+ if (!count)
+ goto out;
+
+ for (action = 0; action < ARRAY_SIZE(kobject_actions); action++) {
+ if (strncmp(kobject_actions[action], buf, count) != 0)
+ continue;
+ if (kobject_actions[action][count] != '\0')
+ continue;
+ *type = action;
+ ret = 0;
+ break;
+ }
+out:
+ return ret;
+}
+
/**
* kobject_uevent_env - send an uevent with environmental data
*
- * @action: action that is happening (usually KOBJ_MOVE)
+ * @action: action that is happening
* @kobj: struct kobject that the action is happening to
* @envp_ext: pointer to environmental data
*
@@ -54,36 +85,26 @@ static struct sock *uevent_sock;
* corresponding error when it fails.
*/
int kobject_uevent_env(struct kobject *kobj, enum kobject_action action,
- char *envp_ext[])
+ char *envp_ext[])
{
- char **envp;
- char *buffer;
- char *scratch;
- const char *action_string;
+ struct kobj_uevent_env *env;
+ const char *action_string = kobject_actions[action];
const char *devpath = NULL;
const char *subsystem;
struct kobject *top_kobj;
struct kset *kset;
struct kset_uevent_ops *uevent_ops;
u64 seq;
- char *seq_buff;
int i = 0;
int retval = 0;
- int j;
pr_debug("%s\n", __FUNCTION__);
- action_string = kobject_actions[action];
- if (!action_string) {
- pr_debug("kobject attempted to send uevent without action_string!\n");
- return -EINVAL;
- }
-
/* search the kset we belong to */
top_kobj = kobj;
- while (!top_kobj->kset && top_kobj->parent) {
+ while (!top_kobj->kset && top_kobj->parent)
top_kobj = top_kobj->parent;
- }
+
if (!top_kobj->kset) {
pr_debug("kobject attempted to send uevent without kset!\n");
return -EINVAL;
@@ -92,7 +113,7 @@ int kobject_uevent_env(struct kobject *kobj, enum kobject_action action,
kset = top_kobj->kset;
uevent_ops = kset->uevent_ops;
- /* skip the event, if the filter returns zero. */
+ /* skip the event, if the filter returns zero. */
if (uevent_ops && uevent_ops->filter)
if (!uevent_ops->filter(kset, kobj)) {
pr_debug("kobject filter function caused the event to drop!\n");
@@ -109,18 +130,11 @@ int kobject_uevent_env(struct kobject *kobj, enum kobject_action action,
return 0;
}
- /* environment index */
- envp = kzalloc(NUM_ENVP * sizeof (char *), GFP_KERNEL);
- if (!envp)
+ /* environment buffer */
+ env = kzalloc(sizeof(struct kobj_uevent_env), GFP_KERNEL);
+ if (!env)
return -ENOMEM;
- /* environment values */
- buffer = kmalloc(BUFFER_SIZE, GFP_KERNEL);
- if (!buffer) {
- retval = -ENOMEM;
- goto exit;
- }
-
/* complete object path */
devpath = kobject_get_path(kobj, GFP_KERNEL);
if (!devpath) {
@@ -128,29 +142,29 @@ int kobject_uevent_env(struct kobject *kobj, enum kobject_action action,
goto exit;
}
- /* event environemnt for helper process only */
- envp[i++] = "HOME=/";
- envp[i++] = "PATH=/sbin:/bin:/usr/sbin:/usr/bin";
-
/* default keys */
- scratch = buffer;
- envp [i++] = scratch;
- scratch += sprintf(scratch, "ACTION=%s", action_string) + 1;
- envp [i++] = scratch;
- scratch += sprintf (scratch, "DEVPATH=%s", devpath) + 1;
- envp [i++] = scratch;
- scratch += sprintf(scratch, "SUBSYSTEM=%s", subsystem) + 1;
- for (j = 0; envp_ext && envp_ext[j]; j++)
- envp[i++] = envp_ext[j];
- /* just reserve the space, overwrite it after kset call has returned */
- envp[i++] = seq_buff = scratch;
- scratch += strlen("SEQNUM=18446744073709551616") + 1;
+ retval = add_uevent_var(env, "ACTION=%s", action_string);
+ if (retval)
+ goto exit;
+ retval = add_uevent_var(env, "DEVPATH=%s", devpath);
+ if (retval)
+ goto exit;
+ retval = add_uevent_var(env, "SUBSYSTEM=%s", subsystem);
+ if (retval)
+ goto exit;
+
+ /* keys passed in from the caller */
+ if (envp_ext) {
+ for (i = 0; envp_ext[i]; i++) {
+ retval = add_uevent_var(env, envp_ext[i]);
+ if (retval)
+ goto exit;
+ }
+ }
/* let the kset specific function add its stuff */
if (uevent_ops && uevent_ops->uevent) {
- retval = uevent_ops->uevent(kset, kobj,
- &envp[i], NUM_ENVP - i, scratch,
- BUFFER_SIZE - (scratch - buffer));
+ retval = uevent_ops->uevent(kset, kobj, env);
if (retval) {
pr_debug ("%s - uevent() returned %d\n",
__FUNCTION__, retval);
@@ -158,11 +172,13 @@ int kobject_uevent_env(struct kobject *kobj, enum kobject_action action,
}
}
- /* we will send an event, request a new sequence number */
+ /* we will send an event, so request a new sequence number */
spin_lock(&sequence_lock);
seq = ++uevent_seqnum;
spin_unlock(&sequence_lock);
- sprintf(seq_buff, "SEQNUM=%llu", (unsigned long long)seq);
+ retval = add_uevent_var(env, "SEQNUM=%llu", (unsigned long long)seq);
+ if (retval)
+ goto exit;
#if defined(CONFIG_NET)
/* send netlink message */
@@ -172,17 +188,19 @@ int kobject_uevent_env(struct kobject *kobj, enum kobject_action action,
/* allocate message with the maximum possible size */
len = strlen(action_string) + strlen(devpath) + 2;
- skb = alloc_skb(len + BUFFER_SIZE, GFP_KERNEL);
+ skb = alloc_skb(len + env->buflen, GFP_KERNEL);
if (skb) {
+ char *scratch;
+
/* add header */
scratch = skb_put(skb, len);
sprintf(scratch, "%s@%s", action_string, devpath);
/* copy keys to our continuous event payload buffer */
- for (i = 2; envp[i]; i++) {
- len = strlen(envp[i]) + 1;
+ for (i = 0; i < env->envp_idx; i++) {
+ len = strlen(env->envp[i]) + 1;
scratch = skb_put(skb, len);
- strcpy(scratch, envp[i]);
+ strcpy(scratch, env->envp[i]);
}
NETLINK_CB(skb).dst_group = 1;
@@ -198,13 +216,19 @@ int kobject_uevent_env(struct kobject *kobj, enum kobject_action action,
argv [0] = uevent_helper;
argv [1] = (char *)subsystem;
argv [2] = NULL;
- call_usermodehelper (argv[0], argv, envp, UMH_WAIT_EXEC);
+ retval = add_uevent_var(env, "HOME=/");
+ if (retval)
+ goto exit;
+ retval = add_uevent_var(env, "PATH=/sbin:/bin:/usr/sbin:/usr/bin");
+ if (retval)
+ goto exit;
+
+ call_usermodehelper (argv[0], argv, env->envp, UMH_WAIT_EXEC);
}
exit:
kfree(devpath);
- kfree(buffer);
- kfree(envp);
+ kfree(env);
return retval;
}
@@ -213,7 +237,7 @@ EXPORT_SYMBOL_GPL(kobject_uevent_env);
/**
* kobject_uevent - notify userspace by ending an uevent
*
- * @action: action that is happening (usually KOBJ_ADD and KOBJ_REMOVE)
+ * @action: action that is happening
* @kobj: struct kobject that the action is happening to
*
* Returns 0 if kobject_uevent() is completed with success or the
@@ -227,52 +251,38 @@ int kobject_uevent(struct kobject *kobj, enum kobject_action action)
EXPORT_SYMBOL_GPL(kobject_uevent);
/**
- * add_uevent_var - helper for creating event variables
- * @envp: Pointer to table of environment variables, as passed into
- * uevent() method.
- * @num_envp: Number of environment variable slots available, as
- * passed into uevent() method.
- * @cur_index: Pointer to current index into @envp. It should be
- * initialized to 0 before the first call to add_uevent_var(),
- * and will be incremented on success.
- * @buffer: Pointer to buffer for environment variables, as passed
- * into uevent() method.
- * @buffer_size: Length of @buffer, as passed into uevent() method.
- * @cur_len: Pointer to current length of space used in @buffer.
- * Should be initialized to 0 before the first call to
- * add_uevent_var(), and will be incremented on success.
- * @format: Format for creating environment variable (of the form
- * "XXX=%x") for snprintf().
+ * add_uevent_var - add key value string to the environment buffer
+ * @env: environment buffer structure
+ * @format: printf format for the key=value pair
*
* Returns 0 if environment variable was added successfully or -ENOMEM
* if no space was available.
*/
-int add_uevent_var(char **envp, int num_envp, int *cur_index,
- char *buffer, int buffer_size, int *cur_len,
- const char *format, ...)
+int add_uevent_var(struct kobj_uevent_env *env, const char *format, ...)
{
va_list args;
+ int len;
- /*
- * We check against num_envp - 1 to make sure there is at
- * least one slot left after we return, since kobject_uevent()
- * needs to set the last slot to NULL.
- */
- if (*cur_index >= num_envp - 1)
+ if (env->envp_idx >= ARRAY_SIZE(env->envp)) {
+ printk(KERN_ERR "add_uevent_var: too many keys\n");
+ WARN_ON(1);
return -ENOMEM;
-
- envp[*cur_index] = buffer + *cur_len;
+ }
va_start(args, format);
- *cur_len += vsnprintf(envp[*cur_index],
- max(buffer_size - *cur_len, 0),
- format, args) + 1;
+ len = vsnprintf(&env->buf[env->buflen],
+ sizeof(env->buf) - env->buflen,
+ format, args);
va_end(args);
- if (*cur_len > buffer_size)
+ if (len >= (sizeof(env->buf) - env->buflen)) {
+ printk(KERN_ERR "add_uevent_var: buffer size too small\n");
+ WARN_ON(1);
return -ENOMEM;
+ }
- (*cur_index)++;
+ env->envp[env->envp_idx++] = &env->buf[env->buflen];
+ env->buflen += len + 1;
return 0;
}
EXPORT_SYMBOL_GPL(add_uevent_var);
@@ -280,9 +290,8 @@ EXPORT_SYMBOL_GPL(add_uevent_var);
#if defined(CONFIG_NET)
static int __init kobject_uevent_init(void)
{
- uevent_sock = netlink_kernel_create(NETLINK_KOBJECT_UEVENT, 1, NULL,
- NULL, THIS_MODULE);
-
+ uevent_sock = netlink_kernel_create(&init_net, NETLINK_KOBJECT_UEVENT,
+ 1, NULL, NULL, THIS_MODULE);
if (!uevent_sock) {
printk(KERN_ERR
"kobject_uevent: unable to create netlink socket!\n");
@@ -294,5 +303,3 @@ static int __init kobject_uevent_init(void)
postcore_initcall(kobject_uevent_init);
#endif
-
-#endif /* CONFIG_HOTPLUG */
diff --git a/lib/percpu_counter.c b/lib/percpu_counter.c
index cf22c617baa..9659eabffc3 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 00000000000..332d8c58184
--- /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 514efb200be..48c250fe223 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -60,9 +60,14 @@ struct radix_tree_path {
};
#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
-#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
+#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
+ RADIX_TREE_MAP_SHIFT))
-static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly;
+/*
+ * The height_to_maxindex array needs to be one deeper than the maximum
+ * path as height 0 holds only 1 entry.
+ */
+static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
/*
* Radix tree node cache.
@@ -93,7 +98,8 @@ radix_tree_node_alloc(struct radix_tree_root *root)
struct radix_tree_node *ret;
gfp_t gfp_mask = root_gfp_mask(root);
- ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
+ ret = kmem_cache_alloc(radix_tree_node_cachep,
+ set_migrateflags(gfp_mask, __GFP_RECLAIMABLE));
if (ret == NULL && !(gfp_mask & __GFP_WAIT)) {
struct radix_tree_preload *rtp;
@@ -104,7 +110,7 @@ radix_tree_node_alloc(struct radix_tree_root *root)
rtp->nr--;
}
}
- BUG_ON(radix_tree_is_direct_ptr(ret));
+ BUG_ON(radix_tree_is_indirect_ptr(ret));
return ret;
}
@@ -137,7 +143,8 @@ int radix_tree_preload(gfp_t gfp_mask)
rtp = &__get_cpu_var(radix_tree_preloads);
while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
preempt_enable();
- node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
+ node = kmem_cache_alloc(radix_tree_node_cachep,
+ set_migrateflags(gfp_mask, __GFP_RECLAIMABLE));
if (node == NULL)
goto out;
preempt_disable();
@@ -240,7 +247,7 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
return -ENOMEM;
/* Increase the height. */
- node->slots[0] = radix_tree_direct_to_ptr(root->rnode);
+ node->slots[0] = radix_tree_indirect_to_ptr(root->rnode);
/* Propagate the aggregated tag info into the new root */
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
@@ -251,6 +258,7 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
newheight = root->height+1;
node->height = newheight;
node->count = 1;
+ node = radix_tree_ptr_to_indirect(node);
rcu_assign_pointer(root->rnode, node);
root->height = newheight;
} while (height > root->height);
@@ -274,7 +282,7 @@ int radix_tree_insert(struct radix_tree_root *root,
int offset;
int error;
- BUG_ON(radix_tree_is_direct_ptr(item));
+ BUG_ON(radix_tree_is_indirect_ptr(item));
/* Make sure the tree is high enough. */
if (index > radix_tree_maxindex(root->height)) {
@@ -283,7 +291,8 @@ int radix_tree_insert(struct radix_tree_root *root,
return error;
}
- slot = root->rnode;
+ slot = radix_tree_indirect_to_ptr(root->rnode);
+
height = root->height;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
@@ -298,7 +307,8 @@ int radix_tree_insert(struct radix_tree_root *root,
rcu_assign_pointer(node->slots[offset], slot);
node->count++;
} else
- rcu_assign_pointer(root->rnode, slot);
+ rcu_assign_pointer(root->rnode,
+ radix_tree_ptr_to_indirect(slot));
}
/* Go a level down */
@@ -318,7 +328,7 @@ int radix_tree_insert(struct radix_tree_root *root,
BUG_ON(tag_get(node, 0, offset));
BUG_ON(tag_get(node, 1, offset));
} else {
- rcu_assign_pointer(root->rnode, radix_tree_ptr_to_direct(item));
+ rcu_assign_pointer(root->rnode, item);
BUG_ON(root_tag_get(root, 0));
BUG_ON(root_tag_get(root, 1));
}
@@ -350,11 +360,12 @@ void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
if (node == NULL)
return NULL;
- if (radix_tree_is_direct_ptr(node)) {
+ if (!radix_tree_is_indirect_ptr(node)) {
if (index > 0)
return NULL;
return (void **)&root->rnode;
}
+ node = radix_tree_indirect_to_ptr(node);
height = node->height;
if (index > radix_tree_maxindex(height))
@@ -398,11 +409,12 @@ void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
if (node == NULL)
return NULL;
- if (radix_tree_is_direct_ptr(node)) {
+ if (!radix_tree_is_indirect_ptr(node)) {
if (index > 0)
return NULL;
- return radix_tree_direct_to_ptr(node);
+ return node;
}
+ node = radix_tree_indirect_to_ptr(node);
height = node->height;
if (index > radix_tree_maxindex(height))
@@ -447,7 +459,7 @@ void *radix_tree_tag_set(struct radix_tree_root *root,
height = root->height;
BUG_ON(index > radix_tree_maxindex(height));
- slot = root->rnode;
+ slot = radix_tree_indirect_to_ptr(root->rnode);
shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
while (height > 0) {
@@ -487,7 +499,11 @@ EXPORT_SYMBOL(radix_tree_tag_set);
void *radix_tree_tag_clear(struct radix_tree_root *root,
unsigned long index, unsigned int tag)
{
- struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
+ /*
+ * The radix tree path needs to be one longer than the maximum path
+ * since the "list" is null terminated.
+ */
+ struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
struct radix_tree_node *slot = NULL;
unsigned int height, shift;
@@ -497,7 +513,7 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,
shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
pathp->node = NULL;
- slot = root->rnode;
+ slot = radix_tree_indirect_to_ptr(root->rnode);
while (height > 0) {
int offset;
@@ -562,8 +578,9 @@ int radix_tree_tag_get(struct radix_tree_root *root,
if (node == NULL)
return 0;
- if (radix_tree_is_direct_ptr(node))
+ if (!radix_tree_is_indirect_ptr(node))
return (index == 0);
+ node = radix_tree_indirect_to_ptr(node);
height = node->height;
if (index > radix_tree_maxindex(height))
@@ -599,6 +616,42 @@ int radix_tree_tag_get(struct radix_tree_root *root,
EXPORT_SYMBOL(radix_tree_tag_get);
#endif
+/**
+ * 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).
+ *
+ * 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);
+
static unsigned int
__lookup(struct radix_tree_node *slot, void **results, unsigned long index,
unsigned int max_items, unsigned long *next_index)
@@ -680,13 +733,13 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
if (!node)
return 0;
- if (radix_tree_is_direct_ptr(node)) {
+ if (!radix_tree_is_indirect_ptr(node)) {
if (first_index > 0)
return 0;
- node = radix_tree_direct_to_ptr(node);
- results[0] = rcu_dereference(node);
+ results[0] = node;
return 1;
}
+ node = radix_tree_indirect_to_ptr(node);
max_index = radix_tree_maxindex(node->height);
@@ -808,13 +861,13 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
if (!node)
return 0;
- if (radix_tree_is_direct_ptr(node)) {
+ if (!radix_tree_is_indirect_ptr(node)) {
if (first_index > 0)
return 0;
- node = radix_tree_direct_to_ptr(node);
- results[0] = rcu_dereference(node);
+ results[0] = node;
return 1;
}
+ node = radix_tree_indirect_to_ptr(node);
max_index = radix_tree_maxindex(node->height);
@@ -844,12 +897,22 @@ EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
static inline void radix_tree_shrink(struct radix_tree_root *root)
{
/* try to shrink tree height */
- while (root->height > 0 &&
- root->rnode->count == 1 &&
- root->rnode->slots[0]) {
+ while (root->height > 0) {
struct radix_tree_node *to_free = root->rnode;
void *newptr;
+ BUG_ON(!radix_tree_is_indirect_ptr(to_free));
+ to_free = radix_tree_indirect_to_ptr(to_free);
+
+ /*
+ * The candidate node has more than one child, or its child
+ * is not at the leftmost slot, we cannot shrink.
+ */
+ if (to_free->count != 1)
+ break;
+ if (!to_free->slots[0])
+ break;
+
/*
* We don't need rcu_assign_pointer(), since we are simply
* moving the node from one part of the tree to another. If
@@ -858,8 +921,8 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
* one (root->rnode).
*/
newptr = to_free->slots[0];
- if (root->height == 1)
- newptr = radix_tree_ptr_to_direct(newptr);
+ if (root->height > 1)
+ newptr = radix_tree_ptr_to_indirect(newptr);
root->rnode = newptr;
root->height--;
/* must only free zeroed nodes into the slab */
@@ -882,7 +945,11 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
*/
void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
{
- struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
+ /*
+ * The radix tree path needs to be one longer than the maximum path
+ * since the "list" is null terminated.
+ */
+ struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
struct radix_tree_node *slot = NULL;
struct radix_tree_node *to_free;
unsigned int height, shift;
@@ -894,12 +961,12 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
goto out;
slot = root->rnode;
- if (height == 0 && root->rnode) {
- slot = radix_tree_direct_to_ptr(slot);
+ if (height == 0) {
root_tag_clear_all(root);
root->rnode = NULL;
goto out;
}
+ slot = radix_tree_indirect_to_ptr(slot);
shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
pathp->node = NULL;
@@ -941,7 +1008,8 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
radix_tree_node_free(to_free);
if (pathp->node->count) {
- if (pathp->node == root->rnode)
+ if (pathp->node ==
+ radix_tree_indirect_to_ptr(root->rnode))
radix_tree_shrink(root);
goto out;
}
@@ -974,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)
diff --git a/lib/sort.c b/lib/sort.c
index 961567894d1..6abbaf3d585 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -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;
diff --git a/lib/swiotlb.c b/lib/swiotlb.c
index a7381d55663..c419ecf334c 100644
--- a/lib/swiotlb.c
+++ b/lib/swiotlb.c
@@ -497,6 +497,7 @@ void
swiotlb_free_coherent(struct device *hwdev, size_t size, void *vaddr,
dma_addr_t dma_handle)
{
+ WARN_ON(irqs_disabled());
if (!(vaddr >= (void *)io_tlb_start
&& vaddr < (void *)io_tlb_end))
free_pages((unsigned long) vaddr, get_order(size));
@@ -676,16 +677,17 @@ swiotlb_sync_single_range_for_device(struct device *hwdev, dma_addr_t dev_addr,
* same here.
*/
int
-swiotlb_map_sg(struct device *hwdev, struct scatterlist *sg, int nelems,
+swiotlb_map_sg(struct device *hwdev, struct scatterlist *sgl, int nelems,
int dir)
{
+ struct scatterlist *sg;
void *addr;
dma_addr_t dev_addr;
int i;
BUG_ON(dir == DMA_NONE);
- for (i = 0; i < nelems; i++, sg++) {
+ for_each_sg(sgl, sg, nelems, i) {
addr = SG_ENT_VIRT_ADDRESS(sg);
dev_addr = virt_to_bus(addr);
if (swiotlb_force || address_needs_mapping(hwdev, dev_addr)) {
@@ -695,7 +697,7 @@ swiotlb_map_sg(struct device *hwdev, struct scatterlist *sg, int nelems,
to do proper error handling. */
swiotlb_full(hwdev, sg->length, dir, 0);
swiotlb_unmap_sg(hwdev, sg - i, i, dir);
- sg[0].dma_length = 0;
+ sgl[0].dma_length = 0;
return 0;
}
sg->dma_address = virt_to_bus(map);
@@ -711,19 +713,21 @@ swiotlb_map_sg(struct device *hwdev, struct scatterlist *sg, int nelems,
* concerning calls here are the same as for swiotlb_unmap_single() above.
*/
void
-swiotlb_unmap_sg(struct device *hwdev, struct scatterlist *sg, int nelems,
+swiotlb_unmap_sg(struct device *hwdev, struct scatterlist *sgl, int nelems,
int dir)
{
+ struct scatterlist *sg;
int i;
BUG_ON(dir == DMA_NONE);
- for (i = 0; i < nelems; i++, sg++)
+ for_each_sg(sgl, sg, nelems, i) {
if (sg->dma_address != SG_ENT_PHYS_ADDRESS(sg))
unmap_single(hwdev, bus_to_virt(sg->dma_address),
sg->dma_length, dir);
else if (dir == DMA_FROM_DEVICE)
dma_mark_clean(SG_ENT_VIRT_ADDRESS(sg), sg->dma_length);
+ }
}
/*
@@ -734,19 +738,21 @@ swiotlb_unmap_sg(struct device *hwdev, struct scatterlist *sg, int nelems,
* and usage.
*/
static void
-swiotlb_sync_sg(struct device *hwdev, struct scatterlist *sg,
+swiotlb_sync_sg(struct device *hwdev, struct scatterlist *sgl,
int nelems, int dir, int target)
{
+ struct scatterlist *sg;
int i;
BUG_ON(dir == DMA_NONE);
- for (i = 0; i < nelems; i++, sg++)
+ for_each_sg(sgl, sg, nelems, i) {
if (sg->dma_address != SG_ENT_PHYS_ADDRESS(sg))
sync_single(hwdev, bus_to_virt(sg->dma_address),
sg->dma_length, dir, target);
else if (dir == DMA_FROM_DEVICE)
dma_mark_clean(SG_ENT_VIRT_ADDRESS(sg), sg->dma_length);
+ }
}
void
diff --git a/lib/zlib_inflate/Makefile b/lib/zlib_inflate/Makefile
index bf065482fa6..49f8ce5774d 100644
--- a/lib/zlib_inflate/Makefile
+++ b/lib/zlib_inflate/Makefile
@@ -15,5 +15,5 @@
obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate.o
-zlib_inflate-objs := inffast.o inflate.o \
+zlib_inflate-objs := inffast.o inflate.o infutil.o \
inftrees.o inflate_syms.o
diff --git a/lib/zlib_inflate/inffast.c b/lib/zlib_inflate/inffast.c
index d84560c076d..8550b0c05d0 100644
--- a/lib/zlib_inflate/inffast.c
+++ b/lib/zlib_inflate/inffast.c
@@ -69,22 +69,22 @@
void inflate_fast(z_streamp strm, unsigned start)
{
struct inflate_state *state;
- unsigned char *in; /* local strm->next_in */
- unsigned char *last; /* while in < last, enough input available */
- unsigned char *out; /* local strm->next_out */
- unsigned char *beg; /* inflate()'s initial strm->next_out */
- unsigned char *end; /* while out < end, enough space available */
+ const unsigned char *in; /* local strm->next_in */
+ const unsigned char *last; /* while in < last, enough input available */
+ unsigned char *out; /* local strm->next_out */
+ unsigned char *beg; /* inflate()'s initial strm->next_out */
+ unsigned char *end; /* while out < end, enough space available */
#ifdef INFLATE_STRICT
unsigned dmax; /* maximum distance from zlib header */
#endif
unsigned wsize; /* window size or zero if not using window */
unsigned whave; /* valid bytes in the window */
unsigned write; /* window write index */
- unsigned char *window; /* allocated sliding window, if wsize != 0 */
+ unsigned char *window; /* allocated sliding window, if wsize != 0 */
unsigned long hold; /* local strm->hold */
unsigned bits; /* local strm->bits */
- code const *lcode; /* local strm->lencode */
- code const *dcode; /* local strm->distcode */
+ code const *lcode; /* local strm->lencode */
+ code const *dcode; /* local strm->distcode */
unsigned lmask; /* mask for first level of length codes */
unsigned dmask; /* mask for first level of distance codes */
code this; /* retrieved table entry */
@@ -92,7 +92,7 @@ void inflate_fast(z_streamp strm, unsigned start)
/* window position, window bytes to copy */
unsigned len; /* match length, unused bytes */
unsigned dist; /* match distance */
- unsigned char *from; /* where to copy match from */
+ unsigned char *from; /* where to copy match from */
/* copy state to local variables */
state = (struct inflate_state *)strm->state;
diff --git a/lib/zlib_inflate/inflate.c b/lib/zlib_inflate/inflate.c
index 7e1e3114a73..f5ce87b0800 100644
--- a/lib/zlib_inflate/inflate.c
+++ b/lib/zlib_inflate/inflate.c
@@ -332,14 +332,14 @@ static int zlib_inflateSyncPacket(z_streamp strm)
int zlib_inflate(z_streamp strm, int flush)
{
struct inflate_state *state;
- unsigned char *next; /* next input */
- unsigned char *put; /* next output */
+ const unsigned char *next; /* next input */
+ unsigned char *put; /* next output */
unsigned have, left; /* available input and output */
unsigned long hold; /* bit buffer */
unsigned bits; /* bits in bit buffer */
unsigned in, out; /* save starting available input and output */
unsigned copy; /* number of stored or match bytes to copy */
- unsigned char *from; /* where to copy match bytes from */
+ unsigned char *from; /* where to copy match bytes from */
code this; /* current decoding table entry */
code last; /* parent table entry */
unsigned len; /* length to copy for repeats, bits to drop */
@@ -897,7 +897,7 @@ int zlib_inflateIncomp(z_stream *z)
/* Setup some variables to allow misuse of updateWindow */
z->avail_out = 0;
- z->next_out = z->next_in + z->avail_in;
+ z->next_out = (unsigned char*)z->next_in + z->avail_in;
zlib_updatewindow(z, z->avail_in);
diff --git a/lib/zlib_inflate/inflate_syms.c b/lib/zlib_inflate/inflate_syms.c
index 2061d4f0676..67329fe9907 100644
--- a/lib/zlib_inflate/inflate_syms.c
+++ b/lib/zlib_inflate/inflate_syms.c
@@ -16,4 +16,5 @@ EXPORT_SYMBOL(zlib_inflateInit2);
EXPORT_SYMBOL(zlib_inflateEnd);
EXPORT_SYMBOL(zlib_inflateReset);
EXPORT_SYMBOL(zlib_inflateIncomp);
+EXPORT_SYMBOL(zlib_inflate_blob);
MODULE_LICENSE("GPL");
diff --git a/lib/zlib_inflate/infutil.c b/lib/zlib_inflate/infutil.c
new file mode 100644
index 00000000000..4824c2cc7a0
--- /dev/null
+++ b/lib/zlib_inflate/infutil.c
@@ -0,0 +1,49 @@
+#include <linux/zutil.h>
+#include <linux/errno.h>
+#include <linux/slab.h>
+#include <linux/vmalloc.h>
+
+/* Utility function: initialize zlib, unpack binary blob, clean up zlib,
+ * return len or negative error code.
+ */
+int zlib_inflate_blob(void *gunzip_buf, unsigned int sz,
+ const void *buf, unsigned int len)
+{
+ const u8 *zbuf = buf;
+ struct z_stream_s *strm;
+ int rc;
+
+ rc = -ENOMEM;
+ strm = kmalloc(sizeof(*strm), GFP_KERNEL);
+ if (strm == NULL)
+ goto gunzip_nomem1;
+ strm->workspace = kmalloc(zlib_inflate_workspacesize(), GFP_KERNEL);
+ if (strm->workspace == NULL)
+ goto gunzip_nomem2;
+
+ /* gzip header (1f,8b,08... 10 bytes total + possible asciz filename)
+ * expected to be stripped from input
+ */
+ strm->next_in = zbuf;
+ strm->avail_in = len;
+ strm->next_out = gunzip_buf;
+ strm->avail_out = sz;
+
+ rc = zlib_inflateInit2(strm, -MAX_WBITS);
+ if (rc == Z_OK) {
+ rc = zlib_inflate(strm, Z_FINISH);
+ /* after Z_FINISH, only Z_STREAM_END is "we unpacked it all" */
+ if (rc == Z_STREAM_END)
+ rc = sz - strm->avail_out;
+ else
+ rc = -EINVAL;
+ zlib_inflateEnd(strm);
+ } else
+ rc = -EINVAL;
+
+ kfree(strm->workspace);
+gunzip_nomem2:
+ kfree(strm);
+gunzip_nomem1:
+ return rc; /* returns Z_OK (0) if successful */
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-06 21:36:49 +0000