Вычисление набора записей при выполнении функции - PullRequest
Новая
       19

Вычисление набора записей при выполнении функции

0 голосов
/ 14 февраля 2019

Я хочу написать функцию 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}, … }

Возвращаемое значение специально указано произвольно - разные методы будут иметь разное пространственное разрешение и разные накладные расходы.

Обратите внимание:

Это оченьнеобычный вопрос программирования, поэтому, если вы считаете, что он должен быть закрыт, дайте мне знать, почему и, в идеале, как сформулировать / разместить его так, чтобы он соответствовал рекомендациям.: -)

1 Ответ

0 голосов
/ 15 февраля 2019

Как предполагает @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 - количество записанных страниц?

...