Организация эффективного менеджера памяти, минимизирующего темпоральные ошибки Милославский А. И.

Термины Крах. Аварийное завершение работы программы. Крах. Аварийное завершение работы программы. Атака. Возможность вмешаться в ход выполнения программы злоумышленником. Атака. Возможность вмешаться в ход выполнения программы злоумышленником. UB. Undefined behavior. Непредсказуемое поведение программы. UB. Undefined behavior. Непредсказуемое поведение программы. Утечки памяти. Утечки памяти. Очистка. Приведение освобожденной памяти в эффективное для повторного выделения состояние. Очистка. Приведение освобожденной памяти в эффективное для повторного выделения состояние.

Виды темпоральных ошибок 1. Многократное освобождение блока. 1. Многократное освобождение блока. Нарушение работы системы выделения памяти. Нарушение работы системы выделения памяти. Удаление чужих данных. Удаление чужих данных.

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

3. Удаление неверного блока памяти. 3. Удаление неверного блока памяти. 4. Утечки памяти. 4. Утечки памяти. Виды темпоральных ошибок

Постановка задачи Требования: Требования: 1. Умеренные накладные расходы. 1. Умеренные накладные расходы. 2. Неограниченное время работы. 2. Неограниченное время работы. 3. Минимизация всех негативных последствий темпоральных ошибок. 3. Минимизация всех негативных последствий темпоральных ошибок. 4. Возможность выполнять временную работу, связанную с большими затратами вычислительной мощности, в «спокойное время» в фоновом режиме. 4. Возможность выполнять временную работу, связанную с большими затратами вычислительной мощности, в «спокойное время» в фоновом режиме. 5. Ранняя очистка. 5. Ранняя очистка. 6. Работа системы с кодом, не приспособленным для этого специально. 6. Работа системы с кодом, не приспособленным для этого специально. Пожелания: Пожелания: 7. Малые накладные расходы. 7. Малые накладные расходы. 8. Возможность аппаратной поддержки. 8. Возможность аппаратной поддержки. 9. Полное исключение темпоральных ошибок. 9. Полное исключение темпоральных ошибок.

Предыдущие работы [1] DinakarDhurjati, Vikram Adve – Efficiently Detecting All Dangling Pointer Uses in Production Servers [1] DinakarDhurjati, Vikram Adve – Efficiently Detecting All Dangling Pointer Uses in Production Servers [2] Wei Xu, Daniel C. DuVarney, R. Sekar - An Efficient and Backwards-Compatible Transformation to Ensure Memory Safety of C Programs [2] Wei Xu, Daniel C. DuVarney, R. Sekar - An Efficient and Backwards-Compatible Transformation to Ensure Memory Safety of C Programs [3] Harish Patil, Charles Fischer - Low-cost, Concurrent Checking of Pointer and Array accesses in C Programs [3] Harish Patil, Charles Fischer - Low-cost, Concurrent Checking of Pointer and Array accesses in C Programs [4] Emery D.Berger, Benjamin G.Zorn – DieHard: Probabilistic Memory Safety for Unsafe Languages [4] Emery D.Berger, Benjamin G.Zorn – DieHard: Probabilistic Memory Safety for Unsafe Languages

Сбор статистики 1. Стартовая нагрузка 1. Стартовая нагрузка 2. Объем использованного виртуального пространства в единицу времени 2. Объем использованного виртуального пространства в единицу времени 3. Распределение запросов по размеру запрошенного блока памяти 3. Распределение запросов по размеру запрошенного блока памяти 4. Типичное время жизни блока 4. Типичное время жизни блока 5. Чередование выделения и освобождения блоков 5. Чередование выделения и освобождения блоков

EVE Online

Компилятор из поставки Visual Studio 2003

Visual Studio 2003

Стартовая нагрузка Пик достигается за несколько секунд Пик достигается за несколько секунд Часто выполняется до 50% от общего числа запросов Часто выполняется до 50% от общего числа запросов В основном короткоживущие блоки В основном короткоживущие блоки Большое чередование Большое чередование Высокий потенциал фрагментации Высокий потенциал фрагментации

Объем использованного виртуального пространства в единицу времени 2-3Мб в секунду 2-3Мб в секунду Можно ожидать 30Мб/с Можно ожидать 30Мб/с Без очистки адресное пространство исчерпается за 100 дней Без очистки адресное пространство исчерпается за 100 дней

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

Типичное время жизни блока В основном очень малое время жизни В основном очень малое время жизни С учетом запросов в секунду, высокий риск возникновения проблем из-за ошибок С учетом запросов в секунду, высокий риск возникновения проблем из-за ошибок

Чередование выделения и освобождения блоков Короткоживущие блоки сильно чередуются с долгоживущими Короткоживущие блоки сильно чередуются с долгоживущими Высокая степень фрагментации Высокая степень фрагментации Корреляция с размером блока Корреляция с размером блока

Среднее число блоков Для EVE Online – около 3 миллионов Для EVE Online – около 3 миллионов Повышенная сложность учета блоков Повышенная сложность учета блоков

DieHard OK Многократное освобождение блока. OK Многократное освобождение блока. 99.5%Работа с блоком после освобождения его памяти. 99.5%Работа с блоком после освобождения его памяти. 99.5%Удаление неверного блока памяти. 99.5%Удаление неверного блока памяти. XУтечки памяти. XУтечки памяти.

Результаты работы Написана платформа для испытаний менеджера памяти на реальных программах Написана платформа для испытаний менеджера памяти на реальных программах Написана система сбора статистики использования памяти в реальных программах Написана система сбора статистики использования памяти в реальных программах Написана программа для анализа собранной статистики Написана программа для анализа собранной статистики Выполнен анализ собранной статистики Выполнен анализ собранной статистики Проведены исследования различных способов устройства менеджера памяти Проведены исследования различных способов устройства менеджера памяти Рассмотрено влияние факторов, выявленных в статистике, на исследованные методы Рассмотрено влияние факторов, выявленных в статистике, на исследованные методы Собрана литература по вариантам, оптимизациям и различным аспектам реализации консервативных сборщиков мусора Собрана литература по вариантам, оптимизациям и различным аспектам реализации консервативных сборщиков мусора

Дальнейшая работа Придумать другие методы реализации менеджера памяти для лучшего выполнения требований и пожеланий Придумать другие методы реализации менеджера памяти для лучшего выполнения требований и пожеланий Добавить консервативный сборщик мусора (подчасть 1 пункта) Добавить консервативный сборщик мусора (подчасть 1 пункта) Реализовать менеджер памяти в коде Реализовать менеджер памяти в коде Испытать менеджера памяти на реальных программах с использованием готовой платформы Испытать менеджера памяти на реальных программах с использованием готовой платформы Внедрить готовый менеджер памяти в ОС Внедрить готовый менеджер памяти в ОС