执行函数时计算写集 [英] Computing the set of writes when executing a function

问题描述

我想编写一个函数computeWriteSet，该函数将任意函数f作为参数，并且(1)执行函数f，而(2)返回修改后的 places 的集合或在f执行期间写入(地址/页面/对象).

I want to write a function computeWriteSet that takes an arbitrary function f as an argument and (1) executes the function f and (2) returns the set of places modified or written to (addresses/pages/objects) during f's execution.

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. 它们的权衡是什么(在哪种情况下哪种实现更有效，并且有哪些局限性?)

注释

该函数在运行时指定，并且可以执行任何操作(即可以包含任何指令集，包括循环，分支和函数/系统调用.

Notes

The function is specified at runtime and can do anything (i.e. can contain any set of instructions, including loops, branching and function/system calls.

应记录从调用f到返回的所有写入(包括从f本身调用的函数).为简单起见，我们假设未从内部调用computeWriteSet.

All writes from the time f is called until it returns should be recorded (this includes functions called from within f itself). For simplicity, let's assume computeWriteSet is not called from within.

特定于操作系统的技巧(可能是必需的).我对 Linux 特别是在用户空间内特别感兴趣.

OS-specific tricks are allowed (and probably required). I'm particularly interested in Linux, ideally within userspace.

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;
}

预期产量

输出应为更改的集合.这可以是页面集:

Expected Output

The output should be the set of changes. This can be either the set of pages:

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

或一组内存地址:

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

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

Or the set of objects ( (based on interposition of allocation functions)

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

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

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

The return value is loosely specified on purpose -- different techniques will have different spatial resolution and different overheads.

这是一个非常不常见的编程问题，因此，如果您认为应该将其关闭，请告诉我原因，以及在理想情况下如何对其进行措辞/放置以使其遵循准则. :-)

推荐答案

如@Barmar所建议的，一种实现方法是通过mprotect.

As suggested by @Barmar, one way of accomplishing this is via mprotect.

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

This will generate one exception for each of the memory pages, which may add considerable overhead depending on the function. This exception is handled by us and we then insert the corresponding address into a set.

一个小型的100行C++/C完全杂乱的程序演示了这一点，如下所示.

A small 100-line C++/C fully-contained messy program showcasing this is included below.

#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编译.

执行将打印出类似以下内容的内容:

Execution prints something like:

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)，以便它们位于不同的内存页中，因此可以区分.

• We make x, y and z large-enough arrays (of size PAGE_SIZE/sizeof(int), which is 1024 on my machine) so that they fall in different memory pages and therefore can be differentiated.

该程序仅适用于全局/静态变量，因此可能比较短.如@AShelly所建议的那样，要使其扩展以与堆一起使用，其他内存映射可以通过插入来完成.

This program will only work for global/static variables so that it can be short-ish. To extend it to work with heaps and other memory mappings can be done via interpositions, as suggested by @AShelly.

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

On-topic follow-up: Is there any way of avoiding the O(N) signals, where N is the number of pages written to?

这篇关于执行函数时计算写集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！