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
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]。
经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节。