From patchwork Wed Dec 14 19:43:05 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella X-Patchwork-Id: 88059 Delivered-To: patch@linaro.org Received: by 10.140.20.101 with SMTP id 92csp376459qgi; Wed, 14 Dec 2016 11:43:31 -0800 (PST) X-Received: by 10.84.142.70 with SMTP id 64mr210492158plw.177.1481744611445; Wed, 14 Dec 2016 11:43:31 -0800 (PST) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id n17si54209011pgj.73.2016.12.14.11.43.31 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 14 Dec 2016 11:43:31 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-return-75895-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org; spf=pass (google.com: domain of libc-alpha-return-75895-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-75895-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:subject:to:references:from:message-id:date :mime-version:in-reply-to:content-type :content-transfer-encoding; q=dns; s=default; b=dErbBPVl5pyYEQ53 08XmSRg1jwMH2g8TfVHdYeTiN0TEgbryQ1RAixQufzUPlqbC7AVfhCOlVeiADsvw I0h1M7iLyZkoeaY1qZvfpN+y0Wz8DDIf3b82gjD/A6AsQdbxbHEcPZiP57mAKGr9 roTTIG64T6Kws8Mt11cR7ZGUFi0= 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:subject:to:references:from:message-id:date :mime-version:in-reply-to:content-type :content-transfer-encoding; s=default; bh=WkzPOavX9IV0RUHdhOakJo VU/Cc=; b=YJhmATgs3xg7tscUwZoAFMxAzJtlL1ubQVY32EQTyWeT9jriFC39nU iYIhDHxjtL9uem6GXmkU2KRE4wNFVf72dY5mIPMcH0e8y+ZZikLIgIWq8Rcro0+L GAhLpmux4LqkF2Ob+pfFmNLoTLDeT/OBa2ee3PxgssgpQSx9A3v0Q= Received: (qmail 18284 invoked by alias); 14 Dec 2016 19:43:22 -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 Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 18260 invoked by uid 89); 14 Dec 2016 19:43:21 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.4 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM, SPF_PASS autolearn=no version=3.3.2 spammy= X-HELO: mail-vk0-f49.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding; bh=pXTLPHIs4nNFWZ6Q3da3NF9gadOIH/+JWXxm7FKnyrE=; b=JE3mcTFZAbT2CwxTeicv04yvLT+fsinhhHRAguZdKAGdv+GEJJfzrn0MUnnL+OK1or kT8NkxAb1PRaSa/MBSap1igBG6ZYLJk4dtAX69acDKRuUROGfVz57rjc9UkTlAx7vN5X 69rSXfw6Jdpf/mUao+63h3CoNPgUTCuRkQo3T5zALzG621ggUPKAOztu7fid7vc/cHOw ss58btWXMOgSAc+Kmr8UOIW+bwW5sfxtFdOjpfy5hmXVUftXDvVD1742r7RPWPzq+iwL GY8jPNeIh21N17nyPkBnsfF3ucBkZf9xR9JIN8VT7D+WMZxsnJ1LbOL0LDiDo+VZ9rvi qbfg== X-Gm-Message-State: AKaTC02PYiCaJ1pGyZmmWwqDIFees9RT20uh1fR9JiNuhI+bbE2xfSUlCIF0DBC+V585Gb8C X-Received: by 10.31.76.68 with SMTP id z65mr28523345vka.59.1481744589609; Wed, 14 Dec 2016 11:43:09 -0800 (PST) Subject: Re: [PATCH v3] Improve strtok(_r) performance To: libc-alpha@sourceware.org References: <20161214154337.38b8cac2@keller> <9ebe0acb-5cc7-aa89-a819-abad9874168e@linaro.org> From: Adhemerval Zanella Message-ID: Date: Wed, 14 Dec 2016 17:43:05 -0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.5.1 MIME-Version: 1.0 In-Reply-To: <9ebe0acb-5cc7-aa89-a819-abad9874168e@linaro.org> On 14/12/2016 17:26, Adhemerval Zanella wrote: > > > On 14/12/2016 16:25, Wilco Dijkstra wrote: >> Hi, >> >> In powerpc64/power7/memchr.S this bit looks suspicious: >> >> L(done): >> #ifdef __LITTLE_ENDIAN__ >> addi r0,r3,-1 >> andc r0,r0,r3 >> popcntd r0,r0 /* Count trailing zeros. */ >> #else >> cntlzd r0,r3 /* Count leading zeros before the match. */ >> #endif >> cmpld r8,r7 /* Are we on the last dword? */ >> srdi r0,r0,3 /* Convert leading/trailing zeros to bytes. */ >> add r3,r8,r0 >> cmpld cr7,r0,r5 /* If on the last dword, check byte offset. */ >> bnelr >> blelr cr7 >> li r3,0 >> blr >> >> When the size is the maximum and the input pointer is at offset 2 or larger within an 8-byte aligned address, r7 == r8, and it will return NULL if it matches in the first 8 bytes since the match appears to be after the end pointer. When it matches later, r7 != r8 and it works. > > I think this snippet is ok, the problem is at r7 calculation where it should > handle overflow. This simple test triggers the issue: > > #define _GNU_SOURCE 1 > #include > #include > > void * > my_rawmemchr (const void *s, int c) > { > if (c != '\0') > return memchr (s, c, (size_t)-1); > return (char *)s + strlen (s); > } > > int main () > { > // p=0x3fffb057fe00 | aling=10 > int seek_char = 0x41; > size_t align = 10; > unsigned char input [32]; > input[10] = 0x34; > input[11] = 0x78; > input[12] = 0x3d; > input[13] = 0x7b; > input[14] = 0xa1; > input[15] = seek_char; > > printf ("%p\n", my_rawmemchr (input+align, seek_char)); > printf ("%p\n", rawmemchr (input+align, seek_char)); > return 0; > } > > On POWER7 memchr.S: > > 24 ENTRY (__memchr) > 25 CALL_MCOUNT 3 > 26 dcbt 0,r3 > 27 clrrdi r8,r3,3 > 28 insrdi r4,r4,8,48 > 29 add r7,r3,r5 /* Calculate the last acceptable address. */ > > And using the example above: > > (gdb) i r r3 r5 > r3 0x3fffffffeab2 70368744172210 > r5 0xffffffffffffffff 18446744073709551615 > (gdb) ni > 30 in ../sysdeps/powerpc/powerpc64/power7/memchr.S > (gdb) i r r7 > r7 0x3fffffffeab1 70368744172209 > > If we set r7 to maximum pointer value (0xf...f) memchr returns the expected result. > This patch should fix test-rawmemchr by adding a saturated addition when calculating the last double address to check. I will prepare a patch when the make check finished on the powerpc64le machine I have access. diff --git a/sysdeps/powerpc/powerpc64/power7/memchr.S b/sysdeps/powerpc/powerpc64/power7/memchr.S index 03f0d7c..34605a7 100644 --- a/sysdeps/powerpc/powerpc64/power7/memchr.S +++ b/sysdeps/powerpc/powerpc64/power7/memchr.S @@ -26,7 +26,15 @@ ENTRY (__memchr) dcbt 0,r3 clrrdi r8,r3,3 insrdi r4,r4,8,48 - add r7,r3,r5 /* Calculate the last acceptable address. */ + + /* Calculate the last acceptable address and also take care of possible + overflow by using a large size. */ + add r7,r3,r5 + subfc r6,r3,r7 + subfe r9,r9,r9 + extsw r6,r9 + or r7,r7,r6 + insrdi r4,r4,16,32 cmpldi r5,32 li r9, -1