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

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