aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig3
-rw-r--r--lib/Kconfig.debug5
-rw-r--r--lib/Makefile3
-rw-r--r--lib/bitmap.c19
-rw-r--r--lib/crc32.c30
-rw-r--r--lib/list_sort.c263
-rw-r--r--lib/show_mem.c14
-rw-r--r--lib/string.c40
8 files changed, 242 insertions, 135 deletions
diff --git a/lib/Kconfig b/lib/Kconfig
index 97b136ff117..8034c46327c 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -160,6 +160,9 @@ config TEXTSEARCH_BM
config TEXTSEARCH_FSM
tristate
+config LIST_SORT
+ boolean
+
config HAS_IOMEM
boolean
depends on !NO_IOMEM
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 5e3407d997b..b520ec1f33c 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -864,8 +864,7 @@ config DEBUG_FORCE_WEAK_PER_CPU
config LKDTM
tristate "Linux Kernel Dump Test Tool Module"
- depends on DEBUG_KERNEL
- depends on KPROBES
+ depends on DEBUG_FS
depends on BLOCK
default n
help
@@ -876,7 +875,7 @@ config LKDTM
called lkdtm.
Documentation on how to use the module can be found in
- drivers/misc/lkdtm.c
+ Documentation/fault-injection/provoke-crashes.txt
config FAULT_INJECTION
bool "Fault-injection framework"
diff --git a/lib/Makefile b/lib/Makefile
index 3b0b4a696db..e39c361b0be 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -21,7 +21,7 @@ lib-y += kobject.o kref.o klist.o
obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
- string_helpers.o gcd.o list_sort.o
+ string_helpers.o gcd.o
ifeq ($(CONFIG_DEBUG_KOBJECT),y)
CFLAGS_kobject.o += -DDEBUG
@@ -40,6 +40,7 @@ lib-$(CONFIG_GENERIC_FIND_FIRST_BIT) += find_next_bit.o
lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o
obj-$(CONFIG_GENERIC_FIND_LAST_BIT) += find_last_bit.o
obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o
+obj-$(CONFIG_LIST_SORT) += list_sort.o
obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o
obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o
obj-$(CONFIG_DEBUG_LIST) += list_debug.o
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 11bf4975058..ffb78c916cc 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -487,7 +487,7 @@ int __bitmap_parse(const char *buf, unsigned int buflen,
EXPORT_SYMBOL(__bitmap_parse);
/**
- * bitmap_parse_user()
+ * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap
*
* @ubuf: pointer to user buffer containing string.
* @ulen: buffer size in bytes. If string is smaller than this
@@ -619,7 +619,7 @@ int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
EXPORT_SYMBOL(bitmap_parselist);
/**
- * bitmap_pos_to_ord(buf, pos, bits)
+ * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
* @buf: pointer to a bitmap
* @pos: a bit position in @buf (0 <= @pos < @bits)
* @bits: number of valid bit positions in @buf
@@ -655,7 +655,7 @@ static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits)
}
/**
- * bitmap_ord_to_pos(buf, ord, bits)
+ * bitmap_ord_to_pos - find position of n-th set bit in bitmap
* @buf: pointer to bitmap
* @ord: ordinal bit position (n-th set bit, n >= 0)
* @bits: number of valid bit positions in @buf
@@ -733,10 +733,9 @@ void bitmap_remap(unsigned long *dst, const unsigned long *src,
bitmap_zero(dst, bits);
w = bitmap_weight(new, bits);
- for (oldbit = find_first_bit(src, bits);
- oldbit < bits;
- oldbit = find_next_bit(src, bits, oldbit + 1)) {
+ for_each_set_bit(oldbit, src, bits) {
int n = bitmap_pos_to_ord(old, oldbit, bits);
+
if (n < 0 || w == 0)
set_bit(oldbit, dst); /* identity map */
else
@@ -903,9 +902,7 @@ void bitmap_onto(unsigned long *dst, const unsigned long *orig,
*/
m = 0;
- for (n = find_first_bit(relmap, bits);
- n < bits;
- n = find_next_bit(relmap, bits, n + 1)) {
+ for_each_set_bit(n, relmap, bits) {
/* m == bitmap_pos_to_ord(relmap, n, bits) */
if (test_bit(m, orig))
set_bit(n, dst);
@@ -934,9 +931,7 @@ void bitmap_fold(unsigned long *dst, const unsigned long *orig,
return;
bitmap_zero(dst, bits);
- for (oldbit = find_first_bit(orig, bits);
- oldbit < bits;
- oldbit = find_next_bit(orig, bits, oldbit + 1))
+ for_each_set_bit(oldbit, orig, bits)
set_bit(oldbit % sz, dst);
}
EXPORT_SYMBOL(bitmap_fold);
diff --git a/lib/crc32.c b/lib/crc32.c
index 02e3b31b3a7..0f45fbff34c 100644
--- a/lib/crc32.c
+++ b/lib/crc32.c
@@ -30,11 +30,15 @@
#include <asm/atomic.h>
#include "crc32defs.h"
#if CRC_LE_BITS == 8
-#define tole(x) __constant_cpu_to_le32(x)
-#define tobe(x) __constant_cpu_to_be32(x)
+# define tole(x) __constant_cpu_to_le32(x)
#else
-#define tole(x) (x)
-#define tobe(x) (x)
+# define tole(x) (x)
+#endif
+
+#if CRC_BE_BITS == 8
+# define tobe(x) __constant_cpu_to_be32(x)
+#else
+# define tobe(x) (x)
#endif
#include "crc32table.h"
@@ -52,20 +56,19 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 *tab)
# else
# define DO_CRC(x) crc = tab[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
# endif
- const u32 *b = (const u32 *)buf;
+ const u32 *b;
size_t rem_len;
/* Align it */
- if (unlikely((long)b & 3 && len)) {
- u8 *p = (u8 *)b;
+ if (unlikely((long)buf & 3 && len)) {
do {
- DO_CRC(*p++);
- } while ((--len) && ((long)p)&3);
- b = (u32 *)p;
+ DO_CRC(*buf++);
+ } while ((--len) && ((long)buf)&3);
}
rem_len = len & 3;
/* load data 32 bits wide, xor data 32 bits wide. */
len = len >> 2;
+ b = (const u32 *)buf;
for (--b; len; --len) {
crc ^= *++b; /* use pre increment for speed */
DO_CRC(0);
@@ -82,6 +85,7 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 *tab)
} while (--len);
}
return crc;
+#undef DO_CRC
}
#endif
/**
@@ -119,9 +123,6 @@ u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
crc = __cpu_to_le32(crc);
crc = crc32_body(crc, p, len, tab);
return __le32_to_cpu(crc);
-#undef ENDIAN_SHIFT
-#undef DO_CRC
-
# elif CRC_LE_BITS == 4
while (len--) {
crc ^= *p++;
@@ -179,9 +180,6 @@ u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
crc = __cpu_to_be32(crc);
crc = crc32_body(crc, p, len, tab);
return __be32_to_cpu(crc);
-#undef ENDIAN_SHIFT
-#undef DO_CRC
-
# elif CRC_BE_BITS == 4
while (len--) {
crc ^= *p++ << 24;
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 19d11e0bb95..4b5cb794c38 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -4,99 +4,214 @@
#include <linux/slab.h>
#include <linux/list.h>
+#define MAX_LIST_LENGTH_BITS 20
+
+/*
+ * Returns a list organized in an intermediate format suited
+ * to chaining of merge() calls: null-terminated, no reserved or
+ * sentinel head node, "prev" links not maintained.
+ */
+static struct list_head *merge(void *priv,
+ int (*cmp)(void *priv, struct list_head *a,
+ struct list_head *b),
+ struct list_head *a, struct list_head *b)
+{
+ struct list_head head, *tail = &head;
+
+ while (a && b) {
+ /* if equal, take 'a' -- important for sort stability */
+ if ((*cmp)(priv, a, b) <= 0) {
+ tail->next = a;
+ a = a->next;
+ } else {
+ tail->next = b;
+ b = b->next;
+ }
+ tail = tail->next;
+ }
+ tail->next = a?:b;
+ return head.next;
+}
+
+/*
+ * Combine final list merge with restoration of standard doubly-linked
+ * list structure. This approach duplicates code from merge(), but
+ * runs faster than the tidier alternatives of either a separate final
+ * prev-link restoration pass, or maintaining the prev links
+ * throughout.
+ */
+static void merge_and_restore_back_links(void *priv,
+ int (*cmp)(void *priv, struct list_head *a,
+ struct list_head *b),
+ struct list_head *head,
+ struct list_head *a, struct list_head *b)
+{
+ struct list_head *tail = head;
+
+ while (a && b) {
+ /* if equal, take 'a' -- important for sort stability */
+ if ((*cmp)(priv, a, b) <= 0) {
+ tail->next = a;
+ a->prev = tail;
+ a = a->next;
+ } else {
+ tail->next = b;
+ b->prev = tail;
+ b = b->next;
+ }
+ tail = tail->next;
+ }
+ tail->next = a ? : b;
+
+ do {
+ /*
+ * In worst cases this loop may run many iterations.
+ * Continue callbacks to the client even though no
+ * element comparison is needed, so the client's cmp()
+ * routine can invoke cond_resched() periodically.
+ */
+ (*cmp)(priv, tail, tail);
+
+ tail->next->prev = tail;
+ tail = tail->next;
+ } while (tail->next);
+
+ tail->next = head;
+ head->prev = tail;
+}
+
/**
- * list_sort - sort a list.
- * @priv: private data, passed to @cmp
+ * list_sort - sort a list
+ * @priv: private data, opaque to list_sort(), passed to @cmp
* @head: the list to sort
* @cmp: the elements comparison function
*
- * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
- * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
- * in ascending order.
+ * This function implements "merge sort", which has O(nlog(n))
+ * complexity.
*
- * The comparison function @cmp is supposed to return a negative value if @a is
- * less than @b, and a positive value if @a is greater than @b. If @a and @b
- * are equivalent, then it does not matter what this function returns.
+ * The comparison function @cmp must return a negative value if @a
+ * should sort before @b, and a positive value if @a should sort after
+ * @b. If @a and @b are equivalent, and their original relative
+ * ordering is to be preserved, @cmp must return 0.
*/
void list_sort(void *priv, struct list_head *head,
- int (*cmp)(void *priv, struct list_head *a,
- struct list_head *b))
+ int (*cmp)(void *priv, struct list_head *a,
+ struct list_head *b))
{
- struct list_head *p, *q, *e, *list, *tail, *oldhead;
- int insize, nmerges, psize, qsize, i;
+ struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
+ -- last slot is a sentinel */
+ int lev; /* index into part[] */
+ int max_lev = 0;
+ struct list_head *list;
if (list_empty(head))
return;
+ memset(part, 0, sizeof(part));
+
+ head->prev->next = NULL;
list = head->next;
- list_del(head);
- insize = 1;
- for (;;) {
- p = oldhead = list;
- list = tail = NULL;
- nmerges = 0;
-
- while (p) {
- nmerges++;
- q = p;
- psize = 0;
- for (i = 0; i < insize; i++) {
- psize++;
- q = q->next == oldhead ? NULL : q->next;
- if (!q)
- break;
- }
- qsize = insize;
- while (psize > 0 || (qsize > 0 && q)) {
- if (!psize) {
- e = q;
- q = q->next;
- qsize--;
- if (q == oldhead)
- q = NULL;
- } else if (!qsize || !q) {
- e = p;
- p = p->next;
- psize--;
- if (p == oldhead)
- p = NULL;
- } else if (cmp(priv, p, q) <= 0) {
- e = p;
- p = p->next;
- psize--;
- if (p == oldhead)
- p = NULL;
- } else {
- e = q;
- q = q->next;
- qsize--;
- if (q == oldhead)
- q = NULL;
- }
- if (tail)
- tail->next = e;
- else
- list = e;
- e->prev = tail;
- tail = e;
+ while (list) {
+ struct list_head *cur = list;
+ list = list->next;
+ cur->next = NULL;
+
+ for (lev = 0; part[lev]; lev++) {
+ cur = merge(priv, cmp, part[lev], cur);
+ part[lev] = NULL;
+ }
+ if (lev > max_lev) {
+ if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
+ printk_once(KERN_DEBUG "list passed to"
+ " list_sort() too long for"
+ " efficiency\n");
+ lev--;
}
- p = q;
+ max_lev = lev;
}
+ part[lev] = cur;
+ }
- tail->next = list;
- list->prev = tail;
+ for (lev = 0; lev < max_lev; lev++)
+ if (part[lev])
+ list = merge(priv, cmp, part[lev], list);
- if (nmerges <= 1)
- break;
+ merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
+}
+EXPORT_SYMBOL(list_sort);
- insize *= 2;
- }
+#ifdef DEBUG_LIST_SORT
+struct debug_el {
+ struct list_head l_h;
+ int value;
+ unsigned serial;
+};
- head->next = list;
- head->prev = list->prev;
- list->prev->next = head;
- list->prev = head;
+static int cmp(void *priv, struct list_head *a, struct list_head *b)
+{
+ return container_of(a, struct debug_el, l_h)->value
+ - container_of(b, struct debug_el, l_h)->value;
}
-EXPORT_SYMBOL(list_sort);
+/*
+ * The pattern of set bits in the list length determines which cases
+ * are hit in list_sort().
+ */
+#define LIST_SORT_TEST_LENGTH (512+128+2) /* not including head */
+
+static int __init list_sort_test(void)
+{
+ int i, r = 1, count;
+ struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL);
+ struct list_head *cur;
+
+ printk(KERN_WARNING "testing list_sort()\n");
+
+ cur = head;
+ for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
+ struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
+ BUG_ON(!el);
+ /* force some equivalencies */
+ el->value = (r = (r * 725861) % 6599) % (LIST_SORT_TEST_LENGTH/3);
+ el->serial = i;
+
+ el->l_h.prev = cur;
+ cur->next = &el->l_h;
+ cur = cur->next;
+ }
+ head->prev = cur;
+
+ list_sort(NULL, head, cmp);
+
+ count = 1;
+ for (cur = head->next; cur->next != head; cur = cur->next) {
+ struct debug_el *el = container_of(cur, struct debug_el, l_h);
+ int cmp_result = cmp(NULL, cur, cur->next);
+ if (cur->next->prev != cur) {
+ printk(KERN_EMERG "list_sort() returned "
+ "a corrupted list!\n");
+ return 1;
+ } else if (cmp_result > 0) {
+ printk(KERN_EMERG "list_sort() failed to sort!\n");
+ return 1;
+ } else if (cmp_result == 0 &&
+ el->serial >= container_of(cur->next,
+ struct debug_el, l_h)->serial) {
+ printk(KERN_EMERG "list_sort() failed to preserve order"
+ " of equivalent elements!\n");
+ return 1;
+ }
+ kfree(cur->prev);
+ count++;
+ }
+ kfree(cur);
+ if (count != LIST_SORT_TEST_LENGTH) {
+ printk(KERN_EMERG "list_sort() returned list of"
+ "different length!\n");
+ return 1;
+ }
+ return 0;
+}
+module_init(list_sort_test);
+#endif
diff --git a/lib/show_mem.c b/lib/show_mem.c
index 238e72a18ce..fdc77c82f92 100644
--- a/lib/show_mem.c
+++ b/lib/show_mem.c
@@ -15,7 +15,7 @@ void show_mem(void)
unsigned long total = 0, reserved = 0, shared = 0,
nonshared = 0, highmem = 0;
- printk(KERN_INFO "Mem-Info:\n");
+ printk("Mem-Info:\n");
show_free_areas();
for_each_online_pgdat(pgdat) {
@@ -49,15 +49,15 @@ void show_mem(void)
pgdat_resize_unlock(pgdat, &flags);
}
- printk(KERN_INFO "%lu pages RAM\n", total);
+ printk("%lu pages RAM\n", total);
#ifdef CONFIG_HIGHMEM
- printk(KERN_INFO "%lu pages HighMem\n", highmem);
+ printk("%lu pages HighMem\n", highmem);
#endif
- printk(KERN_INFO "%lu pages reserved\n", reserved);
- printk(KERN_INFO "%lu pages shared\n", shared);
- printk(KERN_INFO "%lu pages non-shared\n", nonshared);
+ printk("%lu pages reserved\n", reserved);
+ printk("%lu pages shared\n", shared);
+ printk("%lu pages non-shared\n", nonshared);
#ifdef CONFIG_QUICKLIST
- printk(KERN_INFO "%lu pages in pagetable cache\n",
+ printk("%lu pages in pagetable cache\n",
quicklist_total_size());
#endif
}
diff --git a/lib/string.c b/lib/string.c
index a1cdcfcc42d..f71bead1be3 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -36,25 +36,21 @@ int strnicmp(const char *s1, const char *s2, size_t len)
/* Yes, Virginia, it had better be unsigned */
unsigned char c1, c2;
- c1 = c2 = 0;
- if (len) {
- do {
- c1 = *s1;
- c2 = *s2;
- s1++;
- s2++;
- if (!c1)
- break;
- if (!c2)
- break;
- if (c1 == c2)
- continue;
- c1 = tolower(c1);
- c2 = tolower(c2);
- if (c1 != c2)
- break;
- } while (--len);
- }
+ if (!len)
+ return 0;
+
+ do {
+ c1 = *s1++;
+ c2 = *s2++;
+ if (!c1 || !c2)
+ break;
+ if (c1 == c2)
+ continue;
+ c1 = tolower(c1);
+ c2 = tolower(c2);
+ if (c1 != c2)
+ break;
+ } while (--len);
return (int)c1 - (int)c2;
}
EXPORT_SYMBOL(strnicmp);
@@ -693,13 +689,13 @@ EXPORT_SYMBOL(strstr);
*/
char *strnstr(const char *s1, const char *s2, size_t len)
{
- size_t l1 = len, l2;
+ size_t l2;
l2 = strlen(s2);
if (!l2)
return (char *)s1;
- while (l1 >= l2) {
- l1--;
+ while (len >= l2) {
+ len--;
if (!memcmp(s1, s2, l2))
return (char *)s1;
s1++;
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-07 18:44:19 +0000