From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS31976 209.132.180.0/23 X-Spam-Status: No, score=-4.1 required=3.0 tests=AWL,BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_EF,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED,SPF_HELO_PASS,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id 9CC4A20248 for ; Thu, 18 Apr 2019 13:51:21 +0000 (UTC) DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:cc:subject:date:message-id:references :in-reply-to:content-type:content-transfer-encoding :mime-version; q=dns; s=default; b=AzC5jdSo2tFwbnZJwunxQHcDXZ3OX EjgEXO/nsA3DDwDRUPh13uut8t3HZH/HPu/NFzLV8HLZODnl9z1NcSCNbHA4ENlt /Y3EtLjzpmMgrr9EtAIX0Akpjg70TDh8YsG+BMHiQ8vh4G53TZt1P93eUUUXtb0C yxvtyhvX3Yi7T4= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:cc:subject:date:message-id:references :in-reply-to:content-type:content-transfer-encoding :mime-version; s=default; bh=uRczjb+yS5++FH3cFl4iNDdqHds=; b=L21 AELMQXNNcPibALitWoyZ0QW1+jSUDGuo7Erg5k5/tT5jNKijZ1FK5M0xoUtPremC TNJztyv9ahU4Lco9ejkXfCsVKVHHLwOFKQcWjXEiAvXbH+666eWXATJi5KSVdMHl PRWIsYlPAKACyrLuY9xdyZr2YOZP65SC0VLr2fvA= Received: (qmail 94493 invoked by alias); 18 Apr 2019 13:51:18 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Received: (qmail 94482 invoked by uid 89); 18 Apr 2019 13:51:18 -0000 Authentication-Results: sourceware.org; auth=none X-HELO: EUR01-HE1-obe.outbound.protection.outlook.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=5OGmbqI+f+kSLvDWMyF0Vx7bVRSRoEfz81y/k3m+4qU=; b=Qt8u/b7/NX3EAub9l2KIlXHyNKD/XiaEAq38oTsWFghM3jvYZXYlBesGW7FT0HjKlLqIOGu3JUkVfqXXrfj5+A8zfBDByzs7kGKaSkZHdbBLC+HvnxyEVOuQ1PPwMDYKPxClg3G7lFKYb2MY8KBOsZouhw1LScUwpSm534MootU= From: Wilco Dijkstra To: Szabolcs Nagy , Rich Felker CC: nd , Zack Weinberg , GNU C Library Subject: Re: [PATCH v2] Improve performance of strstr Date: Thu, 18 Apr 2019 13:51:14 +0000 Message-ID: References: <2b27b4ca-0370-442d-9f39-210265f00444@arm.com> <20190412171613.GB23599@brightrain.aerifal.cx> <20190415144051.GE23599@brightrain.aerifal.cx> <734450c0-1959-6f47-3d8f-35a746f331c9@arm.com> <953ad13a-cd71-32c4-ccc3-d1b8cac57620@arm.com> <20190416205643.GG23599@brightrain.aerifal.cx>,<427ac1ff-d9c7-f5b8-ee37-2389f2e9d3ad@arm.com> In-Reply-To: <427ac1ff-d9c7-f5b8-ee37-2389f2e9d3ad@arm.com> authentication-results: spf=none (sender IP is ) smtp.mailfrom=Wilco.Dijkstra@arm.com; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-ms-exchange-senderadcheck: 1 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-CrossTenant-mailboxtype: HOSTED Hi Szabolcs, > in this case a large slowdown is not a real vulnerability. Absolutely, performance varies quite dramatically with different inputs. Th= at is true for all algorithms even they are "real-time". Caches and branch predictors are not going away. > i think even doing memcmp at every byte position is not a > denial of service concern if the needle is <=3D 256 bytes. > (maybe we should use a lower limit? <=3D 64?) It couldn't be since its worst case isn't actually much worse (~2.2 times f= or needle size of 256). A simple memcmp at every character is significantly faster than Two-way on the first bad needle, and about the same performance on the second. Also when reducing the size of the needle to 31 from 255 on my algorithm, there is only a 73% speedup for its worst case (bad needle 2). So reducing = the cutoff doesn't really help the worst case since we're clearly not quadratic= . Wilco =