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#include <linux/linkage.h> 10#include <asm/assembler.h> 11#include <asm/mte-def.h> 12 13/* Assumptions: 14 * 15 * ARMv8-a, AArch64, unaligned accesses, min page size 4k. 16 */ 17 18#define L(label) .L ## label 19 20/* Arguments and results. */ 21#define srcin x0 22#define len x0 23 24/* Locals and temporaries. */ 25#define src x1 26#define data1 x2 27#define data2 x3 28#define has_nul1 x4 29#define has_nul2 x5 30#define tmp1 x4 31#define tmp2 x5 32#define tmp3 x6 33#define tmp4 x7 34#define zeroones x8 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#define REP8_01 0x0101010101010101 43#define REP8_7f 0x7f7f7f7f7f7f7f7f 44#define REP8_80 0x8080808080808080 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#ifdef CONFIG_KASAN_HW_TAGS 52#define MIN_PAGE_SIZE MTE_GRANULE_SIZE 53#else 54#define MIN_PAGE_SIZE 4096 55#endif 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 82SYM_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 110L(main_loop_entry): 111 bic src, srcin, 15 112 sub src, src, 16 113L(main_loop): 114 ldp data1, data2, [src, 32]! 115L(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 1281: 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. */ 138L(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 148L(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. */ 172L(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) 185SYM_FUNC_END(__pi_strlen) 186SYM_FUNC_ALIAS_WEAK(strlen, __pi_strlen) 187EXPORT_SYMBOL_NOKASAN(strlen) 188