Задачи по программированию на языке C++, часть 2

Это подолжение обещанного в предыдущем сообщении "Задачи по программированию на языке C, часть 1" : так же задачи, но уже на языке C++.

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

Немного, но есть пересечения по формулировкам задач с 1-й частью - некоторые задачи любопытно посмотреть в сравнении: как это делается на C и что нового привносит C++.

Как и раньше, ссылки даются на последнюю актуальную редакцию - ссылки будут меняться без какого-либо уведомления. Скачать свободно последнюю актуальную редакцию текста и архива кодов можно здесь:
Google: текст, архив кодов
Сейчас это редакция 38 от 13.09.2016, стр. 85.
(после достаточно продолжительного перерыва произошло весьма обстоятельное обновление)

В отношении авторских прав повторю:
Ничто из представленного в этом тексте не заимствовано ни из каких источников (кроме, возможно, идей постановок некоторых задач). Все представленные варианты решений - авторские, со всеми возможными ошибками и неточностями.

Как и всё опубликованное ранее, этот текст и все сопутствующие ему материалы представляется под лицензией: Creative Commons Attribution ShareAlike (http://legalfoto.ru/licenzii/) ("общественное достояние"):
... допускается копирование, коммерческое использование произведения, создание его производных при чётком указании источника, но при том единственном ограничении, что при использовании или переработке разрешается применять результат только на условиях аналогичной лицензии.

Задачи по программированию на языке C, часть 1

Здесь я собрал большой набор вопросов и задач по программированию на языке C. Это систематизированная подборка тех материалов, которые обсуждались на протяжении нескольких лет на форуме (жалко стало, если затеряется). В составе: текст описания (задачи и решения) и архив кодов решений задач. Все решения проверены и делались в Linux, но, в основной своей части, не должны зависеть от операционной системы (некоторые проверялись в VirtualBox в Windows).

Спектр задач достаточно широкий получается: начиная от простых (но не очевидных) вопросов (которые с подтекстом), и заканчивая задачами, написание решений которых могут потребовать 2-3 дня плотной работы. Главным образом, этот материал предназначен для изучающих язык C. Но некоторые задачи потребуют пошевелиться и профессионалов в C, чтобы "не застаиваться" (как этюды для пианиста). Часть задач мне подбрасывали в разные годы те, кто изучали C (под моим ... кураторством, или каким другим образом), и борьба с частью таких задач вызывала азарт интереса.

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

И последнее ... почему "часть 1"? Потому что в работе находится такой же сборник, но по языку C++. Я являюсь последовательным сторонником точки зрения, рассматривающей язык C++ не как некоторое абсолютно автономное изобретение, а как надмножество языка C. И того, что изучать C++ лучше через изучение C с дальнейшим расширением до C++ (Существует другая, противоположная точка зрения). Так вот, "Задачи по программированию на языке C++" - это и будет часть 2.

Скачать свободно последнюю актуальную редакцию текста и архива кодов можно здесь:
Google: текст, архив кодов
Сейчас это редакция 23 от 12.01.2016, страниц 82.

В отношении авторских прав повторю:

Ничто из представленого в этом тексте не заимствовано ни из каких источников (кроме, возможно, идей постановок некоторых задач). Все представленные варианты решений - авторские, со всеми возможными ошибками и неточностями.

Как и всё опубликованное ранее, этот текст и все сопутствующие ему материалы представляется под лицензией: Creative Commons Attribution ShareAlike (http://legalfoto.ru/licenzii/) ("общественное достояние"):

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

Планирование параллельного исполнения в Go

О некоторых особенностях языка Go я уже писал здесь в блоге (Go конспект). Но одно из самых интересных мест Go - это как-раз то, как организуются параллельные ветви выполнения (и на различных процессорах в SMP). Утверждается, что после версии GoLang 1.1 (2012г.-2013г.) этот механизм Go-рутин радикально переделан, улучшен и сделан ещё существенно более эффективным, чем ранее.

Теперь используется алгоритм планирования с заимствованием работ (в оригинале даже "воровством работ", но в русскоязычной терминологии уже установился благозвучный термин заимствование). Обстоятельнейший (на 29 страниц) анализ самих принципов, на которых построен этот механизм, описан в Scheduling Multithreaded Computations by Work Stealing. Там же проведе сложнейший и детальный математический анализ производительности.

Коротко ("на пальцах") механизм описан в заметке The Go scheduler (by Daniel Morsing 30 June 2013). Это настолько интересно, что мной сделан перевод этой заметки, который вы можете найти на странице Диспетчер Go.

Утверждается (и это подтвердают эксперименты), что механизм Go-рутин (параллельного исполнения фрагментов кода) позволяет эффективно выполнять в параллель десятки, если не сотни, тысяч ветвей. К детальному рассмотрению этих механизмов ещё придётся не раз возвращаться.

4 способа писать в защищённую страницу

Паказанные в предыдщем сообщении несколько заметок, о внесении изменений в работу системных вызовов Linux, были готовы к сентябрю, но как-то руки не доходили разместить их здесь вовремя. За это время на Хабрахабр, где они были показаны, развернулось достаточно активное обсуждение ... но, главным образом, не обсуждение для достижения конструктивного результата, а из области любимой народной забавы "подбрасывание говна на вентилятор". Главным предметом обсуждений и сомнений стала необходимость записи в страницы оперативной памяти, отмеченные как защищённые от записи, и то, как это лучше сделать. Один из способов, которым я пользуюсь больше 10 лет, уже был показан в примерах кода к упоминаемым выше заметкам (да и в тексте есть об этом пара слов). Но предмет этот отдельно интересен, а в информационном пространстве есть целый ряд публикаций последних лет о том, как решать подобную задачу.

Перечислению, опробыванию и корректировке предлагаемых способов и посвящена очередная заметка "4 способа писать в защищённую страницу". Поскольку она не такая уж и маленькая (8 страниц), а, главное, требует для подтверждения предоставления подтверждающего кода, то я не вкопирываю текст сюда, а как и раньше просто даю ссылки где это всё можно взять.

Скачать текст можно здесь.
А код, соответственно, здесь.

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

4 статьи о системных вызовах Linux

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

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

1. Делаем доступным все символы ядра.

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

Скачать здесь.

Код здесь.

2. Модификация системного вызова.

Это о том, как вы можете изменить стандартное поведение любого системного вызова Linux.

Скачать здесь.

Код здесь.

3. Сетевые системные вызовы.

Сетевые (сокетные) системные вызовы в Linux обрабатываются не так, как сотни прочих системных вызовов. Это достаточно мало известно.

Скачать здесь.

Код здесь.

4. Добавить системный вызов.

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

Скачать здесь.

Код здесь.

Практикум по Linux Kernel (продолжение)

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

Чтобы тем, кому это интересно, не дёргать код примеров и задач из достаточно хаотичного форума, здесь и сам текст, и коды примеров (к тексту), и задачи, и решения большинства задач - всё это собрано в текстовые файлы для чтения и архив кодов для прогонов.

Выкладываю ссылки на последние актуальные версии:
Номер последней редакции: 245
Размер файла текста: 1039294 
Размер файла ответов задач: 67501 
Размер архива кодов: 1001433 
Дата обновления: 18 марта 2015

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

Скачать свободно последнюю актуальную редакцию текста, архива кодов и ответов на задачи можете здесь:
Google: текст, архив кодов, варианты решений
Yandex: текст, архив кодов

Всё, что хотелось бы обсудить, уточнить, замечания и предожения по тексту, какие бы ещё примеры и задачи включить в рассмотрение - обсуждаем здесь: Linux изнутри.

P.S. Есть ещё один маленький ньюансик, связанный с программированием для ядра Linux: разработчики ядра не связаны никакими соглашениями, типа POSIX для пользовательского пространства. Поэтому, через 5-6 последовательных версий ядра, то, что компилировалось и работало, перестаёт даже компилироваться из-за ошибок (изменения в API). Такие случаи особенно заслуживают указания и обсуждения, чтобы внести изменения в код примеров.

Практикум по Linux Kernel

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

Спектр задач там очень широкий получается: начиная от простейших вопросов, но которые с подтекстом, но разобраться с ними требуется 15 минут - и заканчивая задачами написания реальных драйверов (упрощённых, естественно, насколько можно), которые могут потребовать 2-3 дня плотной работы.

Если кого интересует этот предмет - присоединяйтесь к обсуждению. Найти его можно на форуме Linux, вот здесь: практикум по Linux Kernel

Работа только в самом начале. Объём примеров и задач будет прирастать...
Пока что, если у кого-то возникнет интерес "а как сделать нечто?" - формулируйте, и это станет очередной задачей, и найдёт своё решение.

Драйверы и модули ядра Linux (очередной цикл обновлений)

Предыдущий цикл обновлений рукописи "Драйверы и модули ядра Linux" завершён 10 июля 2014 года, одновременно с завершением цикла лекций по этому материалу для разработчиков компании  Global Logic, а также преподавателей и аспирантов некскольких киевских университетов.
Я предполагал некоторое время ... пожить спокойно, не возвращаться к этому тексту и архиву примеров кодов к нему. Если бы не...
... в версии ядра 3.17 разработчики радикально поменяли прототипы ключевых макросов ... по-крайней мере, то что мне сразу удалось отследить - в подсистеме сетевого стека ("удалось отследить" - это то, что сразу перестали компилироваться как драйвер, например, WiFi чипа Broadcom Corporation BCM43228, так и полтора десятка примеров модулей в архиве этой рукописи).
Какие изменения (те, что я заметил):

1. В <linux/netdevice.h> - создание сетевого интерфейса: 

- было:
#define alloc_netdev( sizeof_priv, name, setup )

- стало:

#define alloc_netdev( sizeof_priv, name, name_assign_type, setup )

Как легко видеть, теперь вместо 3-х параметров 4, 3-й из которых — константа, определяющая порядок нумерации создаваемых интерфейсов, описанная в том же файле определений:

/* interface name assignment types (sysfs name_assign_type attribute) */
#define NET_NAME_UNKNOWN     0 /* unknown origin (not exposed to userspace) */
#define NET_NAME_ENUM        1 /* enumerated by kernel */
#define NET_NAME_PREDICTABLE 2 /* predictably named by the kernel */
#define NET_NAME_USER        3 /* provided by user-space */
#define NET_NAME_RENAMED     4 /* renamed by user-space */

2. Во всём, что касается стандартов WiFi (файл <net/cfg802211.h>) ... в тексте и примерах это никак не нашло отражения, но всё же : начиная с 3.14 ядра изменилось число параметров и стало:
/*
 * cfg80211_ibss_joined - notify cfg80211 that device joined an IBSS
 * @dev: network device
 * @bssid: the BSSID of the IBSS joined
 * @channel: the channel of the IBSS joined
 * @gfp: allocation flags
 *
 * This function notifies cfg80211 that the device joined an IBSS or
 * switched to a different BSSID. Before this function can be called,
 * either a beacon has to have been received from the IBSS, or one of
 * the cfg80211_inform_bss{,_frame} functions must have been called
 * with the locally generated beacon -- this guarantees that there is
 * always a scan result for this IBSS. cfg80211 will handle the rest.
 */
void cfg80211_ibss_joined( struct net_device *dev, const u8 *bssid,

                           struct ieee80211_channel *channel, gfp_t gfp );

Здесь новый 3-й параметр имеет определение (в том же <net/cfg802211.h>):
/*
 * struct ieee80211_channel - channel definition
 *
 * This structure describes a single channel for use
 * with cfg80211.
 *
 * @center_freq: center frequency in MHz
 * @hw_value: hardware-specific value for the channel
 * @flags: channel flags from &enum ieee80211_channel_flags.
 * @orig_flags: channel flags at registration time, used by regulatory
 * code to support devices with additional restrictions
 * @band: band this channel belongs to.
 * @max_antenna_gain: maximum antenna gain in dBi
 * @max_power: maximum transmission power (in dBm)
 * @max_reg_power: maximum regulatory transmission power (in dBm)
 * @beacon_found: helper to regulatory code to indicate when a beacon
 * has been found on this channel. Use regulatory_hint_found_beacon()
 * to enable this, this is useful only on 5 GHz band.
 * @orig_mag: internal use
 * @orig_mpwr: internal use
 * @dfs_state: current state of this channel. Only relevant if radar is required
 * on this channel.
 * @dfs_state_entered: timestamp (jiffies) when the dfs state was entered.
 * @dfs_cac_ms: DFS CAC time in milliseconds, this is valid for DFS channels.
 */
struct ieee80211_channel {   enum ieee80211_band band;
   u16 center_freq;
   u16 hw_value;
   u32 flags;
   int max_antenna_gain;
   int max_power;
   int max_reg_power;
   bool beacon_found;
   u32 orig_flags;
   int orig_mag, orig_mpwr;
   enum nl80211_dfs_state dfs_state;
   unsigned long dfs_state_entered;
   unsigned int dfs_cac_ms;
};

Как это обычно бывает, в старых кодах драйверов, вместо этого 3-го параметра в вызовах cfg80211_ibss_joined(), можно поставить просто NULL (проверено - работает для BCM43228).

В итоге - пришлось сесть за пересмотр текста и примеров раньше, чем это планировалось.

Желающие смогут свободно обновить свой экземпляр текста и примеров кода.

Как и раньше, всё это предоставляется под лицензией Creative Commons Attribution ShareAlike (http://legalfoto.ru/licenzii/), о которой, если кому неизвестно, читайте подробнее в более ранних сообщениях.

Номер последней редакции: 223

Объём (страниц): 425
Размер файла текста: 1478880
Размер архива кодов:  893557
Дата размещения: 20 января 2015

Скачать эту редакцию текст и архив примеров к нему можно:
Google: текст и архив 

Yandex: текст и архив