diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Kconfig | 10 | ||||
| -rw-r--r-- | lib/Makefile | 8 | ||||
| -rw-r--r-- | lib/find_last_bit.c | 4 | ||||
| -rw-r--r-- | lib/find_next_bit.c | 18 | ||||
| -rw-r--r-- | lib/flex_array.c | 51 |
5 files changed, 47 insertions, 44 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index 9c10e38fc609..830181cc7a83 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -19,16 +19,6 @@ config RATIONAL config GENERIC_FIND_FIRST_BIT bool -config GENERIC_FIND_NEXT_BIT - bool - -config GENERIC_FIND_BIT_LE - bool - -config GENERIC_FIND_LAST_BIT - bool - default y - config CRC_CCITT tristate "CRC-CCITT functions" help diff --git a/lib/Makefile b/lib/Makefile index 4b49a249064b..6b597fdb1898 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ idr.o int_sqrt.o extable.o prio_tree.o \ sha1.o irq_regs.o reciprocal_div.o argv_split.o \ proportions.o prio_heap.o ratelimit.o show_mem.o \ - is_single_threaded.o plist.o decompress.o + is_single_threaded.o plist.o decompress.o find_next_bit.o lib-$(CONFIG_MMU) += ioremap.o lib-$(CONFIG_SMP) += cpumask.o @@ -22,7 +22,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 lcm.o list_sort.o uuid.o flex_array.o \ - bsearch.o + bsearch.o find_last_bit.o obj-y += kstrtox.o obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o @@ -39,10 +39,6 @@ obj-$(CONFIG_DEBUG_LOCKING_API_SELFTESTS) += locking-selftest.o obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock_debug.o lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o -lib-$(CONFIG_GENERIC_FIND_FIRST_BIT) += find_next_bit.o -lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o -lib-$(CONFIG_GENERIC_FIND_BIT_LE) += find_next_bit.o -obj-$(CONFIG_GENERIC_FIND_LAST_BIT) += find_last_bit.o CFLAGS_hweight.o = $(subst $(quote),,$(CONFIG_ARCH_HWEIGHT_CFLAGS)) obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o diff --git a/lib/find_last_bit.c b/lib/find_last_bit.c index 5d202e36bdd8..d903959ad695 100644 --- a/lib/find_last_bit.c +++ b/lib/find_last_bit.c @@ -15,6 +15,8 @@ #include <asm/types.h> #include <asm/byteorder.h> +#ifndef find_last_bit + unsigned long find_last_bit(const unsigned long *addr, unsigned long size) { unsigned long words; @@ -43,3 +45,5 @@ found: return size; } EXPORT_SYMBOL(find_last_bit); + +#endif diff --git a/lib/find_next_bit.c b/lib/find_next_bit.c index b0a8767282bf..4bd75a73ba00 100644 --- a/lib/find_next_bit.c +++ b/lib/find_next_bit.c @@ -16,7 +16,7 @@ #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) -#ifdef CONFIG_GENERIC_FIND_NEXT_BIT +#ifndef find_next_bit /* * Find the next set bit in a memory region. */ @@ -59,7 +59,9 @@ found_middle: return result + __ffs(tmp); } EXPORT_SYMBOL(find_next_bit); +#endif +#ifndef find_next_zero_bit /* * This implementation of find_{first,next}_zero_bit was stolen from * Linus' asm-alpha/bitops.h. @@ -103,9 +105,9 @@ found_middle: return result + ffz(tmp); } EXPORT_SYMBOL(find_next_zero_bit); -#endif /* CONFIG_GENERIC_FIND_NEXT_BIT */ +#endif -#ifdef CONFIG_GENERIC_FIND_FIRST_BIT +#ifndef find_first_bit /* * Find the first set bit in a memory region. */ @@ -131,7 +133,9 @@ found: return result + __ffs(tmp); } EXPORT_SYMBOL(find_first_bit); +#endif +#ifndef find_first_zero_bit /* * Find the first cleared bit in a memory region. */ @@ -157,10 +161,9 @@ found: return result + ffz(tmp); } EXPORT_SYMBOL(find_first_zero_bit); -#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ +#endif #ifdef __BIG_ENDIAN -#ifdef CONFIG_GENERIC_FIND_BIT_LE /* include/linux/byteorder does not support "unsigned long" type */ static inline unsigned long ext2_swabp(const unsigned long * x) @@ -186,6 +189,7 @@ static inline unsigned long ext2_swab(const unsigned long y) #endif } +#ifndef find_next_zero_bit_le unsigned long find_next_zero_bit_le(const void *addr, unsigned long size, unsigned long offset) { @@ -229,7 +233,9 @@ found_middle_swap: return result + ffz(ext2_swab(tmp)); } EXPORT_SYMBOL(find_next_zero_bit_le); +#endif +#ifndef find_next_bit_le unsigned long find_next_bit_le(const void *addr, unsigned long size, unsigned long offset) { @@ -274,6 +280,6 @@ found_middle_swap: return result + __ffs(ext2_swab(tmp)); } EXPORT_SYMBOL(find_next_bit_le); +#endif -#endif /* CONFIG_GENERIC_FIND_BIT_LE */ #endif /* __BIG_ENDIAN */ diff --git a/lib/flex_array.c b/lib/flex_array.c index cab7621f98aa..9b8b89458c4c 100644 --- a/lib/flex_array.c +++ b/lib/flex_array.c @@ -24,6 +24,7 @@ #include <linux/slab.h> #include <linux/stddef.h> #include <linux/module.h> +#include <linux/reciprocal_div.h> struct flex_array_part { char elements[FLEX_ARRAY_PART_SIZE]; @@ -70,15 +71,15 @@ static inline int elements_fit_in_base(struct flex_array *fa) * Element size | Objects | Objects | * PAGE_SIZE=4k | 32-bit | 64-bit | * ---------------------------------| - * 1 bytes | 4186112 | 2093056 | - * 2 bytes | 2093056 | 1046528 | - * 3 bytes | 1395030 | 697515 | - * 4 bytes | 1046528 | 523264 | - * 32 bytes | 130816 | 65408 | - * 33 bytes | 126728 | 63364 | - * 2048 bytes | 2044 | 1022 | - * 2049 bytes | 1022 | 511 | - * void * | 1046528 | 261632 | + * 1 bytes | 4177920 | 2088960 | + * 2 bytes | 2088960 | 1044480 | + * 3 bytes | 1392300 | 696150 | + * 4 bytes | 1044480 | 522240 | + * 32 bytes | 130560 | 65408 | + * 33 bytes | 126480 | 63240 | + * 2048 bytes | 2040 | 1020 | + * 2049 bytes | 1020 | 510 | + * void * | 1044480 | 261120 | * * Since 64-bit pointers are twice the size, we lose half the * capacity in the base structure. Also note that no effort is made @@ -88,11 +89,15 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total, gfp_t flags) { struct flex_array *ret; + int elems_per_part = 0; + int reciprocal_elems = 0; int max_size = 0; - if (element_size) - max_size = FLEX_ARRAY_NR_BASE_PTRS * - FLEX_ARRAY_ELEMENTS_PER_PART(element_size); + if (element_size) { + elems_per_part = FLEX_ARRAY_ELEMENTS_PER_PART(element_size); + reciprocal_elems = reciprocal_value(elems_per_part); + max_size = FLEX_ARRAY_NR_BASE_PTRS * elems_per_part; + } /* max_size will end up 0 if element_size > PAGE_SIZE */ if (total > max_size) @@ -102,6 +107,8 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total, return NULL; ret->element_size = element_size; ret->total_nr_elements = total; + ret->elems_per_part = elems_per_part; + ret->reciprocal_elems = reciprocal_elems; if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO)) memset(&ret->parts[0], FLEX_ARRAY_FREE, FLEX_ARRAY_BASE_BYTES_LEFT); @@ -112,7 +119,7 @@ EXPORT_SYMBOL(flex_array_alloc); static int fa_element_to_part_nr(struct flex_array *fa, unsigned int element_nr) { - return element_nr / FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size); + return reciprocal_divide(element_nr, fa->reciprocal_elems); } /** @@ -141,12 +148,12 @@ void flex_array_free(struct flex_array *fa) EXPORT_SYMBOL(flex_array_free); static unsigned int index_inside_part(struct flex_array *fa, - unsigned int element_nr) + unsigned int element_nr, + unsigned int part_nr) { unsigned int part_offset; - part_offset = element_nr % - FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size); + part_offset = element_nr - part_nr * fa->elems_per_part; return part_offset * fa->element_size; } @@ -186,7 +193,7 @@ __fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags) int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src, gfp_t flags) { - int part_nr; + int part_nr = 0; struct flex_array_part *part; void *dst; @@ -202,7 +209,7 @@ int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src, if (!part) return -ENOMEM; } - dst = &part->elements[index_inside_part(fa, element_nr)]; + dst = &part->elements[index_inside_part(fa, element_nr, part_nr)]; memcpy(dst, src, fa->element_size); return 0; } @@ -217,7 +224,7 @@ EXPORT_SYMBOL(flex_array_put); */ int flex_array_clear(struct flex_array *fa, unsigned int element_nr) { - int part_nr; + int part_nr = 0; struct flex_array_part *part; void *dst; @@ -233,7 +240,7 @@ int flex_array_clear(struct flex_array *fa, unsigned int element_nr) if (!part) return -EINVAL; } - dst = &part->elements[index_inside_part(fa, element_nr)]; + dst = &part->elements[index_inside_part(fa, element_nr, part_nr)]; memset(dst, FLEX_ARRAY_FREE, fa->element_size); return 0; } @@ -302,7 +309,7 @@ EXPORT_SYMBOL(flex_array_prealloc); */ void *flex_array_get(struct flex_array *fa, unsigned int element_nr) { - int part_nr; + int part_nr = 0; struct flex_array_part *part; if (!fa->element_size) @@ -317,7 +324,7 @@ void *flex_array_get(struct flex_array *fa, unsigned int element_nr) if (!part) return NULL; } - return &part->elements[index_inside_part(fa, element_nr)]; + return &part->elements[index_inside_part(fa, element_nr, part_nr)]; } EXPORT_SYMBOL(flex_array_get); |
