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 #include <vppinfra/error_bootstrap.h>
  50
  51 #ifdef CLIB_LINUX_KERNEL
  52 #include <linux/string.h>
  53 #endif
  54
  55 #ifdef CLIB_UNIX
  56 #include <string.h>
  57 #endif
  58
  59 #ifdef CLIB_STANDALONE
  60 #include <vppinfra/standalone_string.h>
  61 #endif
  62
  63 #if _x86_64_
  64 #include <x86intrin.h>
  65 #endif
  66
  67 /* Exchanges source and destination. */
  68 void clib_memswap (void *_a, void *_b, uword bytes);
  69
  70 /*
  71  * the vector unit memcpy variants confuse coverity
  72  * so don't let it anywhere near them.
  73  */
  74 #ifndef __COVERITY__
  75 #if __AVX512BITALG__
  76 #include <vppinfra/memcpy_avx512.h>
  77 #define clib_memcpy_fast_arch(a, b, c) clib_memcpy_fast_avx512 (a, b, c)
  78 #elif __AVX2__
  79 #include <vppinfra/memcpy_avx2.h>
  80 #define clib_memcpy_fast_arch(a, b, c) clib_memcpy_fast_avx2 (a, b, c)
  81 #elif __SSSE3__
  82 #include <vppinfra/memcpy_sse3.h>
  83 #define clib_memcpy_fast_arch(a, b, c) clib_memcpy_fast_sse3 (a, b, c)
  84 #endif /* __AVX512BITALG__ */
  85 #endif /* __COVERITY__ */
  86
  87 #ifndef clib_memcpy_fast_arch
  88 #define clib_memcpy_fast_arch(a, b, c) memcpy (a, b, c)
  89 #endif /* clib_memcpy_fast_arch */
  90
  91 static_always_inline void *
  92 clib_memcpy_fast (void *restrict dst, const void *restrict src, size_t n)
  93 {
  94   ASSERT (dst && src &&
  95           "memcpy(src, dst, n) with src == NULL or dst == NULL is undefined "
  96           "behaviour");
  97   return clib_memcpy_fast_arch (dst, src, n);
  98 }
  99
 100 #undef clib_memcpy_fast_arch
 101
 102 #include <vppinfra/memcpy.h>
 103
 104 /* c-11 string manipulation variants */
 105
 106 #ifndef EOK
 107 #define EOK 0
 108 #endif
 109 #ifndef EINVAL
 110 #define EINVAL 22
 111 #endif
 112 #ifndef ESRCH
 113 #define ESRCH 3
 114 #endif
 115 #ifndef EOVERFLOW
 116 #define EOVERFLOW 75
 117 #endif
 118
 119 /*
 120  * In order to provide smooth mapping from unsafe string API to the clib string
 121  * macro, we often have to improvise s1max and s2max due to the additional
 122  * arguments are required for implementing the safe API. This macro is used
 123  * to provide the s1max/s2max. It is not perfect because the actual
 124  * s1max/s2max may be greater than 4k and the mapping from the unsafe API to
 125  * the macro would cause a regression. However, it is not terribly likely.
 126  * So I bet against the odds.
 127  */
 128 #define CLIB_STRING_MACRO_MAX 4096
 129
 130 typedef int errno_t;
 131 typedef uword rsize_t;
 132
 133 void clib_c11_violation (const char *s);
 134 errno_t memcpy_s (void *__restrict__ dest, rsize_t dmax,
 135                   const void *__restrict__ src, rsize_t n);
 136
 137 always_inline errno_t
 138 memcpy_s_inline (void *__restrict__ dest, rsize_t dmax,
 139                  const void *__restrict__ src, rsize_t n)
 140 {
 141   uword low, hi;
 142   u8 bad;
 143
 144   /*
 145    * Optimize constant-number-of-bytes calls without asking
 146    * "too many questions for someone from New Jersey"
 147    */
 148   if (COMPILE_TIME_CONST (n))
 149     {
 150       clib_memcpy_fast (dest, src, n);
 151       return EOK;
 152     }
 153
 154   /*
 155    * call bogus if: src or dst NULL, trying to copy
 156    * more data than we have space in dst, or src == dst.
 157    * n == 0 isn't really "bad", so check first in the
 158    * "wall-of-shame" department...
 159    */
 160   bad = (dest == 0) + (src == 0) + (n > dmax) + (dest == src) + (n == 0);
 161   if (PREDICT_FALSE (bad != 0))
 162     {
 163       /* Not actually trying to copy anything is OK */
 164       if (n == 0)
 165         return EOK;
 166       if (dest == NULL)
 167         clib_c11_violation ("dest NULL");
 168       if (src == NULL)
 169         clib_c11_violation ("src NULL");
 170       if (n > dmax)
 171         clib_c11_violation ("n > dmax");
 172       if (dest == src)
 173         clib_c11_violation ("dest == src");
 174       return EINVAL;
 175     }
 176
 177   /* Check for src/dst overlap, which is not allowed */
 178   low = (uword) (src < dest ? src : dest);
 179   hi = (uword) (src < dest ? dest : src);
 180
 181   if (PREDICT_FALSE (low + (n - 1) >= hi))
 182     {
 183       clib_c11_violation ("src/dest overlap");
 184       return EINVAL;
 185     }
 186
 187   clib_memcpy_fast (dest, src, n);
 188   return EOK;
 189 }
 190
 191 /*
 192  * Note: $$$ This macro is a crutch. Folks need to manually
 193  * inspect every extant clib_memcpy(...) call and
 194  * attempt to provide a real destination buffer size
 195  * argument...
 196  */
 197 #define clib_memcpy(d,s,n) memcpy_s_inline(d,n,s,n)
 198
 199 errno_t memset_s (void *s, rsize_t smax, int c, rsize_t n);
 200
 201 always_inline errno_t
 202 memset_s_inline (void *s, rsize_t smax, int c, rsize_t n)
 203 {
 204   u8 bad;
 205
 206   bad = (s == 0) + (n > smax);
 207
 208   if (PREDICT_FALSE (bad != 0))
 209     {
 210       if (s == 0)
 211         clib_c11_violation ("s NULL");
 212       if (n > smax)
 213         clib_c11_violation ("n > smax");
 214       return (EINVAL);
 215     }
 216   memset (s, c, n);
 217   return (EOK);
 218 }
 219
 220 /*
 221  * This macro is not [so much of] a crutch.
 222  * It's super-typical to write:
 223  *
 224  *   ep = pool_get (<pool>);
 225  *   clib_memset(ep, 0, sizeof (*ep));
 226  *
 227  * The compiler should delete the not-so useful
 228  * (n > smax) test. TBH the NULL pointer check isn't
 229  * so useful in this case, but so be it.
 230  */
 231 #define clib_memset(s,c,n) memset_s_inline(s,n,c,n)
 232
 233 static_always_inline void
 234 clib_memcpy_le (u8 * dst, u8 * src, u8 len, u8 max_len)
 235 {
 236 #if defined (CLIB_HAVE_VEC256)
 237   u8x32 s0, s1, d0, d1;
 238   u8x32 mask = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
 239     18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31
 240   };
 241   u8x32 lv = u8x32_splat (len);
 242   u8x32 add = u8x32_splat (32);
 243
 244   s0 = u8x32_load_unaligned (src);
 245   s1 = u8x32_load_unaligned (src + 32);
 246   d0 = u8x32_load_unaligned (dst);
 247   d1 = u8x32_load_unaligned (dst + 32);
 248
 249   d0 = u8x32_blend (d0, s0, u8x32_is_greater (lv, mask));
 250   u8x32_store_unaligned (d0, dst);
 251
 252   if (max_len <= 32)
 253     return;
 254
 255   mask += add;
 256   d1 = u8x32_blend (d1, s1, u8x32_is_greater (lv, mask));
 257   u8x32_store_unaligned (d1, dst + 32);
 258
 259 #elif defined (CLIB_HAVE_VEC128)
 260   u8x16 s0, s1, s2, s3, d0, d1, d2, d3;
 261   u8x16 mask = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
 262   u8x16 lv = u8x16_splat (len);
 263   u8x16 add = u8x16_splat (16);
 264
 265   s0 = u8x16_load_unaligned (src);
 266   s1 = u8x16_load_unaligned (src + 16);
 267   s2 = u8x16_load_unaligned (src + 32);
 268   s3 = u8x16_load_unaligned (src + 48);
 269   d0 = u8x16_load_unaligned (dst);
 270   d1 = u8x16_load_unaligned (dst + 16);
 271   d2 = u8x16_load_unaligned (dst + 32);
 272   d3 = u8x16_load_unaligned (dst + 48);
 273
 274   d0 = u8x16_blend (d0, s0, u8x16_is_greater (lv, mask));
 275   u8x16_store_unaligned (d0, dst);
 276
 277   if (max_len <= 16)
 278     return;
 279
 280   mask += add;
 281   d1 = u8x16_blend (d1, s1, u8x16_is_greater (lv, mask));
 282   u8x16_store_unaligned (d1, dst + 16);
 283
 284   if (max_len <= 32)
 285     return;
 286
 287   mask += add;
 288   d2 = u8x16_blend (d2, s2, u8x16_is_greater (lv, mask));
 289   u8x16_store_unaligned (d2, dst + 32);
 290
 291   mask += add;
 292   d3 = u8x16_blend (d3, s3, u8x16_is_greater (lv, mask));
 293   u8x16_store_unaligned (d3, dst + 48);
 294 #else
 295   memmove (dst, src, len);
 296 #endif
 297 }
 298
 299 static_always_inline void
 300 clib_memcpy_le64 (u8 * dst, u8 * src, u8 len)
 301 {
 302   clib_memcpy_le (dst, src, len, 64);
 303 }
 304
 305 static_always_inline void
 306 clib_memcpy_le32 (u8 * dst, u8 * src, u8 len)
 307 {
 308   clib_memcpy_le (dst, src, len, 32);
 309 }
 310
 311 static_always_inline void
 312 clib_memset_u64 (void *p, u64 val, uword count)
 313 {
 314   u64 *ptr = p;
 315 #if defined(CLIB_HAVE_VEC512)
 316   u64x8 v512 = u64x8_splat (val);
 317   while (count >= 8)
 318     {
 319       u64x8_store_unaligned (v512, ptr);
 320       ptr += 8;
 321       count -= 8;
 322     }
 323   if (count == 0)
 324     return;
 325 #endif
 326 #if defined(CLIB_HAVE_VEC256)
 327   u64x4 v256 = u64x4_splat (val);
 328   while (count >= 4)
 329     {
 330       u64x4_store_unaligned (v256, ptr);
 331       ptr += 4;
 332       count -= 4;
 333     }
 334   if (count == 0)
 335     return;
 336 #else
 337   while (count >= 4)
 338     {
 339       ptr[0] = ptr[1] = ptr[2] = ptr[3] = val;
 340       ptr += 4;
 341       count -= 4;
 342     }
 343 #endif
 344   while (count--)
 345     ptr++[0] = val;
 346 }
 347
 348 static_always_inline void
 349 clib_memset_u32 (void *p, u32 val, uword count)
 350 {
 351   u32 *ptr = p;
 352 #if defined(CLIB_HAVE_VEC512)
 353   u32x16 v512 = u32x16_splat (val);
 354   while (count >= 16)
 355     {
 356       u32x16_store_unaligned (v512, ptr);
 357       ptr += 16;
 358       count -= 16;
 359     }
 360   if (count == 0)
 361     return;
 362 #endif
 363 #if defined(CLIB_HAVE_VEC256)
 364   u32x8 v256 = u32x8_splat (val);
 365   while (count >= 8)
 366     {
 367       u32x8_store_unaligned (v256, ptr);
 368       ptr += 8;
 369       count -= 8;
 370     }
 371   if (count == 0)
 372     return;
 373 #endif
 374 #if defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
 375   u32x4 v128 = u32x4_splat (val);
 376   while (count >= 4)
 377     {
 378       u32x4_store_unaligned (v128, ptr);
 379       ptr += 4;
 380       count -= 4;
 381     }
 382 #else
 383   while (count >= 4)
 384     {
 385       ptr[0] = ptr[1] = ptr[2] = ptr[3] = val;
 386       ptr += 4;
 387       count -= 4;
 388     }
 389 #endif
 390   while (count--)
 391     ptr++[0] = val;
 392 }
 393
 394 static_always_inline void
 395 clib_memset_u16 (void *p, u16 val, uword count)
 396 {
 397   u16 *ptr = p;
 398 #if defined(CLIB_HAVE_VEC512)
 399   u16x32 v512 = u16x32_splat (val);
 400   while (count >= 32)
 401     {
 402       u16x32_store_unaligned (v512, ptr);
 403       ptr += 32;
 404       count -= 32;
 405     }
 406   if (count == 0)
 407     return;
 408 #endif
 409 #if defined(CLIB_HAVE_VEC256)
 410   u16x16 v256 = u16x16_splat (val);
 411   while (count >= 16)
 412     {
 413       u16x16_store_unaligned (v256, ptr);
 414       ptr += 16;
 415       count -= 16;
 416     }
 417   if (count == 0)
 418     return;
 419 #endif
 420 #if defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
 421   u16x8 v128 = u16x8_splat (val);
 422   while (count >= 8)
 423     {
 424       u16x8_store_unaligned (v128, ptr);
 425       ptr += 8;
 426       count -= 8;
 427     }
 428 #else
 429   while (count >= 4)
 430     {
 431       ptr[0] = ptr[1] = ptr[2] = ptr[3] = val;
 432       ptr += 4;
 433       count -= 4;
 434     }
 435 #endif
 436   while (count--)
 437     ptr++[0] = val;
 438 }
 439
 440 static_always_inline void
 441 clib_memset_u8 (void *p, u8 val, uword count)
 442 {
 443   u8 *ptr = p;
 444 #if defined(CLIB_HAVE_VEC512)
 445   u8x64 v512 = u8x64_splat (val);
 446   while (count >= 64)
 447     {
 448       u8x64_store_unaligned (v512, ptr);
 449       ptr += 64;
 450       count -= 64;
 451     }
 452   if (count == 0)
 453     return;
 454 #endif
 455 #if defined(CLIB_HAVE_VEC256)
 456   u8x32 v256 = u8x32_splat (val);
 457   while (count >= 32)
 458     {
 459       u8x32_store_unaligned (v256, ptr);
 460       ptr += 32;
 461       count -= 32;
 462     }
 463   if (count == 0)
 464     return;
 465 #endif
 466 #if defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
 467   u8x16 v128 = u8x16_splat (val);
 468   while (count >= 16)
 469     {
 470       u8x16_store_unaligned (v128, ptr);
 471       ptr += 16;
 472       count -= 16;
 473     }
 474 #else
 475   while (count >= 4)
 476     {
 477       ptr[0] = ptr[1] = ptr[2] = ptr[3] = val;
 478       ptr += 4;
 479       count -= 4;
 480     }
 481 #endif
 482   while (count--)
 483     ptr++[0] = val;
 484 }
 485
 486 static_always_inline uword
 487 clib_count_equal_u64 (u64 * data, uword max_count)
 488 {
 489   uword count;
 490   u64 first;
 491
 492   if (max_count <= 1)
 493     return max_count;
 494   if (data[0] != data[1])
 495     return 1;
 496
 497   count = 0;
 498   first = data[0];
 499
 500 #if defined(CLIB_HAVE_VEC256)
 501   u64x4 splat = u64x4_splat (first);
 502   while (count + 3 < max_count)
 503     {
 504       u64 bmp;
 505       bmp = u8x32_msb_mask ((u8x32) (u64x4_load_unaligned (data) == splat));
 506       if (bmp != 0xffffffff)
 507         {
 508           count += count_trailing_zeros (~bmp) / 8;
 509           return count;
 510         }
 511
 512       data += 4;
 513       count += 4;
 514     }
 515 #else
 516   count += 2;
 517   data += 2;
 518   while (count + 3 < max_count &&
 519          ((data[0] ^ first) | (data[1] ^ first) |
 520           (data[2] ^ first) | (data[3] ^ first)) == 0)
 521     {
 522       data += 4;
 523       count += 4;
 524     }
 525 #endif
 526   while (count < max_count && (data[0] == first))
 527     {
 528       data += 1;
 529       count += 1;
 530     }
 531   return count;
 532 }
 533
 534 static_always_inline uword
 535 clib_count_equal_u32 (u32 * data, uword max_count)
 536 {
 537   uword count;
 538   u32 first;
 539
 540   if (max_count <= 1)
 541     return max_count;
 542   if (data[0] != data[1])
 543     return 1;
 544
 545   count = 0;
 546   first = data[0];
 547
 548 #if defined(CLIB_HAVE_VEC256)
 549   u32x8 splat = u32x8_splat (first);
 550   while (count + 7 < max_count)
 551     {
 552       u64 bmp;
 553       bmp = u8x32_msb_mask ((u8x32) (u32x8_load_unaligned (data) == splat));
 554       if (bmp != 0xffffffff)
 555         {
 556           count += count_trailing_zeros (~bmp) / 4;
 557           return count;
 558         }
 559
 560       data += 8;
 561       count += 8;
 562     }
 563 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_MSB_MASK)
 564   u32x4 splat = u32x4_splat (first);
 565   while (count + 3 < max_count)
 566     {
 567       u64 bmp;
 568       bmp = u8x16_msb_mask ((u8x16) (u32x4_load_unaligned (data) == splat));
 569       if (bmp != 0xffff)
 570         {
 571           count += count_trailing_zeros (~bmp) / 4;
 572           return count;
 573         }
 574
 575       data += 4;
 576       count += 4;
 577     }
 578 #else
 579   count += 2;
 580   data += 2;
 581   while (count + 3 < max_count &&
 582          ((data[0] ^ first) | (data[1] ^ first) |
 583           (data[2] ^ first) | (data[3] ^ first)) == 0)
 584     {
 585       data += 4;
 586       count += 4;
 587     }
 588 #endif
 589   while (count < max_count && (data[0] == first))
 590     {
 591       data += 1;
 592       count += 1;
 593     }
 594   return count;
 595 }
 596
 597 static_always_inline uword
 598 clib_count_equal_u16 (u16 * data, uword max_count)
 599 {
 600   uword count;
 601   u16 first;
 602
 603   if (max_count <= 1)
 604     return max_count;
 605   if (data[0] != data[1])
 606     return 1;
 607
 608   count = 0;
 609   first = data[0];
 610
 611 #if defined(CLIB_HAVE_VEC256)
 612   u16x16 splat = u16x16_splat (first);
 613   while (count + 15 < max_count)
 614     {
 615       u64 bmp;
 616       bmp = u8x32_msb_mask ((u8x32) (u16x16_load_unaligned (data) == splat));
 617       if (bmp != 0xffffffff)
 618         {
 619           count += count_trailing_zeros (~bmp) / 2;
 620           return count;
 621         }
 622
 623       data += 16;
 624       count += 16;
 625     }
 626 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_MSB_MASK)
 627   u16x8 splat = u16x8_splat (first);
 628   while (count + 7 < max_count)
 629     {
 630       u64 bmp;
 631       bmp = u8x16_msb_mask ((u8x16) (u16x8_load_unaligned (data) == splat));
 632       if (bmp != 0xffff)
 633         {
 634           count += count_trailing_zeros (~bmp) / 2;
 635           return count;
 636         }
 637
 638       data += 8;
 639       count += 8;
 640     }
 641 #else
 642   count += 2;
 643   data += 2;
 644   while (count + 3 < max_count &&
 645          ((data[0] ^ first) | (data[1] ^ first) |
 646           (data[2] ^ first) | (data[3] ^ first)) == 0)
 647     {
 648       data += 4;
 649       count += 4;
 650     }
 651 #endif
 652   while (count < max_count && (data[0] == first))
 653     {
 654       data += 1;
 655       count += 1;
 656     }
 657   return count;
 658 }
 659
 660 static_always_inline uword
 661 clib_count_equal_u8 (u8 * data, uword max_count)
 662 {
 663   uword count;
 664   u8 first;
 665
 666   if (max_count <= 1)
 667     return max_count;
 668   if (data[0] != data[1])
 669     return 1;
 670
 671   count = 0;
 672   first = data[0];
 673
 674 #if defined(CLIB_HAVE_VEC256)
 675   u8x32 splat = u8x32_splat (first);
 676   while (count + 31 < max_count)
 677     {
 678       u64 bmp;
 679       bmp = u8x32_msb_mask ((u8x32) (u8x32_load_unaligned (data) == splat));
 680       if (bmp != 0xffffffff)
 681         return max_count;
 682
 683       data += 32;
 684       count += 32;
 685     }
 686 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_MSB_MASK)
 687   u8x16 splat = u8x16_splat (first);
 688   while (count + 15 < max_count)
 689     {
 690       u64 bmp;
 691       bmp = u8x16_msb_mask ((u8x16) (u8x16_load_unaligned (data) == splat));
 692       if (bmp != 0xffff)
 693         {
 694           count += count_trailing_zeros (~bmp);
 695           return count;
 696         }
 697
 698       data += 16;
 699       count += 16;
 700     }
 701 #else
 702   count += 2;
 703   data += 2;
 704   while (count + 3 < max_count &&
 705          ((data[0] ^ first) | (data[1] ^ first) |
 706           (data[2] ^ first) | (data[3] ^ first)) == 0)
 707     {
 708       data += 4;
 709       count += 4;
 710     }
 711 #endif
 712   while (count < max_count && (data[0] == first))
 713     {
 714       data += 1;
 715       count += 1;
 716     }
 717   return count;
 718 }
 719
 720 /*
 721  * This macro is to provide smooth mapping from memcmp to memcmp_s.
 722  * memcmp has fewer parameters and fewer returns than memcmp_s.
 723  * This macro is somewhat a crutch. When err != EOK is returned from memcmp_s,
 724  * we return 0 and spit out a message in the console because there is
 725  * no way to return the error code to the memcmp callers.
 726  * This condition happens when s1 or s2 is null. Please note
 727  * in the extant memcmp calls, if s1, s2, or both are null, memcmp returns 0
 728  * anyway. So we are consistent in this case for the comparison return
 729  * although we also spit out a C11 violation message in the console to
 730  * warn that they pass null pointers for both s1 and s2.
 731  * Applications are encouraged to use the cool C11 memcmp_s API to get the
 732  * maximum benefit out of it.
 733  */
 734 #define clib_memcmp(s1,s2,m1) \
 735   ({ int __diff = 0;                                   \
 736     memcmp_s_inline (s1, m1, s2, m1, &__diff);  \
 737     __diff; \
 738   })
 739
 740 errno_t memcmp_s (const void *s1, rsize_t s1max, const void *s2,
 741                   rsize_t s2max, int *diff);
 742
 743 always_inline errno_t
 744 memcmp_s_inline (const void *s1, rsize_t s1max, const void *s2, rsize_t s2max,
 745                  int *diff)
 746 {
 747   u8 bad;
 748
 749   bad = (s1 == 0) + (s2 == 0) + (diff == 0) + (s2max > s1max) + (s2max == 0) +
 750     (s1max == 0);
 751
 752   if (PREDICT_FALSE (bad != 0))
 753     {
 754       if (s1 == NULL)
 755         clib_c11_violation ("s1 NULL");
 756       if (s2 == NULL)
 757         clib_c11_violation ("s2 NULL");
 758       if (diff == NULL)
 759         clib_c11_violation ("diff NULL");
 760       if (s2max > s1max)
 761         clib_c11_violation ("s2max > s1max");
 762       if (s2max == 0)
 763         clib_c11_violation ("s2max 0");
 764       if (s1max == 0)
 765         clib_c11_violation ("s1max 0");
 766       return EINVAL;
 767     }
 768
 769   if (PREDICT_FALSE (s1 == s2))
 770     {
 771       *diff = 0;
 772       return EOK;
 773     }
 774
 775   *diff = memcmp (s1, s2, s2max);
 776   return EOK;
 777 }
 778
 779 /*
 780  * This macro is to provide smooth mapping from strnlen to strnlen_s
 781  */
 782 #define clib_strnlen(s,m) strnlen_s_inline(s,m)
 783
 784 size_t strnlen_s (const char *s, size_t maxsize);
 785
 786 always_inline size_t
 787 strnlen_s_inline (const char *s, size_t maxsize)
 788 {
 789   u8 bad;
 790
 791   bad = (s == 0) + (maxsize == 0);
 792   if (PREDICT_FALSE (bad != 0))
 793     {
 794       if (s == 0)
 795         clib_c11_violation ("s NULL");
 796       if (maxsize == 0)
 797         clib_c11_violation ("maxsize 0");
 798       return 0;
 799     }
 800   return strnlen (s, maxsize);
 801 }
 802
 803 /*
 804  * This macro is to provide smooth mapping from strcmp to strcmp_s.
 805  * strcmp has fewer parameters and fewer returns than strcmp_s.
 806  * This macro is somewhat a crutch. When err != EOK is returned from strcmp_s,
 807  * we return 0 and spit out a message in the console because
 808  * there is no way to return the error to the strcmp callers.
 809  * This condition happens when s1 or s2 is null. Please note in the extant
 810  * strcmp call, they would end up crashing if one of them is null.
 811  * So the new behavior is no crash, but an error is displayed in the
 812  * console which I think is more user friendly. If both s1 and s2 are null,
 813  * strcmp returns 0. Obviously, strcmp did the pointers comparison prior
 814  * to actually accessing the pointer contents. We are still consistent
 815  * in this case for the comparison return although we also spit out a
 816  * C11 violation message in the console to warn that they pass null pointers
 817  * for both s1 and s2. The other problem is strcmp does not provide s1max,
 818  * we use CLIB_STRING_MACRO_MAX and hopefully, s1 is null terminated.
 819  * If not, we may be accessing memory beyonf what is intended.
 820  * Applications are encouraged to use the cool C11 strcmp_s API to get the
 821  * maximum benefit out of it.
 822  */
 823 #define clib_strcmp(s1,s2) \
 824   ({ int __indicator = 0; \
 825     strcmp_s_inline (s1, CLIB_STRING_MACRO_MAX, s2, &__indicator);      \
 826     __indicator;                        \
 827   })
 828
 829 errno_t strcmp_s (const char *s1, rsize_t s1max, const char *s2,
 830                   int *indicator);
 831
 832 always_inline errno_t
 833 strcmp_s_inline (const char *s1, rsize_t s1max, const char *s2,
 834                  int *indicator)
 835 {
 836   u8 bad;
 837
 838   bad = (indicator == 0) + (s1 == 0) + (s2 == 0) + (s1max == 0) +
 839     (s1 && s1max && s1[clib_strnlen (s1, s1max)] != '\0');
 840
 841   if (PREDICT_FALSE (bad != 0))
 842     {
 843       if (indicator == NULL)
 844         clib_c11_violation ("indicator NULL");
 845       if (s1 == NULL)
 846         clib_c11_violation ("s1 NULL");
 847       if (s2 == NULL)
 848         clib_c11_violation ("s2 NULL");
 849       if (s1max == 0)
 850         clib_c11_violation ("s1max 0");
 851       if (s1 && s1max && s1[clib_strnlen (s1, s1max)] != '\0')
 852         clib_c11_violation ("s1 unterminated");
 853       return EINVAL;
 854     }
 855
 856   *indicator = strcmp (s1, s2);
 857   return EOK;
 858 }
 859
 860 /*
 861  * This macro is to provide smooth mapping from strncmp to strncmp_s.
 862  * strncmp has fewer parameters and fewer returns than strncmp_s. That said,
 863  * this macro is somewhat a crutch. When we get err != EOK from strncmp_s,
 864  * we return 0 and spit out a message in the console because there is no
 865  * means to return the error to the strncmp caller.
 866  * This condition happens when s1 or s2 is null. In the extant strncmp call,
 867  * they would end up crashing if one of them is null. So the new behavior is
 868  * no crash, but error is displayed in the console which is more
 869  * user friendly. If s1 and s2 are null, strncmp returns 0. Obviously,
 870  * strncmp did the pointers comparison prior to actually accessing the
 871  * pointer contents. We are still consistent in this case for the comparison
 872  * return although we also spit out a C11 violation message in the console to
 873  * warn that they pass null pointers for both s1 and s2.
 874  * Applications are encouraged to use the cool C11 strncmp_s API to get the
 875  * maximum benefit out of it.
 876  */
 877 #define clib_strncmp(s1,s2,n) \
 878   ({ int __indicator = 0; \
 879     strncmp_s_inline (s1, CLIB_STRING_MACRO_MAX, s2, n, &__indicator);  \
 880     __indicator;                        \
 881   })
 882
 883 errno_t strncmp_s (const char *s1, rsize_t s1max, const char *s2, rsize_t n,
 884                    int *indicator);
 885
 886 always_inline errno_t
 887 strncmp_s_inline (const char *s1, rsize_t s1max, const char *s2, rsize_t n,
 888                   int *indicator)
 889 {
 890   u8 bad;
 891   u8 s1_greater_s1max = (s1 && s1max && n > clib_strnlen (s1, s1max));
 892
 893   if (PREDICT_FALSE (s1_greater_s1max && indicator))
 894     {
 895       /*
 896        * strcmp allows n > s1max. If indicator is non null, we can still
 897        * do the compare without any harm and return EINVAL as well as the
 898        * result in indicator.
 899        */
 900       clib_c11_violation ("n exceeds s1 length");
 901       *indicator = strncmp (s1, s2, n);
 902       return EINVAL;
 903     }
 904
 905   bad = (s1 == 0) + (s2 == 0) + (indicator == 0) + (s1max == 0) +
 906     (s1 && s1max && s1[clib_strnlen (s1, s1max)] != '\0') + s1_greater_s1max;
 907
 908   if (PREDICT_FALSE (bad != 0))
 909     {
 910       if (indicator == NULL)
 911         clib_c11_violation ("indicator NULL");
 912       if (s1 == NULL)
 913         clib_c11_violation ("s1 NULL");
 914       if (s2 == NULL)
 915         clib_c11_violation ("s2 NULL");
 916       if (s1max == 0)
 917         clib_c11_violation ("s1max 0");
 918       if (s1 && s1max && s1[clib_strnlen (s1, s1max)] != '\0')
 919         clib_c11_violation ("s1 unterminated");
 920       if (s1_greater_s1max)
 921         clib_c11_violation ("n exceeds s1 length");
 922       return EINVAL;
 923     }
 924
 925   *indicator = strncmp (s1, s2, n);
 926   return EOK;
 927 }
 928
 929 errno_t strcpy_s (char *__restrict__ dest, rsize_t dmax,
 930                   const char *__restrict__ src);
 931
 932 always_inline errno_t
 933 strcpy_s_inline (char *__restrict__ dest, rsize_t dmax,
 934                  const char *__restrict__ src)
 935 {
 936   u8 bad;
 937   uword low, hi;
 938   size_t n;
 939
 940   bad = (dest == 0) + (dmax == 0) + (src == 0);
 941   if (PREDICT_FALSE (bad != 0))
 942     {
 943       if (dest == 0)
 944         clib_c11_violation ("dest NULL");
 945       if (src == 0)
 946         clib_c11_violation ("src NULL");
 947       if (dmax == 0)
 948         clib_c11_violation ("dmax 0");
 949       return EINVAL;
 950     }
 951
 952   n = clib_strnlen (src, dmax);
 953   if (PREDICT_FALSE (n >= dmax))
 954     {
 955       clib_c11_violation ("not enough space for dest");
 956       return (EINVAL);
 957     }
 958   /* Not actually trying to copy anything is OK */
 959   if (PREDICT_FALSE (n == 0))
 960     return EOK;
 961
 962   /* Check for src/dst overlap, which is not allowed */
 963   low = (uword) (src < dest ? src : dest);
 964   hi = (uword) (src < dest ? dest : src);
 965
 966   if (PREDICT_FALSE (low + (n - 1) >= hi))
 967     {
 968       clib_c11_violation ("src/dest overlap");
 969       return EINVAL;
 970     }
 971
 972   clib_memcpy_fast (dest, src, n);
 973   dest[n] = '\0';
 974   return EOK;
 975 }
 976
 977 /*
 978  * This macro is provided for smooth migration from strncpy. It is not perfect
 979  * because we don't know the size of the destination buffer to pass to
 980  * strncpy_s. We improvise dmax with CLIB_STRING_MACRO_MAX.
 981  * Applications are encouraged to move to the C11 strncpy_s API and provide
 982  * the correct dmax for better error checking.
 983  */
 984 #define clib_strncpy(d,s,n) strncpy_s_inline(d,CLIB_STRING_MACRO_MAX,s,n)
 985
 986 errno_t
 987 strncpy_s (char *__restrict__ dest, rsize_t dmax,
 988            const char *__restrict__ src, rsize_t n);
 989
 990 always_inline errno_t
 991 strncpy_s_inline (char *__restrict__ dest, rsize_t dmax,
 992                   const char *__restrict__ src, rsize_t n)
 993 {
 994   u8 bad;
 995   uword low, hi;
 996   rsize_t m;
 997   errno_t status = EOK;
 998
 999   bad = (dest == 0) + (dmax == 0) + (src == 0) + (n == 0);
1000   if (PREDICT_FALSE (bad != 0))
1001     {
1002       /* Not actually trying to copy anything is OK */
1003       if (n == 0)
1004         return EOK;
1005       if (dest == 0)
1006         clib_c11_violation ("dest NULL");
1007       if (src == 0)
1008         clib_c11_violation ("src NULL");
1009       if (dmax == 0)
1010         clib_c11_violation ("dmax 0");
1011       return EINVAL;
1012     }
1013
1014   if (PREDICT_FALSE (n >= dmax))
1015     {
1016       /* Relax and use strnlen of src */
1017       clib_c11_violation ("n >= dmax");
1018       m = clib_strnlen (src, dmax);
1019       if (m >= dmax)
1020         {
1021           /* Truncate, adjust copy length to fit dest */
1022           m = dmax - 1;
1023           status = EOVERFLOW;
1024         }
1025     }
1026   else
1027     /* cap the copy to strlen(src) in case n > strlen(src) */
1028     m = clib_strnlen (src, n);
1029
1030   /* Check for src/dst overlap, which is not allowed */
1031   low = (uword) (src < dest ? src : dest);
1032   hi = (uword) (src < dest ? dest : src);
1033
1034   /*
1035    * This check may fail innocently if src + dmax >= dst, but
1036    * src + strlen(src) < dst. If it fails, check more carefully before
1037    * blowing the whistle.
1038    */
1039   if (PREDICT_FALSE (low + (m - 1) >= hi))
1040     {
1041       m = clib_strnlen (src, m);
1042
1043       if (low + (m - 1) >= hi)
1044         {
1045           clib_c11_violation ("src/dest overlap");
1046           return EINVAL;
1047         }
1048     }
1049
1050   clib_memcpy_fast (dest, src, m);
1051   dest[m] = '\0';
1052   return status;
1053 }
1054
1055 errno_t strcat_s (char *__restrict__ dest, rsize_t dmax,
1056                   const char *__restrict__ src);
1057
1058 always_inline errno_t
1059 strcat_s_inline (char *__restrict__ dest, rsize_t dmax,
1060                  const char *__restrict__ src)
1061 {
1062   u8 bad;
1063   uword low, hi;
1064   size_t m, n, dest_size;
1065
1066   bad = (dest == 0) + (dmax == 0) + (src == 0);
1067   if (PREDICT_FALSE (bad != 0))
1068     {
1069       if (dest == 0)
1070         clib_c11_violation ("dest NULL");
1071       if (src == 0)
1072         clib_c11_violation ("src NULL");
1073       if (dmax == 0)
1074         clib_c11_violation ("dmax 0");
1075       return EINVAL;
1076     }
1077
1078   dest_size = clib_strnlen (dest, dmax);
1079   m = dmax - dest_size;
1080   n = clib_strnlen (src, m);
1081   if (PREDICT_FALSE (n >= m))
1082     {
1083       clib_c11_violation ("not enough space for dest");
1084       return EINVAL;
1085     }
1086
1087   /* Not actually trying to concatenate anything is OK */
1088   if (PREDICT_FALSE (n == 0))
1089     return EOK;
1090
1091   /* Check for src/dst overlap, which is not allowed */
1092   low = (uword) (src < dest ? src : dest);
1093   hi = (uword) (src < dest ? dest : src);
1094
1095   if (PREDICT_FALSE (low + (n - 1) >= hi))
1096     {
1097       clib_c11_violation ("src/dest overlap");
1098       return EINVAL;
1099     }
1100
1101   clib_memcpy_fast (dest + dest_size, src, n);
1102   dest[dest_size + n] = '\0';
1103   return EOK;
1104 }
1105
1106 errno_t strncat_s (char *__restrict__ dest, rsize_t dmax,
1107                    const char *__restrict__ src, rsize_t n);
1108
1109 always_inline errno_t
1110 strncat_s_inline (char *__restrict__ dest, rsize_t dmax,
1111                   const char *__restrict__ src, rsize_t n)
1112 {
1113   u8 bad;
1114   uword low, hi;
1115   size_t m, dest_size, allowed_size;
1116   errno_t status = EOK;
1117
1118   bad = (dest == 0) + (src == 0) + (dmax == 0) + (n == 0);
1119   if (PREDICT_FALSE (bad != 0))
1120     {
1121       /* Not actually trying to concatenate anything is OK */
1122       if (n == 0)
1123         return EOK;
1124       if (dest == 0)
1125         clib_c11_violation ("dest NULL");
1126       if (src == 0)
1127         clib_c11_violation ("src NULL");
1128       if (dmax == 0)
1129         clib_c11_violation ("dmax 0");
1130       return EINVAL;
1131     }
1132
1133   /* Check for src/dst overlap, which is not allowed */
1134   low = (uword) (src < dest ? src : dest);
1135   hi = (uword) (src < dest ? dest : src);
1136
1137   if (PREDICT_FALSE (low + (n - 1) >= hi))
1138     {
1139       clib_c11_violation ("src/dest overlap");
1140       return EINVAL;
1141     }
1142
1143   dest_size = clib_strnlen (dest, dmax);
1144   allowed_size = dmax - dest_size;
1145
1146   if (PREDICT_FALSE (allowed_size == 0))
1147     {
1148       clib_c11_violation ("no space left in dest");
1149       return (EINVAL);
1150     }
1151
1152   if (PREDICT_FALSE (n >= allowed_size))
1153     {
1154       /*
1155        * unlike strcat_s, strncat_s will do the concatenation anyway when
1156        * there is not enough space in dest. But it will do the truncation and
1157        * null terminate dest
1158        */
1159       m = clib_strnlen (src, allowed_size);
1160       if (m >= allowed_size)
1161         {
1162           m = allowed_size - 1;
1163           status = EOVERFLOW;
1164         }
1165     }
1166   else
1167     m = clib_strnlen (src, n);
1168
1169   clib_memcpy_fast (dest + dest_size, src, m);
1170   dest[dest_size + m] = '\0';
1171   return status;
1172 }
1173
1174 /*
1175  * This macro is to provide smooth mapping from strtok_r to strtok_s.
1176  * To map strtok to this macro, the caller would have to supply an additional
1177  * argument. strtokr_s requires s1max which the unsafe API does not have. So
1178  * we have to improvise it with CLIB_STRING_MACRO_MAX. Unlike strtok_s,
1179  * this macro cannot catch unterminated s1 and s2.
1180  * Applications are encouraged to use the cool C11 strtok_s API to avoid
1181  * these problems.
1182  */
1183 #define clib_strtok(s1,s2,p)               \
1184   ({ rsize_t __s1max = CLIB_STRING_MACRO_MAX;   \
1185     strtok_s_inline (s1, &__s1max, s2, p);              \
1186   })
1187
1188 char *strtok_s (char *__restrict__ s1, rsize_t * __restrict__ s1max,
1189                 const char *__restrict__ s2, char **__restrict__ ptr);
1190
1191 always_inline char *
1192 strtok_s_inline (char *__restrict__ s1, rsize_t * __restrict__ s1max,
1193                  const char *__restrict__ s2, char **__restrict__ ptr)
1194 {
1195 #define STRTOK_DELIM_MAX_LEN 16
1196   u8 bad;
1197   const char *pt;
1198   char *ptoken;
1199   uword dlen, slen;
1200
1201   bad = (s1max == 0) + (s2 == 0) + (ptr == 0) +
1202     ((s1 == 0) && ptr && (*ptr == 0));
1203   if (PREDICT_FALSE (bad != 0))
1204     {
1205       if (s2 == NULL)
1206         clib_c11_violation ("s2 NULL");
1207       if (s1max == NULL)
1208         clib_c11_violation ("s1max is NULL");
1209       if (ptr == NULL)
1210         clib_c11_violation ("ptr is NULL");
1211       /* s1 == 0 and *ptr == null is no good */
1212       if ((s1 == 0) && ptr && (*ptr == 0))
1213         clib_c11_violation ("s1 and ptr contents are NULL");
1214       return 0;
1215     }
1216
1217   if (s1 == 0)
1218     s1 = *ptr;
1219
1220   /*
1221    * scan s1 for a delimiter
1222    */
1223   dlen = *s1max;
1224   ptoken = 0;
1225   while (*s1 != '\0' && !ptoken)
1226     {
1227       if (PREDICT_FALSE (dlen == 0))
1228         {
1229           *ptr = 0;
1230           clib_c11_violation ("s1 unterminated");
1231           return 0;
1232         }
1233
1234       /*
1235        * must scan the entire delimiter list
1236        * ISO should have included a delimiter string limit!!
1237        */
1238       slen = STRTOK_DELIM_MAX_LEN;
1239       pt = s2;
1240       while (*pt != '\0')
1241         {
1242           if (PREDICT_FALSE (slen == 0))
1243             {
1244               *ptr = 0;
1245               clib_c11_violation ("s2 unterminated");
1246               return 0;
1247             }
1248           slen--;
1249           if (*s1 == *pt)
1250             {
1251               ptoken = 0;
1252               break;
1253             }
1254           else
1255             {
1256               pt++;
1257               ptoken = s1;
1258             }
1259         }
1260       s1++;
1261       dlen--;
1262     }
1263
1264   /*
1265    * if the beginning of a token was not found, then no
1266    * need to continue the scan.
1267    */
1268   if (ptoken == 0)
1269     {
1270       *s1max = dlen;
1271       return (ptoken);
1272     }
1273
1274   /*
1275    * Now we need to locate the end of the token
1276    */
1277   while (*s1 != '\0')
1278     {
1279       if (dlen == 0)
1280         {
1281           *ptr = 0;
1282           clib_c11_violation ("s1 unterminated");
1283           return 0;
1284         }
1285
1286       slen = STRTOK_DELIM_MAX_LEN;
1287       pt = s2;
1288       while (*pt != '\0')
1289         {
1290           if (slen == 0)
1291             {
1292               *ptr = 0;
1293               clib_c11_violation ("s2 unterminated");
1294               return 0;
1295             }
1296           slen--;
1297           if (*s1 == *pt)
1298             {
1299               /*
1300                * found a delimiter, set to null
1301                * and return context ptr to next char
1302                */
1303               *s1 = '\0';
1304               *ptr = (s1 + 1);  /* return pointer for next scan */
1305               *s1max = dlen - 1;        /* account for the nulled delimiter */
1306               return (ptoken);
1307             }
1308           else
1309             {
1310               /*
1311                * simply scanning through the delimiter string
1312                */
1313               pt++;
1314             }
1315         }
1316       s1++;
1317       dlen--;
1318     }
1319
1320   *ptr = s1;
1321   *s1max = dlen;
1322   return (ptoken);
1323 }
1324
1325 errno_t strstr_s (char *s1, rsize_t s1max, const char *s2, rsize_t s2max,
1326                   char **substring);
1327
1328 always_inline errno_t
1329 strstr_s_inline (char *s1, rsize_t s1max, const char *s2, rsize_t s2max,
1330                  char **substring)
1331 {
1332   u8 bad;
1333   size_t s1_size, s2_size;
1334
1335   bad =
1336     (s1 == 0) + (s2 == 0) + (substring == 0) + (s1max == 0) + (s2max == 0) +
1337     (s1 && s1max && (s1[clib_strnlen (s1, s1max)] != '\0')) +
1338     (s2 && s2max && (s2[clib_strnlen (s2, s2max)] != '\0'));
1339   if (PREDICT_FALSE (bad != 0))
1340     {
1341       if (s1 == 0)
1342         clib_c11_violation ("s1 NULL");
1343       if (s2 == 0)
1344         clib_c11_violation ("s2 NULL");
1345       if (s1max == 0)
1346         clib_c11_violation ("s1max 0");
1347       if (s2max == 0)
1348         clib_c11_violation ("s2max 0");
1349       if (substring == 0)
1350         clib_c11_violation ("substring NULL");
1351       if (s1 && s1max && (s1[clib_strnlen (s1, s1max)] != '\0'))
1352         clib_c11_violation ("s1 unterminated");
1353       if (s2 && s2max && (s2[clib_strnlen (s2, s2max)] != '\0'))
1354         clib_c11_violation ("s2 unterminated");
1355       return EINVAL;
1356     }
1357
1358   /*
1359    * s2 points to a string with zero length, or s2 equals s1, return s1
1360    */
1361   if (PREDICT_FALSE (*s2 == '\0' || s1 == s2))
1362     {
1363       *substring = s1;
1364       return EOK;
1365     }
1366
1367   /*
1368    * s2_size > s1_size, it won't find match.
1369    */
1370   s1_size = clib_strnlen (s1, s1max);
1371   s2_size = clib_strnlen (s2, s2max);
1372   if (PREDICT_FALSE (s2_size > s1_size))
1373     return ESRCH;
1374
1375   *substring = strstr (s1, s2);
1376   if (*substring == 0)
1377     return ESRCH;
1378
1379   return EOK;
1380 }
1381
1382 #endif /* included_clib_string_h */
1383
1384 /*
1385  * fd.io coding-style-patch-verification: ON
1386  *
1387  * Local Variables:
1388  * eval: (c-set-style "gnu")
1389  * End:
1390  */