[PATCH v4 0/2] Improve wcsstr
Adhemerval Zanella
adhemerval.zanella@linaro.org
Tue Mar 19 13:15:26 GMT 2024
Different than strstr, wcsstr still uses an O(m*n) algorithm that might
be considered a security issue (although BZ 23865 was marked security-
since there is no actual application impact).
The gnulib recently added a wrapper to fix it [1] and it is used as the
base de str-two-way.h implementation. This patch adds a similar
implementation, and different than strstr, neither the "shift table"
optimization nor the self-adapting filtering check is used because it
would result in a too-large shift table (and it also simplifies the
implementation bit). The patchset also added a proper tests for wcsstr,
based on strstr one.
With this fix, and with the removal of the powerpc strcasestr
optimization [2], it seems that only x86_64 still provides a non
O(m*n) implementation [3]. Noah already gave a +1, so it would be
good to have some confirmation that this implementation can really
show some quadradic behaviour before propose a removal.
[1] https://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=commit;h=9411c5e467cf60f6295b9fed306029f341a0f24f
[2] https://sourceware.org/git/?p=glibc.git;a=commit;h=4a76fb1da8b7e7fa472741921f49ef32f81bc0a0
[3] https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/strstr-avx512.c;h=3ac53accbdde0b400dfd19a2070fbb579aff4177;hb=4a76fb1da8b7e7fa472741921f49ef32f81bc0a0
--
Changes from v3:
* Fixed check-abi regression.
Changes from v2:
* Remove the test repetition.
Changes from v1:
* Add more tests from gnulib.
* Removed unused macros from wcsstr.
--
Adhemerval Zanella (2):
wcsmbs: Add test-wcsstr
wcsmbs: Ensure wcstr worst-case linear execution time (BZ 23865)
string/test-strstr.c | 316 +++++++++++++++++++++++++++++++++++--------
wcsmbs/Makefile | 1 +
wcsmbs/test-wcsstr.c | 20 +++
wcsmbs/wcs-two-way.h | 312 ++++++++++++++++++++++++++++++++++++++++++
wcsmbs/wcsstr.c | 101 ++++----------
5 files changed, 624 insertions(+), 126 deletions(-)
create mode 100644 wcsmbs/test-wcsstr.c
create mode 100644 wcsmbs/wcs-two-way.h
--
2.34.1
More information about the Libc-alpha
mailing list