mbox series

[v3,0/2] Improve wcsstr

Message ID 20240315172346.2484542-1-adhemerval.zanella@linaro.org
Headers show
Series Improve wcsstr | expand

Message

Adhemerval Zanella Netto March 15, 2024, 5:23 p.m. UTC 
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 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 | 314 +++++++++++++++++++++++++++++++++++--------
 wcsmbs/Makefile      |   1 +
 wcsmbs/test-wcsstr.c |  20 +++
 wcsmbs/wcs-two-way.h | 312 ++++++++++++++++++++++++++++++++++++++++++
 wcsmbs/wcsstr.c      | 103 +++++---------
 5 files changed, 624 insertions(+), 126 deletions(-)
 create mode 100644 wcsmbs/test-wcsstr.c
 create mode 100644 wcsmbs/wcs-two-way.h