src/vppinfra/string.h

   1 /*
   2  * Copyright (c) 2016 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16   Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
  17
  18   Permission is hereby granted, free of charge, to any person obtaining
  19   a copy of this software and associated documentation files (the
  20   "Software"), to deal in the Software without restriction, including
  21   without limitation the rights to use, copy, modify, merge, publish,
  22   distribute, sublicense, and/or sell copies of the Software, and to
  23   permit persons to whom the Software is furnished to do so, subject to
  24   the following conditions:
  25
  26   The above copyright notice and this permission notice shall be
  27   included in all copies or substantial portions of the Software.
  28
  29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  36 */
  37
  38 /** \file
  39
  40     Optimized string handling code, including c11-compliant
  41     "safe C library" variants.
  42 */
  43
  44 #ifndef included_clib_string_h
  45 #define included_clib_string_h
  46
  47 #include <vppinfra/clib.h>      /* for CLIB_LINUX_KERNEL */
  48 #include <vppinfra/vector.h>
  49
  50 #ifdef CLIB_LINUX_KERNEL
  51 #include <linux/string.h>
  52 #endif
  53
  54 #ifdef CLIB_UNIX
  55 #include <string.h>
  56 #endif
  57
  58 #ifdef CLIB_STANDALONE
  59 #include <vppinfra/standalone_string.h>
  60 #endif
  61
  62 #if _x86_64_
  63 #include <x86intrin.h>
  64 #endif
  65
  66 /* Exchanges source and destination. */
  67 void clib_memswap (void *_a, void *_b, uword bytes);
  68
  69 /*
  70  * the vector unit memcpy variants confuse coverity
  71  * so don't let it anywhere near them.
  72  */
  73 #ifndef __COVERITY__
  74 #if __AVX512F__
  75 #include <vppinfra/memcpy_avx512.h>
  76 #elif __AVX2__
  77 #include <vppinfra/memcpy_avx2.h>
  78 #elif __SSSE3__
  79 #include <vppinfra/memcpy_sse3.h>
  80 #else
  81 #define _clib_memcpy(a,b,c) memcpy(a,b,c)
  82 #endif
  83 #else /* __COVERITY__ */
  84 #define _clib_memcpy(a,b,c) memcpy(a,b,c)
  85 #endif
  86
  87 /* c-11 string manipulation variants */
  88
  89 #ifndef EOK
  90 #define EOK 0
  91 #endif
  92 #ifndef EINVAL
  93 #define EINVAL 22
  94 #endif
  95
  96 typedef int errno_t;
  97 typedef uword rsize_t;
  98
  99 void clib_c11_violation (const char *s);
 100 errno_t memcpy_s (void *__restrict__ dest, rsize_t dmax,
 101                   const void *__restrict__ src, rsize_t n);
 102
 103 always_inline errno_t
 104 memcpy_s_inline (void *__restrict__ dest, rsize_t dmax,
 105                  const void *__restrict__ src, rsize_t n)
 106 {
 107   uword low, hi;
 108   u8 bad;
 109
 110   /*
 111    * call bogus if: src or dst NULL, trying to copy
 112    * more data than we have space in dst, or src == dst.
 113    * n == 0 isn't really "bad", so check first in the
 114    * "wall-of-shame" department...
 115    */
 116   bad = (dest == 0) + (src == 0) + (n > dmax) + (dest == src) + (n == 0);
 117   if (PREDICT_FALSE (bad != 0))
 118     {
 119       /* Not actually trying to copy anything is OK */
 120       if (n == 0)
 121         return EOK;
 122       if (dest == NULL)
 123         clib_c11_violation ("dest NULL");
 124       if (src == NULL)
 125         clib_c11_violation ("src NULL");
 126       if (n > dmax)
 127         clib_c11_violation ("n > dmax");
 128       if (dest == src)
 129         clib_c11_violation ("dest == src");
 130       return EINVAL;
 131     }
 132
 133   /* Check for src/dst overlap, which is not allowed */
 134   low = (uword) (src < dest ? src : dest);
 135   hi = (uword) (src < dest ? dest : src);
 136
 137   if (PREDICT_FALSE (low + (n - 1) >= hi))
 138     {
 139       clib_c11_violation ("src/dest overlap");
 140       return EINVAL;
 141     }
 142
 143   _clib_memcpy (dest, src, n);
 144   return EOK;
 145 }
 146
 147 /*
 148  * Note: $$$ This macro is a crutch. Folks need to manually
 149  * inspect every extant clib_memcpy(...) call and
 150  * attempt to provide a real destination buffer size
 151  * argument...
 152  */
 153 #define clib_memcpy(d,s,n) memcpy_s_inline(d,n,s,n)
 154
 155 errno_t memset_s (void *s, rsize_t smax, int c, rsize_t n);
 156
 157 always_inline errno_t
 158 memset_s_inline (void *s, rsize_t smax, int c, rsize_t n)
 159 {
 160   u8 bad;
 161
 162   bad = (s == 0) + (n > smax);
 163
 164   if (PREDICT_FALSE (bad != 0))
 165     {
 166       if (s == 0)
 167         clib_c11_violation ("s NULL");
 168       if (n > smax)
 169         clib_c11_violation ("n > smax");
 170       return (EINVAL);
 171     }
 172   memset (s, c, n);
 173   return (EOK);
 174 }
 175
 176 /*
 177  * This macro is not [so much of] a crutch.
 178  * It's super-typical to write:
 179  *
 180  *   ep = pool_get (<pool>);
 181  *   clib_memset(ep, 0, sizeof (*ep));
 182  *
 183  * The compiler should delete the not-so useful
 184  * (n > smax) test. TBH the NULL pointer check isn't
 185  * so useful in this case, but so be it.
 186  */
 187 #define clib_memset(s,c,n) memset_s_inline(s,n,c,n)
 188
 189 /*
 190  * Copy 64 bytes of data to 4 destinations
 191  * this function is typically used in quad-loop case when whole cacheline
 192  * needs to be copied to 4 different places. First it reads whole cacheline
 193  * to 1/2/4 SIMD registers and then it writes data to 4 destinations.
 194  */
 195
 196 static_always_inline void
 197 clib_memcpy64_x4 (void *d0, void *d1, void *d2, void *d3, void *s)
 198 {
 199 #if defined (__AVX512F__)
 200   __m512i r0 = _mm512_loadu_si512 (s);
 201
 202   _mm512_storeu_si512 (d0, r0);
 203   _mm512_storeu_si512 (d1, r0);
 204   _mm512_storeu_si512 (d2, r0);
 205   _mm512_storeu_si512 (d3, r0);
 206
 207 #elif defined (__AVX2__)
 208   __m256i r0 = _mm256_loadu_si256 ((__m256i *) (s + 0 * 32));
 209   __m256i r1 = _mm256_loadu_si256 ((__m256i *) (s + 1 * 32));
 210
 211   _mm256_storeu_si256 ((__m256i *) (d0 + 0 * 32), r0);
 212   _mm256_storeu_si256 ((__m256i *) (d0 + 1 * 32), r1);
 213
 214   _mm256_storeu_si256 ((__m256i *) (d1 + 0 * 32), r0);
 215   _mm256_storeu_si256 ((__m256i *) (d1 + 1 * 32), r1);
 216
 217   _mm256_storeu_si256 ((__m256i *) (d2 + 0 * 32), r0);
 218   _mm256_storeu_si256 ((__m256i *) (d2 + 1 * 32), r1);
 219
 220   _mm256_storeu_si256 ((__m256i *) (d3 + 0 * 32), r0);
 221   _mm256_storeu_si256 ((__m256i *) (d3 + 1 * 32), r1);
 222
 223 #elif defined (__SSSE3__)
 224   __m128i r0 = _mm_loadu_si128 ((__m128i *) (s + 0 * 16));
 225   __m128i r1 = _mm_loadu_si128 ((__m128i *) (s + 1 * 16));
 226   __m128i r2 = _mm_loadu_si128 ((__m128i *) (s + 2 * 16));
 227   __m128i r3 = _mm_loadu_si128 ((__m128i *) (s + 3 * 16));
 228
 229   _mm_storeu_si128 ((__m128i *) (d0 + 0 * 16), r0);
 230   _mm_storeu_si128 ((__m128i *) (d0 + 1 * 16), r1);
 231   _mm_storeu_si128 ((__m128i *) (d0 + 2 * 16), r2);
 232   _mm_storeu_si128 ((__m128i *) (d0 + 3 * 16), r3);
 233
 234   _mm_storeu_si128 ((__m128i *) (d1 + 0 * 16), r0);
 235   _mm_storeu_si128 ((__m128i *) (d1 + 1 * 16), r1);
 236   _mm_storeu_si128 ((__m128i *) (d1 + 2 * 16), r2);
 237   _mm_storeu_si128 ((__m128i *) (d1 + 3 * 16), r3);
 238
 239   _mm_storeu_si128 ((__m128i *) (d2 + 0 * 16), r0);
 240   _mm_storeu_si128 ((__m128i *) (d2 + 1 * 16), r1);
 241   _mm_storeu_si128 ((__m128i *) (d2 + 2 * 16), r2);
 242   _mm_storeu_si128 ((__m128i *) (d2 + 3 * 16), r3);
 243
 244   _mm_storeu_si128 ((__m128i *) (d3 + 0 * 16), r0);
 245   _mm_storeu_si128 ((__m128i *) (d3 + 1 * 16), r1);
 246   _mm_storeu_si128 ((__m128i *) (d3 + 2 * 16), r2);
 247   _mm_storeu_si128 ((__m128i *) (d3 + 3 * 16), r3);
 248
 249 #else
 250   clib_memcpy (d0, s, 64);
 251   clib_memcpy (d1, s, 64);
 252   clib_memcpy (d2, s, 64);
 253   clib_memcpy (d3, s, 64);
 254 #endif
 255 }
 256
 257 static_always_inline void
 258 clib_memset_u64 (void *p, u64 val, uword count)
 259 {
 260   u64 *ptr = p;
 261 #if defined(CLIB_HAVE_VEC512)
 262   u64x8 v512 = u64x8_splat (val);
 263   while (count >= 8)
 264     {
 265       u64x8_store_unaligned (v512, ptr);
 266       ptr += 8;
 267       count -= 8;
 268     }
 269   if (count == 0)
 270     return;
 271 #endif
 272 #if defined(CLIB_HAVE_VEC256)
 273   u64x4 v256 = u64x4_splat (val);
 274   while (count >= 4)
 275     {
 276       u64x4_store_unaligned (v256, ptr);
 277       ptr += 4;
 278       count -= 4;
 279     }
 280   if (count == 0)
 281     return;
 282 #else
 283   while (count >= 4)
 284     {
 285       ptr[0] = ptr[1] = ptr[2] = ptr[3] = val;
 286       ptr += 4;
 287       count -= 4;
 288     }
 289 #endif
 290   while (count--)
 291     ptr++[0] = val;
 292 }
 293
 294 static_always_inline void
 295 clib_memset_u32 (void *p, u32 val, uword count)
 296 {
 297   u32 *ptr = p;
 298 #if defined(CLIB_HAVE_VEC512)
 299   u32x16 v512 = u32x16_splat (val);
 300   while (count >= 16)
 301     {
 302       u32x16_store_unaligned (v512, ptr);
 303       ptr += 16;
 304       count -= 16;
 305     }
 306   if (count == 0)
 307     return;
 308 #endif
 309 #if defined(CLIB_HAVE_VEC256)
 310   u32x8 v256 = u32x8_splat (val);
 311   while (count >= 8)
 312     {
 313       u32x8_store_unaligned (v256, ptr);
 314       ptr += 8;
 315       count -= 8;
 316     }
 317   if (count == 0)
 318     return;
 319 #endif
 320 #if defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
 321   u32x4 v128 = u32x4_splat (val);
 322   while (count >= 4)
 323     {
 324       u32x4_store_unaligned (v128, ptr);
 325       ptr += 4;
 326       count -= 4;
 327     }
 328 #else
 329   while (count >= 4)
 330     {
 331       ptr[0] = ptr[1] = ptr[2] = ptr[3] = val;
 332       ptr += 4;
 333       count -= 4;
 334     }
 335 #endif
 336   while (count--)
 337     ptr++[0] = val;
 338 }
 339
 340 static_always_inline void
 341 clib_memset_u16 (void *p, u16 val, uword count)
 342 {
 343   u16 *ptr = p;
 344 #if defined(CLIB_HAVE_VEC512)
 345   u16x32 v512 = u16x32_splat (val);
 346   while (count >= 32)
 347     {
 348       u16x32_store_unaligned (v512, ptr);
 349       ptr += 32;
 350       count -= 32;
 351     }
 352   if (count == 0)
 353     return;
 354 #endif
 355 #if defined(CLIB_HAVE_VEC256)
 356   u16x16 v256 = u16x16_splat (val);
 357   while (count >= 16)
 358     {
 359       u16x16_store_unaligned (v256, ptr);
 360       ptr += 16;
 361       count -= 16;
 362     }
 363   if (count == 0)
 364     return;
 365 #endif
 366 #if defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
 367   u16x8 v128 = u16x8_splat (val);
 368   while (count >= 8)
 369     {
 370       u16x8_store_unaligned (v128, ptr);
 371       ptr += 8;
 372       count -= 8;
 373     }
 374 #else
 375   while (count >= 4)
 376     {
 377       ptr[0] = ptr[1] = ptr[2] = ptr[3] = val;
 378       ptr += 4;
 379       count -= 4;
 380     }
 381 #endif
 382   while (count--)
 383     ptr++[0] = val;
 384 }
 385
 386 static_always_inline void
 387 clib_memset_u8 (void *p, u8 val, uword count)
 388 {
 389   u8 *ptr = p;
 390 #if defined(CLIB_HAVE_VEC512)
 391   u8x64 v512 = u8x64_splat (val);
 392   while (count >= 64)
 393     {
 394       u8x64_store_unaligned (v512, ptr);
 395       ptr += 64;
 396       count -= 64;
 397     }
 398   if (count == 0)
 399     return;
 400 #endif
 401 #if defined(CLIB_HAVE_VEC256)
 402   u8x32 v256 = u8x32_splat (val);
 403   while (count >= 32)
 404     {
 405       u8x32_store_unaligned (v256, ptr);
 406       ptr += 32;
 407       count -= 32;
 408     }
 409   if (count == 0)
 410     return;
 411 #endif
 412 #if defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
 413   u8x16 v128 = u8x16_splat (val);
 414   while (count >= 16)
 415     {
 416       u8x16_store_unaligned (v128, ptr);
 417       ptr += 16;
 418       count -= 16;
 419     }
 420 #else
 421   while (count >= 4)
 422     {
 423       ptr[0] = ptr[1] = ptr[2] = ptr[3] = val;
 424       ptr += 4;
 425       count -= 4;
 426     }
 427 #endif
 428   while (count--)
 429     ptr++[0] = val;
 430 }
 431
 432 static_always_inline uword
 433 clib_count_equal_u64 (u64 * data, uword max_count)
 434 {
 435   uword count;
 436   u64 first;
 437
 438   if (max_count == 1)
 439     return 1;
 440   if (data[0] != data[1])
 441     return 1;
 442
 443   count = 0;
 444   first = data[0];
 445
 446 #if defined(CLIB_HAVE_VEC256)
 447   u64x4 splat = u64x4_splat (first);
 448   while (1)
 449     {
 450       u64 bmp;
 451       bmp = u8x32_msb_mask ((u8x32) (u64x4_load_unaligned (data) == splat));
 452       if (bmp != 0xffffffff)
 453         {
 454           count += count_trailing_zeros (~bmp) / 8;
 455           return clib_min (count, max_count);
 456         }
 457
 458       data += 4;
 459       count += 4;
 460
 461       if (count >= max_count)
 462         return max_count;
 463     }
 464 #endif
 465   count += 2;
 466   data += 2;
 467   while (count + 3 < max_count &&
 468          ((data[0] ^ first) | (data[1] ^ first) |
 469           (data[2] ^ first) | (data[3] ^ first)) == 0)
 470     {
 471       data += 4;
 472       count += 4;
 473     }
 474   while (count < max_count && (data[0] == first))
 475     {
 476       data += 1;
 477       count += 1;
 478     }
 479   return count;
 480 }
 481
 482 static_always_inline uword
 483 clib_count_equal_u32 (u32 * data, uword max_count)
 484 {
 485   uword count;
 486   u32 first;
 487
 488   if (max_count == 1)
 489     return 1;
 490   if (data[0] != data[1])
 491     return 1;
 492
 493   count = 0;
 494   first = data[0];
 495
 496 #if defined(CLIB_HAVE_VEC256)
 497   u32x8 splat = u32x8_splat (first);
 498   while (1)
 499     {
 500       u64 bmp;
 501       bmp = u8x32_msb_mask ((u8x32) (u32x8_load_unaligned (data) == splat));
 502       if (bmp != 0xffffffff)
 503         {
 504           count += count_trailing_zeros (~bmp) / 4;
 505           return clib_min (count, max_count);
 506         }
 507
 508       data += 8;
 509       count += 8;
 510
 511       if (count >= max_count)
 512         return max_count;
 513     }
 514 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_MSB_MASK)
 515   u32x4 splat = u32x4_splat (first);
 516   while (1)
 517     {
 518       u64 bmp;
 519       bmp = u8x16_msb_mask ((u8x16) (u32x4_load_unaligned (data) == splat));
 520       if (bmp != 0xffff)
 521         {
 522           count += count_trailing_zeros (~bmp) / 4;
 523           return clib_min (count, max_count);
 524         }
 525
 526       data += 4;
 527       count += 4;
 528
 529       if (count >= max_count)
 530         return max_count;
 531     }
 532 #endif
 533   count += 2;
 534   data += 2;
 535   while (count + 3 < max_count &&
 536          ((data[0] ^ first) | (data[1] ^ first) |
 537           (data[2] ^ first) | (data[3] ^ first)) == 0)
 538     {
 539       data += 4;
 540       count += 4;
 541     }
 542   while (count < max_count && (data[0] == first))
 543     {
 544       data += 1;
 545       count += 1;
 546     }
 547   return count;
 548 }
 549
 550 static_always_inline uword
 551 clib_count_equal_u16 (u16 * data, uword max_count)
 552 {
 553   uword count;
 554   u16 first;
 555
 556   if (max_count == 1)
 557     return 1;
 558   if (data[0] != data[1])
 559     return 1;
 560
 561   count = 0;
 562   first = data[0];
 563
 564 #if defined(CLIB_HAVE_VEC256)
 565   u16x16 splat = u16x16_splat (first);
 566   while (1)
 567     {
 568       u64 bmp;
 569       bmp = u8x32_msb_mask ((u8x32) (u16x16_load_unaligned (data) == splat));
 570       if (bmp != 0xffffffff)
 571         {
 572           count += count_trailing_zeros (~bmp) / 2;
 573           return clib_min (count, max_count);
 574         }
 575
 576       data += 16;
 577       count += 16;
 578
 579       if (count >= max_count)
 580         return max_count;
 581     }
 582 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_MSB_MASK)
 583   u16x8 splat = u16x8_splat (first);
 584   while (1)
 585     {
 586       u64 bmp;
 587       bmp = u8x16_msb_mask ((u8x16) (u16x8_load_unaligned (data) == splat));
 588       if (bmp != 0xffff)
 589         {
 590           count += count_trailing_zeros (~bmp) / 2;
 591           return clib_min (count, max_count);
 592         }
 593
 594       data += 8;
 595       count += 8;
 596
 597       if (count >= max_count)
 598         return max_count;
 599     }
 600 #endif
 601   count += 2;
 602   data += 2;
 603   while (count + 3 < max_count &&
 604          ((data[0] ^ first) | (data[1] ^ first) |
 605           (data[2] ^ first) | (data[3] ^ first)) == 0)
 606     {
 607       data += 4;
 608       count += 4;
 609     }
 610   while (count < max_count && (data[0] == first))
 611     {
 612       data += 1;
 613       count += 1;
 614     }
 615   return count;
 616 }
 617
 618 static_always_inline uword
 619 clib_count_equal_u8 (u8 * data, uword max_count)
 620 {
 621   uword count;
 622   u8 first;
 623
 624   if (max_count == 1)
 625     return 1;
 626   if (data[0] != data[1])
 627     return 1;
 628
 629   count = 0;
 630   first = data[0];
 631
 632 #if defined(CLIB_HAVE_VEC256)
 633   u8x32 splat = u8x32_splat (first);
 634   while (1)
 635     {
 636       u64 bmp;
 637       bmp = u8x32_msb_mask ((u8x32) (u8x32_load_unaligned (data) == splat));
 638       if (bmp != 0xffffffff)
 639         {
 640           count += count_trailing_zeros (~bmp);
 641           return clib_min (count, max_count);
 642         }
 643
 644       data += 32;
 645       count += 32;
 646
 647       if (count >= max_count)
 648         return max_count;
 649     }
 650 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_MSB_MASK)
 651   u8x16 splat = u8x16_splat (first);
 652   while (1)
 653     {
 654       u64 bmp;
 655       bmp = u8x16_msb_mask ((u8x16) (u8x16_load_unaligned (data) == splat));
 656       if (bmp != 0xffff)
 657         {
 658           count += count_trailing_zeros (~bmp);
 659           return clib_min (count, max_count);
 660         }
 661
 662       data += 16;
 663       count += 16;
 664
 665       if (count >= max_count)
 666         return max_count;
 667     }
 668 #endif
 669   count += 2;
 670   data += 2;
 671   while (count + 3 < max_count &&
 672          ((data[0] ^ first) | (data[1] ^ first) |
 673           (data[2] ^ first) | (data[3] ^ first)) == 0)
 674     {
 675       data += 4;
 676       count += 4;
 677     }
 678   while (count < max_count && (data[0] == first))
 679     {
 680       data += 1;
 681       count += 1;
 682     }
 683   return count;
 684 }
 685
 686 #endif /* included_clib_string_h */
 687
 688 /*
 689  * fd.io coding-style-patch-verification: ON
 690  *
 691  * Local Variables:
 692  * eval: (c-set-style "gnu")
 693  * End:
 694  */