Как реализовать детерминированный malloc - PullRequest
6 голосов
/ 07 декабря 2011

Скажем, у меня есть два экземпляра приложения с одинаковыми входными данными и одинаковой последовательностью выполнения.Поэтому один экземпляр является избыточным и используется для сравнения данных в памяти с другим экземпляром, как своего рода механизм обнаружения ошибок.

Теперь я хочу, чтобы все распределения и освобождения памяти происходили одинаково в обоих процессах.Какой самый простой способ достичь этого?Написать свой собственный malloc и бесплатно?А как насчет памяти, выделяемой другими функциями, такими как mmap?

Ответы [ 5 ]

4 голосов
/ 07 декабря 2011

Проще говоря, как уже говорили другие: если выполнение инструкций вашей программы детерминировано, то память, возвращаемая malloc(), будет детерминированной.Это предполагает, что реализация вашей системы не имеет какого-то вызова random() или чего-то подобного.Если вы не уверены, прочитайте код или документацию для вашей системы malloc.

. Это, возможно, за исключением ASLR, о чем также говорили другие.Если у вас нет привилегий root, вы можете отключить его для каждого процесса через системный вызов personality(2) и параметр ADDR_NO_RANDOMIZE.См. здесь для получения дополнительной информации о личностях.

Редактировать: Я должен также сказать, если вы не знаете: то, что вы делаете, называется bisimulation и являетсяхорошо изученная техника.Если вы не знаете терминологию, это может помочь найти это ключевое слово для поиска.

4 голосов
/ 07 декабря 2011

Мне интересно, чего вы пытаетесь достичь. Если ваш процесс является детерминированным, то схема распределения / освобождения должна быть такой же.

Единственной возможной разницей может быть адрес, возвращаемый malloc. Но вы, вероятно, не должны зависеть от них (самый простой способ - не использовать указатели в качестве карты ключей или другой структуры данных). И даже в этом случае разница должна быть только в том случае, если выделение не выполняется через sbrk (glibc использует анонимное mmap для больших выделений) или если вы используете mmap (так как по умолчанию адрес выбирается ядро).

Если вы действительно хотите иметь точно такой же адрес, одним из вариантов является большой статический буфер и запись пользовательского распределителя, который использует память из этого буфера. Это имеет недостаток, заставляющий вас заранее знать максимальный объем памяти, который вам когда-либо понадобится. В исполняемом файле, отличном от PIE (gcc -fno-pie -no-pie), статический буфер будет каждый раз иметь один и тот же адрес. Для исполняемого файла PIE вы можете отключить ядро ​​ рандомизация макета адресного пространства для загрузки программ. В совместно используемой библиотеке отключение ASLR и запуск одной и той же программы дважды должен привести к тому, что динамический компоновщик сделает один и тот же выбор места отображения библиотек.

Если вы не знаете заранее максимального размера памяти, которую вы хотите использовать, или если вы не хотите перекомпилировать каждый раз, когда это увеличение размера, вы также можете использовать mmap для отображения большого анонимного буфера по фиксированному адресу. Просто передайте размер буфера и адрес, который будет использоваться в качестве параметра для вашего процесса, и используйте возвращенную память для реализации своего собственного malloc поверх него.

static void* malloc_buffer = NULL;
static size_t malloc_buffer_len = 0;

void* malloc(size_t size) {
    // Use malloc_buffer & malloc_buffer_len to implement your
    // own allocator. If you don't read uninitialized memory,
    // it can be deterministic.
    return memory;
}

int main(int argc, char** argv) {
    size_t buf_size = 0;
    uintptr_t buf_addr = 0;
    for (int i = 0; i < argv; ++i) {
        if (strcmp(argv[i], "--malloc-size") == 0) {
            buf_size = atoi(argv[++i]);
        }
        if (strcmp(argv[i], "--malloc-addr") == 0) {
            buf_addr = atoi(argv[++i]);
        }
    }

    malloc_buffer = mmap((void*)buf_addr, buf_size, PROT_WRITE|PROT_READ,
                         MAP_FIXED|MAP_PRIVATE, 0, 0);
    // editor's note: omit MAP_FIXED since you're checking the result anyway
    if (malloc_buffer == MAP_FAILED || malloc_buffer != (void*)but_addr) {
        // Could not get requested memory block, fail.
        exit(1);
    }

    malloc_size = buf_size;
}

Используя MAP_FIXED, мы говорим ядру заменить любые существующие сопоставления, которые перекрываются, с этим новым в buf_addr.

(Примечание редактора: MAP_FIXED, вероятно, не то, что вы хотите . Если указать buf_addr в качестве подсказки вместо NULL, то уже запрашивает этот адрес, если это возможно. С MAP_FIXED, mmap будет либо возвращать ошибку, либо адрес, который вы ей дали. Проверка malloc_buffer != (void*)but_addr имеет смысл для случая, отличного от FIXED, который не заменит существующее отображение вашего кода, разделяемой библиотеки или чего-либо еще. Представлен Linux 4.17 MAP_FIXED_NOREPLACE, который вы можете использовать, чтобы заставить mmap возвращать ошибку вместо памяти по неправильному адресу, который вы не хотите использовать. Но все же оставьте проверку, чтобы ваш код работал на старых ядрах.)

Если вы используете этот блок для реализации своего собственного malloc и не используете другие недетерминированные операции в своем коде, вы можете полностью контролировать значения указателя.

Предполагается, что использование вами шаблона malloc / free является детерминированным. И что вы не используете библиотеки, которые являются недетерминированными.


Тем не менее, я думаю, что более простое решение - сохранить ваши алгоритмы детерминированными и не зависеть от адресов. Это возможно. Я работал над крупномасштабным проектом, в котором нескольким компьютерам приходилось детально определять состояние (чтобы каждая программа имела одно и то же состояние, передавая только входные данные). Если вы не используете указатель для чего-то другого, кроме ссылки на объекты (самое важное - никогда не использовать значение указателя ни для чего, кроме как хеш-код, не как ключ на карте, ...), тогда ваше состояние останется детерминированным .

Если вам не нужно иметь возможность снимать всю память процесса и делать двоичный анализ, чтобы определить расхождение. Я думаю, что это плохая идея, потому что как вы узнаете, что оба они достигли одной и той же точки в своих вычислениях? Гораздо проще сравнивать выходные данные, или чтобы процесс мог вычислять хэш состояния и использовать его для проверки их синхронизации, потому что вы можете контролировать, когда это будет сделано (и, таким образом, он станет детерминированным, в противном случае ваше измерение будет недетерминированным).

4 голосов
/ 07 декабря 2011

Что не является детерминированным, так это не только malloc, но mmap (базовый системный вызов для получения большего объема памяти; это не функция, это системный вызов , поэтомуэлементарным или атомарным с точки зрения приложения, поэтому вы не можете переписать его в приложении) из-за рандомизации макета адресного пространства в Linux.

Вы можете отключить его с помощью

 echo 0 > /proc/sys/kernel/randomize_va_space

как root или через sysctl .

Если вы не отключите рандомизацию размещения адресного пространства, вы застряли.

И вы задали похожий вопрос ранее , где я объяснил, что ваши malloc -ы не всегда будут детерминированными.

Я все еще думаю, что для некоторых практических применений malloc не может быть детерминированным.Представьте себе, например, программу, имеющую хэш-таблицу с ключом pid дочерних процессов, которые она запускает.Столкновение в этой таблице не будет одинаковым во всех ваших процессах и т. Д.

Поэтому я считаю, что вам не удастся сделать malloc детерминистическим в вашем смысле, что бы вы ни пытались (если вы не ограничитек узкому классу приложений для контрольной точки, настолько узким, что ваше программное обеспечение не будет очень полезным).

2 голосов
/ 07 декабря 2011

При написании высоконадежного кода обычной практикой является недопущение malloc и другого динамического выделения памяти.Иногда используется компромисс: все такое распределение выполняется только во время инициализации системы.

0 голосов
/ 07 декабря 2011

Вы можете использовать разделяемую память для хранения ваших данных. Он будет доступен из обоих процессов, и вы можете заполнить его детерминистическим способом.

...