Message ID | 20230202181149.2181553-9-adhemerval.zanella@linaro.org |
---|---|
State | New |
Headers | show |
Series | Improve generic string routines | expand |
On 2/2/23 08:11, Adhemerval Zanella wrote: > It follows the strategy: > > - Align the first input to word boundary using byte operations. > > - If second input is also word aligned, read a word per time, check > for null (using has_zero), and check final words using byte > operation. > > - If second input is not word aligned, loop by aligning the source, > and merge the result of two reads. Similar to aligned case, check > for null with has_zero, and check final words using byte operation. > > Checked on x86_64-linux-gnu, i686-linux-gnu, powerpc64-linux-gnu, > and powerpc-linux-gnu by removing the arch-specific assembly > implementation and disabling multi-arch (it covers both LE and BE > for 64 and 32 bits). > --- > string/strncmp.c | 138 ++++++++++++++++++++++++++++++++++------------- > 1 file changed, 101 insertions(+), 37 deletions(-) Reviewed-by: Richard Henderson <richard.henderson@linaro.org> r~
The 02/02/2023 15:11, Adhemerval Zanella via Libc-alpha wrote: > It follows the strategy: > > - Align the first input to word boundary using byte operations. > > - If second input is also word aligned, read a word per time, check > for null (using has_zero), and check final words using byte > operation. > > - If second input is not word aligned, loop by aligning the source, > and merge the result of two reads. Similar to aligned case, check > for null with has_zero, and check final words using byte operation. > > Checked on x86_64-linux-gnu, i686-linux-gnu, powerpc64-linux-gnu, > and powerpc-linux-gnu by removing the arch-specific assembly > implementation and disabling multi-arch (it covers both LE and BE > for 64 and 32 bits). on arm i see FAIL: crypt/badsalttest Program received signal SIGSEGV, Segmentation fault. strncmp_unaligned_loop (n=3, ofs=<optimized out>, w1=2371876, x2=0xf7feb000, x1=0xf7f6563c) at strncmp.c:85 85 w2b = *x2++; this strncmp does out of bounds read: Breakpoint 2, __GI_strncmp (p1=0xf7f65638 <md5_salt_prefix> "$1$", p2=p2@entry=0xf7feafff "*", n=n@entry=3) at strncmp.c:115 0xf7feb000 is mapped PROT_NONE. > +strncmp_unaligned_loop (const op_t *x1, const op_t *x2, op_t w1, uintptr_t ofs, > + size_t n) > +{ > + op_t w2a = *x2++; > + uintptr_t sh_1 = ofs * CHAR_BIT; > + uintptr_t sh_2 = sizeof(op_t) * CHAR_BIT - sh_1; > + > + op_t w2 = MERGE (w2a, sh_1, (op_t)-1, sh_2); > + if (!has_zero (w2) && n > (sizeof (op_t) - ofs)) > { > - c1 = (unsigned char) *s1++; > - c2 = (unsigned char) *s2++; > - if (c1 == '\0' || c1 != c2) > - return c1 - c2; > - n--; > + op_t w2b; > + > + /* Unaligned loop. The invariant is that W2B, which is "ahead" of W1, > + does not contain end-of-string. Therefore it is safe (and necessary) > + to read another word from each while we do not have a difference. */ > + while (1) > + { > + w2b = *x2++; ^^^^^^^^^^^^^^^^^^^^^^ reading ahead is wrong if w1 and w2 already mismatches. > + w2 = MERGE (w2a, sh_1, w2b, sh_2); > + if (n <= sizeof (op_t) || w1 != w2) > + return final_cmp (w1, w2, n); > + n -= sizeof(op_t); > + if (has_zero (w2b) || n <= (sizeof (op_t) - ofs)) > + break; > + w1 = *x1++; > + w2a = w2b; > + } > + > + /* Zero found in the second partial of P2. If we had EOS in the aligned > + word, we have equality. */ > + if (has_zero (w1)) > + return 0; > + > + /* Load the final word of P1 and align the final partial of P2. */ > + w1 = *x1++; > + w2 = MERGE (w2b, sh_1, 0, sh_2); > } > > - return c1 - c2; > + return final_cmp (w1, w2, n);
On 21/02/23 06:28, Szabolcs Nagy wrote: > The 02/02/2023 15:11, Adhemerval Zanella via Libc-alpha wrote: >> It follows the strategy: >> >> - Align the first input to word boundary using byte operations. >> >> - If second input is also word aligned, read a word per time, check >> for null (using has_zero), and check final words using byte >> operation. >> >> - If second input is not word aligned, loop by aligning the source, >> and merge the result of two reads. Similar to aligned case, check >> for null with has_zero, and check final words using byte operation. >> >> Checked on x86_64-linux-gnu, i686-linux-gnu, powerpc64-linux-gnu, >> and powerpc-linux-gnu by removing the arch-specific assembly >> implementation and disabling multi-arch (it covers both LE and BE >> for 64 and 32 bits). > > on arm i see > > FAIL: crypt/badsalttest > > Program received signal SIGSEGV, Segmentation fault. > strncmp_unaligned_loop (n=3, ofs=<optimized out>, w1=2371876, x2=0xf7feb000, x1=0xf7f6563c) at strncmp.c:85 > 85 w2b = *x2++; > > this strncmp does out of bounds read: > > Breakpoint 2, __GI_strncmp (p1=0xf7f65638 <md5_salt_prefix> "$1$", p2=p2@entry=0xf7feafff "*", n=n@entry=3) at strncmp.c:115 > > 0xf7feb000 is mapped PROT_NONE. > >> +strncmp_unaligned_loop (const op_t *x1, const op_t *x2, op_t w1, uintptr_t ofs, >> + size_t n) >> +{ >> + op_t w2a = *x2++; >> + uintptr_t sh_1 = ofs * CHAR_BIT; >> + uintptr_t sh_2 = sizeof(op_t) * CHAR_BIT - sh_1; >> + >> + op_t w2 = MERGE (w2a, sh_1, (op_t)-1, sh_2); >> + if (!has_zero (w2) && n > (sizeof (op_t) - ofs)) >> { >> - c1 = (unsigned char) *s1++; >> - c2 = (unsigned char) *s2++; >> - if (c1 == '\0' || c1 != c2) >> - return c1 - c2; >> - n--; >> + op_t w2b; >> + >> + /* Unaligned loop. The invariant is that W2B, which is "ahead" of W1, >> + does not contain end-of-string. Therefore it is safe (and necessary) >> + to read another word from each while we do not have a difference. */ >> + while (1) >> + { >> + w2b = *x2++; > ^^^^^^^^^^^^^^^^^^^^^^ > > reading ahead is wrong if w1 and w2 already mismatches. Right, I will take a look. > >> + w2 = MERGE (w2a, sh_1, w2b, sh_2); >> + if (n <= sizeof (op_t) || w1 != w2) >> + return final_cmp (w1, w2, n); >> + n -= sizeof(op_t); >> + if (has_zero (w2b) || n <= (sizeof (op_t) - ofs)) >> + break; >> + w1 = *x1++; >> + w2a = w2b; >> + } >> + >> + /* Zero found in the second partial of P2. If we had EOS in the aligned >> + word, we have equality. */ >> + if (has_zero (w1)) >> + return 0; >> + >> + /* Load the final word of P1 and align the final partial of P2. */ >> + w1 = *x1++; >> + w2 = MERGE (w2b, sh_1, 0, sh_2); >> } >> >> - return c1 - c2; >> + return final_cmp (w1, w2, n);
diff --git a/string/strncmp.c b/string/strncmp.c index fd7cee09b6..4c8bf36bb9 100644 --- a/string/strncmp.c +++ b/string/strncmp.c @@ -15,7 +15,12 @@ License along with the GNU C Library; if not, see <https://www.gnu.org/licenses/>. */ +#include <stdint.h> +#include <string-fzb.h> +#include <string-fzc.h> +#include <string-fzi.h> #include <string.h> +#include <sys/param.h> #include <memcopy.h> #undef strncmp @@ -24,51 +29,110 @@ #define STRNCMP strncmp #endif -/* Compare no more than N characters of S1 and S2, - returning less than, equal to or greater than zero - if S1 is lexicographically less than, equal to or - greater than S2. */ -int -STRNCMP (const char *s1, const char *s2, size_t n) +static inline int +final_cmp (const op_t w1, const op_t w2, size_t n) +{ + unsigned int idx = index_first_zero_ne (w1, w2); + if (n <= idx) + return 0; + return extractbyte (w1, idx) - extractbyte (w2, idx); +} + +/* Aligned loop: if a difference is found, exit to compare the bytes. Else + if a zero is found we have equal strings. */ +static inline int +strncmp_aligned_loop (const op_t *x1, const op_t *x2, op_t w1, size_t n) { - unsigned char c1 = '\0'; - unsigned char c2 = '\0'; + op_t w2 = *x2++; - if (n >= 4) + while (w1 == w2) { - size_t n4 = n >> 2; - do - { - c1 = (unsigned char) *s1++; - c2 = (unsigned char) *s2++; - if (c1 == '\0' || c1 != c2) - return c1 - c2; - c1 = (unsigned char) *s1++; - c2 = (unsigned char) *s2++; - if (c1 == '\0' || c1 != c2) - return c1 - c2; - c1 = (unsigned char) *s1++; - c2 = (unsigned char) *s2++; - if (c1 == '\0' || c1 != c2) - return c1 - c2; - c1 = (unsigned char) *s1++; - c2 = (unsigned char) *s2++; - if (c1 == '\0' || c1 != c2) - return c1 - c2; - } while (--n4 > 0); - n &= 3; + if (n <= sizeof (op_t)) + break; + n -= sizeof (op_t); + + if (has_zero (w1)) + return 0; + w1 = *x1++; + w2 = *x2++; } - while (n > 0) + return final_cmp (w1, w2, n); +} + +/* Unaligned loop: align the first partial of P2, with 0xff for the rest of + the bytes so that we can also apply the has_zero test to see if we have + already reached EOS. If we have, then we can simply fall through to the + final comparison. */ +static inline int +strncmp_unaligned_loop (const op_t *x1, const op_t *x2, op_t w1, uintptr_t ofs, + size_t n) +{ + op_t w2a = *x2++; + uintptr_t sh_1 = ofs * CHAR_BIT; + uintptr_t sh_2 = sizeof(op_t) * CHAR_BIT - sh_1; + + op_t w2 = MERGE (w2a, sh_1, (op_t)-1, sh_2); + if (!has_zero (w2) && n > (sizeof (op_t) - ofs)) { - c1 = (unsigned char) *s1++; - c2 = (unsigned char) *s2++; - if (c1 == '\0' || c1 != c2) - return c1 - c2; - n--; + op_t w2b; + + /* Unaligned loop. The invariant is that W2B, which is "ahead" of W1, + does not contain end-of-string. Therefore it is safe (and necessary) + to read another word from each while we do not have a difference. */ + while (1) + { + w2b = *x2++; + w2 = MERGE (w2a, sh_1, w2b, sh_2); + if (n <= sizeof (op_t) || w1 != w2) + return final_cmp (w1, w2, n); + n -= sizeof(op_t); + if (has_zero (w2b) || n <= (sizeof (op_t) - ofs)) + break; + w1 = *x1++; + w2a = w2b; + } + + /* Zero found in the second partial of P2. If we had EOS in the aligned + word, we have equality. */ + if (has_zero (w1)) + return 0; + + /* Load the final word of P1 and align the final partial of P2. */ + w1 = *x1++; + w2 = MERGE (w2b, sh_1, 0, sh_2); } - return c1 - c2; + return final_cmp (w1, w2, n); } +/* Compare no more than N characters of S1 and S2, + returning less than, equal to or greater than zero + if S1 is lexicographically less than, equal to or + greater than S2. */ +int +STRNCMP (const char *p1, const char *p2, size_t n) +{ + /* Handle the unaligned bytes of p1 first. */ + uintptr_t a = MIN (-(uintptr_t)p1 % sizeof(op_t), n); + int diff = 0; + for (int i = 0; i < a; ++i) + { + unsigned char c1 = *p1++; + unsigned char c2 = *p2++; + diff = c1 - c2; + if (c1 == '\0' || diff != 0) + return diff; + } + if (a == n) + return 0; + + /* P1 is now aligned to op_t. P2 may or may not be. */ + const op_t *x1 = (const op_t *) p1; + op_t w1 = *x1++; + uintptr_t ofs = (uintptr_t) p2 % sizeof(op_t); + return ofs == 0 + ? strncmp_aligned_loop (x1, (const op_t *) p2, w1, n - a) + : strncmp_unaligned_loop (x1, (const op_t *) (p2 - ofs), w1, ofs, n - a); +} libc_hidden_builtin_def (STRNCMP)