Роберт Лав - Разработка ядра Linux
patch -p1 < ../my-patch
В этом примере имя файла, который содержит заплату, — my-patch, а находится он в родительском каталоге по отношению к каталогу, в котором хранится дерево исходного кода ядра. Флаг -p1 означает, что необходимо игнорировать (strip) имя первого каталога в путях всех файлов, в которые будут вноситься изменения. Это позволяет применить заплату независимо от того, какие имена каталогов кода ядра были на той машине, где создавалась заплата.
Полезная утилита diffstat позволяет сгенерировать гистограмму изменений, к которым приведет применение заплаты (удаление и добавление строк). Для того чтобы получить эту информацию для какой-либо заплаты, необходимо выполнить следующую команду.
diffstat -p1 my-patch
Обычно полезно включить результат выполнения этой команды при отправлении заплаты в список рассылки lkml. Так как программа patch(1) игнорирует все строки до того момента, пока не будет обнаружен формат diff, то вначале заплаты можно включить короткое описание.
Представление заплат
Заплата должна быть сгенерирована так, как описано в предыдущем разделе. Если заплата касается определенного драйвера или подсистемы, то заплату нужно отправить соответствующему ответственному разработчику, одному из тех, которые перечислены в файле MAINTAINERS. Другой вариант — это отправить сообщение в список рассылки разработчиков ядра по адресу [email protected]
Обычно тема (subject) письма, в котором содержится заплата, должна быть похожа на следующую "[PATCH] короткое описание.". В теле письма должны быть описаны основные технические детали изменений, которые вносятся заплатой, а также обоснования необходимости этих изменений. Описание должно быть максимально конкретным. Также необходимо указать, на какую версию ядра рассчитана заплата.
Большинство разработчиков ядра будут просматривать заплату прямо в теле письма и при необходимости записывать все письмо в файл. Следовательно, лучше всего будет вставить заплату прямо в тело письма, в самом конце сообщения. Будьте внимательны, потому что некоторые злобные почтовые клиенты вводят в сообщения дополнительное форматирование. Это испортит заплату и будет надоедать разработчикам. Если ваш почтовый клиент делает такие вещи, то необходимо поискать возможность включения текста без изменений ("Insert Inline") или что-нибудь аналогичное. Нормально работает также присоединение (attachment) заплаты в виде обычного текста, без перекодировки.
Если заплата большая или содержит несколько принципиальных изменений, то лучше разбить ее на логические части. Например, если вы предложили новый API и изменили несколько драйверов с целью его использования, то эти изменения можно разбить на две заплаты (новый API и изменения драйверов) и выслать их двумя письмами. Если в каком-либо случае необходимо вначале применить предыдущую заплату, то это необходимо специально указать.
После отправки наберитесь терпения и подождите ответа. Не нужно обижаться на негативный ответ — в конце концов это тоже ответ! Обдумайте проблему и вышлите обновленную версию заплаты. Если ответа нет, то попытайтесь разобраться, что было сделано не так, и решить проблему. Спросите у ответственного разработчика и в списке рассылки по поводу комментариев. Если повезет, то ваши изменения будут включены в новую версию ядра!
Заключение
Наиболее важными качествами любого хакера являются желание и умение работать — нужно искать себе проблемы и решать их. В этой книге приведено описание основных частей ядра, рассказано об интерфейсах, структурах данных, алгоритмах и принципах работы. Книга предоставляет вид ядра изнутри и делает это в практической форме. Она предназначена для того, чтобы удовлетворить ваше любопытство и стать отправной точкой в разработке ядра.
Тем не менее, как уже было сказано, единственный способ начать разрабатывать ядро — это начать читать и писать исходный код. Операционная система Linux предоставляет возможность работать в сообществе, которое не только позволяет это делать, но и активно побуждает к указанным действиям. Если есть желание действовать — вперед!
Приложение А
Связанные списки
Связанный список — это структура хранения информации (контейнер), которая может содержать переменное количество элементов данных, часто называемых узлами, и позволяет манипулировать этими данными. В отличие от статического массива, элементы связанного списка можно создавать динамически. Это дает возможность создавать переменное количество элементов списка, причем указанное количество может быть неизвестно на этапе компиляции. Так как элементы связанных списков создаются в разные моменты времени, они не обязательно будут находиться в смежных областях оперативной памяти. Поэтому элементы списка должны быть связаны друг с другом таким образом, чтобы каждый элемент содержал указатель на следующий за ним элемент (next). Вставка или удаление элементов списка выполняется простым изменением указателей на следующий элемент. Структура связанного списка показана на рис. А.1.
Рис. A.1. Односвязный список
В. некоторых связанных списках содержится указатель не только на следующий, но и на предыдущий элемент (prev). Эти списки называются двухсвязными (doubly linked), потому что они связаны как вперед, так и назад. Связанные списки, аналогичные тем, что показаны на рис. А.1, называются односвязными (singly linked). Двухсвязный список показан на рис. А.2.
Рис. А.2. Двухсвязный список
Кольцевые связанные списки
Последний элемент связанного списка не имеет следующего за ним элемента, и значение указателя next последнего элемента обычно устанавливается равным специальному значению, обычно NULL, чтобы показать, что этот элемент списка является последним. в определенных случаях последний элемент списка не указывает на специальное значение, а указывает на первый элемент этого же списка. Такой список называется кольцевым связанным списком (circular linked list), поскольку связи образуют топологию кольца. Кольцевые связанные списки могут быть как односвязными, так и двухсвязными. В двухсвязных кольцевых списках указатель prev первого элемента указывает на последний элемент списка. На рис. А.3 и А.4 показаны соответственно односвязные и двухсвязные кольцевые списки.
Рис. A.3. Односвязный кольцевой список
Рис. А.4. Двухсвязный кольцевой список
Стандартной реализацией связанных списков в ядре Linux является двухсвязный кольцевой список. Такие связанные списки обеспечивают наибольшую гибкость работы.
Перемещение по связанному списку
Перемещение по связанному списку выполняется последовательно (линейно). После того как просмотрен текущий элемент, выполнятся разыменование его указателя next, что позволяет обратиться к следующему за ним элементу и т.д. Это самый простой и наиболее подходящий метод перемещения но связанному списку. Если важна возможность произвольного доступа к любому элементу контейнера, то связанные списки не используются. Связанные списки используются, когда важна возможность динамического добавления и удаления элементов, а также возможность последовательного прохождения по всем элементам списка.
Часто первый элемент списка представлен с помощью специального указателя, который называется головным элементом или головой (head), что дает возможность быстро и легко обращаться к первому элементу. В некольцевом связанном списке последний элемент отличается тем, что его указатель равен значению NULL. В кольцевом связанном списке последний элемент отличается тем, что указывает на головной элемент. Таким образом прохождение списка можно выполнить линейно, начиная с первого элемента и заканчивая последним. В двухсвязном списке прохождение можно также выполнить и в противоположном направлении, начиная с последнего и заканчивая первым элементом. Конечно, если задан определенный элемент списка, то можно перейти по списку вперед и назад на заданное количество элементов. При этом нет необходимости проходить весь список.
Реализация связанных списков в ядре Linux
В ядре Linux для прохождения по связанным спискам используется унифицированный подход. При прохождении связанного списка, если не важен порядок прохода, эту операцию не обязательно начинать с головного элемента, на самом деле вообще не важно, с какого элемента списка начинать прохождение! Важно только, чтобы при таком прохождении были пройдены все узлы. В большинстве случаев нет необходимости вводить концепции первого и последнего элементов. Если в кольцевом связанном списке содержится коллекция несортированных данных, то любой элемент можно назвать головным. Для прохождения всего связанного списка необходимо взять любой элемент и следовать за указателями, пока снова не вернемся к тому элементу, с которого начали обход списка. Это избавляет от необходимости вводить специальный головной элемент. Кроме того, упрощаются процедуры работы со связанными списками. Каждая подпрограмма должна просто принимать указатель на один элемент — любой элемент списка. Разработчики ядра даже немножко гордятся такой остроумной реализацией.
