ハードウエア乱数の生成速度

Linuxの脆弱性軽減策の無効化の方法

インテル CPU の rdrand/rdseed には CrossTalk(SRBDS:Special Register Buffer Data Sampling)という脆弱性がある。 Linux ではその軽減策をしているため rdrand の実行時間が Windows に比べて最悪の場合約４０倍になる。AMD の CPU は私は所持していないので確認をしていない。
軽減策は CPU の rdrand/rdseed 命令のマイクロプログラムを変更しているため、ユーザープログラムから軽減策を無効にすることはできない。例えば Windows で rdrand を使ったプログラムを作成してよい性能が出ていたとしても、それを Linux + wine で実行すると rdrand の実行時間は軽減策の影響で遅くなる。
rdrand/rdseed を多用して性能がプログラムの性能に大きく関わってくる場合は rdrand/rdseed を疑似乱数に書き換えた方がよい。マルウエアに感染していないことが分かっていて、 rdrand/rdseed を多用したい場合はこの軽減策を無効にする方法がある。無効にするにはカーネルコマンドラインに "srbds=off" を加える。具体的には、例えば

sudo vi /etc/default/grub
sudo gedit /etc/default/grub

等のように /etc/default/grub をテキストエディタで編集して 10行目かその前後に

GRUB_CMDLINE_LINUX_DEFAULT="quiet splash"

とあったら

GRUB_CMDLINE_LINUX_DEFAULT="quiet splash srbds=off"

のように srbds=off を加えて保存終了し、

sudo update-grub

を実行しOSを再起動する。

速度測定プログラム(hrng.c)の概要

hrng.c は以下４種類の乱数の実行時間を測定する。

(1)疑似乱数:線形合同法(LCGs)
(2)疑似乱数:Tiny Mersenne Twister (TinyMT)32bit
(3)ハードウエア乱数:rdrand
(4)ハードウエア乱数:rdseed

LCGs は高速だが周期が2³²と短く、偶数と奇数が交互に現れる等低品質である。
TinyMTは周期が2¹²⁷-1もあり良く検定されている。
rdrand は rdseed よりもシングルスレッドで３倍くらい高速である。 rdrand は物理乱数と疑似乱数を組み合わせている。最大で 1022 個かそれ以下の疑似乱数を発生させると種が物理乱数で更新される。さらにスレッド数に比例してスループットが高くなる。 rdrand 命令が失敗することは殆どない。
rdseed は最も予想が困難な乱数である。シングルスレッドでもマルチスレッドでもスループットは同じである。 rdseed 命令は脆弱性軽減策が有効な時は失敗しないが、脆弱性軽減策が無効な時は失敗することがよくある。失敗した場合、プログラムは成功するまで _mm_pause() を 64 回行いながら rdseed を繰り返す。

hrng.c は疑似乱数なら１億回実行して１回あたり何ナノ秒かかったか表示する。
ハードウエア乱数なら百万回実行して１回あたり何ナノ秒かかったか表示する。
OpenMP が使用可能なコンパイラならば、マルチスレッドでの性能も評価する。
各計測をする前に先頭４つの乱数を表示する。

速度測定プログラム(hrng.c)の対応コンパイラ

対応コンパイラ

Borland C++5.5.1
Visual C++5.0～
gcc/g++

OpenMP 対応コンパイラ

Visual C++2005～
gcc/g++ 4.2～

組込み関数対応コンパイラ

Visual C++2013～
gcc/g++ 9.0～

※組込み関数対応コンパイラより古いコンパイラの場合、機械語で対応している。
※組込み関数対応コンパイラでも -DNO_BUILTIN を指定すると機械語で対応する。

速度測定プログラム(hrng.c)のソースコード

/*
hrng.c Measure the execution time of LCGs, TinyMT, Rdrand and Rdseed. 
programmed by Isaku WADA isaku@pb4.so-net.ne.jp
*/
#if!(defined(_M_IX86)||defined(__i386)||defined(_M_X64)||defined(__x86_64__))
 #error Neither x86 nor x64.
#endif
#if defined(_MSC_VER)
 #pragma warning(disable:4127) /* Conditional Expression is Constant */
 #pragma comment(lib,"winmm.lib")
#endif
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#if defined(_OPENMP)
 #include <omp.h>
#endif

#if defined(_M_IX86) || defined(_M_X64) || defined(__MINGW32__)
 #define WINDOWS_API__
 #include <windows.h>
 #include <mmsystem.h>
#endif
#if !defined(NO_BUILTIN)
 #if defined(_MSC_VER) && _MSC_VER >= 1800 /* VC++2013 */
  #include <emmintrin.h>
  #include <intrin.h>
  #pragma intrinsic(__cpuidex,_mm_pause,_rdrand32_step,_rdseed32_step)
  #define Cpuid__(V,EAX) __cpuidex(V,EAX,0)
  #define X86_BUILTIN__
 #elif defined(__GNUC__) && __GNUC__ >= 9
  #include <emmintrin.h>
  #include <x86intrin.h>
  #include <cpuid.h>
  #define Cpuid__(V,EAX) __cpuid_count(EAX,0,V[0],V[1],V[2],V[3])
  #define X86_BUILTIN__
 #endif
#endif

#define N 1000    /* Outer loop size */
#define H 1000    /* Hardware RNG's inner loop size */
#define P 100000  /* Pseudo RNG's inner loop size */
#if defined(_OPENMP)
 #define MAX_PROC_NUM 256
#else
 #define MAX_PROC_NUM 1
#endif
unsigned Err;  /* Counter of rdrand or rdseed failed */
unsigned Sum;  /* To prevent the optimizer removes calculation */
int StartTime;


#if defined(X86_BUILTIN__)
int HaveRdrand(void) { int v[4]; Cpuid__(v,1); return (v[2]>>30)&1; }
int HaveRdseed(void) { int v[4]; Cpuid__(v,7); return (v[1]>>18)&1; }
 #if defined(__GNUC__)
  #pragma GCC push_options
  #pragma GCC target("rdrnd")
 #endif
static __inline int Rdrand32(unsigned*a) { return _rdrand32_step(a); }
 #if defined(__GNUC__)
  #pragma GCC pop_options
 #endif
 #if defined(__GNUC__)
  #pragma GCC push_options
  #pragma GCC target("rdseed")
 #endif
static __inline int Rdseed32(unsigned*a) { return _rdseed32_step(a); }
 #if defined(__GNUC__)
  #pragma GCC pop_options
 #endif
 #if defined(__GNUC__)
  #pragma GCC push_options
  #pragma GCC target("sse2")
 #endif
static __inline void MmPause1(void) { _mm_pause(); }
void MmPause(unsigned a) {
    unsigned b=a>>4;
    while (b--) {
        _mm_pause(); _mm_pause(); _mm_pause(); _mm_pause();
        _mm_pause(); _mm_pause(); _mm_pause(); _mm_pause();
        _mm_pause(); _mm_pause(); _mm_pause(); _mm_pause();
        _mm_pause(); _mm_pause(); _mm_pause(); _mm_pause();
    }
    b=a&15;
    while (b--) _mm_pause();
}
 #if defined(__GNUC__)
  #pragma GCC pop_options
 #endif
#else
 #if defined(__GNUC__)
  #define ALLOC_TEXT__(X) const char X[]__attribute__((section(".text#")))
 #elif defined(_MSC_VER)
  #pragma code_seg(".text")
  #define ALLOC_TEXT__(X) __declspec(allocate(".text"))const char X[]
 #elif defined(__BORLANDC__)
  #define ALLOC_TEXT__(X) extern const char X[]
 #else
  #define ALLOC_TEXT__(X) const char X[]
 #endif
 #if defined(__i386) && defined(__GNUC__) /* gcc 32 */
  #define FAST__ __attribute__((fastcall))
 #elif defined(__x86_64__) || defined(_M_X64)
  #define FAST__
 #elif defined(__BORLANDC__) /* bcc32 */
  #define FAST__ __msfastcall
 #else /* vc++ 32 */
  #define FAST__ __fastcall
 #endif
ALLOC_TEXT__(CheckRdrand__)=
   "\x53"                 /* push ebx    */
   "\xB8\x01\x00\x00\x00" /* mov eax,1   */
   "\x0F\xA2"             /* cpuid       */
   "\x5B"                 /* pop ebx     */
   "\x89\xC8"             /* mov eax,ecx */
   "\xC1\xE8\x1E"         /* shr eax,30  */
   "\x24\x01"             /* and al,1    */
   "\xC3";                /* ret         */
 #define HaveRdrand() (((int(*)(void))(size_t)CheckRdrand__)())

ALLOC_TEXT__(CheckRdseed__)=
   "\x53"                 /* push ebx    */
   "\xB8\x07\x00\x00\x00" /* mov eax,7   */
   "\x31\xC9"             /* xor ecx,ecx */
   "\x0F\xA2"             /* cpuid       */
   "\x89\xD8"             /* mov eax,ebx */
   "\xC1\xE8\x12"         /* shr eax,18  */
   "\x83\xe0\x01"         /* and eax,1   */
   "\x5B"                 /* pop ebx     */
   "\xC3";                /* ret         */
 #define HaveRdseed() (((int(*)(void))(size_t)CheckRdseed__)())
ALLOC_TEXT__(Rdrand32__)=
   "\x31\xC0"     /* xor eax,eax            */
   "\x0F\xC7\xF2" /* rdrand edx             */
   "\x73\x02"     /* jnc +2                 */
   "\xB0\x01"     /* mov al,1               */
 #if defined(__x86_64__) && defined(__unix__)
   "\x89\x17"     /* mov dword ptr[rdi],edx */
 #else
   "\x89\x11"     /* mov dword ptr[rcx],edx */
 #endif
   "\xC3";        /* ret                    */
 #define Rdrand32(A) (((int(FAST__*)(unsigned*))(size_t)Rdrand32__)(A))
ALLOC_TEXT__(Rdseed32__)=
   "\x31\xC0"     /* xor eax,eax            */
   "\x0F\xC7\xFA" /* rdseed edx             */
   "\x73\x02"     /* jnc +2                 */
   "\xB0\x01"     /* mov al,1               */
 #if defined(__x86_64__) && defined(__unix__)
   "\x89\x17"     /* mov dword ptr[rdi],edx */
 #else
   "\x89\x11"     /* mov dword ptr[rcx],edx */
 #endif
   "\xC3";        /* ret                    */
 #define Rdseed32(A) (((int(FAST__*)(unsigned*))(size_t)Rdseed32__)(A))
ALLOC_TEXT__(MmPause1__)=
   "\xF3\x90" /* pause */
   "\xc3";    /* ret   */
 #define MmPause1() (((void(*)(void))(size_t)MmPause1__)())
 #define MMPAUSEx4__ "\xF3\x90\xF3\x90\xF3\x90\xF3\x90"
 #define MMPAUSEx16__ MMPAUSEx4__ MMPAUSEx4__ MMPAUSEx4__ MMPAUSEx4__
 #if defined(__x86_64__) && defined(__unix__)
ALLOC_TEXT__(MmPause__)=
    "\x89\xf8"     /* mov eax,edi */
    "\xc1\xe8\x04" /* shr eax,4   */
    "\xeb\x23"     /* jmp +35     */
     MMPAUSEx16__  /* pause * 16  */
    "\x83\xe8\x01" /* sub eax,1   */
    "\x75\xdb"     /* jnz -37     */
    "\x83\xe7\x0f" /* and edi,15  */
    "\xeb\x05"     /* jmp +5      */
    "\xf3\x90"     /* pause       */
    "\x83\xef\x01" /* sub edi,1   */
    "\x75\xf9"     /* jnz -7      */
    "\xc3";        /* ret         */
 #else
ALLOC_TEXT__(MmPause__)=
    "\x89\xc8"     /* mov eax,ecx */
    "\xc1\xe8\x04" /* shr eax,4   */
    "\xeb\x23"     /* jmp +35     */
     MMPAUSEx16__  /* pause * 16  */
    "\x83\xe8\x01" /* sub eax,1   */
    "\x75\xdb"     /* jnz -37     */
    "\x83\xe1\x0f" /* and ecx,15  */
    "\xeb\x05"     /* jmp +5      */
    "\xf3\x90"     /* pause       */
    "\x83\xe9\x01" /* sub ecx,1   */
    "\x75\xf9"     /* jnz -7      */
    "\xc3";        /* ret         */
 #endif
 #define MmPause(A) (((void(FAST__*)(unsigned))(size_t)MmPause__)(A))
#endif

unsigned StatusLCGs[MAX_PROC_NUM];
unsigned NextLCGs(unsigned*p) { return*p=1103515245**p+12345; }
void InitializeLCGs(unsigned s) { StatusLCGs[s]=(s*2+1)*12345; }

#define RND_MAT1__ 0x8f7011eeU
#define RND_MAT2__ 0xfc78ff1fU
#define RND_TMAT__ 0x3793fdff
#define RND_MIN_LOOP__ 8
#define RND_PRE_LOOP__ 8
#define RND_SH0__ 1
#define RND_SH1__ 10
#define RND_SH8__ 8
#define RND_MSK__ 0x7fffffffU

typedef struct { unsigned o[4]; } Rand_t;
Rand_t StatusTinyMT[MAX_PROC_NUM];

unsigned NextTinyMT(Rand_t*p) {
    unsigned x,y;
    x=(p->o[0]&RND_MSK__)^p->o[1]^p->o[2]; y=p->o[3]; x^=x<<RND_SH0__;
    y^=(y>>RND_SH0__)^x;
    p->o[0]=p->o[1]; p->o[1]=p->o[2]; x^=y<<RND_SH1__;
    p->o[2]=x; p->o[3]=y; y=(unsigned)(-((int)(y&1)));
    p->o[1]^=y&RND_MAT1__; p->o[2]^=y&RND_MAT2__;
    x=p->o[0]+(p->o[2]>>RND_SH8__);
    x=p->o[3]^x^(-((int)(x&1))&RND_TMAT__);
    return x;
}

void InitializeTinyMT(unsigned s) {
    int i; Rand_t*p=StatusTinyMT+s;
    p->o[0]=s;          p->o[1]=RND_MAT1__;
    p->o[2]=RND_MAT2__; p->o[3]=RND_TMAT__;
    for (i=1;i<RND_MIN_LOOP__;i++) {
        s=p->o[i&3]^((unsigned)i+1812433253U*(s^(s>>30)));
        p->o[i&3]=s;
    }
    if ((p->o[0]&RND_MSK__)==0&&p->o[1]==0&&p->o[2]==0&&p->o[3]==0)
    { p->o[0]='T'; p->o[1]='I'; p->o[2]='N'; p->o[3]='Y'; }
    for (i=0;i<RND_PRE_LOOP__;i++) NextTinyMT(p);
}

unsigned NextRdrand32(void) {
    unsigned ret=0; int i; static int err_cnt;
    for (i=0;i<256;i++) {
        if (Rdrand32(&ret)) break;
        MmPause1();
        #if defined(_OPENMP)
         #pragma omp atomic
        #endif
        Err++;
    }
    if (i>=256&&++err_cnt<=5) printf("\nWarning NextRdrand32() failed.\n");
    return ret;
 }

unsigned NextRdseed32(void) {
    unsigned ret=0; int i; static int err_cnt;
    for (i=0;i<256;i++) {
        if (Rdseed32(&ret)) break;
        MmPause(64);
        #if defined(_OPENMP)
         #pragma omp atomic
        #endif
        Err++;
    }
    if (i>=256&&++err_cnt<=5) printf("\nWarning NextRdseed32() failed.\n");
    return ret;
}

#if defined(__unix__)
int Tick(void) { 
    static time_t base; struct timespec t;
    clock_gettime(CLOCK_REALTIME,&t);
    if (base==0) base=t.tv_sec;
    return(int)((t.tv_sec-base)*1000+t.tv_nsec/1000000);
}
 #define TICK_PER_SEC 1000.0
#elif defined(WINDOWS_API__)
 #define Tick() ((int)timeGetTime())
 #define TICK_PER_SEC 1000.0
#else
 #define Tick() ((int)clock())
 #define TICK_PER_SEC ((double)CLOCKS_PER_SEC)
#endif

#define Sample(MSG,FUNC) do { printf(MSG); \
for (i=0;i<4;i++) printf(" %08x",FUNC); \
Err=0; StartTime=Tick(); } while (0)

void PrintOut(int m) {
    printf(" %7.2f nsec Err=%7.3f%%\n",\
       ((Tick()-StartTime)/TICK_PER_SEC/N/m)*1.e9,100.0*Err/N/m);
}

#define IA32_MISC_ENABLE 0x1a0
#define RDRAND_BIT 0x400000

int main(void) {
    int i;
#if defined(_OPENMP)
    int n=omp_get_num_procs();
#endif
#if defined(WINDOWS_API__)
    timeBeginPeriod(1);
#endif
    for (i=0;i<(int)(sizeof StatusLCGs/sizeof*StatusLCGs);i++)
        InitializeLCGs(i);
    for (i=0;i<(int)(sizeof StatusTinyMT/sizeof*StatusTinyMT);i++)
        InitializeTinyMT(i);
    Sample("LCGs   sth",NextLCGs(StatusLCGs));
    for (i=0;i<N;i++) {
        int j; unsigned sum=0;
        for (j=0;j<P;j++) sum+=NextLCGs(StatusLCGs);
        Sum+=sum;
    }
    PrintOut(P);
#if defined(_OPENMP)
    if (n>=2) {
        Sample("LCGs   omp",NextLCGs(StatusLCGs+i));
        #pragma omp parallel for
        for (i=0;i<N;i++) {
            int j; unsigned*p=StatusLCGs+omp_get_thread_num(),sum=0;
            for (j=0;j<P;j++) sum+=NextLCGs(p);
            #pragma omp atomic
            Sum+=sum;
        }
        PrintOut(P);
    }
#endif
    Sample("TinyMT sth",NextTinyMT(StatusTinyMT));
    for (i=0;i<N;i++) {
        int j; unsigned sum=0;
        for (j=0;j<P;j++) sum+=NextTinyMT(StatusTinyMT);
        Sum+=sum;
    }
    PrintOut(P);
#if defined(_OPENMP)
    if (n>=2) {
        Sample("TinyMT omp",NextTinyMT(StatusTinyMT+i));
        #pragma omp parallel for
        for (i=0;i<N;i++) {
            int j; unsigned sum=0;
            Rand_t*p=StatusTinyMT+omp_get_thread_num();
            for (j=0;j<P;j++) sum+=NextTinyMT(p);
            #pragma omp atomic
            Sum+=sum;
        }
        PrintOut(P);
}
#endif
    if (HaveRdrand()) {
        Sample("Rdrand sth",NextRdrand32());
        for (i=0;i<N;i++) {
            int j; unsigned sum=0;
            for (j=0;j<H;j++) sum+=NextRdrand32();
            Sum+=sum;
        }
        PrintOut(H);
#if defined(_OPENMP)
        if (n>=2) {
            Sample("Rdrand omp",NextRdrand32());
            #pragma omp parallel for
            for (i=0;i<N;i++) {
                int j; unsigned sum=0;
                for (j=0;j<H;j++) sum+=NextRdrand32();
                #pragma omp atomic
                Sum+=sum;
            }
            PrintOut(H);
        }
#endif
    } else printf("No rdrand.\n");
    if (HaveRdseed()) {
        Sample("Rdseed sth",NextRdseed32());
        for (i=0;i<N;i++) {
            int j; unsigned sum=0;
            for (j=0;j<H;j++) sum+=NextRdseed32();
            Sum+=sum;
        }
        PrintOut(H);
#if defined(_OPENMP)
        if (n>=2) {
            Sample("Rdseed omp",NextRdseed32());
            #pragma omp parallel for
            for (i=0;i<N;i++) {
                int j; unsigned sum=0;
                for (j=0;j<H;j++) sum+=NextRdseed32();
                #pragma omp atomic
                Sum+=sum;
            }
            PrintOut(H);
        }
#endif
    } else printf("No rdseed.\n");
#if defined(_OPENMP)
    printf("omp_get_num_procs()=%d ",n);
#endif
    printf("Sum=%u\n",Sum);
#if defined(WINDOWS_API__)
    timeEndPeriod(1);
#endif
    return 0;
}

速度測定プログラム(hrng.c)の結果

Core i5-10210U 1.60GHz 2.10GHz
Ubuntu 22.04 srbds
gcc -O4 -Wall -fopenmp hrng.c

LCGs   sth d3dc167e a70427df d6651c2c 0daa96f5    1.16 nsec Err=  0.000%
LCGs   omp df63578a 7b93e308 234baf92 cb037c1c    0.14 nsec Err=  0.000%
TinyMT sth 603155f1 82215390 1fcd0635 ba561fd8    3.36 nsec Err=  0.000%
TinyMT omp 48a3f287 2529e569 cb029379 e5f1528f    0.70 nsec Err=  0.000%
Rdrand sth 18de5634 ece3b620 1821a6d7 60a29b86 1164.00 nsec Err=  0.000%
Rdrand omp d1adaae2 c549c26a 9f426a11 83569030  975.00 nsec Err=  0.000%
Rdseed sth 9f933414 53bcf062 0d6f8239 efeb25a6 1164.00 nsec Err=  0.000%
Rdseed omp c62bb95f ae3eaa17 4aa4cacd edda1b21  977.00 nsec Err=  0.000%
omp_get_num_procs()=8 Sum=292897177

Core i5-10210U 1.60GHz 2.10GHz
Ubuntu 22.04 srbds=off
gcc -O4 -Wall -fopenmp hrng.c

LCGs   sth d3dc167e a70427df d6651c2c 0daa96f5    1.18 nsec Err=  0.000%
LCGs   omp df63578a 7b93e308 234baf92 cb037c1c    0.15 nsec Err=  0.000%
TinyMT sth 603155f1 82215390 1fcd0635 ba561fd8    3.35 nsec Err=  0.000%
TinyMT omp 48a3f287 2529e569 cb029379 e5f1528f    0.70 nsec Err=  0.000%
Rdrand sth 0ed8711b f225abf5 2cac5d3d 77f0a8ca  123.00 nsec Err=  0.000%
Rdrand omp c0b3782f 587f935f 383a6029 a7128e7f   25.00 nsec Err=  0.000%
Rdseed sth b0e5b581 b93251e5 e54eacea 2ec0cfec  439.00 nsec Err= 12.617%
Rdseed omp 6d05954c 85ed0543 534ff21f f3b94ff7  473.00 nsec Err=132.655%
omp_get_num_procs()=8 Sum=2808607595

Core i5-10210U 1.60GHz 2.10GHz
Windows 10 Pro 22H2
VisualC++2022 /O2 /openmp

LCGs   sth d3dc167e a70427df d6651c2c 0daa96f5    0.93 nsec Err=  0.000%
LCGs   omp df63578a 7b93e308 234baf92 cb037c1c    0.21 nsec Err=  0.000%
TinyMT sth 603155f1 82215390 1fcd0635 ba561fd8    4.10 nsec Err=  0.000%
TinyMT omp 48a3f287 2529e569 cb029379 e5f1528f    3.59 nsec Err=  0.000%
Rdrand sth c643584c 423eff55 dbbdf8fb 955fbe70  144.00 nsec Err=  0.000%
Rdrand omp 12333332 6d014e07 7ff1c597 e21c4110   34.00 nsec Err=  0.000%
Rdseed sth 3ecdd9c2 6d65831f 4a9e3a78 b9a5133b  487.00 nsec Err= 12.540%
Rdseed omp de87ce97 cd0a9f8a d21ef7c4 af07d720  573.00 nsec Err=113.907%
omp_get_num_procs()=8 Sum=450198964

Core i5-10500T 2.30GHz
Windows 11 Pro 22H2
VisualC++2022 /O2 /openmp