执行函数时计算写入集

Question

我想编写一个函数 computeWriteSet，它接受任意函数 f 作为参数，并且 (1) 执行函数 f 和 ( 2) 返回在 f 执行期间修改或写入(地址/页面/对象)的位置。

writeset computeWriteSet(function f) {
  writeset ws = createEmptyWriteset();
  // prepare to execute f
  startRecordingWrites(&ws);
  f();
  stopRecordingWrites(&ws);
  // post-process the write-set
  return ws;
}

1. 有哪些实现方案？
2. 他们的权衡是什么(在哪种情况下哪种实现更有效，有哪些局限性？)

注意事项

该函数在运行时指定并且可以做任何事情(即可以包含任何指令集，包括循环、分支和函数/系统调用。

从 f 被调用到它返回的所有写入都应该被记录(这包括从 f 本身调用的函数)。为简单起见，我们假设 computeWriteSet 不是从内部调用的。

特定于操作系统的技巧是允许的(并且可能是必需的)。我对 Linux 特别感兴趣，最好是在用户空间内。

例子

static int x = 0;
static int y = 0;
static int z = 0;

void a() {
  if (y) z++;
  if (x) y++;
  x = (x + 1) % 2;
}

int main() {
  computeWriteSet(a); // returns { &x }     => {x,y,z} = {1, 0, 0}
  computeWriteSet(a); // returns { &x, &y } => {x,y,z} = {0, 1, 0}
  computeWriteSet(a); // returns { &x, &z } => {x,y,z} = {1, 1, 1}
  return 0;
}

预期输出

输出应该是一组变化。这可以是页面集:

{ <address of x>, <address of y>, …}

或者内存地址的集合:

{<page of x and y>, <page of z>, …}

或对象集((基于分配函数的插入)

x = malloc(100) // returns address 0xAAA
y = malloc(200) // returns address 0xBBB
…

{ {address, size}, {0xAAA, 100}, {0xBBB, 200}, … }

返回值是有意松散指定的——不同的技术将具有不同的空间分辨率和不同的开销。

请注意:

这是一个非常不常见的编程问题，因此，如果您认为它应该关闭，请告诉我原因，以及理想情况下如何措辞/​​放置它以使其遵循指南。 :-)

Answer 1

正如@Barmar 所建议的，实现这一点的一种方法是通过 mprotect。

这将为每个内存页面生成一个异常，这可能会增加相当大的开销，具体取决于函数。这个异常由我们处理，然后我们将相应的地址插入到一个集合中。

一个 100 行的小 C++/C 完全包含的困惑程序展示了下面的内容。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <signal.h>
#include <ucontext.h>
#include <fcntl.h>
#include <execinfo.h>
#include <sys/mman.h>

#include <set>
#include <functional>
#include <cassert>

extern "C" {
extern int __data_start;
extern int _end;
}

#define PAGE_SIZE sysconf(_SC_PAGESIZE)
#define PAGE_MASK (PAGE_SIZE - 1)
#define PAGE_ALIGN_DOWN(x) (((intptr_t) (x)) & ~PAGE_MASK)
#define PAGE_ALIGN_UP(x) ((((intptr_t) (x)) + PAGE_MASK) & ~PAGE_MASK)
#define GLOBALS_START PAGE_ALIGN_DOWN((intptr_t) &__data_start)
#define GLOBALS_END   PAGE_ALIGN_UP((intptr_t) &_end - 1)
#define GLOBALS_SIZE  (GLOBALS_END - GLOBALS_START)

std::set<void*> *addresses = new std::set<void*>();

void sighandler(int signum, siginfo_t *siginfo, void *ctx) {
    void *addr = siginfo->si_addr;
    void *aligned_addr = reinterpret_cast<void*>(PAGE_ALIGN_DOWN(addr));
    switch(siginfo->si_code) {
    case SEGV_ACCERR:
        mprotect(aligned_addr, PAGE_SIZE, PROT_READ | PROT_WRITE);
        addresses->insert(aligned_addr);
        break;
    default:
        exit(-1);
    }
}

void computeWriteSet(std::function<void()> f) {
    static bool initialized = false;
    if (!initialized) {
        // install signal handler
        stack_t sigstk;
        sigstk.ss_sp = malloc(SIGSTKSZ);
        sigstk.ss_size = SIGSTKSZ;
        sigstk.ss_flags = 0;
        sigaltstack(&sigstk, NULL);
        struct sigaction siga;
        sigemptyset(&siga.sa_mask);
        sigaddset(&siga.sa_mask, SIGSEGV);
        sigprocmask(SIG_BLOCK, &siga.sa_mask, NULL);
        siga.sa_flags = SA_SIGINFO | SA_ONSTACK | SA_RESTART | SA_NODEFER;
        siga.sa_sigaction = sighandler;
        sigaction(SIGSEGV, &siga, NULL);
        sigprocmask(SIG_UNBLOCK, &siga.sa_mask, NULL);
        initialized = true;
    }
    addresses->clear();
    printf("\nexecuting function\n");
    printf("--------------\n");
    mprotect(reinterpret_cast<void*>(GLOBALS_START), GLOBALS_SIZE, PROT_READ);
    f();
    mprotect(reinterpret_cast<void*>(GLOBALS_START), GLOBALS_SIZE, PROT_READ | PROT_WRITE);
    printf("--------------\n");
    printf("pages written:\n");
    for (auto addr : *addresses) {
        printf("%p\n", addr);
    }
}

void f() {
    static int x[1024] = {0};
    static int y[1024] = {0};
    static int z[1024] = {0};
    static bool firsttime = true;
    if (firsttime) {
        printf("&x[0] = %p\n&y[0] = %p\n&z[0] = %p\n", x, y, z);
        firsttime = false;
    }
    if (y[0]) z[0]++;
    if (x[0]) y[0]++;
    x[0] = (x[0] + 1) % 2;
    printf("{x, y, z} = {%d, %d, %d}\n", x[0], y[0], z[0]);
}

int main() {
    computeWriteSet(f);
    computeWriteSet(f);
    computeWriteSet(f);
    return 0;
}

使用 g++ --std=c++11 example.cpp 编译。

执行打印如下内容:

executing function
--------------
&x[0] = 0x6041c0
&y[0] = 0x6051c0
&z[0] = 0x6061c0
{x, y, z} = {1, 0, 0}
--------------
pages written:
0x604000

executing function
--------------
{x, y, z} = {0, 1, 0}
--------------
pages written:
0x604000
0x605000

executing function
--------------
{x, y, z} = {1, 1, 1}
--------------
pages written:
0x604000
0x606000

一些注意事项:

• 我们制作 x、y 和 z 足够大的数组(大小为 PAGE_SIZE/sizeof(int) ，在我的机器上是 1024)，所以它们落在不同的内存页中，因此可以区分。

• 这个程序只适用于全局/静态变量，因此它可以很短。要扩展它以使用堆和其他内存映射，可以通过插入来完成，正如@AShelly 所建议的那样。

主题跟进:有什么方法可以避免 O(N) 信号，其中 N 是写入的页数？