From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pl1-x632.google.com (mail-pl1-x632.google.com [IPv6:2607:f8b0:4864:20::632]) by sourceware.org (Postfix) with ESMTPS id 414843858C36 for ; Tue, 19 Mar 2024 13:15:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 414843858C36 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linaro.org ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 414843858C36 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::632 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1710854137; cv=none; b=Gx5mBGByAQ6e/aUavVWdZs2ZSGVN5MCa2ek5WLDL+q4+wj4a7tUgh+VnLJDP3ysl8caW3Yy7Kf2kGGXoDFjoFKpx6a5KB/Shp9Ofy98rn+p4eJ5fBi3bsgdwbtXV6vdAAKpFMsIYeIUeAqobzkBEjzuQxubSBe7pvNv020xjGs8= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1710854137; c=relaxed/simple; bh=zN8gKHmbbZ66vn6a2XdaUD/y+62CYRZ2tTyq0VAtN0w=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=dH/uLJ0ReS61G/PRqFaJjfAp0Stc9zPfgWdrU7BPo3jJWpdt4F9HUJkSuIw265i0AtdntEoqfBkwARXJRQArTQzWQ4OhAaaxcr2FuvFl5cK4yI0Q81mzLbOLdgf9FOjUMmAj2DdTj4KWFzDbsd20ICJ/57dHmHpWdVGc7Hkj3F4= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pl1-x632.google.com with SMTP id d9443c01a7336-1df01161b39so28284315ad.3 for ; Tue, 19 Mar 2024 06:15:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1710854133; x=1711458933; darn=sourceware.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=8HXh4HUucEDUkTAogxqDpn+MBy5W8YkmFEd+AvVpg2E=; b=wSWsBxWns4+s/HQqizmTM/q3iKwX6a4xRkDY/OuY93S7S2xi93Qw+j/Nuf+Qm4PiAQ klINoharTXW7xxobYXPnjuBGBzoGTPb7K105TEzyqXKa4wjLoSWeDKhbJGeH4IILFfEf 0LPceYTjCoy2FMO/S4fx39sS+K7qL446kkSs4uQ3lh3o2X7pM70UQtR0eAszFYXVl8vg JFiXHQ3MYiYUMZsvEJioicCz0GRkoWfAHrT7xzlYa7m8yPZccqG7UGR/OTZdOjAOUDa8 yk7uxO2BSMuNpf7g2e8Ml0GZknxCvhuwX45IXZPMmwvoL6OdXrPOAmJyP7b6RK3jsjOe IHlA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710854133; x=1711458933; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=8HXh4HUucEDUkTAogxqDpn+MBy5W8YkmFEd+AvVpg2E=; b=kCnhyRU3ibbIko6ihV5XR3mDY8Sc63MKDwmXmd3h63V8IZ/u9sx/60WmvCK/p11HKV AmVg8eT1n3mOfDOOgSJScD6WE9uPJMtAtvKQeeHSVfDbd1MJlqI3W3VtxxlLkyhmk4AO TC+n2pSNUxhG9kiOfU9zaxTPwpuQpcCno592V1TUdkT5oK0BDZNPZ94DlPFI0a0ojdeJ H+hKTLdS2XFBnRxo0KQOC2mcYIx5z5wCFlZ4y4cVddr/DgA1j2eJhHLLek7htDbJfwmZ hGeXeY9oG2g2iDco9ZxLef4NZ5oM9olcJ9Z27qYu/1vBTdbNWr0o6ByHQItqbekibc7H 55yw== X-Gm-Message-State: AOJu0YxxLezcoLxdSx7gAgH7uhtyGCLVMfmSr714dlLFx+mYQI9jXhLR 7HIgeG5NDRcVNzB52j0Fra7PQrPTTHusIE+JDIWU20OMP5dBLzCnmG+sS7n4JeMJx8bHJRLkcgT U X-Google-Smtp-Source: AGHT+IG/c5vd/ptok9ao4Lo5fGdXiTeQuBxnCsKhcYURGV7kWtn1L5YFi9NzlNVUjbiGLi2qMw9ovQ== X-Received: by 2002:a17:902:ef87:b0:1dc:8eba:42c3 with SMTP id iz7-20020a170902ef8700b001dc8eba42c3mr13588199plb.23.1710854133445; Tue, 19 Mar 2024 06:15:33 -0700 (PDT) Received: from mandiga.. ([2804:1b3:a7c3:1d04:8a61:ccbb:553e:b05c]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm11401094plb.137.2024.03.19.06.15.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Mar 2024 06:15:32 -0700 (PDT) From: Adhemerval Zanella To: libc-alpha@sourceware.org Cc: DJ Delorie Subject: [PATCH v4 0/2] Improve wcsstr Date: Tue, 19 Mar 2024 10:15:26 -0300 Message-Id: <20240319131528.3222248-1-adhemerval.zanella@linaro.org> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-5.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: 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