Автоматический поиск состояний гонок в ядре OC Linux (1187393), страница 6
Текст из файла (страница 6)
Недостатком является меньшая вероятность найти состояние гонки в остальном коде. Это связано с тем, что для того, чтобы состояние гонкибыло найдено, оно должно произойти между ядрами, а не между заданиями, которыемогли быть запущены планировщиком на одном ядре.4.1.6Отчеты об ошибкахОдним из важных преимуществ разработанного детектора являются подробныесообщения об ошибках. На листингах 13 и 14 приведен отчет об ошибке, которыйпечатает детектор KernelThreadSanitizer при обнаружении состояния гонки.
В отчетеприводится много информации, которая может помочь найти и исправить ошибку.В заголовке сообщения об ошибке приводятся стеки вызовов для обращений к памяти, которые находятся в состоянии гонки. Кроме адресов внутри бинарного файлаядра и имен функций, в стеке вызовов также показаны названия файлов с исходным28кодом и номера строк в этих файлах. Более того, в стеке вызовов показываются ивстроенные (англ. inline) вызовы.В следующей части отчета перечислены мьютексы, взятые каждым из потоков,которые находятся в состоянии гонки.
Для каждого из мьютексов приводится стеквызовов на момент взятия этого мьютекса.1ThreadSanitizer : data - race in ipc _obtain_obj ect_check23456789Read at 0 xffff88047f810f68 of size 8 by thread 2749 on CPU 5:[ < ffffffff8147d84d >] ipc_obtain_ object_chec k +0 x7d /0 xd0ipc / util . c :621[<inline>] msq_obtain_ object_chec k ipc / msg .
c :90[ < ffffffff8147e708 >] msgctl_nolock . constprop .9+0 x208 /0 x430ipc / msg . c :480[<inline>] SYSC_msgctl ipc / msg . c :538[ < ffffffff8147f061 >] SyS_msgctl +0 xa1 /0 xb0 ipc / msg . c :522[ < ffffffff81ee3e11 >] en tr y_S YS CA LL_ 64 _f ast pa th +0 x31 /0 x95arch / x86 / entry / entry_64 . S :188101112131415161718Previous write at 0 xffff88047f810f68 of size 8 by thread 2755 onCPU 4:[ < ffffffff8147cf97 >] ipc_addid +0 x217 /0 x260 ipc / util .
c :257[ < ffffffff8147eb4c >] newque +0 xac /0 x240 ipc / msg . c :141[<inline>] ipcget_public ipc / util . c :355[ < ffffffff8147daa2 >] ipcget +0 x202 /0 x280 ipc / util . c :646[<inline>] SYSC_msgget ipc / msg . c :255[ < ffffffff8147efaa >] SyS_msgget +0 x7a /0 x90 ipc / msg . c :241[ < ffffffff81ee3e11 >] en tr y_S YS CA LL_ 64 _fa st pa th +0 x31 /0 x95arch / x86 / entry / entry_64 . S :188Листинг 13: Отчет детектора KernelThreadSanitizer: заголовок сообщения об ошибкеи стек вызовов для обращений к памяти2912345678Mutexes locked by thread 2755:Mutex 445417 is locked here :[ < ffffffff81ee0d45 >] down_write +0 x65 /0 x80kernel / locking / rwsem .
c :62[<inline>] ipcget_public ipc / util . c :348[ < ffffffff8147d90c >] ipcget +0 x6c /0 x280 ipc / util . c :646[<inline>] SYSC_msgget ipc / msg . c :255[ < ffffffff8147efaa >] SyS_msgget +0 x7a /0 x90 ipc / msg . c :241[ < ffffffff81ee3e11 >] en tr y_S YS CA LL_ 64 _f ast pa th +0 x31 /0 x95arch / x86 / entry / entry_64 . S :18891011121314151617181920Mutex 453634 is locked here :[<inline>] __raw_spin_lockinclude / linux / spinlock_api_smp .
h :158[ < ffffffff81ee37d0 >] _raw_spin_lock +0 x50 /0 x70kernel / locking / spinlock . c :151[<inline>] spin_lock include / linux / spinlock . h :312[ < ffffffff8147ce0e >] ipc_addid +0 x8e /0 x260 ipc / util . c :238[ < ffffffff8147eb4c >] newque +0 xac /0 x240 ipc / msg . c :141[<inline>] ipcget_public ipc / util .
c :355[ < ffffffff8147daa2 >] ipcget +0 x202 /0 x280 ipc / util . c :646[<inline>] SYSC_msgget ipc / msg . c :255[ < ffffffff8147efaa >] SyS_msgget +0 x7a /0 x90 ipc / msg . c :241[ < ffffffff81ee3e11 >] en tr y_S YS CA LL_ 64 _fa st pa th +0 x31 /0 x95arch / x86 / entry / entry_64 . S :188Листинг 14:мьютексов4.2ОтчетдетектораKernelThreadSanitizer:описаниезахваченныхПроизводительностьПри тестировании детектора учитывались потребление памяти и замедлениепроизводительности ядра.
Максимальный расход памяти детектором достигает 16ГБ в обычном режиме и 1 ГБ в per-cpu режиме. Производительность ядра засчетработы детектора замедляется в среднем в 6 раз при работе детектора в обычномрежиме и в 2 раза в per-cpu режиме.Большой расход памяти детектором в обычном режиме, связан с большим количеством примитивов синхронизации и большим потенциальным количеством потоков, которые создает ядро. При нормальной работе ядра количество примитивов синхронизации может достигать 106 , а количество одновременно существующих потоковна определенных этапах загрузки близко к 103 . Чем больше число примитивов син30Таблица 1: Сравнение детекторов KernelStrider, RaceHound и KernelThreadSanitizerKernelStrider RaceHound KTSANОбработка высокоуровневой синхронизацииДаДаДаОбработка низкоуровневой синхронизацииНетДаДаОтсутствие ложных срабатыванийНетДаДаОтсутствие пропусков ошибокНетНетНетПоиск ошибок во всем ядреНетНетДаПоиск ошибок в планировщике ядраНетНетДахронизации и потоков, тем больше памяти расходуется на векторные часы.
Напомню,что размер векторных часов равен числу потоков, а их количество пропорциональноколичеству примитивов синхронизации. В per-cpu режиме, количество потоков снижается на порядки и размер памяти, необходимой для хранения векторных часовсущественно уменьшается.В таблице 1 показано сравнение детекторов KernelStrider, RaceHound и разработанного детектора KernelThreadSanitizer. Как видно из таблицы, преимуществамидетектора KernelThreadSanitizer является возможность поиска состояний гонок вовсем коде ядра включая планировщик и отсутствие ложных срабатываний.4.3Найденные ошибкиТестирование ядра с помощью динамических детекторов осложняется отсут-ствием набора модульных тестов с достаточно высоким покрытием кода1 .
В результате, приходится использовать рандомизированное тестирование.Trinity [33] – это одна из утилит, применяемая для рандомизированного тестирования ядра Linux. Принцип ее работы заключается в вызове системных вызовов сослучайными аргументами. Однако, передавая в системные вызовы абсолютно случайные аргументы, их выполнение часто не проходит дальше, чем проверка этих аргументов на корректность. Trinity поступает умнее и передает не совсем случайныеаргументы. Например, при запуске она генерирует список всех доступных файловых1«"Regression testing"? What’s that? If it compiles, it is good; if it boots up, it is perfect.», LinusTorvalds, Linux Kernel Mailing List, 1998-04-08.31дескрипторов и передает один из них в качестве аргумента тем системным вызовам,соответствующим аргументом которых должен быть именно файловый дескриптор.В процессе тестирования ядра с применением детектора KernelThreadSanitizerи утилиты Trinity детектор нашел большое количество состояний гонок.
К сожалению, большая их часть хоть и являются состояниями гонок по определению, но неприводят к существенным негативным последствиям, и разработчики ядра не заинтересованы в их исправлении. Примером такого состояния гонки является несинхронизированное обращение из нескольких потоков к переменной, которая являетсясчетчиком какой-либо незначительной статистики.Тем не менее, в процессе тестирования было найдено 23 настоящих ошибки:в основном обращения из нескольких потоков к разделяемой переменной, а такженесколько пропущенных барьеров доступов к памяти. Часть ошибок были подтверждены (14 ошибок) и исправлены (10 ошибок) разработчиками ядра.Одна из найденных ошибок оказалась серьезной уязвимостью подсистемы ядраIPC [34]. С помощью этой уязвимости возможно добиться повышения привилегийв системе.
Уязвимы оказались несколько современных дистрибутивов на базе Linuxвключая Ubuntu 12.04 LTS [35].5ЗаключениеДля автоматического поиска ошибок в ядре Linux был разработан детекторKernelThreadSanitizer. Основными преимуществами нового детектора над существующими является поддержка обработки низкоуровневых примитивов синхронизации,возможность поиска состояний гонок во всем ядре и качество отчетов о найденныхошибках. В результате тестирования ядра Linux с применением разработанного детектора, были найдены более 20 ранее неизвестных дефектов в ядре Linux, частькоторых была впоследствии исправлена разработчиками ядра.• Разработан новый метод поиска состояний гонок для ядра Linux, применимыйдля всего кода ядра. Разработанный метод не обладает ложными срабатываниями.• На основе разработанного метода реализован детектор состояний гонок для32ядра KernelThreadSanitizer.
Исходный код детектора открыт и доступен дляиспользования.• С помощью разработанного детектора найдено более 20 состояний гонок в ядреLinux, часть которых подтверждена и исправлена разработчиками ядра.• Детектор KernelThreadSanitizer внедрен в процесс тестирования ядра Linux вкомпании Google.• Результаты представлены на 57-й научной конференции МФТИ [36] и на конференции LinuxCon North America 2015 [37].33Список литературы[1] Leveson Nancy G, Turner Clark S. An investigation of the therac-25 accidents// Computer. — 1993.
— V. 26, no. 7. — P. 18–41.[2] Linux. — http://ru.wikipedia.org/wiki/Linux.[3] ХОРОШИЛОВ АВ, МУТИЛИН ВС, НОВИКОВ ЕМ. Анализ типовых ошибокв драйверах операционной системы linux // Труды Института системного программирования РАН. — 2012. — V. 22.[4] Ernst Michael D. Static and dynamic analysis: Synergy and duality // WODA 2003:ICSE Workshop on Dynamic Analysis / Citeseer. — 2003. — P. 24–27.[5] Исходжанов Т.Р. Автоматический поиск ошибок в компьютерных программахс применением динамического анализа: дис.
. . . канд. физ.-мат. наук / Т.Р. Исходжанов. — МФТИ. — 2013.[6] ThreadSanitizer. — https://github.com/google/sanitizers/wiki.[7] Helgrind: a thread error detector. —http://valgrind.org/docs/manual/hg-manual.html.[8] A theory of data race detection / Utpal Banerjee, Brian Bliss, Zhiqiang Ma,Paul Petersen // Proceedings of the 2006 workshop on Parallel and distributedsystems: testing and debugging / ACM. — 2006.
— P. 69–78.[9] Iso/iec14882:2011,standardforprogramminglanguagec++:Rep./Technical report, 2011. http://www.open-std.org/jtc1/sc22/wg21. — Executor:C++ Standards Committee et al.: 2011.[10] 2011 CWE/SANS Top 25 Most Dangerous Software Errors. — http://cwe.mitre.org/top25/.[11] GCC, the GNU Compiler Collection.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
