libstdc++-v3/src/c++11/random.cc

   1 // random -*- C++ -*-
   2
   3 // Copyright (C) 2012-2024 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 #define _GLIBCXX_USE_CXX11_ABI 1
  26 #define _CRT_RAND_S // define this before including <stdlib.h> to get rand_s
  27
  28 #include <random>
  29 #include <system_error>
  30
  31 #if defined __i386__ || defined __x86_64__
  32 # include <cpuid.h>
  33 # ifdef _GLIBCXX_X86_RDRAND
  34 #  define USE_RDRAND 1
  35 # endif
  36 # ifdef _GLIBCXX_X86_RDSEED
  37 #  define USE_RDSEED 1
  38 # endif
  39 #elif defined __powerpc64__ && defined __BUILTIN_CPU_SUPPORTS__
  40 # define USE_DARN 1
  41 #endif
  42
  43 #include <cerrno>
  44 #include <cstdio>
  45 #include <cctype> // For std::isdigit.
  46
  47 #if defined _GLIBCXX_HAVE_UNISTD_H && defined _GLIBCXX_HAVE_FCNTL_H
  48 # include <unistd.h>
  49 # include <fcntl.h>
  50 // Use POSIX open, close, read etc. instead of ISO fopen, fclose, fread
  51 # define USE_POSIX_FILE_IO
  52 #endif
  53
  54 #ifdef _GLIBCXX_HAVE_SYS_IOCTL_H
  55 # include <sys/ioctl.h>
  56 #endif
  57
  58 #ifdef _GLIBCXX_HAVE_LINUX_TYPES_H
  59 # include <linux/types.h>
  60 #endif
  61
  62 #ifdef _GLIBCXX_HAVE_LINUX_RANDOM_H
  63 # include <linux/random.h>
  64 #endif
  65
  66 #ifdef _GLIBCXX_USE_CRT_RAND_S
  67 # include <stdlib.h>
  68 #endif
  69
  70 #ifdef _GLIBCXX_HAVE_GETENTROPY
  71 # include <unistd.h>
  72 #endif
  73
  74 #if defined _GLIBCXX_USE_CRT_RAND_S || defined _GLIBCXX_USE_DEV_RANDOM \
  75   || _GLIBCXX_HAVE_GETENTROPY
  76 // The OS provides a source of randomness we can use.
  77 # pragma GCC poison _M_mt
  78 #elif defined USE_RDRAND || defined USE_RDSEED || defined USE_DARN
  79 // Hardware instructions might be available, but use cpuid checks at runtime.
  80 # pragma GCC poison _M_mt
  81 // If the runtime cpuid checks fail we'll use a linear congruential engine.
  82 # define USE_LCG 1
  83 #else
  84 // Use the mt19937 member of the union, as in previous GCC releases.
  85 # define USE_MT19937 1
  86 #endif
  87
  88 #ifdef USE_LCG
  89 # include <chrono>
  90 #endif
  91
  92 namespace std _GLIBCXX_VISIBILITY(default)
  93 {
  94   namespace
  95   {
  96     [[noreturn]]
  97     inline void
  98     __throw_syserr([[maybe_unused]] int e, [[maybe_unused]] const char* msg)
  99     { _GLIBCXX_THROW_OR_ABORT(system_error(e, std::generic_category(), msg)); }
 100
 101 #if USE_RDRAND
 102     unsigned int
 103     __attribute__ ((target("rdrnd")))
 104     __x86_rdrand(void*)
 105     {
 106       unsigned int retries = 100;
 107       unsigned int val;
 108
 109       while (__builtin_ia32_rdrand32_step(&val) == 0) [[__unlikely__]]
 110         if (--retries == 0)
 111           std::__throw_runtime_error(__N("random_device: rdrand failed"));
 112
 113       return val;
 114     }
 115 #endif
 116
 117 #if USE_RDSEED
 118     unsigned int
 119     __attribute__ ((target("rdseed")))
 120     __x86_rdseed(void* fallback)
 121     {
 122       unsigned int retries = 100;
 123       unsigned int val;
 124
 125       while (__builtin_ia32_rdseed_si_step(&val) == 0) [[__unlikely__]]
 126         {
 127           if (--retries == 0)
 128             {
 129               if (auto f = reinterpret_cast<unsigned int(*)(void*)>(fallback))
 130                 return f(nullptr);
 131               std::__throw_runtime_error(__N("random_device: rdseed failed"));
 132             }
 133           __builtin_ia32_pause();
 134         }
 135
 136       return val;
 137     }
 138
 139 #if USE_RDRAND
 140     unsigned int
 141     __attribute__ ((target("rdseed,rdrnd")))
 142     __x86_rdseed_rdrand(void*)
 143     {
 144       return __x86_rdseed(reinterpret_cast<void*>(&__x86_rdrand));
 145     }
 146 #endif
 147 #endif
 148
 149 #ifdef USE_DARN
 150     unsigned int
 151     __attribute__((target("cpu=power9")))
 152     __ppc_darn(void*)
 153     {
 154       const uint64_t failed = -1;
 155       unsigned int retries = 10;
 156       uint64_t val = __builtin_darn();
 157       while (val == failed) [[__unlikely__]]
 158         {
 159           if (--retries == 0)
 160             std::__throw_runtime_error(__N("random_device: darn failed"));
 161           val = __builtin_darn();
 162         }
 163       return (uint32_t)val;
 164     }
 165 #endif
 166
 167 #ifdef _GLIBCXX_USE_CRT_RAND_S
 168     unsigned int
 169     __winxp_rand_s(void*)
 170     {
 171       unsigned int val;
 172       if (::rand_s(&val) != 0)
 173         std::__throw_runtime_error(__N("random_device: rand_s failed"));
 174       return val;
 175     }
 176 #endif
 177
 178 #ifdef _GLIBCXX_HAVE_GETENTROPY
 179     unsigned int
 180     __libc_getentropy(void*)
 181     {
 182       unsigned int val;
 183       if (::getentropy(&val, sizeof(val)) != 0)
 184         std::__throw_runtime_error(__N("random_device: getentropy failed"));
 185       return val;
 186     }
 187 #endif
 188
 189 #ifdef _GLIBCXX_HAVE_ARC4RANDOM
 190     unsigned int
 191     __libc_arc4random(void*)
 192     {
 193       return ::arc4random();
 194     }
 195 #endif
 196
 197 #ifdef USE_LCG
 198     // TODO: use this to seed std::mt19937 engine too.
 199     unsigned
 200     bad_seed(void* p) noexcept
 201     {
 202       // Poor quality seed based on hash of the current time and the address
 203       // of the object being seeded. Better than using the same default seed
 204       // for every object though.
 205       const uint64_t bits[] = {
 206         (uint64_t) chrono::system_clock::now().time_since_epoch().count(),
 207         (uint64_t) reinterpret_cast<uintptr_t>(p)
 208       };
 209       auto bytes = reinterpret_cast<const unsigned char*>(bits);
 210       // 32-bit FNV-1a hash
 211       uint32_t h = 2166136261u;
 212       for (unsigned i = 0; i < sizeof(bits); ++i)
 213         {
 214           h ^= *bytes++;
 215           h *= 16777619u;
 216         }
 217       return h;
 218     }
 219
 220     // Same as std::minstd_rand0 but using unsigned not uint_fast32_t.
 221     using lcg_type
 222       = linear_congruential_engine<unsigned, 16807UL, 0UL, 2147483647UL>;
 223
 224     inline lcg_type*
 225     construct_lcg_at(void* addr) noexcept
 226     {
 227       return ::new(addr) lcg_type(bad_seed(addr));
 228     }
 229
 230     inline void
 231     destroy_lcg_at(void* addr) noexcept
 232     {
 233       static_cast<lcg_type*>(addr)->~lcg_type();
 234     }
 235
 236     unsigned int
 237     __lcg(void* ptr) noexcept
 238     {
 239       auto& lcg = *static_cast<lcg_type*>(ptr);
 240       return lcg();
 241     }
 242 #endif
 243
 244     enum Which : unsigned {
 245       device_file = 1, prng = 2, rand_s = 4, getentropy = 8, arc4random = 16,
 246       rdseed = 64, rdrand = 128, darn = 256,
 247       any = 0xffff
 248     };
 249
 250     constexpr Which
 251     operator|(Which l, Which r) noexcept
 252     { return Which(unsigned(l) | unsigned(r)); }
 253
 254     inline Which
 255     which_source(random_device::result_type (*func [[maybe_unused]])(void*),
 256                  void* file [[maybe_unused]])
 257     {
 258 #ifdef _GLIBCXX_USE_CRT_RAND_S
 259       if (func == &__winxp_rand_s)
 260         return rand_s;
 261 #endif
 262
 263 #ifdef USE_RDSEED
 264 #ifdef USE_RDRAND
 265       if (func == &__x86_rdseed_rdrand)
 266         return rdseed;
 267 #endif
 268       if (func == &__x86_rdseed)
 269         return rdseed;
 270 #endif
 271
 272 #ifdef USE_RDRAND
 273       if (func == &__x86_rdrand)
 274         return rdrand;
 275 #endif
 276
 277 #ifdef USE_DARN
 278       if (func == &__ppc_darn)
 279         return darn;
 280 #endif
 281
 282 #ifdef _GLIBCXX_USE_DEV_RANDOM
 283       if (file != nullptr)
 284         return device_file;
 285 #endif
 286
 287 #ifdef _GLIBCXX_HAVE_ARC4RANDOM
 288       if (func == __libc_arc4random)
 289         return arc4random;
 290 #endif
 291
 292 #ifdef _GLIBCXX_HAVE_GETENTROPY
 293       if (func == __libc_getentropy)
 294         return getentropy;
 295 #endif
 296
 297 #ifdef USE_LCG
 298       if (func == &__lcg)
 299         return prng;
 300 #endif
 301
 302 #ifdef USE_MT19937
 303       return prng;
 304 #endif
 305
 306       return any; // should be unreachable
 307     }
 308   }
 309
 310   void
 311   random_device::_M_init(const std::string& token)
 312   {
 313 #ifdef USE_MT19937
 314     // If no real random device is supported then use the mt19937 engine.
 315     _M_init_pretr1(token);
 316     return;
 317 #else
 318
 319     _M_file = nullptr;
 320     _M_func = nullptr;
 321     _M_fd = -1;
 322
 323     const char* fname [[gnu::unused]] = nullptr;
 324
 325     Which which;
 326
 327     if (token == "default")
 328       {
 329         which = any;
 330         fname = "/dev/urandom";
 331       }
 332 #ifdef USE_RDSEED
 333     else if (token == "rdseed")
 334       which = rdseed;
 335 #endif // USE_RDSEED
 336 #ifdef USE_RDRAND
 337     else if (token == "rdrand" || token == "rdrnd")
 338       which = rdrand;
 339 #endif // USE_RDRAND
 340 #ifdef USE_DARN
 341     else if (token == "darn")
 342       which = darn;
 343 #endif
 344 #if defined USE_RDRAND || defined USE_RDSEED || defined USE_DARN
 345     else if (token == "hw" || token == "hardware")
 346       which = rdrand | rdseed | darn;
 347 #endif
 348 #ifdef _GLIBCXX_USE_CRT_RAND_S
 349     else if (token == "rand_s")
 350       which = rand_s;
 351 #endif // _GLIBCXX_USE_CRT_RAND_S
 352 #ifdef _GLIBCXX_HAVE_GETENTROPY
 353     else if (token == "getentropy")
 354       which = getentropy;
 355 #endif // _GLIBCXX_HAVE_GETENTROPY
 356 #ifdef _GLIBCXX_HAVE_ARC4RANDOM
 357     else if (token == "arc4random")
 358       which = arc4random;
 359 #endif // _GLIBCXX_HAVE_ARC4RANDOM
 360 #ifdef _GLIBCXX_USE_DEV_RANDOM
 361     else if (token == "/dev/urandom" || token == "/dev/random")
 362       {
 363         fname = token.c_str();
 364         which = device_file;
 365       }
 366 #endif // _GLIBCXX_USE_DEV_RANDOM
 367 #ifdef USE_LCG
 368     else if (token == "prng")
 369       which = prng;
 370 #endif
 371     else
 372       std::__throw_syserr(EINVAL, __N("random_device::random_device"
 373                                       "(const std::string&):"
 374                                       " unsupported token"));
 375
 376 #if defined ENOSYS
 377     [[maybe_unused]] const int unsupported = ENOSYS;
 378 #elif defined ENOTSUP
 379     [[maybe_unused]] const int unsupported = ENOTSUP;
 380 #else
 381     [[maybe_unused]] const int unsupported = 0;
 382 #endif
 383     int err = 0;
 384
 385 #ifdef _GLIBCXX_USE_CRT_RAND_S
 386     if (which & rand_s)
 387     {
 388       _M_func = &__winxp_rand_s;
 389       return;
 390     }
 391 #endif // _GLIBCXX_USE_CRT_RAND_S
 392
 393 #ifdef USE_RDSEED
 394     if (which & rdseed)
 395     {
 396       unsigned int eax, ebx, ecx, edx;
 397       // Check availability of cpuid and, for now at least, also the
 398       // CPU signature for Intel and AMD.
 399       if (__get_cpuid_max(0, &ebx) > 0
 400           && (ebx == signature_INTEL_ebx || ebx == signature_AMD_ebx))
 401         {
 402           // CPUID.(EAX=07H, ECX=0H):EBX.RDSEED[bit 18]
 403           __cpuid_count(7, 0, eax, ebx, ecx, edx);
 404           if (ebx & bit_RDSEED)
 405             {
 406 #ifdef USE_RDRAND
 407               // CPUID.01H:ECX.RDRAND[bit 30]
 408               __cpuid(1, eax, ebx, ecx, edx);
 409               if (ecx & bit_RDRND)
 410                 {
 411                   _M_func = &__x86_rdseed_rdrand;
 412                   return;
 413                 }
 414 #endif
 415               _M_func = &__x86_rdseed;
 416               return;
 417             }
 418         }
 419       err = unsupported;
 420     }
 421 #endif // USE_RDSEED
 422
 423 #ifdef USE_RDRAND
 424     if (which & rdrand)
 425     {
 426       unsigned int eax, ebx, ecx, edx;
 427       // Check availability of cpuid and, for now at least, also the
 428       // CPU signature for Intel and AMD.
 429       if (__get_cpuid_max(0, &ebx) > 0
 430           && (ebx == signature_INTEL_ebx || ebx == signature_AMD_ebx))
 431         {
 432           // CPUID.01H:ECX.RDRAND[bit 30]
 433           __cpuid(1, eax, ebx, ecx, edx);
 434           if (ecx & bit_RDRND)
 435             {
 436               _M_func = &__x86_rdrand;
 437               return;
 438             }
 439         }
 440       err = unsupported;
 441     }
 442 #endif // USE_RDRAND
 443
 444 #ifdef USE_DARN
 445     if (which & darn)
 446       {
 447         if (__builtin_cpu_supports("darn"))
 448           {
 449             _M_func = &__ppc_darn;
 450             return;
 451           }
 452         err = unsupported;
 453       }
 454 #endif // USE_DARN
 455
 456 #ifdef _GLIBCXX_HAVE_ARC4RANDOM
 457     if (which & arc4random)
 458       {
 459         _M_func = &__libc_arc4random;
 460         return;
 461       }
 462 #endif // _GLIBCXX_HAVE_ARC4RANDOM
 463
 464 #ifdef _GLIBCXX_HAVE_GETENTROPY
 465     if (which & getentropy)
 466       {
 467         unsigned int i;
 468         if (::getentropy(&i, sizeof(i)) == 0) // On linux the syscall can fail.
 469           {
 470             _M_func = &__libc_getentropy;
 471             return;
 472           }
 473         err = unsupported;
 474       }
 475 #endif // _GLIBCXX_HAVE_GETENTROPY
 476
 477 #ifdef _GLIBCXX_USE_DEV_RANDOM
 478     if (which & device_file)
 479     {
 480 #ifdef USE_POSIX_FILE_IO
 481       _M_fd = ::open(fname, O_RDONLY);
 482       if (_M_fd != -1)
 483         {
 484           // Set _M_file to non-null so that _M_fini() will do clean up.
 485           _M_file = &_M_fd;
 486           return;
 487         }
 488 #else // USE_POSIX_FILE_IO
 489       _M_file = static_cast<void*>(std::fopen(fname, "rb"));
 490       if (_M_file)
 491         return;
 492 #endif // USE_POSIX_FILE_IO
 493       err = errno;
 494     }
 495 #endif // _GLIBCXX_USE_DEV_RANDOM
 496
 497 #ifdef USE_LCG
 498     // Either "prng" was requested explicitly, or "default" was requested
 499     // but nothing above worked, use a PRNG.
 500     if (which & prng)
 501     {
 502       static_assert(sizeof(lcg_type) <= sizeof(_M_fd), "");
 503       static_assert(alignof(lcg_type) <= alignof(_M_fd), "");
 504       _M_file = construct_lcg_at(&_M_fd);
 505       _M_func = &__lcg;
 506       return;
 507     }
 508 #endif
 509
 510     auto msg = __N("random_device::random_device(const std::string&):"
 511                    " device not available");
 512     if (err)
 513       std::__throw_syserr(err, msg);
 514     else
 515       std::__throw_runtime_error(msg);
 516 #endif // USE_MT19937
 517   }
 518
 519   // This function is called by _M_init for targets that use mt19937 for
 520   // randomness, and by code compiled against old releases of libstdc++.
 521   void
 522   random_device::_M_init_pretr1(const std::string& token)
 523   {
 524 #ifdef USE_MT19937
 525     unsigned long seed = 5489UL;
 526     if (token != "default" && token != "mt19937" && token != "prng")
 527       {
 528         const char* nptr = token.c_str();
 529         char* endptr;
 530         seed = std::strtoul(nptr, &endptr, 0);
 531         if (*nptr == '\0' || *endptr != '\0')
 532           std::__throw_syserr(EINVAL, __N("random_device::_M_init_pretr1"
 533                                           "(const std::string&)"));
 534       }
 535     _M_mt.seed(seed);
 536 #else
 537     // Convert old default token "mt19937" or numeric seed tokens to "default".
 538     if (token == "mt19937" || std::isdigit((unsigned char)token[0]))
 539       _M_init("default");
 540     else
 541       _M_init(token);
 542 #endif
 543   }
 544
 545   // Called by old ABI version of random_device::_M_init(const std::string&).
 546   void
 547   random_device::_M_init(const char* s, size_t len)
 548   {
 549     const std::string token(s, len);
 550 #ifdef USE_MT19937
 551     _M_init_pretr1(token);
 552 #else
 553     _M_init(token);
 554 #endif
 555   }
 556
 557   void
 558   random_device::_M_fini()
 559   {
 560     // _M_file == nullptr means no resources to free.
 561     if (!_M_file)
 562       return;
 563
 564 #if USE_LCG
 565     if (_M_func == &__lcg)
 566       {
 567         destroy_lcg_at(_M_file);
 568         return;
 569       }
 570 #endif
 571
 572 #ifdef _GLIBCXX_USE_DEV_RANDOM
 573 #ifdef USE_POSIX_FILE_IO
 574     ::close(_M_fd);
 575     _M_fd = -1;
 576 #else
 577     std::fclose(static_cast<FILE*>(_M_file));
 578 #endif
 579     _M_file = nullptr;
 580 #endif
 581   }
 582
 583   random_device::result_type
 584   random_device::_M_getval()
 585   {
 586 #ifdef USE_MT19937
 587     return _M_mt();
 588 #else
 589
 590     if (_M_func)
 591       return _M_func(_M_file);
 592
 593     result_type ret;
 594     void* p = &ret;
 595     size_t n = sizeof(result_type);
 596 #ifdef USE_POSIX_FILE_IO
 597     do
 598       {
 599         const int e = ::read(_M_fd, p, n);
 600         if (e > 0)
 601           {
 602             n -= e;
 603             p = static_cast<char*>(p) + e;
 604           }
 605         else if (e != -1 || errno != EINTR)
 606           __throw_syserr(errno, __N("random_device could not be read"));
 607       }
 608     while (n > 0);
 609 #else // USE_POSIX_FILE_IO
 610     const size_t e = std::fread(p, n, 1, static_cast<FILE*>(_M_file));
 611     if (e != 1)
 612       __throw_runtime_error(__N("random_device could not be read"));
 613 #endif // USE_POSIX_FILE_IO
 614
 615     return ret;
 616 #endif // USE_MT19937
 617   }
 618
 619   // Only called by code compiled against old releases of libstdc++.
 620   // Forward the call to _M_getval() and let it decide what to do.
 621   random_device::result_type
 622   random_device::_M_getval_pretr1()
 623   { return _M_getval(); }
 624
 625   double
 626   random_device::_M_getentropy() const noexcept
 627   {
 628     const int max = sizeof(result_type) * __CHAR_BIT__;
 629
 630     switch(which_source(_M_func, _M_file))
 631     {
 632     case rdrand:
 633     case rdseed:
 634     case darn:
 635       return (double) max;
 636     case arc4random:
 637     case getentropy:
 638       return (double) max;
 639     case rand_s:
 640     case prng:
 641       return 0.0;
 642     case device_file:
 643       // handled below
 644       break;
 645     default:
 646       return 0.0;
 647     }
 648
 649 #if defined _GLIBCXX_USE_DEV_RANDOM \
 650     && defined _GLIBCXX_HAVE_SYS_IOCTL_H && defined RNDGETENTCNT
 651
 652 #ifdef USE_POSIX_FILE_IO
 653     const int fd = _M_fd;
 654 #else
 655     const int fd = ::fileno(static_cast<FILE*>(_M_file));
 656 #endif
 657     if (fd < 0)
 658       return 0.0;
 659
 660     int ent;
 661     if (::ioctl(fd, RNDGETENTCNT, &ent) < 0)
 662       return 0.0;
 663
 664     if (ent < 0)
 665       return 0.0;
 666
 667     if (ent > max)
 668       ent = max;
 669
 670     return static_cast<double>(ent);
 671 #else
 672     return 0.0;
 673 #endif // _GLIBCXX_USE_DEV_RANDOM && _GLIBCXX_HAVE_SYS_IOCTL_H && RNDGETENTCNT
 674   }
 675
 676 #ifdef USE_MT19937
 677   template class mersenne_twister_engine<
 678     uint_fast32_t,
 679     32, 624, 397, 31,
 680     0x9908b0dfUL, 11,
 681     0xffffffffUL, 7,
 682     0x9d2c5680UL, 15,
 683     0xefc60000UL, 18, 1812433253UL>;
 684 #endif // USE_MT19937
 685
 686 #ifdef USE_LCG
 687   template class
 688     linear_congruential_engine<unsigned, 16807UL, 0UL, 2147483647UL>;
 689   template struct __detail::_Mod<unsigned, 2147483647UL, 16807UL, 0UL>;
 690 #endif
 691 }