| commit | a4959aa6f819df0efdab6995e5de530655734389 | [log] [tgz] |
|---|---|---|
| author | Elliott Hughes <enh@google.com> | Tue Oct 08 12:04:09 2019 -0700 |
| committer | Elliott Hughes <enh@google.com> | Tue Oct 08 12:04:09 2019 -0700 |
| tree | 7f2ceae2b6c167bbfd20d1e9bbc9c1d52ff6fa7e | |
| parent | 29ec2881a0a87ccda75c77fd967934d863d53cc1 [diff] |
Reimplement the <ctype.h> is* functions.
Following on from the towlower()/towupper() changes, add benchmarks for
most of <ctype.h>, rewrite the tests to cover the entire defined range
for all of these functions, and then reimplement most of the functions.
The old table-based implementation is mostly a bad idea on modern
hardware, with only ispunct() showing a significant benefit compared to
any other way I could think of writing it, and isalnum() a marginal but
still convincingly genuine benefit.
My new benchmarks make an effort to test an example from each relevant
range of characters to avoid, say, accidentally optimizing the behavior
of `isalnum('0')` at the expense of `isalnum('z')`.
Interestingly, clang is able to generate what I believe to be the
optimal implementations from the most readable code, which is
impressive. It certainly matched or beat all my attempts to be clever!
The BSD table-based implementations made a special case of EOF despite
having a `_ctype_` table that's offset by 1 to include EOF at index 0.
I'm not sure why they didn't take advantage of that, but removing the
explicit check for EOF measurably improves the generated code on arm and
arm64, so even the two functions that still use the table benefit from
this rewrite.
Here are the benchmark results:
arm64 before:
BM_ctype_isalnum_n 3.73 ns 3.73 ns 183727137
BM_ctype_isalnum_y1 3.82 ns 3.81 ns 186383058
BM_ctype_isalnum_y2 3.73 ns 3.72 ns 187809830
BM_ctype_isalnum_y3 3.78 ns 3.77 ns 181383055
BM_ctype_isalpha_n 3.75 ns 3.75 ns 189453927
BM_ctype_isalpha_y1 3.76 ns 3.75 ns 184854043
BM_ctype_isalpha_y2 4.32 ns 3.78 ns 186326931
BM_ctype_isascii_n 2.49 ns 2.48 ns 275583822
BM_ctype_isascii_y 2.51 ns 2.51 ns 282123915
BM_ctype_isblank_n 3.11 ns 3.10 ns 220472044
BM_ctype_isblank_y1 3.20 ns 3.19 ns 226088868
BM_ctype_isblank_y2 3.11 ns 3.11 ns 220809122
BM_ctype_iscntrl_n 3.79 ns 3.78 ns 188719938
BM_ctype_iscntrl_y1 3.72 ns 3.71 ns 186209237
BM_ctype_iscntrl_y2 3.80 ns 3.80 ns 184315749
BM_ctype_isdigit_n 3.76 ns 3.74 ns 188334682
BM_ctype_isdigit_y 3.78 ns 3.77 ns 186249335
BM_ctype_isgraph_n 3.99 ns 3.98 ns 177814143
BM_ctype_isgraph_y1 3.98 ns 3.95 ns 175140090
BM_ctype_isgraph_y2 4.01 ns 4.00 ns 178320453
BM_ctype_isgraph_y3 3.96 ns 3.95 ns 175412814
BM_ctype_isgraph_y4 4.01 ns 4.00 ns 175711174
BM_ctype_islower_n 3.75 ns 3.74 ns 188604818
BM_ctype_islower_y 3.79 ns 3.78 ns 154738238
BM_ctype_isprint_n 3.96 ns 3.95 ns 177607734
BM_ctype_isprint_y1 3.94 ns 3.93 ns 174877244
BM_ctype_isprint_y2 4.02 ns 4.01 ns 178206135
BM_ctype_isprint_y3 3.94 ns 3.93 ns 175959069
BM_ctype_isprint_y4 4.03 ns 4.02 ns 176158314
BM_ctype_isprint_y5 3.95 ns 3.94 ns 178745462
BM_ctype_ispunct_n 3.78 ns 3.77 ns 184727184
BM_ctype_ispunct_y 3.76 ns 3.75 ns 187947503
BM_ctype_isspace_n 3.74 ns 3.74 ns 185300285
BM_ctype_isspace_y1 3.77 ns 3.76 ns 187202066
BM_ctype_isspace_y2 3.73 ns 3.73 ns 184105959
BM_ctype_isupper_n 3.81 ns 3.80 ns 185038761
BM_ctype_isupper_y 3.71 ns 3.71 ns 185885793
BM_ctype_isxdigit_n 3.79 ns 3.79 ns 184965673
BM_ctype_isxdigit_y1 3.76 ns 3.75 ns 188251672
BM_ctype_isxdigit_y2 3.79 ns 3.78 ns 184187481
BM_ctype_isxdigit_y3 3.77 ns 3.76 ns 187635540
arm64 after:
BM_ctype_isalnum_n 3.37 ns 3.37 ns 205613810
BM_ctype_isalnum_y1 3.40 ns 3.39 ns 204806361
BM_ctype_isalnum_y2 3.43 ns 3.43 ns 205066077
BM_ctype_isalnum_y3 3.50 ns 3.50 ns 200057128
BM_ctype_isalpha_n 2.97 ns 2.97 ns 236084076
BM_ctype_isalpha_y1 2.97 ns 2.97 ns 236083626
BM_ctype_isalpha_y2 2.97 ns 2.97 ns 236084246
BM_ctype_isascii_n 2.55 ns 2.55 ns 272879994
BM_ctype_isascii_y 2.46 ns 2.45 ns 286522323
BM_ctype_isblank_n 3.18 ns 3.18 ns 220431175
BM_ctype_isblank_y1 3.18 ns 3.18 ns 220345602
BM_ctype_isblank_y2 3.18 ns 3.18 ns 220308509
BM_ctype_iscntrl_n 3.10 ns 3.10 ns 220344270
BM_ctype_iscntrl_y1 3.10 ns 3.07 ns 228973615
BM_ctype_iscntrl_y2 3.07 ns 3.07 ns 229192626
BM_ctype_isdigit_n 3.07 ns 3.07 ns 228925676
BM_ctype_isdigit_y 3.07 ns 3.07 ns 229182934
BM_ctype_isgraph_n 2.66 ns 2.66 ns 264268737
BM_ctype_isgraph_y1 2.66 ns 2.66 ns 264445277
BM_ctype_isgraph_y2 2.66 ns 2.66 ns 264327427
BM_ctype_isgraph_y3 2.66 ns 2.66 ns 264427480
BM_ctype_isgraph_y4 2.66 ns 2.66 ns 264155250
BM_ctype_islower_n 2.66 ns 2.66 ns 264421600
BM_ctype_islower_y 2.66 ns 2.66 ns 264341148
BM_ctype_isprint_n 2.66 ns 2.66 ns 264415198
BM_ctype_isprint_y1 2.66 ns 2.66 ns 264268793
BM_ctype_isprint_y2 2.66 ns 2.66 ns 264419205
BM_ctype_isprint_y3 2.66 ns 2.66 ns 264205886
BM_ctype_isprint_y4 2.66 ns 2.66 ns 264440797
BM_ctype_isprint_y5 2.72 ns 2.72 ns 264333293
BM_ctype_ispunct_n 3.52 ns 3.51 ns 198956572
BM_ctype_ispunct_y 3.38 ns 3.38 ns 201661792
BM_ctype_isspace_n 3.39 ns 3.39 ns 206896620
BM_ctype_isspace_y1 3.39 ns 3.39 ns 206569020
BM_ctype_isspace_y2 3.39 ns 3.39 ns 206564415
BM_ctype_isupper_n 2.76 ns 2.75 ns 254227134
BM_ctype_isupper_y 2.76 ns 2.75 ns 254235314
BM_ctype_isxdigit_n 3.60 ns 3.60 ns 194418653
BM_ctype_isxdigit_y1 2.97 ns 2.97 ns 236082424
BM_ctype_isxdigit_y2 3.48 ns 3.48 ns 200390011
BM_ctype_isxdigit_y3 3.48 ns 3.48 ns 202255815
arm32 before:
BM_ctype_isalnum_n 4.77 ns 4.76 ns 129230464
BM_ctype_isalnum_y1 4.88 ns 4.87 ns 147939321
BM_ctype_isalnum_y2 4.74 ns 4.73 ns 145508054
BM_ctype_isalnum_y3 4.81 ns 4.80 ns 144968914
BM_ctype_isalpha_n 4.80 ns 4.79 ns 148262579
BM_ctype_isalpha_y1 4.74 ns 4.73 ns 145061326
BM_ctype_isalpha_y2 4.83 ns 4.82 ns 147642546
BM_ctype_isascii_n 3.74 ns 3.72 ns 186711139
BM_ctype_isascii_y 3.79 ns 3.78 ns 183654780
BM_ctype_isblank_n 4.20 ns 4.19 ns 169733252
BM_ctype_isblank_y1 4.19 ns 4.18 ns 165713363
BM_ctype_isblank_y2 4.22 ns 4.21 ns 168776265
BM_ctype_iscntrl_n 4.75 ns 4.74 ns 145417484
BM_ctype_iscntrl_y1 4.82 ns 4.81 ns 146283250
BM_ctype_iscntrl_y2 4.79 ns 4.78 ns 148662453
BM_ctype_isdigit_n 4.77 ns 4.76 ns 145789210
BM_ctype_isdigit_y 4.84 ns 4.84 ns 146909458
BM_ctype_isgraph_n 4.72 ns 4.71 ns 145874663
BM_ctype_isgraph_y1 4.86 ns 4.85 ns 142037606
BM_ctype_isgraph_y2 4.79 ns 4.78 ns 145109612
BM_ctype_isgraph_y3 4.75 ns 4.75 ns 144829039
BM_ctype_isgraph_y4 4.86 ns 4.85 ns 146769899
BM_ctype_islower_n 4.76 ns 4.75 ns 147537637
BM_ctype_islower_y 4.79 ns 4.78 ns 145648017
BM_ctype_isprint_n 4.82 ns 4.81 ns 147154780
BM_ctype_isprint_y1 4.76 ns 4.76 ns 145117604
BM_ctype_isprint_y2 4.87 ns 4.86 ns 145801406
BM_ctype_isprint_y3 4.79 ns 4.78 ns 148043446
BM_ctype_isprint_y4 4.77 ns 4.76 ns 145157619
BM_ctype_isprint_y5 4.91 ns 4.90 ns 147810800
BM_ctype_ispunct_n 4.74 ns 4.73 ns 145588611
BM_ctype_ispunct_y 4.82 ns 4.81 ns 144065436
BM_ctype_isspace_n 4.78 ns 4.77 ns 147153712
BM_ctype_isspace_y1 4.73 ns 4.72 ns 145252863
BM_ctype_isspace_y2 4.84 ns 4.83 ns 148615797
BM_ctype_isupper_n 4.75 ns 4.74 ns 148276631
BM_ctype_isupper_y 4.80 ns 4.79 ns 145529893
BM_ctype_isxdigit_n 4.78 ns 4.77 ns 147271646
BM_ctype_isxdigit_y1 4.74 ns 4.74 ns 145142209
BM_ctype_isxdigit_y2 4.83 ns 4.82 ns 146398497
BM_ctype_isxdigit_y3 4.78 ns 4.77 ns 147617686
arm32 after:
BM_ctype_isalnum_n 4.35 ns 4.35 ns 161086146
BM_ctype_isalnum_y1 4.36 ns 4.35 ns 160961111
BM_ctype_isalnum_y2 4.36 ns 4.36 ns 160733210
BM_ctype_isalnum_y3 4.35 ns 4.35 ns 160897524
BM_ctype_isalpha_n 3.67 ns 3.67 ns 189377208
BM_ctype_isalpha_y1 3.68 ns 3.67 ns 189438146
BM_ctype_isalpha_y2 3.75 ns 3.69 ns 190971186
BM_ctype_isascii_n 3.69 ns 3.68 ns 191029191
BM_ctype_isascii_y 3.68 ns 3.68 ns 191011817
BM_ctype_isblank_n 4.09 ns 4.09 ns 171887541
BM_ctype_isblank_y1 4.09 ns 4.09 ns 171829345
BM_ctype_isblank_y2 4.08 ns 4.07 ns 170585590
BM_ctype_iscntrl_n 4.08 ns 4.07 ns 170614383
BM_ctype_iscntrl_y1 4.13 ns 4.11 ns 171495899
BM_ctype_iscntrl_y2 4.19 ns 4.18 ns 165255578
BM_ctype_isdigit_n 4.25 ns 4.24 ns 165237008
BM_ctype_isdigit_y 4.24 ns 4.24 ns 165256149
BM_ctype_isgraph_n 3.82 ns 3.81 ns 183610114
BM_ctype_isgraph_y1 3.82 ns 3.81 ns 183614131
BM_ctype_isgraph_y2 3.82 ns 3.81 ns 183616840
BM_ctype_isgraph_y3 3.79 ns 3.79 ns 183620182
BM_ctype_isgraph_y4 3.82 ns 3.81 ns 185740009
BM_ctype_islower_n 3.75 ns 3.74 ns 183619502
BM_ctype_islower_y 3.68 ns 3.68 ns 190999901
BM_ctype_isprint_n 3.69 ns 3.68 ns 190899544
BM_ctype_isprint_y1 3.68 ns 3.67 ns 190192384
BM_ctype_isprint_y2 3.67 ns 3.67 ns 189351466
BM_ctype_isprint_y3 3.67 ns 3.67 ns 189430348
BM_ctype_isprint_y4 3.68 ns 3.68 ns 189430161
BM_ctype_isprint_y5 3.69 ns 3.68 ns 190962419
BM_ctype_ispunct_n 4.14 ns 4.14 ns 171034861
BM_ctype_ispunct_y 4.19 ns 4.19 ns 168308152
BM_ctype_isspace_n 4.50 ns 4.50 ns 156250887
BM_ctype_isspace_y1 4.48 ns 4.48 ns 155124476
BM_ctype_isspace_y2 4.50 ns 4.50 ns 155077504
BM_ctype_isupper_n 3.68 ns 3.68 ns 191020583
BM_ctype_isupper_y 3.68 ns 3.68 ns 191015669
BM_ctype_isxdigit_n 4.50 ns 4.50 ns 156276745
BM_ctype_isxdigit_y1 3.28 ns 3.27 ns 214729725
BM_ctype_isxdigit_y2 4.48 ns 4.48 ns 155265129
BM_ctype_isxdigit_y3 4.48 ns 4.48 ns 155216846
I've also corrected a small mistake in the documentation for isxdigit().
Test: tests and benchmarks
Change-Id: I4a77859f826c3fc8f0e327e847886882f29ec4a3
bionic is Android's C library, math library, and dynamic linker.
See the user documentation.
This documentation is about making changes to bionic itself.
The C library. Stuff like fopen(3) and kill(2).
The math library. Traditionally Unix systems kept stuff like sin(3) and cos(3) in a separate library to save space in the days before shared libraries.
The dynamic linker interface library. This is actually just a bunch of stubs that the dynamic linker replaces with pointers to its own implementation at runtime. This is where stuff like dlopen(3) lives.
The C++ ABI support functions. The C++ compiler doesn't know how to implement thread-safe static initialization and the like, so it just calls functions that are supplied by the system. Stuff like __cxa_guard_acquire and __cxa_pure_virtual live here.
The dynamic linker. When you run a dynamically-linked executable, its ELF file has a DT_INTERP entry that says "use the following program to start me". On Android, that's either linker or linker64 (depending on whether it's a 32-bit or 64-bit executable). It's responsible for loading the ELF executable into memory and resolving references to symbols (so that when your code tries to jump to fopen(3), say, it lands in the right place).
The tests/ directory contains unit tests. Roughly arranged as one file per publicly-exported header file.
The benchmarks/ directory contains benchmarks, with its own documentation.
libc/
arch-arm/
arch-arm64/
arch-common/
arch-mips/
arch-mips64/
arch-x86/
arch-x86_64/
# Each architecture has its own subdirectory for stuff that isn't shared
# because it's architecture-specific. There will be a .mk file in here that
# drags in all the architecture-specific files.
bionic/
# Every architecture needs a handful of machine-specific assembler files.
# They live here.
string/
# Most architectures have a handful of optional assembler files
# implementing optimized versions of various routines. The <string.h>
# functions are particular favorites.
syscalls/
# The syscalls directories contain script-generated assembler files.
# See 'Adding system calls' later.
include/
# The public header files on everyone's include path. These are a mixture of
# files written by us and files taken from BSD.
kernel/
# The kernel uapi header files. These are scrubbed copies of the originals
# in external/kernel-headers/. These files must not be edited directly. The
# generate_uapi_headers.sh script should be used to go from a kernel tree to
# external/kernel-headers/ --- this takes care of the architecture-specific
# details. The update_all.py script should be used to regenerate bionic's
# scrubbed headers from external/kernel-headers/.
private/
# These are private header files meant for use within bionic itself.
dns/
# Contains the DNS resolver (originates from NetBSD code).
upstream-freebsd/
upstream-netbsd/
upstream-openbsd/
# These directories contain unmolested upstream source. Any time we can
# just use a BSD implementation of something unmodified, we should.
# The structure under these directories mimics the upstream tree,
# but there's also...
android/
include/
# This is where we keep the hacks necessary to build BSD source
# in our world. The *-compat.h files are automatically included
# using -include, but we also provide equivalents for missing
# header/source files needed by the BSD implementation.
bionic/
# This is the biggest mess. The C++ files are files we own, typically
# because the Linux kernel interface is sufficiently different that we
# can't use any of the BSD implementations. The C files are usually
# legacy mess that needs to be sorted out, either by replacing it with
# current upstream source in one of the upstream directories or by
# switching the file to C++ and cleaning it up.
malloc_debug/
# The code that implements the functionality to enable debugging of
# native allocation problems.
stdio/
# These are legacy files of dubious provenance. We're working to clean
# this mess up, and this directory should disappear.
tools/
# Various tools used to maintain bionic.
tzcode/
# A modified superset of the IANA tzcode. Most of the modifications relate
# to Android's use of a single file (with corresponding index) to contain
# time zone data.
zoneinfo/
# Android-format time zone data.
# See 'Updating tzdata' later.
The first question you should ask is "should I add a libc wrapper for this system call?". The answer is usually "no".
The answer is "yes" if the system call is part of the POSIX standard.
The answer is probably "yes" if the system call has a wrapper in at least one other C library.
The answer may be "yes" if the system call has three/four distinct users in different projects, and there isn't a more specific library that would make more sense as the place to add the wrapper.
In all other cases, you should use syscall(3) instead.
Adding a system call usually involves:
__INTRODUCED_IN().As mentioned above, this is currently a two-step process:
Note that if you're actually just trying to expose device-specific headers to build your device drivers, you shouldn't modify bionic. Instead use TARGET_DEVICE_KERNEL_HEADERS and friends described in config.mk.
This is handled by the libcore team, because they own icu, and that needs to be updated in sync with bionic). See system/timezone/README.android.
If you make a change that is likely to have a wide effect on the tree (such as a libc header change), you should run make checkbuild. A regular make will not build the entire tree; just the minimum number of projects that are required for the device. Tests, additional developer tools, and various other modules will not be built. Note that make checkbuild will not be complete either, as make tests covers a few additional modules, but generally speaking make checkbuild is enough.
The tests are all built from the tests/ directory.
$ mma # In $ANDROID_ROOT/bionic.
$ adb root && adb remount && adb sync
$ adb shell /data/nativetest/bionic-unit-tests/bionic-unit-tests
$ adb shell \
/data/nativetest/bionic-unit-tests-static/bionic-unit-tests-static
# Only for 64-bit targets
$ adb shell /data/nativetest64/bionic-unit-tests/bionic-unit-tests
$ adb shell \
/data/nativetest64/bionic-unit-tests-static/bionic-unit-tests-static
Note that we use our own custom gtest runner that offers a superset of the options documented at https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuide.md#running-test-programs-advanced-options, in particular for test isolation and parallelism (both on by default).
Most of the unit tests are executed by CTS. By default, CTS runs as a non-root user, so the unit tests must also pass when not run as root. Some tests cannot do any useful work unless run as root. In this case, the test should check getuid() == 0 and do nothing otherwise (typically we log in this case to prevent accidents!). Obviously, if the test can be rewritten to not require root, that's an even better solution.
Currently, the list of bionic CTS tests is generated at build time by running a host version of the test executable and dumping the list of all tests. In order for this to continue to work, all architectures must have the same number of tests, and the host version of the executable must also have the same number of tests.
Running the gtests directly is orders of magnitude faster than using CTS, but in cases where you really have to run CTS:
$ make cts # In $ANDROID_ROOT.
$ adb unroot # Because real CTS doesn't run as root.
# This will sync any *test* changes, but not *code* changes:
$ cts-tradefed \
run singleCommand cts --skip-preconditions -m CtsBionicTestCases
The host tests require that you have lunched either an x86 or x86_64 target. Note that due to ABI limitations (specifically, the size of pthread_mutex_t), 32-bit bionic requires PIDs less than 65536. To enforce this, set /proc/sys/kernel/pid_max to 65536.
$ ./tests/run-on-host.sh 32 $ ./tests/run-on-host.sh 64 # For x86_64-bit *targets* only.
You can supply gtest flags as extra arguments to this script.
As a way to check that our tests do in fact test the correct behavior (and not just the behavior we think is correct), it is possible to run the tests against the host's glibc.
$ ./tests/run-on-host.sh glibc
For either host or target coverage, you must first:
$ export NATIVE_COVERAGE=truebionic_coverage=true in libc/Android.mk and libm/Android.mk.$ mma
$ adb sync
$ adb shell \
GCOV_PREFIX=/data/local/tmp/gcov \
GCOV_PREFIX_STRIP=`echo $ANDROID_BUILD_TOP | grep -o / | wc -l` \
/data/nativetest/bionic-unit-tests/bionic-unit-tests
$ acov
acov will pull all coverage information from the device, push it to the right directories, run lcov, and open the coverage report in your browser.
First, build and run the host tests as usual (see above).
$ croot $ lcov -c -d $ANDROID_PRODUCT_OUT -o coverage.info $ genhtml -o covreport coverage.info # or lcov --list coverage.info
The coverage report is now available at covreport/index.html.
Bionic's test runner will run each test in its own process by default to prevent tests failures from impacting other tests. This also has the added benefit of running them in parallel, so they are much faster.
However, this also makes it difficult to run the tests under GDB. To prevent each test from being forked, run the tests with the flag --no-isolate.
See 32-bit ABI bugs.