Разработка инструментария для повышения эффективности использования кэш-памяти процессора

Разработка инструментария для повышения эффективности использования кэш-памяти процессора

Введение

На протяжении длительного времени прогресс в области микропроцессоров фактически отождествлялся со значением тактовой частоты. Закон Мура гласит, что количество транзисторов <https://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B0%D0%BD%D0%B7%D0%B8%D1%81%D1%82%D0%BE%D1%80>, размещаемых на кристалле интегральной схемы, удваивается каждые 24 месяца, но возможно в ближайшее время он перестанет работать. В двухтысячном году в корпоративных планах производителей микропроцессоров значилось, что уже к концу десятилетия будет преодолен барьер в 10 ГГц. Но эти планы оказались неосуществимы.

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

Память в современных процессорах имеет иерархическую структуру. Кэш-память реализована на кристалле процессора, с целью улучшить время обращения к памяти. Однако может возникнуть проблема, заключающаяся в том, что локальные кэши процессоров содержат данные не согласованные с данными хранящимися в оперативной памяти. Для решения этой проблемы был разработан алгоритм когерентности, который называется MESI. Работа алгоритма когерентности влияет на производительность всей системы. В многопоточных приложениях может возникнуть ситуация, когда разные объекты делят одну и ту же кэш-линию процессора. Такую проблему называют ложным разделением данных или false sharing. Если происходит false sharing, то система должна согласовать данные в кэшах каждого процессора. Чтобы оптимизировать программу и более эффективно использовать кэш процессора, необходимо улучшить пространственную и временную локальность, а также необходимо заранее выравнивать код и данные. Часто разработчики не задумываются об этих особенностях, что является причиной медленного выполнения разработанного программного обеспечения. Возможно, применяется неэффективный алгоритм или разработчики нерезультативно работают с массивами или со структурами данных в многопоточной среде.

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

1. Постановка задачи

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

Статический анализатор должен выявлять обращения к массивам или структурам данных, т.е. перехватывать обращение к памяти. Библиотека времени выполнения должна взаимодействовать с модулем ядра передавая ему информацию об обращении к памяти. Модуль, обработав данные, передаст профилировщику информацию о физическом адресе.

Так как симулятору словарю и библиотеки времени выполнения необходимо обмениваться информацией, то необходимо средство межпроцессорного взаимодействия. Чтобы выявить какое средство производительней, в рамках дипломной работы необходимо разработать библиотеку, которая предоставляла бы возможности сразу нескольких механизмов межпроцессорного взаимодействия.

1. Описание предметной области

.1 Многопроцессорные системы

У всех мультипроцессоров каждый центральный процессор может адресоваться ко всей памяти. Однако по характеру доступа к памяти эти машины делятся на два класса. Мультипроцессоры, у которых каждое слово данных может быть считано с одинаковой скоростью, называются UMA-мультипроцессорами (Uniform Memory Access - однородный доступ к памяти). В противоположность им мультипроцессоры NUMA (NonUniform Memory Access - неоднородный доступ к памяти) этим свойством не обладают. [1]

.1.1 Архитектура многопроцессорных систем с общей шиной

В основе простейшей архитектуры мультипроцессоров лежит идея общей шины (см. рисунок 1).

Рисунок 1- Многопроцессорная система с обшей памятью

Несколько центральных процессоров и несколько модулей памяти одновременно используют одну и ту же шину для общения друг с другом. Когда центральный процессор хочет прочитать слово в памяти, он сначала проверяет, свободна ли шина. Если шина свободна, центральный процессор выставляет на нее адрес нужного ему слова, подает несколько управляющих сигналов и ждет, пока память не выставит нужное слово на шину данных. Если шина занята, центральный процессор просто ждет, пока она не освободится. В этом заключается проблема данной архитектуры. При двух или трех центральных процессорах состязанием за шину можно управлять. При 32 или 64 центральных процессорах шина будет постоянно занята, а производительность системы будет полностью ограничена пропускной способностью шины. При этом большую часть времени центральные процессоры будут простаивать. [1]

Чтобы решить эту проблему необходимо добавить каждому центральному процессору кэш. Кэш может располагаться на кристалле центрального процессора. Так как большее количество обращений к памяти будет удовлетворенно кэшем, возможно будет использовать большее число процессоров. Как правило, кэширование выполняется не для отдельных слов, а для блока данных по 32 или по 64 байта. При обращении к слову весь блок считывается в кэш центрального процессора, обратившегося к слову. [1]

.1.2 Архитектура многопроцессорных систем с неоднородным доступом к памяти

В вычислительных системах с неоднородным доступом к памяти реализована технология NUMA (Non-Uniform Memory Access). Технология неоднородного доступа к памяти позволяет создавать крупномасштабные вычислительные системы. В архитектуре NUMA память физически распределена между процессорами, но логически общедоступна. Это позволяет сохранить преимущества архитектуры с единым адресным пространством, а также ощутимо расширить возможности масштабирования ВС. Архитектура NUMA систем показана на рисунке 2.

Рисунок 2 - Архитектура мультипроцессоров NUMA

У машин NUMA есть ключевые характеристики, которые отличают их от других мультипроцессоров.

·Имеются два или более узлов, каждый из которых может быть представлен процессорным элементом с кэш-памятью.

·Каждый узел имеет локальную память, которая рассматривается как часть глобальной памяти системы.

·Узлы соединены посредством высокоскоростной сети.

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

·Когерентность кэшей обычно поддерживается аппаратными средствами (ccNUMA), но возможен вариант без таких средств (nccNUMA).

·Вычислительная система управляется единой операционной системой, как в SMP, но возможен вариант с разбиением, где каждый раздел работает под управлением своей операционной системой.

.2 Многоядерные процессоры

Многоядерная архитектура - это архитектуры процессоров, состоящих из двух или более вычислительных ядер в одном процессоре. Ядром процессора называют систему исполнительных устройств (набор арифметико-логических устройств) предназначенных для обработки информации. Многоядерный процессор размещается на одном процессорном разъеме. Система воспринимает каждое вычислительное ядро, как отдельный логический процессор, обладающий всеми необходимыми исполняющими ресурсами.

Рисунок 3 - Структура многоядерного процессора

Работа, выполняемая в традиционных микропроцессорах одним ядром, может быть разделена между несколькими вычислительными ядрами, таким образом, многоядерный процессор может выполнять большее количество инструкций, улучшив работу пользователей с операционной системой. Чтобы это стало возможным, программное обеспечение распределять нагрузку между вычислительными ядрами процессора. Эта функциональность называется параллелизмом на уровне потоков или многопоточной обработкой.

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

В многоядерных процессорах каждое ядро может поддерживать технологию SMT (Simultaneous multithreading), позволяющую выполнять несколько потоков вычислений на каждом ядра. На процессорах, выпускаемых компаний Intel, данная технология называется Hyper-threading. В процессорах с поддержкой Hyper-Threading, набор регистров имеется у каждого логического процессора, но не поддерживается одновременное выполнение инструкций выборки/декодирования в двух потоках. Такие инструкции будут выполняться поочередно.

Рассмотрим пример, когда применение технологии Hyper-Threading оправдано. Предположим, что процессор выполняет поток инструкций первого логического процессора. Выполнение потока может приостановиться по одной из причин:

·произошёл промах <https://ru.wikipedia.org/wiki/%D0%9A%D1%8D%D1%88_%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D1%81%D1%81%D0%BE%D1%80%D0%B0> при обращении к кэшу <https://ru.wikipedia.org/wiki/%D0%9A%D1%8D%D1%88_%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D1%81%D1%81%D0%BE%D1%80%D0%B0>;

·неверно предсказано ветвление <https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%B4%D1%81%D0%BA%D0%B0%D0%B7%D0%B0%D0%BD%D0%B8%D0%B5_%D0%B2%D0%B5%D1%82%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9>;

·ожидается результат предыдущей инструкции.

Центральный процессор при включенной поддержке Hyper-Threading не будет простаивать, а передаст управление второму логическому процессору. Следовательно, пока один логический процессор ожидает, вычислительные ресурсы процессора будут использованы другим логическим процессором.

.3 Кэш память

На ранних компьютерах иерархия памяти была представлена три уровнями: регистры процессора, оперативная память и память на внешних носителях. Чтобы уменьшить разницу в скорости работы центрального процессора и оперативной памяти, системные инженеры приняли решение разместить на кристалле процессора маленькую SRAM память, которую они назвали кэш-памятью. Скорость обращения к кэшу первого уровня равнялся 4 тактам процессора. В дополнении к кэшу первого уровня было принято решении создать кэш второго уровня большего размера. Скорость обращения за данными хранящимися в кэше L2 равняется 10 тактам процессора. Современные процессоры включают еще больший кэш, называемый L3 кэш, находящийся между кэшем L2 и основной памятью и доступ к которому равен 50 тактам процессора. Основная структура одинакова для кэша любого уровня. [2]

.3.1 Структура кэша

Рассмотрим компьютерную систему, где адрес памяти равен m бит и имеется M=2m уникальных адресов. Кэш организован как массив, состоящий из S=2s множеств. На рисунке 3.4 показан пример множественно-ассоциативного кэша.

Каждое множество состоит из кэш-линий. Каждая линия содержит блок данных размеров B=2b байт, бит корректности, который показывает, что в кэш-линии хранится значимая информация и таг поле равное t = m - (b + s) бит. Таг поле уникально идентифицирует кэш-линию в конкретном множестве. [2]

Обычно, структуру кэша можно представить в виде кортежа (S, E, B, m). Емкость кэша вычисляется, как С = S * E * B без учета битов поля таг и бита корректности. Когда центральному процессору поступает инструкция чтения данных из памяти по адресу A, он посылает адрес A в кэш. Если в кэше хранится копия данных по адресу A, то блок данных немедленно отправляется CPU. Кэш может найти запрашиваемые данные, просто извлекая биты из адреса, подобно хэш-таблицы с чрезвычайно простой хэш-функцией. Логическое разделение адреса на составные части показана на рисунке 4.

Есть несколько структур кэшей, разница между которыми состоит в том, сколько кэш-линий хранится во множестве. Кэш состоящий только из одной кэш-линии называется кэшем прямого отображения.

Рисунок 4 - Структура множественно-ассоциативного кэша

Будем предполагать, что у нас имеется система с CPU, регистрами, кэшем первого уровня и оперативной памятью. Когда CPU выполняет инструкцию чтения данных, он запрашивает их из кэша L1. Если в кэше имеется копия запрашиваемых данных, то это cache hit и данные будут незамедлительно возвращены центральному процессору. Однако, если происходит cache miss, т.е. запрашиваемые данные отсутствуют, кэш L1 запросит копию данных из оперативной памяти. Пример промаха по кэшу показан на рисунке 3.5. Прежде чем извлечь блок данных необходимо выполнить три шага: выбрать множество, определить кэш-линию, извлечь данные.

Чтобы выбрать множество из адреса, который передаются кэшу, извлекаются s биты, которые уникально идентифицируют множество. После того как было найдено множество на следующем шаге извлекаются биты поля таг, чтобы определить кэш-линию. Копия данных будет передана серверу, если и только если бит корректности установлен в единицу и толе таг в адресе равняется полю таг в кэш-линии. В противном случае произойдет cache miss и блок данных, как было сказано выше, будет запрошен с оперативной памяти. Если произошел cache hit, то по смещению в кэш блоке считываем необходимые данные.

Рисунок 5 - Пример возникновения промаха по кэшу

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

Множественно-ассоциативный кэш подобен кэшу прямого отображения за исключением того, что множество содержит более одной кэш-линии. Если данные имеются в кэше, то происходит cache hit, иначе cache miss. Если во множестве есть свободная линия, то данные запрошенные из оперативной памяти будут скопированы в неё. Иначе будет применен алгоритм замещения, который выберет линию, которая будет замещена. Например, политика least frequently used (LRU) замещает линию, которая наименее часто использовалась. Политика least recently used (LRU) вытесняет линию, которая не использовалась дольше всех. Алгоритм Белади, считается наиболее эффективным алгоритмом замещения, замещает ту кэш-линию, данные в которой не потребуется в течение длительного времени, как правило, на практике этот алгоритм не реализуется. Политика Random Replacement (RR) случайным образом выбирает кандидата на замещение и отбрасывает его при необходимости освободить место в кэше. Этот алгоритм не требует хранить историю обращений к кэш-линии. Из-за своей простоты использовался в процессорах ARM.

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

.3.2 Ложное разделение данных

В симметричных мультипроцессорных системах, каждый процессора имеет локальный кэш. Система должна гарантировать согласованность данных в кэшах процессоров. Ложное разделение данных (False sharing) происходит, когда потоки, выполняющиеся на разных процессорах, изменяют переменные, которые находятся в одной и той же строке кэша. Это делает строку кэша недействительной, заставляя систему задействовать механизм когерентности кэша, что вредит производительности всей системы. [7]

Ложное разделение данных - это хорошо известная проблема, влияющая на производительность в многопроцессорных системах. На рисунке 3.7, показан пример возникновения ложного разделения данных.

Для лучшего понимания ситуации приводящей к False sharing необходимо рассмотреть реальный пример кода (см. листинг 3.1).

В листинге 3.1, массив sum используется всеми потоками, что конкретно в данном случае приводит к ложному разделению данных. Этот массив достаточно мал, чтобы каждая ячейка массива поместилась в одной строке кэша. Когда потоки параллельно изменяют данные хранящиеся в массиве, т.е. каждому потоку соответствует ровно одна ячейка массива, аннулируются все строки кэша для всех процессоров.

Рисунок 6 - Ситуация приводящая к False sharing

На рисунке 6, потоки 0 и 1, обращаются к переменным, которые хранятся в смежных адресах памяти и делят одну и ту же кэш-линию. Хотя потоки изменяют разные переменные, кэш-линия становится недействительной, заставляю систему обновить память для поддержки когерентности кэша. Для обеспечения согласованности данных в нескольких кэшах процессоры компании Intel реализуют алгоритм MESI. При первой загрузке строки кэша, процессора маркирует её, как строку с эксклюзивным доступом. Пока кэш-линия помечена как эксклюзивная, последующие операции с данной кэш-линией могут свободно использовать хранящиеся в ней данные. Если процессор замечает, что другим процессором используется та же кэш-линия, он помечает ее, как кэш-линию с общим доступом. Если в одном из процессоров кэш-линия помечается, как модифицированная, то для всех других процессоров она становится недействительной. Ложное разделение данных может заметно ухудшить производительность приложения. Компиляторы могут оптимизировать код, устраняя ситуацию ложного разделения данных. Но для этого необходимо скомпилировать программу с оптимизацией, иначе проблема ложного разделения данных не будет рассматриваться компилятором.

Листинг 1 - Пример кода, в котором не учитывается проблема False sharing

2. Основная часть

2.1 Взаимодействие user space с kernel space

В то время как сетевые и дисковые файловые системы позволяют пользователю работать с информацией, хранящейся вне ядра, специальные файловые системы могут предоставить программам и системным администраторам простой способ манипулирования структурами данных ядра и реализации особых возможностей операционной системы. В таблице 1 перечислены наиболее распространенные специальные файловые системы, используемые в Linux. Для каждой из них указана точка монтирования и приведено краткое описание. [3]

Таблица 1 - Самые распространенные специальные файловые системы

НазваниеТочка монтированияОписаниеbdevНетБлочные устройстваbinfnt_miscЛюбаяРазличные исполняемые форматыeventpollfsНетИспользуется механизмом эффективного опроса событийpipefsНетКаналыргос/procОбщая точка доступа к структурам данных ядраrootfsНетПредоставляет пустой корневой каталог на этапе загрузкиshimНетОбласти памяти, совместно используемые при межпроцессорном взаимодействииmqueueЛюбаяИспользуется для реализации очередей сообщений POSIXsockfsНетСокетыsysfs/sysОбщая точка доступа к системным даннымtmpfsЛюбаяВременные файлы (хранятся в оперативной памяти, если не выполняется подкачка)usbfs/proc/bus/usbUSB-устройстваdevfs/devДинамическая файловая система, предназначенная для управления файлами устройствСпециальные файловые системы не привязаны к физическим блочным устройствам. Однако ядро присваивает каждой смонтированной специальной файловой системе фиктивное блочное устройство, у которого старший номер равен нулю, а в качестве младшего номера берется произвольное значение (индивидуальное у каждой файловой системы). [3]

Файловая система devfs монтируется в каталог /dev. В этом каталоге размещены описание устройств системы. В ОС Linux всё рассматривается, как файл, даже такие устройства, как порты, жёсткие диски и т.д. Для всех таких устройств существует запись в каталоге /dev.

Ядро Linux предоставляет механизмы создания записей в специальных файловых системах, т.е. для взаимодействия с модулем, в момент его инициализации необходимо вызвать специальные функции, которые позволят управлять в дальнейшем модулем. Каждая файловая система /proc, /dev или /sys, предоставляет набор функций и структур данных, которые используется, для взаимодействия между пространством пользователя и пространством ядра. В рамках дипломной работы при реализации модуля, использовались возможности файловой системы devfs и procfs.

В системе Linux каждому устройству соответствует запись в каталоге /dev. Все устройства характеризуется двумя номерами: старшим номером, определяющим класс устройства, и младшим номером, указывающим внутри своего класса на конкретный экземпляр устройства.

Старший и младший номер уникально характеризуют устройства в системе. Модуль соединяется с устройством не по имени его в системе, а по старшему и младшему номеру устройства. Не запрещается использовать при регистрации устройства, заранее зарезервированные номера из файла Documentation/devices.txt, но при этом возможен конфликт с уже используемым оборудованием.

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

Символьное устройство в ядре описывается структурой типа struct cdev. Данная структура объявлена в файле /linux/cdev.h. Объявление структуры struct cdev показано в листинге 1.

Листинг 1 - Объявление структуры struct cdev

Тип dev_t - используется, чтобы хранить старший/младший номер устройства.

Структура file_operations <#"justify">Листинг 2 - Объявление структуры struct kobject

Как уже говорилось, ядро использует структуры типа cdev для объявления символьных устройств. До того, как будут вызваны операции данного устройства, мы должны выделить и зарегистрировать хотя бы одну структуру данных типа cdev. Для инициализации структуры необходимо вызвать функцию cdev_init(). При вызове функции необходимо передать структуру file_operations, в которой перечислены функции ввода/вывода.

После инициализации структуры, необходимо вызывать функцию cdev_add(), которая сообщит ядру о том, что происходит регистрация нового устройства в системе. При вызове cdev_add() необходимо учесть, некоторые особенности. Во-первых, вызов может потерпеть неудачу. Если он вернул код ошибки, то устройство не было добавлено в систему. Если cdev_add() выполняется успешно, то устройство считается работоспособным. Запрещено вызывать функцию cdev_add(), пока драйвер устройства не полностью готов проводить операции.

Чтобы удалить символьное устройство из системы, необходимо вызвать функцию cdev_del().

Обращаться к структуре cdev после передачи её в cdev_del() нельзя. В старых версия ядра Linux, например 2.6, можно увидеть, что почти все символьные устройства не пользуются интерфейсом cdev, они используют два устаревших вызова для регистрации устройства в системе, которые показаны в листинге 3.

Листинг 3 - Объявление устаревших функций регистрации устройств

Работа с файловой системой procfs схожа с принципами работы с файловой системой devfs. Первоначально файловая система procfs разрабатывалась как средство получения информации о выполняющихся процессах в системе. Но из-за ее удобства многие подсистемы ядра Linux стали использовать эту файловую систему, как средство получения информации и конфигурирования. Файловая система procfs имеет иерархическую структуру в виде каталогов, для того чтобы структурировать информацию запрашиваемую из ядра.

Каталог /proc напрямую контролируется ядром Linux. Из-за того, что он предоставляет информацию, получаемую из ядра, то каждый файл в каталоге имеет нулевую длину. Если выполнить операцию чтения для какого-нибудь файла, то в терминале отобразится соответствующая информация. Это объясняется тем, что виртуальные файловые системы, регистрируются на уровне VFS (Виртуальная Файловая Система), и нет существенной разницы в работе с виртуальным файлом или обычным.

Основная структура, которая полностью описывает механизмы работы с каталогом proc, является struct proc_dir_entry, объявление структуры показано в листинге 4.

Листинг 4 - Объявление структуры

Чтобы создать запись в каталоге proc необходимо вызвать функцию proc_create <#"justify">Листинг 5 - Реализация функции

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

Чтобы удалить запись из каталога proc необходимо воспользоваться функцией proc_remove <#"justify">Листинг 6 - Объявление необходимых функций при создании каталогов

.2 Средства синхронизации ядра Linux

Можно считать ядро неким сервером, отвечающим на запросы. Эти запросы поступают либо от процесса, выполняемого процессором, либо от внешнего устройства, генерирующего запрос на прерывание. Фрагменты кода ядра выполняются не последовательно, а вперемешку. В результате между ними может возникнуть конкуренция за ресурсы, и эту ситуацию следует контролировать с помощью соответствующих приемов синхронизации. [3]

С появлением многоядерных процессоров, появились такие понятия, как конфликт одновременного обращения и критическая область. Те же определения справедливы не только к пользовательским процессам, но и в отношении управляющих трактов ядра. Конфликт одновременного обращения может возникнуть, когда результат вычислений зависит от вложенности двух и более перемежающихся трактов ядра. Критическая область - это участок кода, который должен быть до конца выполнен трактом ядра, вошедшим в него, прежде чем в него сможет войти другой тракт ядра. Разработчики должны быть исключительно внимательны при идентификации критических областей в обработчиках исключений, обработчиках прерываний, функциях отложенного выполнения и потоках ядра. Когда критическая область локализована, она должна быть соответствующим образом защищена, чтоб в любой момент времени внутри ее находилось не более одного управляющего тракта ядра. [3]

Для синхронизации процессов в ядре используются разные примитивы синхронизации. Приведу список примитивов синхронизации, которые применяются в данный момент в ядре:

·Атомарные переменные

·Спин-блокировки

·Последовательные блокировки

·Семафоры

·Семафоры чтения/записи

·Мьютексы реального времени

·Механизмы ожидания завершения

В ядре также существует конкуренция за ресурсы, при реализации модуля ядра необходимо позаботится о защиты критических участков кода, где возможно обращения к общим ресурсам несколькими потоками. Из перечисленного списка примитивов синхронизации, в модуле ядра применяется только три. Атомарные переменные и семафоры применяются для синхронизации операций чтения и записи, выполняются эти операции, когда процесс из пользовательского пространства обращается к модулю ядра. Спин-блокировки используются для реализации потокобезопасной очереди. Необходимость в очереди возникла для того чтобы при обращении к ядру запросы ставились в очередь на ожидание, для того чтобы улучшить производительность работы операций ввода/вывода.

.2.1 Реализация семафоров в Linux

Чтобы использовать семафоры код ядра должен подключить <asm/semaphore.h>. Семафоры могут быть объявлены и проинициализированы разными способами. Первый способ, создание семафора и инициализация его затем с помощью sema_init(struct semaphore *sem, int val), где аргумент val - является начальным значением семафора.

Часто семафоры применяются в режиме мьютекса. Ядро предоставляет набор функций и макросов, чтобы использовать семафор в качестве мьютекса. Мьютекс можно проинициализировать с помощью макросов, объявление которых показано в листинге 7.

Листинг 7 - Объявление макросов создания мьютекса

DECLARE_MUTEX(name);

DECLARE_MUTEX_LOCKED(name);

После вызова макросов мьютекс будет объявлен с именем name и инициализирован в 1 (DECLARE_MUTEX) или в 0 (DECLARE_MUTEX_LOCKED). Мьютекс имеет заблокированное состояние, если он был инициализирован значением 0. Поэтому он должен быть явным образом разблокирован до того, как потоку будет разрешён доступ.

Для захвата семафора служит функция down(), также существует различные варианты данного вызова. Операция down() уменьшает значение семафора, и тракт ядра пытающий захватить семафор может перейти в режим ожидания, до тех пор, пока семафор не освободится. В ядре реализовано три версии вызова down(), объявление которых показано в листинге 8.

Листинг 8 - Объявление функций захвата семафора

Функция down() уменьшает значение семафора и ожидает неограниченное время, а вот функция down_interruptible() выполняет те же самые действия, но она может быть прервана. Прерываемая версия вызова наиболее часто применяется при реализации критических секций в коде ядра, так как она позволяет процессу в режиме ожидания быть прерванным.

Функция down_interruptible() требует дополнительные проверки при ее использовании, т.е. если операция была прервана, функция возвратит значение не равное нулю, которое нужно корректным образом обработать.

Функции down_trylock() не переходит в режим ожидания, если семафор был захвачен другим потоком и возвратит значение не равное нулю в данном случае. Если функция down() выполняется успешно в каком-либо потоке, то считается, что этот поток владеет семафором. Захват семафора, означает право на доступ к критической секции. После того, как все операции в критической секции будут выполнены, семафор должен быть разблокирован вызовом функции up().

Как только функция up() была вызвана, поток больше не владеет семафором. Необходимо, чтобы каждый поток, который получил права владения семафором, освободил его вызовом up().

.2.2 Реализация спин-блокировок

Семафоры часто используемый примитив синхронизации, но это не единственный примитив применяем для реализации критических секций. Существует примитив, называемый спин-блокировкой. Спин-блокировка имеет только два состояния: "Свободна" и "Заблокирована". Для хранения того или иного состояния используется только один бит. Поток желающий овладеть блокировкой, проверяет текущее состояние блокировки. Поток продолжит работу в критической секции, только в случае если она окажется свободной. Если блокировка уже была захвачена, поток желающий получить блокировку перейдет в короткий цикл ожидания, где постоянно будет проверять значение блокировки.

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

В обработчиках прерываний разрешается использовать спин-блокировки, в отличие от семафоров, которые переводят процесс в состояние ожидания. Блокировка может быть использована в обработчике прерывания, только если перед захватом блокировки были запрещены все прерывания. Иначе может возникнуть ситуация, когда прерывается выполнения кода из-за вызова обработчика прерывания, где был выполнен захват блокировки, и обработчик также пытается овладеть данной блокировкой, что приведет к катастрофическим последствиям.

Для использования спин-блокировок необходимо подключить файл <linux/spinlock.h>. Спин-блокировка описывается типом spinlock_t.

Как и все другие примитивы, спин-блокировка должна быть проинициализирована. Существует несколько вариантов инициализации, можно использовать макрос SPIN_LOCK_UNLOCKED или вызвать явно функцию spin_lock_init.

Перед тем как войти в критическую секцию поток должен захватить блокировку вызовом void spin_lock(spinlock_t *lock).

Для освобождения полученной блокировки необходимо вызвать функцию void spin_unlock(spinlock_t *lock).

Ядро предоставляет механизм, который позволяет удобным образом запретить прерывания и захватить блокировку одновременно. Пример использования показан в листинге 9.

Листинг 9 - Пример использования механизма запрета прерывания

spinlock_t mr_lock = SPIN_LOCK_UNLOCKED;unsigned long flags;spin_lock_irqsave(&mr_lock, flags);/* критический участок кода... */spin_unlock_irqrestore(&mr_lock, flags);

Вызов spin_lock_irqsave() сохранит текущее состояние системы прерываний, запретит прерывания и попытается захватить блокировку. Функция spin_unlock_irqrestore(), наоборот освобождит блокировку и восстанавливит предыдущее состояние.

2.2.3 Реализация атомарных операций

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

Ядро предоставляет два набора интерфейсов для выполнения атомарных операций: один - для работы с целыми числами, а другой - для работы с отдельными битами. Эти интерфейсы реализованы для всех аппаратных платформ, которые поддерживаются операционной системой Linux. Большинство аппаратных платформ поддерживают атомарные операции или непосредственно, или путем блокировки шины доступа к памяти при выполнении одной операции (что в свою очередь гарантирует, что другая операция не может выполниться параллельно). Это как-то позволяет справиться с проблемой в случае аппаратных платформ, таких как SPARC, которые не поддерживают базовых машинных инструкций для выполнения атомарных операций. [4]

Средства выполнения атомарных операций с целыми числами работают с типом данных atomic_t. Вместо того, чтобы использовать функции, которые работают непосредственно с типом данных int языка Си, по ряду причин используется специальный тип данных. Во-первых, функции, которые выполняют атомарные операции, принимают только аргументы типа atomic_t, это гарантирует, что атомарные операции выполняются только с данными этого специального типа. В то же время это также гарантирует, что данные этого типа не смогут передаваться в другие функции, которые не выполняют атомарных операций. [4]

Объявления всех атомарных операций, находятся в заголовочном файле <asm/atomic.h>. Для некоторых аппаратных платформ существуют дополнительные возможности, которые характерны только для конкретной платформы. Основные методы и макросы для работы с атомарными операциями перечислены в таблице 2. Атомарные операции реализуются, как встроенные функции с ассемблерными вставками.

Таблица 2 - Полный список целочисленных атомарных операций

Атомарная операцияОписаниеATOMIC_INIT(int i)Инициализировать атомарную переменную значением iint atomic_read(atomic_t *v)Считать значение атомарной переменнойvoid atomic_set(atomic_t *v, int i)Присвоить атомарной переменной значение ivoid atomic_add(int i, atomic_t *v)Увеличить значение атомарной переменной на ivoid atomic_sub(int i, atomic_t *v)Уменьшить значение атомарной переменной на ivoid atomic_inc(atomic_t *v)Инкрементировать значение на 1void atomic_dec(atomic_t *v)Декрементировать значение на 1int atomic_sub_and_test(int i, atomic_t *v)Вычесть значение i с v и проверить, не равно ли значение атомарной переменной нулюint atomic_add_negative(int i, atomic_t *v)Сложить значение i с v и проверить, не является ли значение отрицательнымint atomic_dec_and_test(atomic_t *v)Декрементировать значение на 1 и проверить, не равно ли значение атомарной переменной нулюint atomic_inc_and_test(atomic_t *v)Инкрементировать значение на 1 и проверить, не равно ли значение атомарной переменной нулю

.3 Очереди ожиданий Linux

При реализации модуля ядра возникла необходимость в использовании блокируемого ввода/вывода. Если мы считываем информацию из модуля ядра, то может возникнуть ситуация, приводящая к ожиданию запрашиваемых данных. Такую ситуацию нужно корректно обработать, либо вернуть признак ошибки, либо ожидать пока данные не станут доступны. В Linux есть множество вариантов реализации ожидании какого-либо события, например, примитив синхронизации называемый механизм ожидания завершения. В рамках дипломной работы, используются возможности очередей ожидания реализованных в ядре Linux. Данный механизм существует ещё с версии ядра 2.4 и при переносе на более старые платформы требует меньше исправлений в исходном коде.

Очередь ожиданий - это очередь процессов, которые ожидают наступления конкретного события в системе (см. рисунок 7).

Рисунок 7 - Очередь ожиданий в ядре версии 2.4

Объявление и инициализация очереди показана в листинге 10.

Листинг 10 - Пример объявления и инициализации очереди

Очередь можно инициализировать во время компиляции используя специальный макрос DECLARE_WAIT_QUEUE_HEAD (my_queue). Как только очередь ожидания объявлена и проинициализирована процесс может использовать ее, чтобы ожидать конкретного события. Процесс может заснуть, вызвав один из вариантов sleep_on(), в зависимости от того, как долго процесс будет ожидать и может ли он быть прерван при появлении прерывания.

Вызов sleep_on() ставит процесс в очередь. Функция sleep_on() имеет недостаток, т.е. если процесс ожидает появление события, то должно гарантироваться, что данное событие наступит или в противном случае процесс будет ожидать вечно.

Прерываемый вариант interruptible_sleep_on() работает так же, как sleep_on(), за исключением того, что процесс может быть прерван сигналом. Данная функция, использовалась разработчиками ядра, прежде чем появился вызов wait_event_interruptible().

Листинг 11 - Объявление функций переводящих процесс в состояние ожидания

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

.4 Связанные списки ядра Linux

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

Чтобы воспользоваться списками ядра, необходимо включить struct list_head в качестве дополнительной переменной внутрь другой структуры. Пример применения struct list_head для реализации потокобезопасной очереди, показан в листинге 12.

Списки должны быть проинициализированы перед использованием с помощью макроса INIT_LIST_HEAD или с помощью LIST_HEAD. Большинство функций для работы со списками определены в заголовочном файле <linux/list.h>.

Листинг 12 - Объявление структур используемых при реализации потокобезопасной очереди

Рисунок 8 - Структура данных list_head

Макрос list_add(struct list_head *new, struct list_head *head) добавляет новую запись сразу же после головы списка, т.е. в начало списка. Таким образом, она может быть использована для создания стеков.

Макрос list_add_tail(struct list_head *new, struct list_head *head) добавляет элемент new перед головой списка, т.е. в конец списка. Данная функция может быть использована для создания очередей.

Макросы list_del(), list_del_init() удаляют запись из списка. Если потребуется, чтобы запись была вставлена в другой список, необходимо использовать list_del_init(), которая инициализирует заново указатели связного списка. Макросы list_move() и list_move_init() удаляют запись из своего текущего списка и добавляют ее в начало головы.

Пример реализации макроса list_entry() в ядре linux, показан в листинге 13.

Листинг 13 - Реализация макроса list_entry

Макрос list_entry() развернется в следующую запись, как показано в листинге 14, если использовать его для структуры queue_t.

Листинг 14 - Пример вызова макросы для структуры queue_t

Прием из листинга 4.14 широко известен. Используя указатель на поле типа struct list_head, макрос list_entry() вычисляет начальный адрес самой структуры. Чтобы выполнить такой расчёт, необходимо рассчитать смещение struct list_head от начало структуры. Потом вычисляется смещение члена типа struct list_head по отношению к переданному указателю.

Реализация потокобезопасной очереди на основе применения структуры list_head

Очередь создается посредством вызова функции queue_create(), которая в первую очередь выделяет память для «головы» очереди типа queue_t, а затем инициализирует спин-блокировку, вызывая функцию spin_lock_init().

Чтобы поместить в очередь элемент необходимо вызвать функцию queue_enqueue() передав в качестве первого аргумента указатель на очередь, а вторым аргументом сам элемент. Элемент помещается в конец очереди при помощи вызова list_add_tail(). Перед тем, как добавить элемент в очередь, захватывается блокировка. Реализация данной функции показана в листинге 15.

Листинг 15 - Реализация функции

Чтобы извлечь из очереди элемент необходимо вызвать функцию queue_dequeue(). Перед тем как извлечь элемент, нужно получить указатель на структуру типа queue_item_t при помощи макроса list_first_entry(), данный макрос вычисляет смещение структуры типа struct list_head в структуре queue_item_t и возвращает указатель на начало структуры queue_item_t.

queue_enqueue()

Также как и в случае функции queue_enqueue(), необходимо захватить блокировку перед извлечением данных. Реализация данной функции показана в листинге 16.

Листинг.16 - Реализация функции

_dequeue()

void* queue_dequeue(queue_t *q)

{_item_t *queue_item;*item;(queue_is_empty(q))NULL;_lock(q);_item =_first_entry(&(q->list), queue_item_t, list);= queue_item->item;_del(&(queue_item->list));(queue_item);_unlock(q); item;

}

Для захвата блокировки вызывается функция queue_lock(), а для освобождения queue_unlock(). Реализация функций показана в листинге 17.

Листинг 17 - Пример реализации функции queue_lock() и queue_unlock()

.5 Реализация модуля ядра в Linux

Перед тем как будут вызваны операции чтения/записи модуля ядра, необходимо с начало открыть файл в каталоге dev. При загрузке модуля вызывается функция инициализации mcva_init(), в которой осуществляется инициализация ресурсов и создается запись в каталоге /dev. В нашем случае модуль зарегистрирован под именем mcva. Во время системного вызова open() в модуле ядра происходит инициализация всех дополнительных структур данных, которые будут использоваться в дальнейшем. Например, инициализация потокобезопасной очереди происходит именно при открытии файла. Реализация функции open() в модуле ядра, показана в листинге 18.

Листинг 18 - Пример реализации функции open()

int mcva_open(struct inode *inode, struct file *file)

{_t *__module;

__module = kmalloc(sizeof(icva_t), GFP_KERNEL);(__module == NULL) -ENOMEM;((__module->data_queue = queue_create()) == NULL)-ENOMEM;_icva(__module);>private_data = __module;0;

}

Для взаимодействия пользовательского пространства и пространства ядра были реализованы две основные функции - это чтение и запись данных из модуля. Чтобы увеличить производительность и сократить время выполнения операции записи, было принято решения использовать в ядре потокобезопасную очередь. Выше было сказано, про то, что операции ввода/вывода должны быть блокирующими. Данную возможность можно реализовать, воспользовавшись очередями ожиданий. Если пользовательский процесс вызывает операцию чтения и очередь пуста, то процесс ожидает до тех пор, пока не выполнится операция записи. Как только выполняется операция записи, атомарно устанавливается флаг, сигнализирующий о том, что данные доступны. Возможна ситуация, когда одновременно будут выполняться две операции чтения из файла /dev/mcva. Чтобы избежать гонки за данными в начале вызова операций ввода/вывода осуществляется захват семафора посредством вызова down_interruptible(), а в конце его освобождение с помощью вызова функции up().Реализация операции записи, показана в листинге 19.

Листинг 19 - Пример реализации операции записи

static ssize_t mcva_bwrite(struct file *file,

const char __user *buf, size_t count, loff_t *f_pos)

{ret;_data_t *input_data;_t *__module = file->private_data;(down_interruptible(&__module->semwrite))-ERESTARTSYS;((input_data = (sizeof(in_data_t), GFP_KERNEL)) == NULL) {(KERN_DEBUG

"<%s> kmalloc failed\n", __func__);(&__module->semwrite);-ENOMEM;

}(copy_from_user(input_data, buf, count)) {(&__module->semwrite);-EFAULT;

}((ret = _enqueue(__module->data_queue,

(void *)input_data)) < 0) {(KERN_DEBUG

"<%s> queue_enqueue failed\n", __func__);(&__module->semwrite);ret;

}(atomic_read(&__module->readiness_read) == 0) {_set(&__module->readiness_read, 1);_up_interruptible(&__module->readq);

}(&__module->semwrite);count;

}

Ядро операционной системы располагается в своем собственном адресном пространстве, как и все пользовательские процессы в системе. При копировании данных из пространства пользователя в пространство ядра необходимо использовать специальные функции copy_to_user(), copy_from_user().

Функция copy_to_user() копирует данные из пространства ядра в пространство пользователя. Первым аргументом этой функции является указатель на буфер пространства пользователя, второй аргумент указывает на буфер ядра и в третьем аргументе задается размер блока в байтах. В случае успешного вызова функция возвратит ненулевое значение.

Функция copy_from_user() копирует данные из пространства пользователя в буфер пространства ядра. Первым аргументом этой функции является указатель на буфер в пространстве ядра, второй аргумент указывает на буфер источник в пространстве пользователя и в третьем аргументе передается размер копируемого блока в байтах.

При закрытии файла в каталоге /dev в модуле ядра вызывается функция mcva_release(), которая освобождает все ресурсы, которые был выделены во время вызовы функции open. Реализация функции release() показана в листинге 20.

Листинг 20 - Пример реализации функции release()

.5 Обход каталогов страниц

Каждый выполняющийся процесс в ядре представлен структурой task_struct. Данную структуру называют дескриптором процесса. Структура, описывающая процесс имеет большие размеры и хранит всю необходимую информацию, а именно указатель на список используемых виртуальных страниц, текущее состояние процесса, число открытых файлов, указатель на процесс родитель при вызове функции fork и т.д. Виртуальное пространство процесса описывается структурой типа mm_struct. Чтобы отслеживать области памяти каждого процесса, в ядре реализована структура vm_area_struct, которая хранит их в виде двусвязного списка областей, причем две области никогда не пересекаются. Начало каждой области указано в переменной vm_start, а конец области в переменной vm_end. Область, выделенная для процесса, может быть доступна, как для чтения или для записи. Следует отметить тот факт, что даже если область была выделена процессу, в действительности физической страницы памяти может не существовать.

Каждый процесс в системе указывает на свой собственный каталог PGD (Page Global Directory). Каталог состоит из записей типа pgd_t. Тип является архитектурно зависимым и объявлен в файле <asm/page.h>. Для архитектуры x86, процесс копирует значение, хранящееся в переменной mm_struct->pgd в регистр cr3, что приводит к сбросу TLB буфера. Каждая активная запись в каталоге PGD указывает на страничный фрейм, который хранится в каталоге PMD (Page Middle Directory). В данном каталоге каждая запись представлена типом pmd_t, которая в свою очередь указывает на страничный фрейм, содержащийся в каталоге PTE (Page Table Entries). Все записи в данном каталоге представлены типом pte_t, где каждая запись фактически указывает на действительные пользовательские данные. В случае, если страница была выгружена на жесткий диск, запись о данной странице будет сохранена в каталоге PTE. Во время вызова функции do_swap_page() информация о выгруженной странице будет найдена в каталоге PTE. Иерархия каталогов страниц показана на рисунке 9.

Рисунок 9 - Иерархия каталогов страниц

Как видно из рисунка виртуальный адрес логически делится на части, которые представляют смещение от начало каждого из каталогов. Чтобы упростить работу с виртуальным адресом в ядре были реализованы макросы. Пример SHIFT макросов показан на рисунке 10.

Рисунок 10 - Пример SHIFT макросов

Как уже говорилось, каждая запись в каталогах страниц описывается типом pgd_t, pmd_t и pte_t. Хотя значениями каждой записи являются обычные целые числа без знака, любой из типов представляется в виде структуры по нескольким причинам. Во-первых, необходимо хранить для каждой страницы, права доступа, которые описываются как набор битов. Во-вторых, в режиме PAE возникает необходимость в дополнительных параметрах. Все биты описывающие состояние страницы перечислены в таблице 3.

Таблица 3 - Описание битов состояния страницы

_PAGE_PRESENTСтраница расположена в оперативной памяти_PAGE_PROTNONEСтраница в памяти, но не доступна_PAGE_RWУстанавливается, если страница доступна для чтения/записи _PAGE_USERУстанавливается, если страница доступна из пользовательского пространства_PAGE_DIRTYУстанавливается, если произошла операции записи_PAGE_ACCESSEDУстанавливается, если страница доступнаВсе необходимые макросы по работе с каталогами страниц определены в файле <asm/pgtable.h>. Ориентироваться по каталогам страниц позволяют три основных макроса. pgd_offset() в качестве первого аргумента принимает структуру типа mm_struct, а в качестве второго аргумента виртуальный адрес и возвращает запись типа pgd_t. В макрос pmd_offset() первым аргументом передается значение типа pgd_t, а вторым аргументом передается виртуальный адрес. Данный макрос возвращает запись типа pmd_t. Макрос pte_offset() принимает первым аргументом значение типа pmd_t и вторым аргументом, как и макросы выше виртуальный адрес. Данный макрос возвращает структуры типа struct page, которая описывает физическую страницу памяти.

Так как в рамках дипломной работы необходимо было по виртуальному адресу получать физический адрес памяти, то в модуле ядра была реализована функция, которая обходит иерархию каталогов страниц, как описано в тексте выше. Часть реализация данной функции показана в листинге 21.

Листинг 21 - Реализации функции обхода каталогов страниц

pgd = pgd_offset(mm, va);(pgd_none(*pgd) || pgd_bad(*pgd)) {_ERROR(*pgd); return 0;

}= pud_offset(pgd, va);(pud_none(*pud) || pud_bad(*pud)) {_ERROR(*pud); return 0;

}= pmd_offset(pud, va);(pmd_none(*pmd) || pmd_bad(*pmd)) {_ERROR(*pmd); return 0;

}= pte_offset_map(pmd, va);(!pte || pte_none(*pte) || !pte_present(*pte)) {_ERROR(*pte); return 0;

}= pte_page(*pte); (!page) {(KERN_INFO "page bad!\n"); return 0;

}= page_to_phys(page); // physical address_unmap(pte);

.6 Реализации библиотеки IPC

Чтобы минимальным образом, воздействовать на адресное пространство профилируемой программы, было принято решение реализовать словарь кэш-промахов и ложного разделения данных, как отдельный процесс. При такой реализации профилировщика требуется применение средств межпроцессорного взаимодействия. В операционной системе Linux реализованы различные средства позволяющие процессам, взаимодействовать между собой. Одними из самых часто применяемых средств межпроцессорного взаимодействия считаются: очереди сообщений, разделяемую память и доменные сокеты UNIX. В рамках дипломной работы стояла задача реализовать библиотеку, которая позволяла использовать все существующие высокопроизводительные средства IPC (Inter Process Communications).

Очереди сообщений, реализованные в Linux, представлены в виде связного списка сообщений, который хранится в памяти ядра, и идентифицируются уникальным номером очереди сообщений. [5]

Структура struct msqid_ds определяет состояние очереди. Некоторые реализации включают дополнительные поля в эту структуру, которые не определяются в стандарте.

Создание очереди сообщений происходит на стороне словаря. Профилировщик инициализирует клиентскую часть и с помощью вызовов ipc_read, ipc_write взаимодействует со словарем. Библиотека IPC реализована на основе классов c++. Объявление класса ObjectIPCClientMsgQueue показана в листинге 4.22, а код реализующий клиентскую часть соединения в листинге 23.

Листинг 22 - Пример объявления класса ObjectIPCClientMsgQueue

class ObjectIPCClientMsgQueue {

private:msgid;:(): msgid(-1) { }

~ObjectIPCClientMsgQueue() { } * connect_to_server(void);

};

Листинг 23 - Реализация клиентской части соединения для очереди сообщений

ConnectionObject* ObjectIPCClientMsgQueue::connect_to_server(void)

{_t key;char *name = "/tmp";((key = ftok(name, 'a')) == (key_t) -1) {("ftok");NULL;

}((msgid = msgget(key, 0666)) < 0) {("msgget");NULL;

}new ConnectionObjectMsgQueue(msgid, 1);

}

К одним из самых производительных механизмов межпроцессорного взаимодействия относят разделяемую память. С каждой областью разделяемой памяти связывается структура struct shmid_ds. Эта структура определяет текущее состояние разделяемой памяти. Некоторые реализации включают дополнительные поля в эту структуру, которые не определяются в стандарте.

Механизм разделяемой памяти позволяет двум или более процессам совместно использовать одну и ту же область памяти. При её использовании существует сложность в обеспечении синхронизированного доступа к ней. Если сервер размещает данные в области разделяемой памяти, клиент не должен пытаться читать данные до тех пор, пока сервер не завершит работу с разделяемой памятью. [5]

Чтобы увеличить пропускную способность соединения при использовании разделяемой памяти был реализован кольцевой буфер. Кольцевой буфер расположен в разделяемой памяти, доступ к нему синхронизируется с помощью семафоров. Пример взаимодействия процессов через кольцевой буфер показан на рисунке 4.5.

Всю основную часть работы связанную с инициализацией семафоров и созданием области разделяемой памяти выполняет серверная часть, которая реализуется в классе ObjectIPCServerShdMemory. При вызове функции connect_to_client() создается объект типа ConnectionObjectShdMemory, который перегружает функции ipc_read и ipc_write. Реализации функции ipc_read показана в листинге 4.24, а реализация функции ipc_write в листинге 4.25.

Листинг 24 - Пример реализации функции ipc_read

int ::ipc_read(profiler_data_t *data)

{(data == NULL)-1;(semid, &WaitFull, 1);(semid, &WaitMutex, 1);_data_t *data_in_buffer = NULL;_in_buffer =

&ringbuffer->data[ringbuffer->head++];>head &= MASK_RING_BUFFER;(data, data_in_buffer, (profiler_data_t));(semid, &SignalMutex, 1);(semid, &SignalEmpty, 1);

return 0;

}

Семафор WaitFull будет захвачен только в том случае, если была вызвана операция ipc_write и в кольцевом буфере имеются элементы. После того, как будет извлечен элемент, семафор SignalEmpty увеличивается на 1, сигнализируя о свободном слоте в кольцевом буфере.

Листинг 25 - Пример реализации функции ipc_write

int ConnectionObjectShdMemory::ipc_write(profiler_data_t *data)

{(data == NULL)-1;(semid, &WaitEmpty, 1); (semid, &WaitMutex, 1);_data_t *ptr_on_spot_in_buffer = NULL;_on_spot_in_buffer =

&ringbuffer->data[ringbuffer->tail++];(ptr_on_spot_in_buffer, data, (profiler_data_t));>tail &= MASK_RING_BUFFER;(semid, &SignalMutex, 1);(semid, &SingalFull, 1); 0;

}

Семафор WaitEmpty будет захвачен только в том случае, если была вызвана операция ipc_read и в кольцевом буфере имеются свободные слоты. После того, как будет помещен элемент, семафор SignalFull увеличивается на 1, сигнализируя о помещении нового элемента в кольцевой буфер.

Последним механизмом, применяемым при реализации библиотеки IPC, является доменные сокеты UNIX. Доменные сокеты, в отличие от сокетов интернета не используют сетевой протокол для взаимодействия. При создании сокета указывается имя файла в файловой системе, через который будут взаимодействовать процессы. Установление соединения происходит при вызове функции connect(). [8]

Доменные сокеты UNIX - это самый простой в использовании механизм взаимодействия. Объект класса ObjectIPCServerDomainSocket создается словарем, чтобы взаимодействовать с профилируемой программой. Объявление класса ObjectIPCServerDomainSocket показана в листинге 26.

Рисунок 11 - Пример взаимодействия через разделяемую память

Листинг 26 - Пример объявления класса ObjectIPCServerDomainSocket

.7 Инструментация кода средствами Clang

Компилятор Clang - это компилятор с открытым исходным кодом для языков программирования семейства Си. Компилятор построен на основе LLVM оптимизатора и кода генератора, которые обеспечивают высококачественную оптимизацию и кода генерацию для различных целей. Помимо базовых языков и диалектов, clang поддерживает широкий спектр расширений, которые описываются в документации. Эти расширения включены, чтобы быть совместимым с GCC, Microsoft и другими популярными компиляторами, а также для улучшения функциональности компилятора Clang. Драйвер Clang и функции языка специально разработаны так, чтобы быть совместимыми с GNU GCC компилятором, для ослабления миграции кода из GCC на Clang. [6]

Если потребуется написать анализатор кода или механизм инструментации кода, то компилятор Clang станет наилучшим выбором для этих целей. Главная цель компилятора Clang построение C/C++, Objective C фронтенда для LLVM компилятора. Фронтенд - это программа, которая использует исходный код и преобразует его в структурированное дерево, сформированное дерево называется абстрактно-синтаксическим деревом или Abstract Syntax Tree (AST). В большинстве случаев, Clang запускает препроцессор, который развернет все макросы и разпарсит исходный код в AST. Если имеется абстрактно-синтаксическое дерево программы, то анализ исходного кода становится проще. Например, если потребуется изменить старое название переменной, необходимо всего лишь найти в AST узел VariableDeclaration и задать новое имя.

Почти каждый компилятор и инструмент статического анализа кода использует AST для представления исходного кода. Абстрактно-синтаксическое дерево имеет довольно сложную структуру, но в действительности такое разнообразие различных узлов в дереве позволяет более качественно анализировать код. В общем случае, Clang AST состоит из двух очень гибких классов: Decl и Stmt. Существует множество подклассов для каждого из классов. Например, FunctionDecl - описывает прототипы функций и их определения, BinaryOperator - описывает бинарные выражения типа (a + b), CallExpr - описывает вызовы функций, такие как sin(a). [6]

Для анализа кода компилятор Clang предлагает несколько различных механизмов: LibTooling, LibClang.

LibClang - это очень удобный механизм, в случае когда необходим стабильный API. Интерфейс классов компилятора Clang периодически изменяется, и если используется LibTooling, возможно, придется обновлять исходный код анализатора, чтобы соответствовать изменениям Clang. Механизм LibClang не дает полноценный доступ к абстрактно-синтаксическому дереву, он предоставляет только высокоуровневый доступ. Для анализа AST часто рекомендуют использовать LibTooling, который обладает большой гибкостью и имеет полный доступ к абстрактно-синтаксическому дереву.

.8 Библиотека времени выполнения

Статический анализатор кода, реализованный с помощью библиотеки LibTooling анализирует исходный код программы и перехватывает обращение к массивам данных, вставляя вызовы runtime библиотеки. Пользователь, до того как запустить профилировщик в конфигурационном файле задает имена языковых объектов, обращение к которым необходимо отслеживать. Вся основная работа, связанная с взаимодействием с модулем ядра и словарем кэш-промахов и ложного разделения данных заложена в функции mem_ref. Принципы работы функции mem_ref и потока обработчика взаимодействующего с модулем ядра показаны на рисунке 12.

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

Рисунок 12 - Пример взаимодействия основного потока и потока обработчика

Листинг.27 - Создание потока обработчика

Поток обработчик открывает файл /dev/mcva, для того чтобы взаимодействовать с модулем ядра. Взаимодействие потока обработчика с основным потоком осуществляется при помощи потокобезопасной очереди, реализованной на с++. Основной поток заносит информацию о виртуальном адресе и идентификаторе потока, который обращался к памяти в очередь. Потребность в потокобезопасной очереди возникла, чтобы улучшить производительность runtime библиотеки. Поток обработчик в цикле считывает данные из очереди и формирует их для отправки модулю ядра. Как только модуль ядра по виртуальному адресу найдет физический адрес памяти, он передаст эту информацию обратно потоку обработчику, который уже с помощью средств межпроцессорного взаимодействия передаст всю необходимую информацию словарю. В листинге 28 показана реализация основного цикла потока обработчика.

Листинг 28 - Основной цикл потока обработчика

for (;;) {::shared_ptr<T> data = queue->wait_and_pop();* ptr_data = data.get();

/* Формируем данные перед отправкой модулю ядра */

input_data.pid = ptr_data->pid;_data.va = ptr_data->va;("thread handler va = %lu\n", ptr_data->va);(fd, &input_data, sizeof(in_data_t));(fd, &output_data, sizeof(out_data_t));("thread handler pa = %lu\n", output_data.pa);

/* Формируем данные перед отправкой симулятору кэша */

memcpy(&profiler_data.name, ptr_data->name,

strlen(ptr_data->name));_data.operation = ptr_data->operation;_data.pa = output_data.pa;_data.va = output_data.va;(conn_object->ipc_write(&profiler_data) < 0) {::cerr << "failed sending data" << std::endl;(-1);

}(ptr_data->va == 0)

break;

}

3. Результаты профилирования

Чтобы продемонстрировать работу профилировщика, была выбрана программа, реализующая алгоритм умножения матриц, в неоптимизированной версии, которой выявлена проблема с частыми кэш промахами, из-за нарушения локальности обращения к близлежащим ячейкам памяти. Реализация алгоритма показана в листинге 5.1, а результаты профилирования показаны в таблице 4. Размер матриц задается константно в программе и равен 100x100.

Листинг 3.1 - Неоптимизированный алгоритм умножения матриц

Таблица 4 - Результаты профилирования программы из листинга 5.1

ПрофилировщикЧисло кэш промаховperf168726valgrind134365Раз. Инструмен.135757

Простейший вариант оптимизации алгоритма умножения матриц показан в листинге 3.2. Результаты профилирования показаны в таблице 5.2.

Листинг 3.2 - Оптимизированный алгоритм умножения матриц

Таблица 5 - Результаты профилирования программы из листинга 5.2

Профилировщик2.8 Библиотека времени выполнения Число кэш промаховperf160714valgrind127599Раз. Инструмен.119651

Заключение

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

память кэш синхронизация код

Библиография

1Таненбаум Э. Современные операционные системы. - СПб.: Питер, 2010. - 1120 с.

Randal E. Bryant, David R. O'Hallaron. Computer Systems: A Programmer's Perspective. - Addison-Wesley, 2014. - 1084 с.

Бовет Д., Чезати М. Ядро Linux, 3-е изд. - СПб.: БХВ-Петербург, 2007. - 1104 с.

Лав Р. Ядро Linux: описание процесса разработки, 3-е изд. - М.: Вильямс, 2015. - 496 с.

Стивенс У., Раго С. UNIX. Профессиональное программирование, 2-е изд. - СПб.: Символ, 2007. - 1035 с.

Clang - Официальный сайт поддержки компилятора Clang. - URL: #"justify">Приложение 1

Наиболее употребляемые текстовые сокращения

CPU - central processing unit

SMT - simultaneous multithreading - symmetric multiprocessing

NUMA - non-uniform memory architecture <#"justify">Приложение 2

Листинг В.1 - Реализация модуля ядра

/* mcva.h */

#ifndef MCVA_H

#define MCVA_H

#include <linux/wait.h>

#include <linux/semaphore.h>

#include <linux/module.h>

#include <asm/atomic.h>

#include "data.h"

#include "queue.h"struct information_converting_virtual_addresses {_queue_head_t readq;semaphore semread;semaphore semwrite;_t readiness_read;_t *data_queue;

} icva_t;

#endif // MCVA_H

/* data.h */

#ifndef DATA_H

#define DATA_H

#define NAME_LENGTH 64enum {_READ,_WRITE

} rw_oper_t;struct processing_data {_t pid;name[NAME_LENGTH];long va;_oper_t operation;

} proc_data_t;

/* Структуры обрабатываемые модулем ядра */struct input_data {_t pid;long va;

} in_data_t;struct output_data {long va;long pa;

} out_data_t;struct profiler_data {

int pid;name[NAME_LENGTH];long pa;long va;_oper_t operation;

} profiler_data_t;

/* mcva_dev_main.c */<linux/fs.h><linux/pid.h><linux/slab.h><linux/cdev.h><linux/init.h><linux/sched.h><asm/uaccess.h><asm/pgtable.h><linux/device.h><linux/mm_types.h><linux/rcupdate.h>"mcva.h"DEVICE_NAME "mcva"DEVICE_FIRST 0DEVICE_COUNT 1_LICENSE("GPL");_AUTHOR("Kirill Ryzhkov");_VERSION("1.0");struct class *mcva_class;struct cdev mcva_cdev;dev_t mcva_dev_number; int flag_busy = 0; inline void initialization_icva(icva_t *p)

{_waitqueue_head(&p->readq);_set(&p->readiness_read, 0);_init(&p->semread, 1);_init(&p->semwrite, 1);

}mcva_open(struct inode *inode, struct file *file)

{(flag_busy == 0) {_t *__module;

__module = kmalloc(sizeof(icva_t), GFP_KERNEL);(__module == NULL) -ENOMEM;((__module->data_queue = queue_create()) == NULL)-ENOMEM;_icva(__module);>private_data = __module;_busy = 1;

} else {(KERN_INFO "module is currently busy\n");-EBUSY;

}0;

}mcva_release(struct inode *inode, struct file *file)

{_t *__module = file->private_data;(__module->data_queue);(__module);>private_data = NULL; _busy = 0;0;

}checking_virtual_address(struct mm_struct *mm, unsigned long va)

{vm_area_struct *vm_area;(vm_area = mm->mmap;

vm_area != NULL; vm_area = vm_area->vm_next) {(vm_area->vm_start >= va && va <= vm_area->vm_end)1;

}0;

}long traversal_page_directory(struct mm_struct *mm, unsigned long va)

{long pa;page *page;_t *pgd;_t *pud;_t *pmd;_t *pte;= pgd_offset(mm, va);(pgd_none(*pgd) || pgd_bad(*pgd)) {_ERROR(*pgd);0;

}= pud_offset(pgd, va);(pud_none(*pud) || pud_bad(*pud)) {_ERROR(*pud);0;

}= pmd_offset(pud, va);(pmd_none(*pmd) || pmd_bad(*pmd)) {_ERROR(*pmd);0;

}= pte_offset_map(pmd, va);(!pte || pte_none(*pte) || !pte_present(*pte)) {_ERROR(*pte);0;

}= pte_page(*pte); (!page) {(KERN_INFO "page bad!\n");0;

}= page_to_phys(page);_unmap(pte);pa;

}unsigned long get_pa(struct task_struct *task, unsigned long va)

{traversal_page_directory(task->mm, va);

}ssize_t mcva_bread(struct file *file, char __user *buf,

size_t count, loff_t *f_pos)

{pid *pid;task_struct *task;_data_t output_data;_data_t *input_data;long page_address;long offset_address;_t *__module = file->private_data;(down_interruptible(&__module->semread))-ERESTARTSYS;(atomic_read(&__module->readiness_read) == 1) {((input_data = (in_data_t *)

queue_dequeue(__module->data_queue)) == NULL)_set(&__module->readiness_read, 0);

}(atomic_read(&__module->readiness_read) == 0) {(&__module->semread);(file->f_flags & O_NONBLOCK)-EAGAIN;

if (wait_event_interruptible(__module->readq,

atomic_read(&__module->readiness_read) != 0))-ERESTARTSYS;(down_interruptible(&__module->semread))-ERESTARTSYS;

/* wake up due to signals */((input_data = (in_data_t *)

queue_dequeue(__module->data_queue)) == NULL)_set(&__module->readiness_read, 0);

}_read_lock();= find_vpid(input_data->pid);_read_unlock();((task = get_pid_task(pid, PIDTYPE_PID)) == NULL) {(KERN_DEBUG "<%s> get_pid_task failed\n", __func__);(&__module->semread);-EINVAL;

}_address = get_pa(task, input_data->va);_address = page_address +

(input_data->va & (PAGE_SIZE - 1));_data.va = input_data->va;_data.pa = offset_address;(copy_to_user(buf, (void* )&output_data, count)) {(&__module->semread);-EFAULT;

}ssize_t mcva_bwrite(struct file *file, char __user *buf, size_t count, loff_t *f_pos)

{ret;_data_t *input_data;_t *__module = file->private_data;(down_interruptible(&__module->semwrite))-ERESTARTSYS;((input_data = (sizeof(in_data_t), GFP_KERNEL)) == NULL) {(KERN_DEBUG "<%s> kmalloc failed\n", __func__);(&__module->semwrite);-ENOMEM;

}(copy_from_user(input_data, buf, count)) {(KERN_DEBUG

"<%s> copy_from_user failed\n", __func__);(&__module->semwrite);-EFAULT;

}((ret = _enqueue(__module->data_queue, (void *)input_data)) < 0) {(KERN_DEBUG "<%s> queue_enqueue failed\n", __func__);(&__module->semwrite);ret;

}(atomic_read(&__module->readiness_read) == 0) {_set(&__module->readiness_read, 1);_up_interruptible(&__module->readq);

}(&__module->semwrite);count;

}struct file_operations mcva_fops = {= THIS_MODULE,= mcva_open,= mcva_bread,= mcva_bwrite,= mcva_release,

};int __init mcva_init(void)

{ret;dynamic allocation of a device major number */(alloc_chrdev_region(&mcva_dev_number, DEVICE_FIRST, _COUNT, DEVICE_NAME) < 0) {(KERN_DEBUG "=== Can not register device === \n");-1;

}_class = class_create(THIS_MODULE, DEVICE_NAME);_init(&mcva_cdev, &mcva_fops);_cdev.owner = THIS_MODULE;((ret = cdev_add(&mcva_cdev, mcva_dev_number, 1)) < 0) {_chrdev_region(mcva_dev_number, DEVICE_COUNT);(KERN_DEBUG "=== Can not add char device === \n");err;

}_create(mcva_class, NULL, mcva_dev_number, "%s", DEVICE_NAME);(KERN_INFO "=== mcva installed %d:%d === \n", (mcva_dev_number), MINOR(mcva_dev_number));:ret;

}void __exit mcva_exit(void)

{the major number */_chrdev_region(mcva_dev_number, DEVICE_COUNT);_destroy(mcva_class, mcva_dev_number);_destroy(mcva_class);_del(&mcva_cdev);

}_init(mcva_init);_exit(mcva_exit);

Листинг В.2 - Реализация потокобезопасной очереди применяемой в ядре

/* queue.h */QUEUE_HQUEUE_H<linux/list.h><linux/spinlock.h>struct queue_item {list_head list;*item;

} queue_item_t;struct queue_data {list_head list;_t lock;

} queue_t;_t* queue_create(void);queue_delete(queue_t *q);queue_enqueue(queue_t *q, void *item);* queue_dequeue(queue_t *q);queue_is_empty(queue_t *q);queue_lock(queue_t *q);queue_unlock(queue_t *q);// QUEUE_H

/* queue.c */<linux/init.h><linux/slab.h><linux/module.h>"queue.h"_LICENSE("GPL");_AUTHOR("Kirill Ryzhkov");_VERSION("1.0");_t* queue_create(void)

{_t * q;= (queue_t *)kmalloc(sizeof(queue_t), GFP_KERNEL);(!q) {(KERN_DEBUG "<%s> kmalloc failed\n", __func__);NULL;

}_LIST_HEAD(&(q->list));_lock_init(&(q->lock));q;

}queue_delete(queue_t *q)

{((void *)q);

}queue_enqueue(queue_t *q, void *item)

{_item_t *queue_item;_item =

(queue_item_t *)kmalloc(sizeof(queue_item_t), GFP_KERNEL);(!queue_item) {(KERN_DEBUG "<%s> kmalloc failed\n", __func__);-ENOMEM;

}_item->item = item;_lock(q);_add_tail(&(queue_item->list), &(q->list));_unlock(q);0;

}* queue_dequeue(queue_t *q)

{_item_t *queue_item;*item;(queue_is_empty(q))NULL;_lock(q);_item = list_first_entry(&(q->list), queue_item_t, list);= queue_item->item;_del(&(queue_item->list));(queue_item);_unlock(q);item;

}queue_is_empty(queue_t *q)

{ret;_lock(q);= list_empty(&(q->list));_unlock(q);ret;

}queue_lock(queue_t *q)

{_lock(&(q->lock));0;

}queue_unlock(queue_t *q)

{_unlock(&(q->lock));0;

}

Листинг В.3 - Реализация потокобезопасной очереди применяемой в runtime библиотеке

/* threadsafe_queue.hpp */THREADSAFE_QUEUE_HTHREADSAFE_QUEUE_H<mutex><memory><condition_variable><typename T>threadsafe_queue {:node {::shared_ptr<T> data;::unique_ptr<node> next;

};::mutex head_mutex;::unique_ptr<node> head;::mutex tail_mutex;* tail;::condition_variable data_cond;* get_tail()

{::lock_guard<std::mutex> tail_lock(tail_mutex);tail;

}::unique_ptr<node> pop_head()

{::unique_ptr<node> old_head = std::move(head);= std::move(old_head->next);old_head;

}::unique_lock<std::mutex> wait_for_data()

{::unique_lock<std::mutex> head_lock(head_mutex);_cond.wait(head_lock,

[&]{return head.get() != get_tail();});std::move(head_lock);

}::unique_ptr<node> wait_pop_head()

{::unique_lock<std::mutex> _lock(wait_for_data());pop_head();

}::unique_ptr<node> wait_pop_head(T& value)

{::unique_lock<std::mutex> _lock(wait_for_data());= std::move(*head->data);pop_head();

}::unique_ptr<node> try_pop_head()

{::lock_guard<std::mutex> head_lock(head_mutex);(head.get() == get_tail()) {std::unique_ptr<node>();

}pop_head();

}::unique_ptr<node> try_pop_head(T& value)

{::lock_guard<std::mutex> head_lock(head_mutex);(head.get() == get_tail()) {std::unique_ptr<node>();

}= std::move(*head->data);pop_head();

}:_queue(): head(new node), tail(head.get()) {}_queue(const threadsafe_queue& other) = delete;_queue& =(const threadsafe_queue& other) = delete;::shared_ptr<T> try_pop()

{::unique_ptr<node> old_head = try_pop_head();old_head ? old_head->data:

std::shared_ptr<T>();

}try_pop(T& value)

{::unique_ptr<node> const old_head = _pop_head(value);old_head;

}::shared_ptr<T> wait_and_pop()

{::unique_ptr<node> const old_head = _pop_head();old_head->data;

}wait_and_pop(T& value)

{::unique_ptr<node> const old_head = _pop_head(value);

}push(T new_value)

{::shared_ptr<T> _data(std::make_shared<T>(std::move(new_value)));::unique_ptr<node> p(new node);

{::lock_guard<std::mutex>

tail_lock(tail_mutex);>data = new_data;* const new_tail = p.get();>next = std::move(p);= new_tail;

}_cond.notify_one();

}empty()

{::lock_guard<std::mutex> head_lock(head_mutex);(head.get() = get_tail());

}

};// THREADSAFE_QUEUE_H

Листинг В.4 - Реализация серверных классов библиотеки IPC

/* ObjectIPCServerSocket.cpp */<stdlib.h><errno.h>"mutex.h""ringbuffer.h""ConnectionObject.h"ObjectIPCServerDomainSocket {:__socket;sockaddr_un addr;:()

{

__socket = -1; (&addr, 0, sizeof(struct sockaddr_un));

}();create_ipc(void);close_ipc(void);* connect_to_client(void);

};::~ObjectIPCServerDomainSocket()

{ close_ipc(); }ObjectIPCServerDomainSocket::close_ipc(void)

{(__socket != -1) {(__socket);

__socket = -1;

}0;

}ObjectIPCServerDomainSocket::create_ipc(void)

{_t len;char *path = "/tmp/profiler_socket";((__socket = socket(AF_UNIX, SOCK_STREAM, 0)) < 0) {("socket");(-1);

}.sun_family = AF_UNIX;(addr.sun_path, path); (path);= strlen(addr.sun_path) + sizeof(addr.sun_family);(bind(__socket, (struct sockaddr *)&addr, len) < 0) {("bind");(-1);

}(listen(__socket, 10) < 0) {("listen");(-1);

}0;

}* ObjectIPCServerDomainSocket::connect_to_client(void)

{__client_socket;_t sock_len;((__client_socket = (__socket, (struct sockaddr *)&addr, &sock_len)) < 0) {("accept");NULL;

}new ConnectionObjectDomainSocket(__client_socket);

}ObjectIPCServerMsgQueue {:msgid;:(): msgid(-1) { }

~ObjectIPCServerMsgQueue() { close_ipc(); }create_ipc(void);close_ipc(void);* connect_to_client(void);

};ObjectIPCServerMsgQueue::create_ipc(void)

{_t key;char *name = "/tmp";((key = ftok(name, 'a')) == (key_t) -1) {("ftok");-1;

}((msgid = msgget(key, IPC_CREAT | 0666)) < 0) {("msgget");-1;

}0;

}ObjectIPCServerMsgQueue::close_ipc(void)

{err;(msgid != -1) {((err = msgctl(msgid, IPC_RMID, NULL)) < 0) {("msgctl");(-1);

}= -1;

}0;

}* ObjectIPCServerMsgQueue::connect_to_client(void)

{new ConnectionObjectMsgQueue(msgid, 0);

}union semun

{val;semid_ds *buf;*array;

} seminfo;ObjectIPCServerShdMemory {shmid;semid;:(): shmid(-1), semid(-1) { }

~ObjectIPCServerShdMemory();create_ipc(void);close_ipc(void);* connect_to_client(void);

};::~ObjectIPCServerShdMemory()

{_ipc();

}ObjectIPCServerShdMemory::close_ipc(void)

{shmid_ds shminfo;(semid != -1) {(semctl(semid, SEM_COUNT - 1, IPC_RMID, 0) < 0) {("semctl");-1;

}= -1;

}(shmid != -1) {(shmctl(shmid, IPC_RMID, &shminfo) < 0) {("shmid");-1;

}= -1;

}0;

}ObjectIPCServerShdMemory::create_ipc(void)

{_t key;char *name = "/tmp";((key = ftok(name, 'b')) == (key_t) -1) {("ftok");-1;

}((semid = semget(key, 3, IPC_CREAT | 0666)) < 0) {("semget");-1;

}.val = BUF_SIZE;(semid, SEM_EMPTY, SETVAL, seminfo); .val = 1;(semid, SEM_MUTEX, SETVAL, seminfo);.val = 0;(semid, SEM_FULL, SETVAL, seminfo);((key = ftok(name, 'c')) == (key_t) -1) {("ftok");-1;

}((shmid =

shmget(key, sizeof(ring_buffer_t), IPC_CREAT | 0666)) < 0) {("shmget");-1;

}_buffer_t *ringbuffer =

(ring_buffer_t *) shmat(shmid, 0, SHM_W);(ringbuffer == (void *) (-1)) {("shmat failed");-1;

}

/* initialize ring buffer */>head = 0;>tail = 0;(shmdt(ringbuffer) < 0) {("shmdt failed");-1;

}0;

}* ObjectIPCServerShdMemory::connect_to_client(void)

{new ConnectionObjectShdMemory(shmid, semid);

}

Листинг 5 - Реализация клиентских классов библиотеки IPC

/* ObjectIPCClientSocket.cpp */ <stdio.h><stdlib.h><errno.h><string.h><unistd.h><stdlib.h><sys/types.h><sys/socket.h><sys/un.h>"data.h""ConnectionObject.h"ObjectIPCClientDomainSocket {:__socket;:() { }

~ObjectIPCClientDomainSocket() { close (__socket); }* connect_to_server(void);

};* ObjectIPCClientDomainSocket::connect_to_server(void)

{sockaddr_un remote;char *path = "/tmp/profiler_socket";((__socket = socket(AF_UNIX, SOCK_STREAM, 0)) < 0) {("socket");NULL;

}.sun_family = AF_UNIX;(remote.sun_path, path); _t len = (remote.sun_path) + sizeof(remote.sun_family);(connect(__socket, (struct sockaddr *)&remote, len) < 0) {("connect");NULL;

}new ConnectionObjectDomainSocket(__socket);

}ObjectIPCClientMsgQueue {:msgid;:(): msgid(-1) { }

~ObjectIPCClientMsgQueue() { } * connect_to_server(void);

};* ObjectIPCClientMsgQueue::connect_to_server(void)

{_t key;char *name = "/tmp";((key = ftok(name, 'a')) == (key_t) -1) {("ftok");NULL;

}((msgid = msgget(key, 0666)) < 0) {("msgget");NULL;

}new ConnectionObjectMsgQueue(msgid, 1);

}ObjectIPCClientShdMemory {:shmid;semid;:(): shmid(-1), semid(-1) { }

~ObjectIPCClientShdMemory() { } * connect_to_server(void);

};* ObjectIPCClientShdMemory::connect_to_server(void)

{_t key;char *name = "/tmp";((key = ftok(name, 'b')) == (key_t) -1) {("ftok");NULL;

}((semid = semget(key, 0, 0666)) < 0) {("semget");NULL;

}((key = ftok(name, 'c')) == (key_t) -1) {("ftok");NULL;

}((shmid = shmget(key, 0, 0666)) < 0) {("shmget");NULL;

}new ConnectionObjectShdMemory(shmid, semid);

}

Листинг В.6 - Реализация класса ConnectionObject

/* mutex.h */MUTEX_HMUTEX_H <sys/sem.h><sys/ipc.h>SEM_MUTEX 0SEM_EMPTY 1SEM_FULL 2SEM_COUNT 3sembuf WaitMutex={SEM_MUTEX, -1, 0};sembuf SignalMutex={SEM_MUTEX, 1, 0};sembuf WaitEmpty={SEM_EMPTY, -1, 0};sembuf SignalEmpty={SEM_EMPTY, 1, 0};sembuf WaitFull={SEM_FULL, -1, 0};sembuf SingalFull={SEM_FULL, 1, 0};// MUTEX_H

/* ringbuffer.h */RING_BUFFER_HRING_BUFFER_H"data.h"BUF_SIZE 10MASK_RING_BUFFER (BUF_SIZE - 1)struct ringbuffer {head;tail;_data_t data[BUF_SIZE];

} ring_buffer_t;// RING_BUFFER_H

/* ConnectionObject.c */<stdio.h><stdlib.h><unistd.h><sys/un.h><sys/types.h><sys/socket.h><sys/msg.h><sys/shm.h><sys/ipc.h>"data.h""mutex.h""ringbuffer.h"struct wrap_profiler_data {type;_data_t data;

} msg_data_t;ConnectionObject {:() { }

~ConnectionObject() { }int ipc_read(profiler_data_t *data) = 0;int ipc_write(profiler_data_t *data) = 0;

};ConnectionObjectDomainSocket: public ConnectionObject {:__client_socket;:(int __socket): _socket(__socket) { }() { }ipc_read(profiler_data_t *data)

{ err;((err = recv(__client_socket, , sizeof(profiler_data_t), 0)) < 0) {("recv");(-1);

}0;

}ipc_write(profiler_data_t *data)

{err;((err = send(__client_socket, , sizeof(profiler_data_t), 0)) < 0) {("send");(-1);

}0;

}

};ConnectionObjectMsgQueue: public ConnectionObject {:mode;msgid;:(int __socket, int __mode /* 0 - server, 1 - client */) (__socket), mode(__mode) { }() { }ipc_read(profiler_data_t *data)

{err = 0;_data_t recvbuffer;(mode == 0) {((err = msgrcv(msgid, (void *)&recvbuffer,

sizeof(msg_data_t) - sizeof(long), 2L, 0)) < 0){("msgrcv");-1;

}

} else {((err = msgrcv(msgid, (void *)&recvbuffer,

sizeof(msg_data_t) - sizeof(long), 1L, 0)) < 0){("msgrcv");-1;

}

}(data, &recvbuffer.data, (profiler_data_t));err;

}ipc_write(profiler_data_t *data)

{err = 0;_data_t sendbuffer;(mode == 0) {.type = 1L; // client data(&(sendbuffer.data), data, (profiler_data_t));((err = msgsnd(msgid, (void *)&sendbuffer, (msg_data_t) - sizeof(long), 0)) < 0) {("msgsnd");(-1);

}

} else {.type = 2L; // server data(&(sendbuffer.data), data, (profiler_data_t));((err = msgsnd(msgid, (void *)&sendbuffer, (msg_data_t) - sizeof(long), 0)) < 0) {("msgsnd");(-1);

}

}err;

}

};ConnectionObjectShdMemory: public ConnectionObject {:_buffer_t *ringbuffer;shmid;semid;:(int __shmid, int __semid): (__shmid), semid(__semid)

{ =

(ring_buffer_t *)shmat(shmid, 0, SHM_R | SHM_W); (ringbuffer == (void *) -1) {= NULL;

}

}()

{(ringbuffer != NULL) {(ringbuffer);

}

}ipc_read(profiler_data_t *data)

{(data == NULL)-1;(semid, &WaitFull, 1);(semid, &WaitMutex, 1);_data_t *data_in_buffer = NULL;_in_buffer =

&ringbuffer->data[ringbuffer->head++];>head &= MASK_RING_BUFFER;(data, data_in_buffer, sizeof(profiler_data_t));(semid, &SignalMutex, 1);(semid, &SignalEmpty, 1);0;

}ipc_write(profiler_data_t *data)

{(data == NULL)-1;(semid, &WaitEmpty, 1); (semid, &WaitMutex, 1);_data_t *ptr_on_spot_in_buffer = NULL;_on_spot_in_buffer =

&ringbuffer->data[ringbuffer->tail++];(ptr_on_spot_in_buffer, data,

sizeof(profiler_data_t));>tail &= MASK_RING_BUFFER;(semid, &SignalMutex, 1);(semid, &SingalFull, 1);0;

}

};

Листинг В.7 - Реализация runtime библиотеки<mutex><iostream><thread><condition_variable><fcntl.h><unistd.h><stdlib.h><sys/un.h><sys/stat.h><sys/types.h><sys/socket.h><pthread.h>"data.h""threadsafe_queue.h""ObjectIPCDomainSocket.h""ObjectIPCShdMemory.h""ConnectionObject.h"int initialization = 0;_queue<struct processing_data> * queue;int termination_condition = 0;_mutex_t __mutex = PTHREAD_MUTEX_INITIALIZER;_cond_t __condition = PTHREAD_COND_INITIALIZER;<typename T>Handler(void)

{ipc;* conn_object;_object = ipc.connect_to_server();(conn_object == NULL) {::cerr <<

"connection on the server failed" << std::endl;

exit(-1);

}

/* Открываем файл устройства для взаимодействия

с модулем ядра */fd = open("/dev/mcva", O_RDWR);(fd < 0) {::cerr << "failed open /dev/mcva" << std::endl;(-1);

}_data_t input_data;_data_t output_data;_data_t profiler_data;(;;) {::shared_ptr<T> data = queue->wait_and_pop();* ptr_data = data.get();

/* Формируем данные перед отправкой модулю ядра */

input_data.pid = ptr_data->pid;_data.va = ptr_data->va;("thread handler va = %lu\n", ptr_data->va);(fd, &input_data, sizeof(in_data_t));(fd, &output_data, sizeof(out_data_t));("thread handler pa = %lu\n", output_data.pa);

/* Формируем данные перед отправкой симулятору кэша */

memcpy(&profiler_data.name, ptr_data->name,

strlen(ptr_data->name));_data.operation = ptr_data->operation;_data.pa = output_data.pa;_data.va = output_data.va;_data.pid = ptr_data->pid;(conn_object->ipc_write(&profiler_data) < 0) {::cerr << "failed sending data" << std::endl;(-1);

}(ptr_data->va == 0);

}_mutex_lock(&__mutex);_condition = 1;_mutex_unlock(&__mutex);_cond_signal(&__condition);

}mem_ref(const char *name, unsigned long va, int operation)

{processing_data data; (&data, 0, sizeof(struct processing_data));(initialization == 0) {= new threadsafe_queue<struct processing_data>;::thread thread(Handler<struct processing_data>);= 1;.detach();

}(&data.name, name, strlen(name));.operation = (operation == 1) ? OPER_WRITE: OPER_READ;.pid = getpid();.va = va;

queue->push(data);

/* Дождаться завершения потока */

if (va == 0) {::cout << "waiting the end a thread" << std::endl;_mutex_lock(&__mutex);(termination_condition != 1)_cond_wait(&__condition, &__mutex);

pthread_mutex_unlock(&__mutex);

}

}