第92章 OpenMP

OpenMP是一种相对简单的、实现多线程并发功能的编程API。

本章将以加密学意义上的非重复随机数nonce为例,演示OpenMP的应用方法。下面这段代码把nonce和不加密的明文进行串联(即添加),以进行非可逆加密,从而增加截获、破解密文的难度。此外,Bitcion协议约定,在某个阶段中通过nonce使消息块的hash包含特定长度的、连续的零。这种机制又叫作“prove of system”(系统验证)(https://en.wikipedia.org/wiki/Proof-of-work_system

),即参与通信的系统通过这种机制证明它已经采取了精密而耗时的计算。

虽然下面这段代码和Bitcoin没有直接关系,但是功能颇为类似。它会向字符串“hello,word!_”添加一个数字,使得“hello,word!_<数字>”的SHA512 hash包含三个或三个以上的0字节。

假设穷举的区间为[0,INT32最大数−1](即0~0x7FFFFFFE/2147483646)。

整个算法并不复杂:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include "sha512.h"

int found=0;
int32_t checked=0;

int32_t* __min;
int32_t* __max;

time_t start;

#ifdef __GNUC__
#define min(X,Y) ((X) < (Y) ? (X) : (Y))
#define max(X,Y) ((X) > (Y) ? (X) : (Y))
#endif

void check_nonce (int32_t nonce)
{
          uint8_t buf[32];
          struct sha512_ctx ctx;
          uint8_t res[64];

          // update statistics
          int t=omp_get_thread_num();

          if (__min[t]==-1)
                    __min[t]=nonce;
          if (__max[t]==-1)
                    __max[t]=nonce;

          __min[t]=min(__min[t], nonce);
          __max[t]=max(__max[t], nonce);

          // idle if valid nonce found
          if (found)
                    return;

          memset (buf, 0, sizeof(buf));
          sprintf (buf, "hello, world!_%d", nonce);

          sha512_init_ctx (&ctx);
          sha512_process_bytes (buf, strlen(buf), &ctx);
          sha512_finish_ctx (&ctx, &res);
          if (res[0]==0 && res[1]==0 && res[2]==0)
          {
                    printf ("found (thread %d): [%s]. seconds spent=%d\n", t, buf, time(NULL)-start);
                    found=1;
          };
          #pragma omp atomic
          checked++;

          #pragma omp critical
          if ((checked % 100000)==0)
                    printf ("checked=%d\n", checked);
};

int main()
{
          int32_t i;
          int threads=omp_get_max_threads();
          printf ("threads=%d\n", threads);

          __min=(int32_t*)malloc(threads*sizeof(int32_t));
          __max=(int32_t*)malloc(threads*sizeof(int32_t));
          for (i=0; i<threads; i++)
                    __min[i]=__max[i]=-1;

          start=time(NULL);

          #pragma omp parallel for
          for (i=0; i<INT32_MAX; i++)
                    check_nonce (i);

          for (i=0; i<threads; i++)
                    printf ("__min[%d]=0x%08x __max[%d]=0x%08x\n", i, __min[i], i, __max[i]);

          free(__min); free(__max);
};

函数check_nonce() 有3个作用:向字符串添加数字、使用SHA512算法计算新字符串的hash、检查hash中是否有3个为0的字节。

这段代码中较为重要的部分是:

          #pragma omp parallel for
          for (i=0; i<INT32_MAX; i++)
                   check_nonce (i);

这个程序确实不复杂。如果没有#pragma,程序会从0依次穷举到INT32的最大值(0x7fffffff,即2147483647),依次用check_nonce() 函数验证。加上#pragma之后,编译器会添加特定的代码把整个区间划分为若干子区间,充分利用CPU的多核进行并行运算。[1]

我们可以通过下述指令,使用MSVC 2012进行编译[2]

cl openmp_example.c sha512.obj /openmp /O1 /Zi /Faopenmp_example.asm

GCC对应的编译指令为:

gcc -fopenmp 2.c sha512.c -S -masm=intel

92.1 MSVC

MSVC 2012生成的主循环的指令如下所示。

指令清单92.1 MSVC 2012

          push    OFFSET _main$omp$1
          push    0
          push    1
          call    __vcomp_fork
          add     esp, 16                              ; 00000010H

所有以vcomp开头的函数都是与OpenMP有关的函数,通过vcomp*.dll进行加载。它将发起一组线程进行并行计算。

具体来说,_main$omp$1的汇编代码如下所示。

指令清单92.2 MSVC 2012

$T1 = -8                                                 ; size = 4
$T2 = -4                                                 ; size = 4
_main$omp$1 PROC                                         ; COMDAT
        push    ebp
        mov     ebp,  esp
        push    ecx
        push    ecx
        push    esi
        lea     eax, DWORD PTR $T2[ebp]
        push    eax
        lea     eax, DWORD PTR $T1[ebp]
        push    eax
        push    1
        push    1
        push    2147483646                               ; 7ffffffeH
        push    0
        call    __vcomp_for_static_simple_init
        mov     esi, DWORD PTR $T1[ebp]
        add     esp, 24                                  ; 00000018H
        jmp     SHORT $LN6@main$omp$1
$LL2@main$omp$1:
        push    esi
        call    _check_nonce
        pop     ecx
        inc     esi
$LN6@main$omp$1:
        cmp     esi, DWORD PTR $T2[ebp]
        jle     SHORT $LL2@main$omp$1
        call    __vcomp_for_static_end
        pop     esi
        leave
        ret     0
_main$omp$1 ENDP

这个函数会启动n个并发线程,其中n就是CPU核芯(cores)的总数。函数vcomp_for_static_ simple_init()计算当前线程里for() 结构体的区间,而区间的间隔则由当前线程的总数决定。循环计数器的起始值和结束值分别存储于局部变量$T1和$T2。细心的读者可能注意到函数vcomp_for_ static_simple_init() 的一个参数为0x7ffffffeh(即2147483646)——它是整个循环体的迭代次数,最终会被n整除。

接下来程序发起了调用函数check_nonce() 的循环,完成余下的工作。

我在源代码的check_nonce() 函数中有意添加了统计代码,用来统计参数被调用的次数。

整个程序的运行结果如下:

threads=4
...
checked=2800000
checked=3000000
checked=3200000
checked=3300000
found (thread 3): [hello, world!_1611446522]. seconds spent=3
__min[0]=0x00000000 __max[0]=0x1fffffff
__min[1]=0x20000000 __max[1]=0x3fffffff
__min[2]=0x40000000 __max[2]=0x5fffffff
__min[3]=0x60000000 __max[3]=0x7ffffffe

计算结果的前3个字节确实是零:

C:\...\sha512sum test
000000f4a8fac5a4ed38794da4c1e39f54279ad5d9bb3c5465cdf57adaf60403
df6e3fe6019f5764fc9975e505a7395fed780fee50eb38dd4c0279cb114672e2 *test

在笔者的4核Intel Xeon E3-1220 3.10Ghz CPU上运行这个程序,总耗时大约2~3秒。我们可以在任务管理器中看到5个线程:1个主线程和4个子线程。虽然理论上它还有精简的空间,但是我没有对程序源代码进行深度优化。深度优化应当可以大幅度提升它的运行效率。另外,因为我的CPU有4个内核,所以它发起了4个子线程——这完全符合OpenMP规范。

通过程序输出的统计数据,我们可以清楚地观察到整个穷举空间被划分为大致相等的四个部分。严格地说,考虑到最后一个比特位,这四个区间确实并非完全相等。

OpenMP还提供了保障模块crtomic(原子性)的Prugms指令。顾名思义,被标记为原子性的代码不会被拆分为多个子线程运行。我们来看看这段代码:

          #pragma omp atomic
          checked++;

          #pragma omp critical
          if ((checked % 100000)==0)
                    printf ("checked=%d\n", checked);

经MSVC 2012编译,上述代码对应的汇编指令如下所示。

指令清单92.3 MSVC 2012

         push     edi
         push     OFFSET _checked
         call     __vcomp_atomic_add_i4
; Line 55
         push     OFFSET _$vcomp$critsect$
         call     __vcomp_enter_critsect
         add      esp, 12                                    ; 0000000cH
; Line 56
         mov      ecx, DWORD PTR _checked
         mov      eax, ecx
         cdq
         mov      esi, 100000                                ; 000186a0H
         idiv     esi
         test     edx, edx
         jne      SHORT $LN1@check_nonc
; Line 57
         push     ecx
         push     OFFSET ??_C@_0M@NPNHLIOO@checked?$DN?$CFd?6?$AA@
         call     _printf
         pop      ecx
         pop      ecx
$LN1@check_nonc:
         push     DWORD PTR _$vcomp$critsect$
         call     __vcomp_leave_critsect
         pop      ecx

封装在vcomp*.dll里的函数vcomp_atomic_add_i4() 只是一个使用了LOCK XADD指令的小函数。[3]

函数vcomp_enter_critsect() 调用的是Win32 API函数EnterCriticalSection()[4]

92.2 GCC

经GCC 4.8.1生成的程序,其统计结果和上面的程序一样。所以GCC分割区间的方法与MSVC相同。

指令清单92.4 GCC 4.8.1

          mov       edi, OFFSET FLAT:main._omp_fn.0
          call      GOMP_parallel_start
          mov       edi, 0
          call      main._omp_fn.0
          call      GOMP_parallel_end

由GCC编译生成的程序,会发起3个新的线程,原有线程扮演第4进程的角色。所以,总体上GCC的进程数是4,MSVC的进程数是5。

其中,函数main._omp_fn.0的代码如下所示。

指令清单92.5 GCC 4.8.1

main._omp_fn.0:
        push    rbp
        mov     rbp, rsp
        push    rbx
        sub     rsp, 40
        mov     QWORD PTR [rbp-40], rdi
        call    omp_get_num_threads
        mov     ebx, eax
        call    omp_get_thread_num
        mov     esi, eax
        mov     eax, 2147483647 ; 0x7FFFFFFF
        cdq
        idiv    ebx
        mov     ecx, eax
        mov     eax, 2147483647 ; 0x7FFFFFFF
        cdq
        idiv    ebx
        mov     eax, edx
        cmp     esi, eax
        jl      .L15
.L18:
        imul    esi, ecx
        mov     edx, esi
        add     eax, edx
        lea     ebx, [rax+rcx]
        cmp     eax, ebx
        jge     .L14
        mov     DWORD PTR [rbp-20], eax
.L17:
        mov     eax, DWORD PTR [rbp-20]
        mov     edi, eax
        call    check_nonce
        add     DWORD PTR [rbp-20], 1
        cmp     DWORD PTR [rbp-20], ebx
        jl      .L17
        jmp     .L14
.L15:
        mov     eax, 0
        add     ecx, 1
        jmp     .L18
.L14:
        add     rsp, 40
        pop     rbx
        pop     rbp
        ret

上述指令清晰地显示出:程序通过调用函数omp_get_num_threads() 和另一个函数omp_get_ thread_num() 获取当前线程的总数以及当前线程的编号,然后分割循环体。之后,它再运行check_nonce()。

GCC在代码中直接使用LOCK ADD指令,而MSVC则是调用另一个DLL文件中的独立函数。

指令清单92.6 GCC 4.8.1

        lock add         DWORD PTR checked[rip], 1
        call    GOMP_critical_start
        mov     ecx, DWORD PTR checked[rip]
        mov     edx, 351843721
        mov     eax, ecx
        imul    edx
        sar     edx, 13
        mov     eax, ecx
        sar     eax, 31
        sub     edx, eax
        mov     eax, edx
        imul    eax, eax, 100000
        sub     ecx, eax
        mov     eax, ecx
        test    eax, eax
        jne     .L7
        mov     eax, DWORD PTR checked[rip]
        mov     esi, eax
        mov     edi, OFFSET FLAT:.LC2 ; "checked=%d\n"
        mov     eax, 0
        call    printf
.L7:
        call    GOMP_critical_end

以GOMP开头的函数来自于GNU OpenMP Library。您可在GitHub下载到它的源文件(https:// github.com/gcc-mirror/gcc/tree/master/libgomp

)。不过,微软的vcomp*.dll文件没有源代码可查。


[1] 本例仅为示范性说明。在实际情况下,使用OpenMP技术往往更为困难、复杂。

[2] sha512.(c|h)和u64.h的源文件可照搬OpenSSL的库文件:http://www.openssl.org/ source/。

[3] 有关LOCK前缀的详细说明,请参见本书附录A.6.1。

[4] 请参见本书68.4节。