linux-toradex.git/lib/find_next_bit.c, branch v4.9.76

lib: rename lib/find_next_bit.c to lib/find_bit.c

2015-04-17T13:03:54+00:00

This file contains implementation for all find_*_bit{,_le}
So giving it more generic name looks reasonable.

Signed-off-by: Yury Norov 
Reviewed-by: Rasmus Villemoes 
Reviewed-by: George Spelvin 
Cc: Alexey Klimov 
Cc: David S. Miller 
Cc: Daniel Borkmann 
Cc: Hannes Frederic Sowa 
Cc: Lai Jiangshan 
Cc: Mark Salter 
Cc: AKASHI Takahiro 
Cc: Thomas Graf 
Cc: Valentin Rothberg 
Cc: Chris Wilson 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

lib: move find_last_bit to lib/find_next_bit.c

2015-04-17T13:03:54+00:00

Currently all 'find_*_bit' family is located in lib/find_next_bit.c,
except 'find_last_bit', which is in lib/find_last_bit.c. It seems,
there's no major benefit to have it separated.

Signed-off-by: Yury Norov 
Reviewed-by: Rasmus Villemoes 
Reviewed-by: George Spelvin 
Cc: Alexey Klimov 
Cc: David S. Miller 
Cc: Daniel Borkmann 
Cc: Hannes Frederic Sowa 
Cc: Lai Jiangshan 
Cc: Mark Salter 
Cc: AKASHI Takahiro 
Cc: Thomas Graf 
Cc: Valentin Rothberg 
Cc: Chris Wilson 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

lib: find_*_bit reimplementation

2015-04-17T13:03:53+00:00

This patchset does rework to find_bit function family to achieve better
performance, and decrease size of text.  All rework is done in patch 1.
Patches 2 and 3 are about code moving and renaming.

It was boot-tested on x86_64 and MIPS (big-endian) machines.
Performance tests were ran on userspace with code like this:

	/* addr[] is filled from /dev/urandom */
	start = clock();
	while (ret < nbits)
		ret = find_next_bit(addr, nbits, ret + 1);

	end = clock();
	printf("%ld\t", (unsigned long) end - start);

On Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz measurements are: (for
find_next_bit, nbits is 8M, for find_first_bit - 80K)

	find_next_bit:		find_first_bit:
	new	current		new	current
	26932	43151		14777	14925
	26947	43182		14521	15423
	26507	43824		15053	14705
	27329	43759		14473	14777
	26895	43367		14847	15023
	26990	43693		15103	15163
	26775	43299		15067	15232
	27282	42752		14544	15121
	27504	43088		14644	14858
	26761	43856		14699	15193
	26692	43075		14781	14681
	27137	42969		14451	15061
	...			...

find_next_bit performance gain is 35-40%;
find_first_bit - no measurable difference.

On ARM machine, there is arch-specific implementation for find_bit.

Thanks a lot to George Spelvin and Rasmus Villemoes for hints and
helpful discussions.

This patch (of 3):

New implementations takes less space in source file (see diffstat) and in
object.  For me it's 710 vs 453 bytes of text.  It also shows better
performance.

find_last_bit description fixed due to obvious typo.

[akpm@linux-foundation.org: include linux/bitmap.h, per Rasmus]
Signed-off-by: Yury Norov 
Reviewed-by: Rasmus Villemoes 
Reviewed-by: George Spelvin 
Cc: Alexey Klimov 
Cc: David S. Miller 
Cc: Daniel Borkmann 
Cc: Hannes Frederic Sowa 
Cc: Lai Jiangshan 
Cc: Mark Salter 
Cc: AKASHI Takahiro 
Cc: Thomas Graf 
Cc: Valentin Rothberg 
Cc: Chris Wilson 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

lib: reduce the use of module.h wherever possible

2012-03-07T20:04:04+00:00

For files only using THIS_MODULE and/or EXPORT_SYMBOL, map
them onto including export.h -- or if the file isn't even
using those, then just delete the include.  Fix up any implicit
include dependencies that were being masked by module.h along
the way.

Signed-off-by: Paul Gortmaker

arch: remove CONFIG_GENERIC_FIND_{NEXT_BIT,BIT_LE,LAST_BIT}

2011-05-27T00:12:38+00:00

By the previous style change, CONFIG_GENERIC_FIND_NEXT_BIT,
CONFIG_GENERIC_FIND_BIT_LE, and CONFIG_GENERIC_FIND_LAST_BIT are not used
to test for existence of find bitops anymore.

Signed-off-by: Akinobu Mita 
Acked-by: Greg Ungerer 
Cc: Arnd Bergmann 
Cc: Russell King 
Cc: Martin Schwidefsky 
Cc: Heiko Carstens 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

bitops: add #ifndef for each of find bitops

2011-05-27T00:12:38+00:00

The style that we normally use in asm-generic is to test the macro itself
for existence, so in asm-generic, do:

	#ifndef find_next_zero_bit_le
	extern unsigned long find_next_zero_bit_le(const void *addr,
		unsigned long size, unsigned long offset);
	#endif

and in the architectures, write

	static inline unsigned long find_next_zero_bit_le(const void *addr,
		unsigned long size, unsigned long offset)
	#define find_next_zero_bit_le find_next_zero_bit_le

This adds the #ifndef for each of the find bitops in the generic header
and source files.

Suggested-by: Arnd Bergmann 
Signed-off-by: Akinobu Mita 
Acked-by: Russell King 
Cc: Martin Schwidefsky 
Cc: Heiko Carstens 
Cc: Greg Ungerer 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

bitops: introduce CONFIG_GENERIC_FIND_BIT_LE

2011-03-24T02:46:14+00:00

This introduces CONFIG_GENERIC_FIND_BIT_LE to tell whether to use generic
implementation of find_*_bit_le() in lib/find_next_bit.c or not.

For now we select CONFIG_GENERIC_FIND_BIT_LE for all architectures which
enable CONFIG_GENERIC_FIND_NEXT_BIT.

But m68knommu wants to define own faster find_next_zero_bit_le() and
continues using generic find_next_{,zero_}bit().
(CONFIG_GENERIC_FIND_NEXT_BIT and !CONFIG_GENERIC_FIND_BIT_LE)

Signed-off-by: Akinobu Mita 
Cc: Greg Ungerer 
Cc: Arnd Bergmann 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

asm-generic: change little-endian bitops to take any pointer types

2011-03-24T02:46:12+00:00

This makes the little-endian bitops take any pointer types by changing the
prototypes and adding casts in the preprocessor macros.

That would seem to at least make all the filesystem code happier, and they
can continue to do just something like

  #define ext2_set_bit __test_and_set_bit_le

(or whatever the exact sequence ends up being).

Signed-off-by: Akinobu Mita 
Cc: Arnd Bergmann 
Cc: Richard Henderson 
Cc: Ivan Kokshaysky 
Cc: Mikael Starvik 
Cc: David Howells 
Cc: Yoshinori Sato 
Cc: "Luck, Tony" 
Cc: Ralf Baechle 
Cc: Kyle McMartin 
Cc: Matthew Wilcox 
Cc: Grant Grundler 
Cc: Paul Mundt 
Cc: Kazumoto Kojima 
Cc: Hirokazu Takata 
Cc: "David S. Miller" 
Cc: Chris Zankel 
Cc: Ingo Molnar 
Cc: Thomas Gleixner 
Cc: Hans-Christian Egtvedt 
Cc: "H. Peter Anvin" 
Cc: Benjamin Herrenschmidt 
Cc: Paul Mackerras 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

asm-generic: rename generic little-endian bitops functions

2011-03-24T02:46:11+00:00

As a preparation for providing little-endian bitops for all architectures,
This renames generic implementation of little-endian bitops.  (remove
"generic_" prefix and postfix "_le")

s/generic_find_next_le_bit/find_next_bit_le/
s/generic_find_next_zero_le_bit/find_next_zero_bit_le/
s/generic_find_first_zero_le_bit/find_first_zero_bit_le/
s/generic___test_and_set_le_bit/__test_and_set_bit_le/
s/generic___test_and_clear_le_bit/__test_and_clear_bit_le/
s/generic_test_le_bit/test_bit_le/
s/generic___set_le_bit/__set_bit_le/
s/generic___clear_le_bit/__clear_bit_le/
s/generic_test_and_set_le_bit/test_and_set_bit_le/
s/generic_test_and_clear_le_bit/test_and_clear_bit_le/

Signed-off-by: Akinobu Mita 
Acked-by: Arnd Bergmann 
Acked-by: Hans-Christian Egtvedt 
Cc: Geert Uytterhoeven 
Cc: Roman Zippel 
Cc: Andreas Schwab 
Cc: Greg Ungerer 
Cc: Benjamin Herrenschmidt 
Cc: Paul Mackerras 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

bitops: remove "optimizations"

2008-04-29T15:11:16+00:00

The mapsize optimizations which were moved from x86 to the generic
code in commit 64970b68d2b3ed32b964b0b30b1b98518fde388e increased the
binary size on non x86 architectures.

Looking into the real effects of the "optimizations" it turned out
that they are not used in find_next_bit() and find_next_zero_bit().

The ones in find_first_bit() and find_first_zero_bit() are used in a
couple of places but none of them is a real hot path.

Remove the "optimizations" all together and call the library functions
unconditionally.

Boot-tested on x86 and compile tested on every cross compiler I have.

Signed-off-by: Thomas Gleixner 
Signed-off-by: Linus Torvalds