| 1 | /* SPDX-License-Identifier: GPL-2.0-only */
|
| 2 | /*
|
| 3 | * Copyright (c) 2013-2021, Arm Limited.
|
| 4 | *
|
| 5 | * Adapted from the original at:
|
| 6 | * https://github.com/ARM-software/optimized-routines/blob/98e4d6a5c13c8e54/string/aarch64/strlen.S
|
| 7 | */
|
| 8 |
|
| 9 | |
| 10 | |
| 11 | |
| 12 |
|
| 13 | /* Assumptions:
|
| 14 | *
|
| 15 | * ARMv8-a, AArch64, unaligned accesses, min page size 4k.
|
| 16 | */
|
| 17 |
|
| 18 | |
| 19 |
|
| 20 | /* Arguments and results. */
|
| 21 | |
| 22 | |
| 23 |
|
| 24 | /* Locals and temporaries. */
|
| 25 | |
| 26 | |
| 27 | |
| 28 | |
| 29 | |
| 30 | |
| 31 | |
| 32 | |
| 33 | |
| 34 | |
| 35 |
|
| 36 | /* NUL detection works on the principle that (X - 1) & (~X) & 0x80
|
| 37 | (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and
|
| 38 | can be done in parallel across the entire word. A faster check
|
| 39 | (X - 1) & 0x80 is zero for non-NUL ASCII characters, but gives
|
| 40 | false hits for characters 129..255. */
|
| 41 |
|
| 42 | |
| 43 | |
| 44 | |
| 45 |
|
| 46 | /*
|
| 47 | * When KASAN_HW_TAGS is in use, memory is checked at MTE_GRANULE_SIZE
|
| 48 | * (16-byte) granularity, and we must ensure that no access straddles this
|
| 49 | * alignment boundary.
|
| 50 | */
|
| 51 | |
| 52 | |
| 53 | |
| 54 | |
| 55 | |
| 56 |
|
| 57 | /* Since strings are short on average, we check the first 16 bytes
|
| 58 | of the string for a NUL character. In order to do an unaligned ldp
|
| 59 | safely we have to do a page cross check first. If there is a NUL
|
| 60 | byte we calculate the length from the 2 8-byte words using
|
| 61 | conditional select to reduce branch mispredictions (it is unlikely
|
| 62 | strlen will be repeatedly called on strings with the same length).
|
| 63 |
|
| 64 | If the string is longer than 16 bytes, we align src so don't need
|
| 65 | further page cross checks, and process 32 bytes per iteration
|
| 66 | using the fast NUL check. If we encounter non-ASCII characters,
|
| 67 | fallback to a second loop using the full NUL check.
|
| 68 |
|
| 69 | If the page cross check fails, we read 16 bytes from an aligned
|
| 70 | address, remove any characters before the string, and continue
|
| 71 | in the main loop using aligned loads. Since strings crossing a
|
| 72 | page in the first 16 bytes are rare (probability of
|
| 73 | 16/MIN_PAGE_SIZE ~= 0.4%), this case does not need to be optimized.
|
| 74 |
|
| 75 | AArch64 systems have a minimum page size of 4k. We don't bother
|
| 76 | checking for larger page sizes - the cost of setting up the correct
|
| 77 | page size is just not worth the extra gain from a small reduction in
|
| 78 | the cases taking the slow path. Note that we only care about
|
| 79 | whether the first fetch, which may be misaligned, crosses a page
|
| 80 | boundary. */
|
| 81 |
|
| 82 | SYM_FUNC_START(__pi_strlen)
|
| 83 | and tmp1, srcin, MIN_PAGE_SIZE - 1
|
| 84 | mov zeroones, REP8_01
|
| 85 | cmp tmp1, MIN_PAGE_SIZE - 16
|
| 86 | b.gt L(page_cross)
|
| 87 | ldp data1, data2, [srcin]
|
| 88 | sub tmp1, data1, zeroones
|
| 89 | orr tmp2, data1, REP8_7f
|
| 90 | sub tmp3, data2, zeroones
|
| 91 | orr tmp4, data2, REP8_7f
|
| 92 | bics has_nul1, tmp1, tmp2
|
| 93 | bic has_nul2, tmp3, tmp4
|
| 94 | ccmp has_nul2, 0, 0, eq
|
| 95 | beq L(main_loop_entry)
|
| 96 |
|
| 97 | /* Enter with C = has_nul1 == 0. */
|
| 98 | csel has_nul1, has_nul1, has_nul2, cc
|
| 99 | mov len, 8
|
| 100 | rev has_nul1, has_nul1
|
| 101 | clz tmp1, has_nul1
|
| 102 | csel len, xzr, len, cc
|
| 103 | add len, len, tmp1, lsr 3
|
| 104 | ret
|
| 105 |
|
| 106 | /* The inner loop processes 32 bytes per iteration and uses the fast
|
| 107 | NUL check. If we encounter non-ASCII characters, use a second
|
| 108 | loop with the accurate NUL check. */
|
| 109 | .p2align 4
|
| 110 | L(main_loop_entry):
|
| 111 | bic src, srcin, 15
|
| 112 | sub src, src, 16
|
| 113 | L(main_loop):
|
| 114 | ldp data1, data2, [src, 32]!
|
| 115 | L(page_cross_entry):
|
| 116 | sub tmp1, data1, zeroones
|
| 117 | sub tmp3, data2, zeroones
|
| 118 | orr tmp2, tmp1, tmp3
|
| 119 | tst tmp2, zeroones, lsl 7
|
| 120 | bne 1f
|
| 121 | ldp data1, data2, [src, 16]
|
| 122 | sub tmp1, data1, zeroones
|
| 123 | sub tmp3, data2, zeroones
|
| 124 | orr tmp2, tmp1, tmp3
|
| 125 | tst tmp2, zeroones, lsl 7
|
| 126 | beq L(main_loop)
|
| 127 | add src, src, 16
|
| 128 | 1:
|
| 129 | /* The fast check failed, so do the slower, accurate NUL check. */
|
| 130 | orr tmp2, data1, REP8_7f
|
| 131 | orr tmp4, data2, REP8_7f
|
| 132 | bics has_nul1, tmp1, tmp2
|
| 133 | bic has_nul2, tmp3, tmp4
|
| 134 | ccmp has_nul2, 0, 0, eq
|
| 135 | beq L(nonascii_loop)
|
| 136 |
|
| 137 | /* Enter with C = has_nul1 == 0. */
|
| 138 | L(tail):
|
| 139 | csel has_nul1, has_nul1, has_nul2, cc
|
| 140 | sub len, src, srcin
|
| 141 | rev has_nul1, has_nul1
|
| 142 | add tmp2, len, 8
|
| 143 | clz tmp1, has_nul1
|
| 144 | csel len, len, tmp2, cc
|
| 145 | add len, len, tmp1, lsr 3
|
| 146 | ret
|
| 147 |
|
| 148 | L(nonascii_loop):
|
| 149 | ldp data1, data2, [src, 16]!
|
| 150 | sub tmp1, data1, zeroones
|
| 151 | orr tmp2, data1, REP8_7f
|
| 152 | sub tmp3, data2, zeroones
|
| 153 | orr tmp4, data2, REP8_7f
|
| 154 | bics has_nul1, tmp1, tmp2
|
| 155 | bic has_nul2, tmp3, tmp4
|
| 156 | ccmp has_nul2, 0, 0, eq
|
| 157 | bne L(tail)
|
| 158 | ldp data1, data2, [src, 16]!
|
| 159 | sub tmp1, data1, zeroones
|
| 160 | orr tmp2, data1, REP8_7f
|
| 161 | sub tmp3, data2, zeroones
|
| 162 | orr tmp4, data2, REP8_7f
|
| 163 | bics has_nul1, tmp1, tmp2
|
| 164 | bic has_nul2, tmp3, tmp4
|
| 165 | ccmp has_nul2, 0, 0, eq
|
| 166 | beq L(nonascii_loop)
|
| 167 | b L(tail)
|
| 168 |
|
| 169 | /* Load 16 bytes from [srcin & ~15] and force the bytes that precede
|
| 170 | srcin to 0x7f, so we ignore any NUL bytes before the string.
|
| 171 | Then continue in the aligned loop. */
|
| 172 | L(page_cross):
|
| 173 | bic src, srcin, 15
|
| 174 | ldp data1, data2, [src]
|
| 175 | lsl tmp1, srcin, 3
|
| 176 | mov tmp4, -1
|
| 177 | lsl tmp1, tmp4, tmp1 /* Shift (tmp1 & 63). */
|
| 178 | orr tmp1, tmp1, REP8_80
|
| 179 | orn data1, data1, tmp1
|
| 180 | orn tmp2, data2, tmp1
|
| 181 | tst srcin, 8
|
| 182 | csel data1, data1, tmp4, eq
|
| 183 | csel data2, data2, tmp2, eq
|
| 184 | b L(page_cross_entry)
|
| 185 | SYM_FUNC_END(__pi_strlen)
|
| 186 | SYM_FUNC_ALIAS_WEAK(strlen, __pi_strlen)
|
| 187 | EXPORT_SYMBOL_NOKASAN(strlen)
|