From patchwork Thu Sep 14 18:36:58 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella X-Patchwork-Id: 722582 Delivered-To: patch@linaro.org Received: by 2002:adf:f0d1:0:b0:31d:da82:a3b4 with SMTP id x17csp551674wro; Thu, 14 Sep 2023 11:37:20 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHy9oZNkXoN4bEGHoVjXLMB7NOu6tIKpsrRnByXDC1r7Qir/Dox4h8F8csN7FXu9J5huzRQ X-Received: by 2002:a2e:958e:0:b0:2bc:d522:dfd4 with SMTP id w14-20020a2e958e000000b002bcd522dfd4mr5457207ljh.8.1694716640185; Thu, 14 Sep 2023 11:37:20 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1694716640; cv=none; d=google.com; s=arc-20160816; b=osbZZPZVy3NsXyDFXCCOiLwqqgMgapImxoOoq99hCNMXwBksS67xncUeVuuppWZKjC IppN1Pzwx3Mvk2tb2oWQJtksZvVxDBazROkZqMgSjVoJTfwBsjsBHXK8LtkM6oQCtDxd kMQXVsqhN0SghRQ/sPy8LlWC5in1uWNE8em2YKe4APbbWO8eUtlL4e6V16uMFKr2JIeb 44HaiO2ENr+jLpszVCgnVt2CitgXC2mtukx0651Oj2vm4uiuz3igyKY7FBhF54UySeiI Lpzbce5NQcb9tf5fxgbjpIz/cuH8wlm8bGhNWzpltjcjZCz3YiiaTkGCUPaXY19YzKlR MM/g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:to:from :dkim-signature:dmarc-filter:delivered-to; bh=3gxuH9ByZCz9s0Dh7UOISa4Ep/Exr8sPymluuI3E+qI=; fh=ubzLPtaquqORyAJ/TX35zypB35/iXKzZJOEWlgP8mu4=; b=UYQnsb3ACGXCfNinO3rVGyfoivuQsJmD2fW1xHdqVgdzeaY8b34kIcnDEamOOvYvQg qZEQlFsRAdMlOeaWZ77gluCaJG1jsQDjNEjlCsRQnNiEz/xipusuiHaQ4pfmZUp8aU/W LZMj/7v1HX9pKnN/lRvV/1vyU38HQEYV8ShFYSm0+9JD+rhdfWOXQktPAvGJmDNC2CzY AYIOLNx7onHuvsjjLRsrIALwBQ9iGInErYY1W7RQmEe3isx9glS00sx4MdaE7Mp7SvyU mFFQLtY4hiJmo8L0jkfA1l5dccgp+5d1+Jmn7aMkq5okNan1riLvM0BLHx52Ao7ikDPa bX+g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=BG3I9AD2; spf=pass (google.com: domain of libc-alpha-bounces+patch=linaro.org@sourceware.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="libc-alpha-bounces+patch=linaro.org@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from server2.sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id u2-20020a1709064ac200b00991f598188csi1874444ejt.214.2023.09.14.11.37.19 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 14 Sep 2023 11:37:20 -0700 (PDT) Received-SPF: pass (google.com: domain of libc-alpha-bounces+patch=linaro.org@sourceware.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=BG3I9AD2; spf=pass (google.com: domain of libc-alpha-bounces+patch=linaro.org@sourceware.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="libc-alpha-bounces+patch=linaro.org@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 3192C3858416 for ; Thu, 14 Sep 2023 18:37:19 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-oo1-xc34.google.com (mail-oo1-xc34.google.com [IPv6:2607:f8b0:4864:20::c34]) by sourceware.org (Postfix) with ESMTPS id D45043858C52 for ; Thu, 14 Sep 2023 18:37:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D45043858C52 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linaro.org Received: by mail-oo1-xc34.google.com with SMTP id 006d021491bc7-5739972accdso1281158eaf.1 for ; Thu, 14 Sep 2023 11:37:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1694716631; x=1695321431; darn=sourceware.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:from:to:cc:subject:date:message-id :reply-to; bh=3gxuH9ByZCz9s0Dh7UOISa4Ep/Exr8sPymluuI3E+qI=; b=BG3I9AD2KgcgTwVa2v/Vp5OiXlpxYwTGfALovC+lfWoJZ08G3STG/SHpJJoqWmQ4gu 4c3miGiDSmyYPqfAq/3Fo9xYX5cG5zOP+NqYgUV+3XdUwln0emORBjkfgMLFuM/MV1G4 xwZK2qdN7e95DK3I2pSiKUiy0GFZlcKY01TDXuYDVjciGiCY+mr7NTR1CN70M3Q2cjF6 bjGv4qb3SkBevwU7nmsm+IBafjZKEkQjMZ2BDI8/cVoVtt0yK7b56MbtH3ZNd3PA1nuP 4xAm7UkhM3aEROr/bDrEwGKgcTwmJAQfcHte2cv+JhocZ0DlS6GuT3QypH7dqm4Hu/0N JGMQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1694716631; x=1695321431; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=3gxuH9ByZCz9s0Dh7UOISa4Ep/Exr8sPymluuI3E+qI=; b=PJdEeOgMZOzOqTl1hzd4HxyFSxgZJeo95/eoR7fXX0kSiHirIUVoaGgjizmytBaQRS v+lAJSzsZTKAPWNOrWMQnsUd/6yETscpjHfL/KLs7IXArrYVbyaljRG+RU1S10H9aw0G VOM8NiiF4m8MRtFIUyJUPQs4oL1RUnpVT/zpWFDgv+qPF4npH0xyVF3jZUhT0qHV7Jwn ZLoYAkVIrOQkRVIK6run73U5eaINj/5tHP7mmUSQdxBvadrrfxvELBWBjT+s3PlrnReX 3QUWv7dYqnIZpsuyPxhnKLh1Dty1HS6xw4ZbQcmRb1ff9DqYkGfwhFvjre0jRbtdy18G 06Pg== X-Gm-Message-State: AOJu0YwMX/UYyM2sAbjJ4PE6dKqmGDUwcuvUM62p9k/vuHtUuV6aRzqs /kOvKM8JQ22b9bKYlJIxpcdBz/8C2WQ4tUza7zjdJQ== X-Received: by 2002:a05:6870:969f:b0:1bb:48c5:9d56 with SMTP id o31-20020a056870969f00b001bb48c59d56mr1951755oaq.18.1694716631546; Thu, 14 Sep 2023 11:37:11 -0700 (PDT) Received: from mandiga.. ([2804:1b3:a7c0:91cb:5173:d70:d8d:4d2c]) by smtp.gmail.com with ESMTPSA id cc6-20020a056871e18600b001b3d67934e9sm1056930oac.26.2023.09.14.11.37.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 14 Sep 2023 11:37:10 -0700 (PDT) From: Adhemerval Zanella To: libc-alpha@sourceware.org, Noah Goldstein , Paul Eggert , Florian Weimer Subject: [PATCH v7 1/7] string: Add internal memswap implementation Date: Thu, 14 Sep 2023 15:36:58 -0300 Message-Id: <20230914183704.1386534-2-adhemerval.zanella@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230914183704.1386534-1-adhemerval.zanella@linaro.org> References: <20230914183704.1386534-1-adhemerval.zanella@linaro.org> MIME-Version: 1.0 X-Spam-Status: No, score=-12.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libc-alpha-bounces+patch=linaro.org@sourceware.org The prototype is: void __memswap (void *restrict p1, void *restrict p2, size_t n) The function swaps the content of two memory blocks P1 and P2 of len N. Memory overlap is NOT handled. It will be used on qsort optimization. Checked on x86_64-linux-gnu and aarch64-linux-gnu. --- include/string.h | 3 + string/Makefile | 13 +++ string/memswap.c | 41 +++++++++ string/test-memswap.c | 191 ++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 248 insertions(+) create mode 100644 string/memswap.c create mode 100644 string/test-memswap.c diff --git a/include/string.h b/include/string.h index 86d1fa4abe..f31a7f6006 100644 --- a/include/string.h +++ b/include/string.h @@ -45,6 +45,9 @@ extern void *__memrchr (const void *__s, int __c, size_t __n) extern void *__memchr (const void *__s, int __c, size_t __n) __attribute_pure__; +extern void __memswap (void *restrict __p1, void *restrict __p2, size_t __n) + attribute_hidden; + extern void __bzero (void *__s, size_t __n) __THROW __nonnull ((1)); extern int __ffs (int __i) __attribute__ ((const)); diff --git a/string/Makefile b/string/Makefile index 8cdfd5b000..3d0a3d5682 100644 --- a/string/Makefile +++ b/string/Makefile @@ -69,6 +69,7 @@ routines := \ mempcpy \ memrchr \ memset \ + memswap \ rawmemchr \ sigabbrev_np \ sigdescr_np \ @@ -209,6 +210,18 @@ tests := \ tst-xbzero-opt \ # tests +tests-static-internal := \ + test-memswap \ +# tests-static-internal + +tests-internal := \ + $(tests-static-internal) \ + # tests-internal + +tests-static := \ + $(tests-static-internal) \ + # tests-static + # Both tests require the .mo translation files generated by msgfmt. tests-translation := \ tst-strerror \ diff --git a/string/memswap.c b/string/memswap.c new file mode 100644 index 0000000000..37640c47ad --- /dev/null +++ b/string/memswap.c @@ -0,0 +1,41 @@ +/* Swap the content of two memory blocks, overlap is NOT handled. + Copyright (C) 2023 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include + +void +__memswap (void *restrict p1, void *restrict p2, size_t n) +{ + /* Use multiple small memcpys with constant size to enable inlining on most + targets. */ + enum { SWAP_GENERIC_SIZE = 32 }; + unsigned char tmp[SWAP_GENERIC_SIZE]; + while (n > SWAP_GENERIC_SIZE) + { + memcpy (tmp, p1, SWAP_GENERIC_SIZE); + p1 = __mempcpy (p1, p2, SWAP_GENERIC_SIZE); + p2 = __mempcpy (p2, tmp, SWAP_GENERIC_SIZE); + n -= SWAP_GENERIC_SIZE; + } + while (n > 0) + { + unsigned char t = ((unsigned char *)p1)[--n]; + ((unsigned char *)p1)[n] = ((unsigned char *)p2)[n]; + ((unsigned char *)p2)[n] = t; + } +} diff --git a/string/test-memswap.c b/string/test-memswap.c new file mode 100644 index 0000000000..7696c43711 --- /dev/null +++ b/string/test-memswap.c @@ -0,0 +1,191 @@ +/* Test and measure memcpy functions. + Copyright (C) 2023 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#include + +#define TEST_MAIN +#define BUF1PAGES 3 +#include "test-string.h" + +static unsigned char *ref1; +static unsigned char *ref2; + +static void +do_one_test (unsigned char *p1, unsigned char *ref1, unsigned char *p2, + unsigned char *ref2, size_t len) +{ + __memswap (p1, p2, len); + + TEST_COMPARE_BLOB (p1, len, ref2, len); + TEST_COMPARE_BLOB (p2, len, ref1, len); +} + +static inline void +do_test (size_t align1, size_t align2, size_t len) +{ + align1 &= page_size; + if (align1 + len >= page_size) + return; + + align2 &= page_size; + if (align2 + len >= page_size) + return; + + unsigned char *p1 = buf1 + align1; + unsigned char *p2 = buf2 + align2; + for (size_t repeats = 0; repeats < 2; ++repeats) + { + size_t i, j; + for (i = 0, j = 1; i < len; i++, j += 23) + { + ref1[i] = p1[i] = j; + ref2[i] = p2[i] = UCHAR_MAX - j; + } + + do_one_test (p1, ref1, p2, ref2, len); + } +} + +static void +do_random_tests (void) +{ + for (size_t n = 0; n < ITERATIONS; n++) + { + size_t len, size, size1, size2, align1, align2; + + if (n == 0) + { + len = getpagesize (); + size = len + 512; + size1 = size; + size2 = size; + align1 = 512; + align2 = 512; + } + else + { + if ((random () & 255) == 0) + size = 65536; + else + size = 768; + if (size > page_size) + size = page_size; + size1 = size; + size2 = size; + size_t i = random (); + if (i & 3) + size -= 256; + if (i & 1) + size1 -= 256; + if (i & 2) + size2 -= 256; + if (i & 4) + { + len = random () % size; + align1 = size1 - len - (random () & 31); + align2 = size2 - len - (random () & 31); + if (align1 > size1) + align1 = 0; + if (align2 > size2) + align2 = 0; + } + else + { + align1 = random () & 63; + align2 = random () & 63; + len = random () % size; + if (align1 + len > size1) + align1 = size1 - len; + if (align2 + len > size2) + align2 = size2 - len; + } + } + unsigned char *p1 = buf1 + page_size - size1; + unsigned char *p2 = buf2 + page_size - size2; + size_t j = align1 + len + 256; + if (j > size1) + j = size1; + for (size_t i = 0; i < j; ++i) + ref1[i] = p1[i] = random () & 255; + + j = align2 + len + 256; + if (j > size2) + j = size2; + + for (size_t i = 0; i < j; ++i) + ref2[i] = p2[i] = random () & 255; + + do_one_test (p1 + align1, ref1 + align1, p2 + align2, ref2 + align2, len); + } +} + +static int +test_main (void) +{ + test_init (); + /* Use the start of buf1 for reference buffers. */ + ref1 = buf1; + ref2 = buf1 + page_size; + buf1 = ref2 + page_size; + + printf ("%23s", ""); + printf ("\t__memswap\n"); + + for (size_t i = 0; i < 18; ++i) + { + do_test (0, 0, 1 << i); + do_test (i, 0, 1 << i); + do_test (0, i, 1 << i); + do_test (i, i, 1 << i); + } + + for (size_t i = 0; i < 32; ++i) + { + do_test (0, 0, i); + do_test (i, 0, i); + do_test (0, i, i); + do_test (i, i, i); + } + + for (size_t i = 3; i < 32; ++i) + { + if ((i & (i - 1)) == 0) + continue; + do_test (0, 0, 16 * i); + do_test (i, 0, 16 * i); + do_test (0, i, 16 * i); + do_test (i, i, 16 * i); + } + + for (size_t i = 19; i <= 25; ++i) + { + do_test (255, 0, 1 << i); + do_test (0, 4000, 1 << i); + do_test (0, 255, i); + do_test (0, 4000, i); + } + + do_test (0, 0, getpagesize ()); + + do_random_tests (); + + return 0; +} + +#include