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

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