• Linus Torvalds's avatar
    word-at-a-time: make the interfaces truly generic · 36126f8f
    Linus Torvalds authored
    This changes the interfaces in <asm/word-at-a-time.h> to be a bit more
    complicated, but a lot more generic.
    
    In particular, it allows us to really do the operations efficiently on
    both little-endian and big-endian machines, pretty much regardless of
    machine details.  For example, if you can rely on a fast population
    count instruction on your architecture, this will allow you to make your
    optimized <asm/word-at-a-time.h> file with that.
    
    NOTE! The "generic" version in include/asm-generic/word-at-a-time.h is
    not truly generic, it actually only works on big-endian.  Why? Because
    on little-endian the generic algorithms are wasteful, since you can
    inevitably do better. The x86 implementation is an example of that.
    
    (The only truly non-generic part of the asm-generic implementation is
    the "find_zero()" function, and you could make a little-endian version
    of it.  And if the Kbuild infrastructure allowed us to pick a particular
    header file, that would be lovely)
    
    The <asm/word-at-a-time.h> functions are as follows:
    
     - WORD_AT_A_TIME_CONSTANTS: specific constants that the algorithm
       uses.
    
     - has_zero(): take a word, and determine if it has a zero byte in it.
       It gets the word, the pointer to the constant pool, and a pointer to
       an intermediate "data" field it can set.
    
       This is the "quick-and-dirty" zero tester: it's what is run inside
       the hot loops.
    
     - "prep_zero_mask()": take the word, the data that has_zero() produced,
       and the constant pool, and generate an *exact* mask of which byte had
       the first zero.  This is run directly *outside* the loop, and allows
       the "has_zero()" function to answer the "is there a zero byte"
       question without necessarily getting exactly *which* byte is the
       first one to contain a zero.
    
       If you do multiple byte lookups concurrently (eg "hash_name()", which
       looks for both NUL and '/' bytes), after you've done the prep_zero_mask()
       phase, the result of those can be or'ed together to get the "either
       or" case.
    
     - The result from "prep_zero_mask()" can then be fed into "find_zero()"
       (to find the byte offset of the first byte that was zero) or into
       "zero_bytemask()" (to find the bytemask of the bytes preceding the
       zero byte).
    
       The existence of zero_bytemask() is optional, and is not necessary
       for the normal string routines.  But dentry name hashing needs it, so
       if you enable DENTRY_WORD_AT_A_TIME you need to expose it.
    
    This changes the generic strncpy_from_user() function and the dentry
    hashing functions to use these modified word-at-a-time interfaces.  This
    gets us back to the optimized state of the x86 strncpy that we lost in
    the previous commit when moving over to the generic version.
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    36126f8f
Name
Last commit
Last update
Documentation Loading commit data...
arch Loading commit data...
block Loading commit data...
crypto Loading commit data...
drivers Loading commit data...
firmware Loading commit data...
fs Loading commit data...
include Loading commit data...
init Loading commit data...
ipc Loading commit data...
kernel Loading commit data...
lib Loading commit data...
mm Loading commit data...
net Loading commit data...
samples Loading commit data...
scripts Loading commit data...
security Loading commit data...
sound Loading commit data...
tools Loading commit data...
usr Loading commit data...
virt/kvm Loading commit data...
.gitignore Loading commit data...
.mailmap Loading commit data...
COPYING Loading commit data...
CREDITS Loading commit data...
Kbuild Loading commit data...
Kconfig Loading commit data...
MAINTAINERS Loading commit data...
Makefile Loading commit data...
README Loading commit data...
REPORTING-BUGS Loading commit data...