...

суббота, 3 октября 2015 г.

[Перевод] Написание высокодоступного кода: 6 советов от инженера Imgur

Примечание переводчика: В нашем блоге мы много пишем о построении облачного сервиса 1cloud, но немало интересного можно почерпнуть и из опыта по работе с инфраструктурой других компаний. Инженер фотосервиса Imgur Джейкоб Гринлиф (Jacob Greenleaf) опубликовл в блоге на Medium материал, в котором изложил несколько советов по созданию высокодоступного кода для отказоустойчивых систем. Мы представляем вашему вниманию адаптированный перевод этой заметки.

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

Все нужно ограничивать


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

У нас в Imgur есть задача cron, которая называется «убийцей длинных запросов» — она сканирует активные зарпосы в MySQL, которые выполняются от имени запросов пользователей, и проверяет, как долго они выполняются, убивая те, что превышают заданный порог. Учитывая тот факт, что в PHP таймаут (max_execution_time) равняется 30 секундам, то запросы не должны выполняться больше нескольких минут. Этот убийца запросов, вполне вероятно, спас нас от многих бессонных ночей. Если у вас такого нет, создайте. Потом сами же скажете себе спасибо.

Используйте повторный запуск, но ограниченное число раз


Джим Грей написал в книге Why Do Computers Stop and What Can Be Done About It («Почему компьютеры останавливаются, и что с этим можно сделать») такую фразу: «большинство сбоев промышленных систем являются мягкими. Если просто перезапустить не выполнившуюся задачу, то обычно во второй раз сбоя не будет». Бывают баги, которые всплывают лишь время от времени, поэтому повысить доступность систем можно с помощью добавления функции повторного запуска. Однако, тут нужно быть аккуратным, чтобы не устроить DDoS на свои системы собственными руками!

Следует последовать первому совету и использовать ограниченное количество попыток перезапуска и заставлять систему ждать все больше времени при каждой попытке повторного пуска. Это поможет распределить нагрузку.

Нужно использовать контрольные процессы


Для создания софта с высокими требованиями по части доступности часто используется Erlang. В нем есть паттерн контроля (supervisors): каждая задача, которую выполняет программа, структурирована таким образом, чтобы работать под надзором контролирующего процесса (супервизора). Если супервизор обнаруживает неожиданное завершение задачи, он ее перезапускает (как в предыдущем правиле) с известного безошибочного состояния. Нет никакого смысла перезапускать то, что все равно не будет работать. Хорошим средством автоматического перезапуска веб-сервера или процессов-демонов является Monit.

Важно добавлять проверки здоровья и использовать их для перераспределения запросов


Разработчик должен думать о том, как свести всю кучу переменных в коде системе к простому булевому вопросу «здорова ли эта вещь? Работает ли она?» В Imgur используется встроенный в ELB мониторинг здоровья, который проверяет, живы ли сетевые узлы, и автоматически перераспределяет запросы к ним в случае падения.

Избыточность не просто «хорошо бы иметь», она обязательно должна быть


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

Как-то раз в Imgur пришло уведомление о выключении виртуальных машин в облаке Amazon. Обычно такие алерты приходят заранее, но в тот раз это случилось уже после удаления виртуалок (и после того, как PagerDuty и Nagios предупредили о наличии проблем).

Лучше проверенные временем средства, чем горячие новинки


Противостоять искушению попробовать в деле новые популярные инструменты довольно сложно. К прмиеру, DevOps-сообщество сходит с ума по CoreOS и легким контейнерам «в стиле LXC». Однако когда Джейкоб Гринлиф попробовал с ним работать, выяснилось, что в компоненте ядра (FleetD) содержался баг, затрагивавший работу с планировщиком, который мог повлечь остановку работы системы. Гринлиф смог разобраться с проблемой после многих часов отладки, завершившейся в два часа утра. Новые технологии часто могут содержать никому еще неизвестные ошибки и причины для сбоя.

Кроме того, у более новых проектов есть общая черта — часто они слишком сырые для работы в продакшене. Например, у Golang нет официального отладчика, а альтернативный открытый отладчик появился всего несколько месяцев назад. Также инструменты мониторинга и трассировки языка Go ни в какое сравнение не идут с Java JMX и Erlang.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

[Перевод] 40 ключевых концепций информационных технологий доступно и понятно

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

Для того, чтобы сделать обучение более веселым и интересным, представляю вам перечень важных теорий и концепций информатики, объяснённых с помощью аналогий с минимальным количеством технических деталей. Это будет похоже на очень быстрый курс информатики для всех с целью просто дать вам общее представление об основных концепциях.

Важные замечания:

  • Пункты с неуказанным источником написаны мной самостоятельно. Поправьте меня, если вы заметите какие-то неточности. Предложите лучшую аналогию, если это возможно.
  • Заголовки ссылаются на соответствующие им статьи в Wikipedia. Пожалуйста, читайте эти статьи для более серьезных и детальных объяснений.
  • Аналогии — отличный способ объяснить материал, но они не идеальны. Если вы хотите по-настоящему понять перечисленные концепции, вам следует начать с фундаментальных азов и рассуждать, исходя из них.

Также зацените эту инфографику (вариант на русском), если вы просто начинающий программист.
Допустим вы заказываете полную коллекцию серии фильмов о Гарри Поттере из 8 частей на Amazon и скачиваете ту же самую коллекцию в то же время. Вы хотите проверить, какой метод быстрее. Магазин доставил коллекцию почти через день, а скачивание завершилось всего на 30 минут раньше этого. Класс! Это была близкая гонка.
Но что если я закажу несколько Blu-ray фильмов, например Властелин Колец, Сумерки, трилогию о Тёмном Рыцаре и тому подобное, и в то же время буду пытаться скачать все эти фильмы? Доставка всё равно займёт день, но скачивание в сети продлится на этот раз 3 дня.
При покупках в интернете количество покупаемых вещей (входные данные) никак не влияет на время, за которое они будут доставлены. Выходные данные константны. Мы называем это О(1).
Но при скачивании в сети время скачивания прямо пропорционально размеру скачиваемых фильмов (входные данные). Мы называем это O(n). Из этих экспериментов мы понимаем, что покупки в интернете лучше масштабируются, чем загрузка файлов из сети. Очень важно понимать “О-большое”-нотацию, так как это поможет вам анализировать эффективность и масштабируемость алгоритмов.
Замечание: нотация “О-большое” служит для оценки эффективности в худшем случае для алгоритма. Давайте согласимся, что О(1) и О(n) — худшие сценарии для приведённого примера.
Больше информации: Big O Notations (video), Plain English explanation of Big O, A Beginner’s Guide to Big O Notation

Больше информации: Sorting Algorithm Animations, Beautiful and configurable visualizations of sorting algorithm

Кто-то в кино спрашивает вас, на каком ряду вы сидите. Вы слишком ленивы, чтобы посчитать, так что вы спрашиваете человека, сидящего перед вами. Вы просто будете должны добавить 1 к его ответу, чтобы получить номер своего ряда. Отличная идея, не так ли? Однако, человек перед вами сделает то же самое, и так дальше. В конце концов вопрос доберётся до первого ряда и человек на первом ряду ответит “Я в ряду номер 1!”. С этого момента правильное сообщение (увеличиваемое на 1 за каждый ряд) пройдёт весь свой путь обратно к тому, что изначально спросил.

Aaron Krolik/Quora

Есть ещё один пример, известный как эффект Дросте (на русском).
Медсестра несет поднос с пачкой какао и чашкой, на которой нарисовано уменьшенное изображение её, держащей всё то же самое, которое в свою очередь содержит ещё более маленькое изображение той же картинки, и так далее.
Тут вы можете найти ещё больше примеров эффекта Дросте, если хотите, чтобы вам стало сонливо.

Если вы ещё не до конца поняли рекурсию, попробуйте посмотреть тут… Ну а если поняли — продолжайте читать.

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

Balaji Viswanathan/Quora

Термин “большие данные” описывает наборы данных на столько большие и сложные, что с ними невозможно работать с помощью обычных инструментов обработки данных.
Больше информации: Big Data by TED-Ed (video), What is Big Data and Hadoop (video)


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

Представьте, что вы решили прогуляться, и ваша цель — добраться до самого высокого места. У вас есть карта, но на карте тысячи возможных путей. Вы слишком ленивы и у вас просто нет времени, чтобы попробовать каждый из них. Так что к черту карту! Вы просто идете вперёд с простой стратегией — быть жадным и близоруким. Вы просто выберете пути, которые как можно более наклонены вверх.
После того, как ваше путешествие завершилось и ваше тело стало измученным и уставшим, вы посмотрели на карту местности впервые. О боже мой! Вот грязная речка, через которую я должен был переправиться вместо того, чтобы идти вверх!
Жадный алгоритм делает лучший выбор в текущий момент времени и никогда не пересматривает своих решений.

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

Это — гора Эверест, самый крупный вызов, с которым вы сталкивались. Ваша задача — добраться до вершины, но это очень непрактично забираться на Эверест помногу раз. У вас есть только один шанс. И вы стали куда более предусмотрительнее, чем раньше. Вместо того, чтобы всегда взбираться наверх, вы изредка двигаетесь вниз и находите новые пути, чтобы уменьшить риск пойти по неправильному пути. Чем выше вы забираетесь, тем меньше вероятность того, что вы пойдёте вниз.

Отец: *Пишет “1+1+1+1+1+1+1+1 =” на куске бумаги*
Отец: Чему это равно?
Ребенок: *Считает и тремя секундами спустя* Восемь!
Отец: *Дописывает ещё “+1”*
Отец: А теперь?
Ребенок: *Сразу же* Девять!
Отец: Ого, как ты посчитал так быстро?
Ребенок: Ты просто добавил ещё один!
Отец: Ты понял, что тебе не нужно пересчитывать, потому что ты запомнил, что это было восемь до этого. Отлично!

Jonathan Paulson / Quora

Пример выше описывает мемоизацию (на русском) (да, мемоизация — это не запоминание), подход к динамическому программированию сверху вниз, при котором результаты предыдущих рассчетов сохраняются для дальнейшего использования.
Больше информации: Dynamic Programming – From Novice to Advanced (TopCoder), Tutorial for Dynamic Programming (CodeChef)


Парат Шах привел прекрасную аналогию тут, но она слишком длинная, чтобы включать её в эту статью.
Равенство классов P и NP задач — одна из наиболее популярных и важных неразрешенных проблем в информатике.
Допустим, у нас есть следующая задача:
Задача 1: 7 x 17 = p
Ответ — 119.
Это было легко, не так ли? Но что если у нас противоположная задача:
Задача 2: p x q = 119 (p и q не могут быть 1 и 119)
Для того, чтобы решить вторую задачу, предполагая, что вы не видели первую, вам нужно пройтись по всем возможным числам от 2 до 118. Существует хороший алгоритм, позволяющий просто раскладывать числа на множители (на русском).
Что если я спрошу: может ли p быть 7? Вы сможете очень просто ответить, просто разделив 119 на 7.
Умножение — это просто. Разложение на множители числа — сложно.
В итоге, задача 1 — P (полиномиальная), так как её просто решить. Компьютер отлично справляется с умножением двух огромных чисел, не тратя существенно больше времени, чем умножая два небольших числа.
Задача 2 — это NP (недетерминированная полиномиальная), потому что её легко проверить, но сложно решить. Разложение на множители числа 119 — все ещё не очень сложная задача для компьютера, но что на счёт числа, состоящего из 500 знаков? Это невозможно ни для одного компьютера в наши дни.
И тут начинается важная часть: являются ли NP-задачи (например, разложение на множители) также и P-задачами (как умножение), а мы просто ещё не обнаружили эффективного способа решения NP-задач? Действительно ли NP-зачадачи сложны или нам просто нужен момент просветления какого-нибудь хорошего ученого (может быть вас?), который придумает эффективный алгоритм? Или может быть люди слишком глупы? Представьте, что существует машина или жизнь, обладающая куда большим интелектом, чем человек. Мы для них, как муравьи для нас. Наш уровень интеллекта для них совершенно несущественен. Решение данной проблемы для них как 1+1.
Так или иначе, почему же задача равенства классов P и NP задач так важна? Если мы сможем доказать, что P=NP, это означает, что все NP-задачи могут быть решены за разумное компьютерное время. Мы сможем вылечить рак (укладка белка, на русском), взламывать пароли (RSA, на русском) и тому подобное. Это изменит мир.
Проблема равенства классов P- и NP-полных задач является одной из семи в списке проблем тысячелетия от математического института Клэя. Наградой за первое верное решение является $1 000 000.
Больше информации: P vs. NP and the Computational Complexity Zoo (video), Simple Wikipedia

3.1 Как работают компьютеры



Компьютеры работают, добавляя сложность поверх сложности (Computers work by adding complexity on top of complexity). Для того, чтобы вести машину, не обязательно понимать, как работает её двигатель. Сложные детали скрыты.
Так как же компьютер превращают бинарный код, нолики и единички в программы? Вот превосходное видео, в котором с помощью домино визуализируется, как компьютеры осуществляют бинарные вычисления на самом базовом, фундаментальном уровне:


Больше информации: Interactive explanation on how computer works



Больше информации: The Freeze App Analogy, Simple Wikipedia

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


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

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


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

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

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


Вот, что произойдет, если вы допустите выполнение параллельных транзакций в системе банкинга, а состояние гонки не будет обрабатываться:
  • У вас есть $1000 на вашем счету
  • Кто-то переводит вам $500, а вы снимаете $300 в банкомате
  • Представьте, что обе транзакции происходят одновременно — обе транзакции будут считать. что ваш текущий баланс равен $1000
  • Теперь, транзакция А добавляет $500 на ваш счёт и ваш текущий баланс становится равным $1500. Однако, транзакция B так же считала, что ваш текущий баланс равен $1000, и она, допустим, завершится на одну миллисекунду позже, чем транзакция А. Она вычтет $300 из $1000 и сделает ваш текущий баланс равным $700
  • Теперь у вас есть $700 вместо $1200, так как транзакция В перезаписала действия транзакции А
  • Это произошло, так как банковская система не принимала в расчет текущих происходящих транзакций

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

На этот раз, в тот момент, когда совершается транзакция А, ваш счет заблокируется. Вы не сможете снять деньги в банкомате. Он будет разблокирован, как только транзакция А завершится.

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

Давайте немного изменим наше решение.


4.4.1 Бинарный семафор


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

4.4.2 Семафор с подсчётом


Двоичный семафор прост. 1 = продолжить транзакцию. 0 = ждать. С другой стороны, подсчитывающий семафор позволяет более одному процессу выполняться одновременно.

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


Взаимная блокировка — это еще одна стандартная проблема с параллельными вычислениями.

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

  • Питер переводит вам $1000 (транзакция А), а вы переводите ему $500 в то же самое время (транзакция В)
  • Транзакция А блокирует счет Питера и снимает $1000 с его счета
  • Транзакция В блокирует ваш счет и снимает $500 с вашего счета
  • Теперь, транзакция А пытается получить доступ к вашему аккаунту, чтобы добавить на него $1000 от Питера
  • В то же время, транзакция В так же пытается добавить ваши $500 на счет Питера

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

А вот пример из реальной жизни:

Парень: пусть она первая подойдёт
Девушка: пусть он первая подойдёт
Так и умерла многообещающая любовная история

Padmakar Kalghatgi/Quora

5.1 Компьютерное хакерство [взлом]


Хакерство похоже на взлом дома. Ниже приведены некоторые популярные хакерские техники:

5.1.1 Атака полным перебором (или атака методом грубой силы) (на русском)


Попробуйте сотни или тысячи различных ключей. Опытный грабитель сначала попробует самые часто используемые ключи.

Атака полным перебором пробует каждый возможный пароль, и обычно начинает угадывать с самых распространенных паролей, таких как «123456», «йцукен» и т.п.

5.1.2 Социальная инженерия (на русском)


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

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

5.1.3 Брешь в безопасности (эксплойт) (на русском)


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

5.1.4 Троян (на русском)


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

Троян — вредоносная программа, которая притворяется полезной, запуская вредоносный код в фоне.

5.1.5 Руткит (на русском)


Ваш замок заклинило и вы вызвали слесаря. Он починил ваш замок и тайно сделал себе дубликат ключа.

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

5.1.6 Распределенная атака типа «Отказ в обслуживании» (DDoS, на русском)


Приведем аналогию с книжным магазином.

Представьте, что 100 человек приходят в ваш маленький книжный магазин в одно время. Ваш книжный магазин весь забит и больше никто не может войти. Вы не можете попросить их уйти, потому что не похоже, чтобы они приходили группами. Они может быть и не знают друг друга вовсе. Многие из них кажутся реально заинтересовавшимися вашими книгами. Некоторые даже спрашивают вас, где находятся книжные полки. Кто-то на кассе пытается расплатиться копейками.

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

DDoS пытается вывести из строя ваш сайт или сервис, просто затапливая, переполняя его посетителями.

Ссылка на оригинальную визуализацию


5.2.1 Симметричная криптография (на русском)


Допустим, Элис и Боб хотят отправлять что-то друг другу. Чтобы убедиться, что никто не сможет увидеть, что они друг другу отправляют, они запирают это в коробке. Они делают 2 идентичных (симметричных) ключа для замка и встречаются, чтобы обменяться этими ключами.

5.2.2 Асимметричная криптография (на русском)


Обмен одинаковыми ключами сносно работает для двух людей. Что если Элис хочет обмениваться вещами с другим парнем по имени Карл, и Элис так же не хочет, чтобы кто-то видел эти вещи. Элис не может использовать тот же замок и ключ, которые они использовали с Бобом, так как Боб сможет открыть коробку своим ключом.

Конечно Элис может обменяться совершенно новым и соответственно другим ключом и замком с Карлом, но что если Элис хочет обмениваться вещами с 10 различными людьми? Ей придется владеть 10 различными ключами!

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

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

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

Больше информации: Public Key Cryptography: Diffie-Hellman Key Exchange (video)


Вы выясняете всё, что нужно сделать, и записываете требования. Это как водопад: тут нет пути назад, пока вы не начнете с самого начала. Вы перемещаетесь к следующей фазе только когда текущая фаза завершена.

Вы понимаете некоторые вещи, которые вы должны сделать в первую очередь. Затем последовательно улучшаете, эволюционируете, адаптируете ПО в процессе разработки.

Приведу некоторые популярные реализации гибкой методологии разработки:


6.3 Разработка ПО в реальном мире


Итак, вы научились программировать. Вы пишите хороший и красивый код (надеюсь), и всё прекрасно. Дайте мне представить вам ковбойское программирование — методологию разработки, которую не преподают в колледже.

Ещё вы удивляетесь, почему вы застряли с оценкой времени разработки:

И методологии часто неправильно используют:

Dilbert

Dilbert

Ну вот и всё. Информатика в двух словах.

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


Вопрос 1: В чем разница между ученым-информатиком и программистом

Специалист в информатике (computer scientist) это как физик, а программист — это как инженер.

HerbN/Stack Overflow

Вопрос 2: что такое программирование?


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

Что это значит? Представьте, что вы должны научить ребенка ходить в душ. Ребенок знает только как следовать вашим инструкциям. Так что вы говорите ребенку:

  1. Зайти в ванну
  2. Включить душ
  3. Встать под душ
  4. Взять мыло
  5. И так далее...

О, черт, ребёнок не снял свою одежду перед тем, как встать под душ!

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

Вопрос 3: почему вы не должны отвлекать программиста, когда он сосредоточен?

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

EpsilonVector/Programmers Stack Exchange

Вопрос 4: В чем разница между Java и JavaScript?


Они никак не связаны.

Java и JavaScript похожи примерно так же, как корова и караван (или как Ленин и Ленинград?)

Greg Hewgill/Stack Overflow

Вопрос 5: В чем разница между JavaScript и JQuery?


JQuery — это библиотека, сделанная с помощью JavaScript.

JavaScript — это страшненький задрот, а JQuery — это волшебник, который превращает его в привлекательного игрока футбольной команды.

Совет от Will Sargent

Вопрос 6: В чем разница между фреймворком (каркасом) и библиотекой?


Ваш код вызывает библиотеку. Фреймворк вызывает ваш код.

Ian Boyd/Stack Overflow

Библиотека — это инструмент. Фреймворк — это образ жизни.

James Curran/Stack Overflow

Вопрос 7: Как много строк кода средний разработчик пишет в день?


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

Измерение продуктивности в программировании количеством строк кода — это как измерять прогресс постройки самолёта по его весу.

Bill Gates

Вопрос 8: Что такое объектно-ориентированное программирование?


Объекты — это существительные, методы — глаголы.

k rey/Programmers Stack Exchange

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

Вот пример: если я ваш объект «прачечная», вы можете дать мне вашу грязную одежду и отправить мне сообщение, в котором сказать «Пожалуйста, постирайте мои вещи». Я знаю лучшую прачечную в Сан Франциско. Я говорю по-английски и у меня есть деньги. Так что я выхожу, сажусь в такси и говорю водителю отвезти меня туда. Я получаю ваши постиранные вещи, снова сажусь в такси и возвращаюсь обратно. Я отдаю вам ваши чистые вещи со словами «Вот ваши чистые вещи».

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

Steve Jobs/Rolling Stone Interview
В ресторане вы заказываете еду (вызываете API) из меню (набор методов API). Как только ваша еда готова (готов ответ от API), официант принесет вам еду.

Базовая идея такова: попросите то, что вам нужно, и система вернет вам результат, не раскрывая того, как именно она это сделала.

Вопрос 10: В чем разница между SQL и NoSQL базами данных



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

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

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

mgoffin/Stack Overflow

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

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

Предыдущую часть обсуждения мы завершили на такой вот оптимистической ноте: «Подобным образом мы можем изменить поведение любого системного вызова Linux». И тут я слукавил — любого… да не любого. Исключение составляют (могут составлять) группа сетевых системных вызовов, работающих с BSD сокетами. Когда сталкиваешься с этим артефактом в первый раз — это изрядно озадачивает.
Для прояснения картины воспользуемся заметками одного из непосредственных разработчиков сетевой подсистемы Linux:
Network systems calls on Linux (2008 год). Я коротко перескажу её основное содержание (в интересующей нас части), кому это не интересно может воспользоваться оригиналом.

Когда поддержка BSD сокетов были добавлена в ядро Linux, разработчики решили добавить их единовременно все 17 (на сегодня 20) сокетных вызовов, и добавили для этих вызовов один дополнительный уровень косвенности. Для всей группы этих вызовов введен один новый, редко упоминаемый, системный вызов (см. man socketcall(2)):

int socketcall( int call, unsigned long *args ); 


где:
— call — численный номер сетевого вызова (SYS_CONNECT, SYS_ACCEPT… мы их увидим вскоре);
— args — указатель 6-ти элементного массива (блок параметров), в который последовательно упакованы все параметры любого из системных вызовов этой группы (сетевой), без различения их типа (приведенные к unsigned long);

А вот такой макрос в ядре (<net/socket.c>), в котором «зашито» сколько фактически параметров должен использовать каждый из сокетных вызовов в зависимости от его номера (в диапазоне от 1 до 20):

/* Argument list sizes for sys_socketcall */ 
#define AL(x) ((x) * sizeof(unsigned long)) 
static const unsigned char nargs[ 21 ] = { 
       AL(0),AL(3),AL(3),AL(3),AL(2),AL(3), 
       AL(3),AL(3),AL(4),AL(4),AL(4),AL(6), 
       AL(6),AL(2),AL(5),AL(5),AL(3),AL(3),
       AL(4),AL(5),AL(4)
}; 
#undef AL


(Причём, narg[ 0 ] вообще не используется, потому размерность его и 21.)

Номер сокетного вызова в пространство ядра (int 0x80 или sysenter) передаётся в регистре eax. Значения самих этих констант мы можем подсмотреть в заголовках пространства пользователя (<linux/net.h>):

#define SYS_SOCKET      1               /* sys_socket(2)                */ 
#define SYS_BIND        2               /* sys_bind(2)                  */ 
#define SYS_CONNECT     3               /* sys_connect(2)               */ 
#define SYS_LISTEN      4               /* sys_listen(2)                */ 
#define SYS_ACCEPT      5               /* sys_accept(2)                */ 
...
#define SYS_SENDMSG     16              /* sys_sendmsg(2)               */ 
#define SYS_RECVMSG     17              /* sys_recvmsg(2)               */ 
#define SYS_ACCEPT4     18              /* sys_accept4(2)               */ 
#define SYS_RECVMMSG    19              /* sys_recvmmsg(2)              */ 
#define SYS_SENDMMSG    20              /* sys_sendmmsg(2)              */ 


Собственно, схема обработки к этому моменту уже должна быть понятна:
— необходимое число параметров системного вызова пакуется в массив unsigned long, наибольшее число параметров (6) для SYS_SENDTO=11 (nargs[ 11 ]):
ssize_t sendto( int sockfd, const void *buf, size_t len, int flags, 
                const struct sockaddr *dest_addr, socklen_t addrlen ); 


— адрес сформированного массива передаётся 2-м параметром системного вызова, первым параметром передаётся номер сокетного вызова (например SYS_SENDTO);
— все сокетные вызовы обрабатываются единственным обработчиком ядра sys_socketcall() (__NR_socketcall = 102);
— обработчик сначала копирует из пространства пользователя массив значений-параметров, а далее, в зависимости от eax, копирует из пространства пользователя вослед и области данных, указываемые (возможно) значениями указателей из этого массива параметров.

Некоторые новые архитектуры (так в оригинале) не используют такой непрямой способ вызова, а используют для этих вызовов такую же реализацию, как и для всех остальных системных вызовов. Так это реализовано, в частности, для X86_64 и ARM. Таким образом, даже 64-битовые и 32-битовые (эмулируемые в системе X86_64) приложения будут выполняться по разной схеме. Но не станем на это пока отвлекаться…

Удостовериться в том, что обслуживание сокетных вызовов в 32 и 64 битовых системах осуществляется принципиально по-разному, можно если в каталоге приложений пространства пользователя (заголовочные файлы библиотек языка C, <i386-linux-gnu/asm>) рассмотреть, для сравнения, определения набора системных вызовов для 32 и 64 битовых режимов:

$ cat unistd_32.h | grep socketcall 
#define __NR_socketcall 102 
$ cat unistd_32.h | grep connect 

$ cat unistd_64.h | grep socketcall 
$ cat unistd_64.h | grep connect 
#define __NR_connect 42        


В 32-бит системе присутствует вызов sys_socketcall(), но отсутствуют вызовы для каждого из 20 сокетых вызовов. И напротив, в 64-бит системе отсутствует такой системный вызов как sys_socketcall(), но присутствует весь полный набор системных вызовов для каждого из 20-ти сокетных вызовов.

Сам же автор заметки в завершение, в качестве оценки, пишет следующее: Данная методика кажется довольно уродливой (rather ugly) на первый взгляд, при сравнении с современными методами объектно-ориентированного программирования, но есть и определенная простота в нем. Он, также, хранит данные компактно, что улучшает попадание в кэши. Единственная проблема заключается в том, что выборка должна быть выполнена вручную, а это означает, что здесь легко выстрелить себе в ногу.


Возможность перехвата сетевых системных вызовов будем иллюстрировать на макете распределённого файервола (максимально его упростив). Одно время с этой идеей очень сильно носились, в качестве реализации файервола для больших и сверхбольших сетей (особенно в окружении Cisco). Существует много публикаций на эту тему, например, две из них, дающие полное представление о том, что понимается как распределённый файервол: Implementing a Distributed Firewall и
Automated Implementation of Stateful Firewalls in Linux.

Предложение состоит в том, чтобы контролировать не весь TCP/IP трафик на уровне IP пакетов, а осуществлять регламент на каждом хосте сверхбольшой сети только для протокола TCP и только в момент установления соединения. Под контроль попадают только 2 системных вызова: accept() и connect(). Более глубокое обсуждение распределённого файервола увело бы нас очень далеко от наших целей … рассмотрим только то как мы могли бы контролировать эти сетевые сетевые вызовы.

В качестве иллюстрации реализации перехвата сокетных вызовов был реализован модуль такого сетевого фильтра я ядре для вызовов accept() и connect(). Сделан этот модуль в максимально упрощенной (усечённой) реализации: в качестве параметров при загрузке модуль получает IP адрес (параметр deny) и TCP порт (параметр port), соединения с которыми должны быть запрещены (и ещё один дополнительный параметр debug — уровень диагностического вывода).

Примечание: В тестируемом варианте запрещённые IP адреса и TCP порты допускались множественными, хранились в циклическом списке типа struct list_head (как это и принято повсеместно в ядре), а помещались (или удалялись) они туда отдельным приложением — демоном политики в пространстве пользователя. Фильтр в ядре и должен функционировать некоторым подобным образом, но это слишком громоздко для статьи, описывающей принцип, тем более, что не принцип файервола, а принцип работы с сетевыми системными вызовами. При всех упрощениях код всё ещё великоват, поэтому я помеаю его под спойлер.

Итак, код модуля-примера:
static int debug = 0;                                       // debug output level: 0, 1, 2 
module_param( debug, uint, 0 ); 
static char* deny;                                          // string parameter: denied IPv4 
module_param( deny, charp, 0 ); 
static int port = 0;                                        // denied port 
module_param( port, int, 0 ); 

static void **taddr;                                        // table sys_call_table address 
u32 ipdeny;                                                 // denied IP 

#include "find.c" 
#include "CR0.c" 

inline char* in4_ntoa( uint32_t ip ) {                      // mapping IP to a string 
   static char saddr[ MAX_ADDR_LEN ]; 
   sprintf( saddr, "%d.%d.%d.%d", 
            ( ip >> 24 ) & 0xFF, ( ip >> 16 ) & 0xFF, 
            ( ip >> 8 ) & 0xFF, ( ip ) & 0xFF 
          ); 
   return saddr; 
} 

asmlinkage long (*old_sys_socketcall) ( int call, unsigned long __user *args ); 

asmlinkage long new_sys_socketcall( int call, unsigned long __user *args ) { 
#define PARMS 3 
   static unsigned long a[ PARMS ]; // accept() and connect() have the same number of parameters 3 
   static struct sockaddr sa; 
   // ----------- nested functions are a GCC extension --------- 
   long get_addr( void ) { 
      const unsigned int len = PARMS * sizeof( unsigned long ); 
      if( copy_from_user( a, args, len ) ) 
         return -EFAULT; 
      if( copy_from_user( &sa, (struct sockaddr __user*)a[ 1 ], sizeof( struct sockaddr ) ) ) 
         return -EFAULT; 
      return 0; 
   } 
   // ---------------------------------------------------------- 
   long ret; 
   if( SYS_ACCEPT == call ) {                               // accept() before syscall 
      long err; 
      if( ( err = get_addr() ) < 0 ) return err; 
      if( AF_INET == sa.sa_family ) {                       // only IPv4 
         struct sockaddr_in *usin = (struct sockaddr_in *)&sa; 
         if( ntohs( usin->sin_port ) == port ) { 
            LOG( "accept from denied port %d\n", ntohs( usin->sin_port ) ); 
            return -EIO; 
         } 
      } 
   } 
   if( SYS_CONNECT == call ) {                       // connect() before syscall 
      long err; 
      if( ( err = get_addr() ) < 0 ) return err; 
      if( AF_INET == sa.sa_family ) {                // only IPv4 
         struct sockaddr_in *usin = (struct sockaddr_in *)&sa; 
         DEB( "connect to %s:%d\n", 
              in4_ntoa( ntohl( usin->sin_addr.s_addr ) ), ntohs( usin->sin_port ) ); 
         if( ( deny != NULL && ntohl( usin->sin_addr.s_addr ) == ipdeny ) || 
             ( port  != 0 && ntohs( usin->sin_port ) == port ) )  { 
            LOG( "connect to %s:%d denied\n", 
                 in4_ntoa( ntohl( usin->sin_addr.s_addr ) ), ntohs( usin->sin_port ) ); 
            return -EACCES; 
         } 
      } 
   } 
   ret = old_sys_socketcall( call, args );           // retranslate to original sys_socketcall() 
   if( SYS_ACCEPT == call ) {                        // accepr() after syscall 
      long err; 
      if( ( err = get_addr() ) < 0 ) return err; 
      if( AF_INET == sa.sa_family ) {                // only IPv4 
         struct sockaddr_in *usin = (struct sockaddr_in *)&sa; 
         DEB( "accept from %s:%d\n", 
              in4_ntoa( ntohl( usin->sin_addr.s_addr ) ), ntohs( usin->sin_port ) ); 
         if( ( deny != NULL && ntohl( usin->sin_addr.s_addr ) == ipdeny ) || 
             ( port  != 0 && ntohs( usin->sin_port ) == port ) )  { 
            LOG( "accept from %s:%d denied\n", 
                 in4_ntoa( ntohl( usin->sin_addr.s_addr ) ), ntohs( usin->sin_port ) ); 
            return -EACCES; 
         } 
      } 
   } 
   return ret; 
} 

static int __init init( void ) { 
   void *waddr; 
   // ----------- nested functions are a GCC extension --------- 
   int pos_in_table( const char *symbol ) {          // position in sys_call_table (__NR_*) 
      const int last = __NR_process_vm_writev;       // near last syscall in i386 
      int n; 
      waddr = find_sym( symbol ); 
      if( NULL == waddr ) return -1; 
      for( n = 0; n <= last; n++ ) 
         if( taddr[ n ] == waddr ) break; 
      return n <= last ? n : -1; 
   } 
   // -------------------------------------------------------- 
   void show_in_table( char *symb ) {                // print info about symbol 
      waddr = find_sym( symb ); 
      if( NULL == waddr ) { 
         DEB( "symbol %s not found in kernel\n", symb ); 
      } 
      else { 
         int n = pos_in_table( symb ); 
         if( n > 0 ) 
            DEB( "symbol %s address = %p, position in sys_call_table = %d\n", symb, waddr, n ); 
         else 
            DEB( "symbol %s address = %p, not found in sys_call_table\n", symb, waddr ); 
      } 
   } 
   // -------------------------------------------------------- 
   ipdeny = ntohl( deny != NULL ? in_aton( deny ) : in_aton( "0.0.0.0" ) ); 
   LOG( "denied IP: %s\n", deny != NULL ? in4_ntoa( ipdeny ) : "no" ); 
   if( port != 0 ) 
      LOG( "denied TCP port: %d\n", port ); 
   if( NULL == ( taddr = find_sym( "sys_call_table" ) ) ) { 
      ERR( "sys_call_table not found\n" ); return -EINVAL; 
   } 
   DEB( "sys_call_table address = %p\n", taddr ); 
   show_in_table( "sys_accept" ); 
   show_in_table( "sys_connect" ); 
   show_in_table( "sys_socketcall" );                       // only diagnostic 
   old_sys_socketcall = (void*)taddr[ __NR_socketcall ]; 
   if( NULL == ( waddr = find_sym( "sys_socketcall" ) ) ) { // sys_socketcall not exported 
      ERR( "sys_socketcall not found\n" ); return -EINVAL; 
   } 
   if( old_sys_socketcall != waddr ) {                      // reinsurance! 
      ERR( "Oooops! I don't understand: addresses not equal\n" ); return -EINVAL; 
   } 
   if( debug ) show_cr0(); 
   rw_enable(); 
   taddr[ __NR_socketcall ] = new_sys_socketcall; 
   if( debug ) show_cr0(); 
   rw_disable(); 
   if( debug ) show_cr0(); 
   LOG( "install new sys_socketcall handler: %p\n", &new_sys_socketcall ); 
   return 0; 
} 
 
static void __exit exit( void ) { 
   LOG( "sys_socketcall handler before unload: %p\n", (void*)taddr[ __NR_socketcall ] ); 
   rw_enable(); 
   taddr[ __NR_socketcall ] = old_sys_socketcall; 
   rw_disable(); 
   LOG( "restore old sys_socketcall handler: %p\n", (void*)taddr[ __NR_socketcall ] ); 
   return; 
} 

module_init( init ); 
module_exit( exit ); 



Код максимально упрощён, такие вещи, как макросы диагностики LOG(), ERR() уже показывались, отчасти, в предыдущих частях. Функция find() тоже уже обсуждалась. Для записи в защищённую от записи область таблицы sys_call_table существует, как минимум, 3-4 альтернативных варианта, все они назывались и давались ссылками в обсуждениях предыдущей части. Защита от выгрузки модуля на время обслуживания системных вызовов, путём инкремента счётчика ссылок модуля, тоже не показана (называлось в предыдущей части). Все эти подробности присутствуют в кодах прилагаемого архива. Кроме того, коды в архиве обильно пересыпаны комментариями, содержащими выдержки из исходников ядра, с указанием файлов в дереве кодов ядра — это подсказывает требуемые структуры данных.

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

  • взять под контроль (сменить обработчик) системного вызова sys_socketcall();
  • если код вызова (1-й параметр sys_socketcall()) равен SYS_ACCEPT или SYS_CONNECT, то скопировать из пространства пользователя 3-х элементный массив параметров unsigned long (в общем случае 6 элементов, для SYS_SENDMSG, например);
  • 2-й элемент массива (соответствующий 2-му параметру accept() или connect()), хоть он и выглядит как unsigned long — это указатель на struct sockaddr в адресном пространстве пользователя, вторым шагом доступа к параметрам копируем структуру из адресного пространства пользователя;
  • структура содержит параметры IP адрес и TCP порт, если они попадают в перечень запрещённых — возвращаем код ошибки и отменяется операция, если нет — вызываем оригинальный обработчик системного вызова;
  • для всех остальных (18-ти, не SYS_ACCEPT и SYS_CONNECT) сокетных вызовов просто осуществляем транзитом вызов оригинального sys_socketcall();
  • запросы, не относящиеся к протоколу IPv4 без модификации передаются сетевому стеку;

Некоторую дополнительную сложность создаёт тот факт, что для вызова accept() проверку приходится выполнять дважды:
  • номер TCP порта раньше оригинального системного вызова, когда сервер начинает прослушивать не присоединенный сокет;
  • IP адрес источника после установления соединения для сокета, после возврата из функции оригинального системного вызова;

Как это выглядит в работе? Как-то так:
$ sudo insmod fwnet.ko deny=192.168.56.101 port=10000 debug=1 
$ lsmod | head -n2 
Module                  Size  Used by 
fwnet                  13116  0 
$ dmesg | tail -n10
[  786.609568] ! denied IP: 192.168.56.101 
[  786.609572] ! denied TCP port: 10000 
[  786.613047] ! sys_call_table address = c15b4000 
[  786.636336] ! symbol sys_accept address = c149a070, not found in sys_call_table 
[  786.656437] ! symbol sys_connect address = c149a0a0, not found in sys_call_table 
[  786.661444] ! symbol sys_socketcall address = c149acd0, position in sys_call_table = 102 
[  786.663994] ! CR0 = 8005003b 
[  786.664090] ! CR0 = 8004003b 
[  786.664096] ! CR0 = 8005003b 
[  786.664100] ! install new sys_socketcall handler: e1ad50d0 


Естественно, для того, чтобы наблюдать работу сетевого фильтра ядра в действии, нам необходимы TCP клиент и сервер (например, ncat). Но для детального тестирования были подготовлены специальные ретранслирующий сервер (tcpserv) и клиент (tcpcli). Не считая некоторых мелочей, заточенных под эту работу, они ничего особенного не представляют и рассматриваться здесь не будут (но они есть в прилагаемом архиве).
Вот как будут выглядеть некоторые из попыток установления запрещённых TCP соединений:

— Запуск сервера, прослушивающего запрещённый порт:

$ ./tcpserv -v -p10000 
listening on the TCP port 10000 
denied TCP port: Input/output error 
$ dmesg | tail -n5 
...
[11213.888556] ! accept before: port = 10000 
[11213.888562] ! accept from denied port 10000 


— Попытка подключения клиента к запрещённому порту:
$ ./tcpcli -v -h 127.0.0.1 -p 10000 
client: can't connect to server: Permission denied 
$ dmesg | tail -n5 
...
[10984.082051] ! connect to 127.0.0.1:10000 
[10984.082060] ! connect to 127.0.0.1:10000 denied 
[11166.236948] ! connect to 127.0.0.1:53 
...


Ну и так далее — задача предоставляет широкое и увлекательное поле для экспериментирования…

(Здесь в протоколе специально сохранено и показано обращение в это же время к DNS по порту 53. Точно также, во время экспериментов с фильтрацией можно наблюдать множество соединений к TCP порту 80 — всё время не нарушая работы идёт HTTP трафик.)

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

$ sudo rmmod fwnet
$ dmesg | grep \! | tail -n2
[ 2890.602419] ! sys_socketcall handler before unload: e1ad50d0 
[ 2890.602439] ! restore old sys_socketcall handler: c149acd0 


Вот так, несколько с выдумкой, осуществляется в Linux обработка сетевых системных вызовов … по крайней мере, в 32 бит реализации. При первом столкновении с этими системными вызовами способ их работы несколько обескураживает.

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

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Удачи в цифровую эпоху! Или включите параноика и проверьте защиту своих данных

Вы еще не слышали про экшн «Преступная группировка ‪Билайн‬?
Сегодня — вторая серия!
Месяц назад неизвестные лица получили мою симкарту в „Билайне“ без документов.Пытались вскрыть Яндекс.Кошелек, хакнули все почты, пришлось поменять все банковские карты (Вы представляете, что это такое??)
Компания якобы провела расследование и заявила, что „нарушения устранены, виновные привлечены и это никогда не повторится“. Мне даже зачислили 2000 рублей на счёт в качестве компенсации (!:))
Однако…
Позавчера в 18 часов вечера моя симкарта снова была выдана неизвестным лицам! И сразу были украдены деньги с Яндекса по одноразовому паролю. Проведя вечер субботы в офисе Билайна, и вспомнив всю ненормативную лексику, я заменила симкарту.
Наутро, вчера, в 12 часов дня моя сим-карта СНОВА была выдана посторонним лицам в городе Екатеринбурге!!!
Я снова приехала в офис Билайна за новой симкой.
И… Через 43 минуты (!!) после этого моя карта была вновь выдана в офисе Билайна кому-то, теперь уже в городе Омске!!!
При том, что в системе стоит запрет на выдачу карты во всех офисах страны и мира, кроме одного, и то — с предъявлением паспорта, водительских прав и кодовым словом!
Мне хотелось бы понять — руководство компании „Билайн“ хочет, чтобы я жила у них в офисе?
Это что за беспредел?! За последние сутки они 3 раза выдали мою симкарту мошенникам без документов, без кодового слова, без моего присутствия, в разных городах страны!
Хотя я приезжала в офис, звонили в службу безопасности, писали, бесполезно.
А ни у кого из сотрудников не возник вопрос — зачем абонент меняет симкарту 5 раз в течение суток? Он-идиот? Конечно нет! Потому что сотрудники компании сами завязаны в процессе, поэтому им и не нужен мой паспорт, кодовое слово, запрет системы на выдачу. Ничего не помогает! Чтобы ты не делал, какие бы защиты не ставил — сотрудники „Билайна“ выдают сим-карты своим подельникам. Которые затем получают доступы к электронным кошелькам, почте и банковским эккаунтам.
Похоже, что в „Билайне“ действует большая преступная группировка, операторы системы по всей стране выдают сим-карты по липовым доверенностям мошенникам, те вскрывают кошельки, деньги пилятся. Говорят, что из Билайна недавно уволили девушку, говорят, что сотрудник получал 2% от добытого.
Итого: я провела выходные в офисе Билайна, два дня без телефона, все три почты взломаны — Гугл, Яндекс, Мейл, украдены деньги с кошелька.
Работают виртуозно: пока я вчера мчалась в офис Билайна в 4-й раз менять симкарту, эти люди успели за 20 минут получить на мой номер новые пароли от почт, зайти туда и ввести новые привязанные телефоны, резервные адреса и даже контрольный вопрос поменять в одном случае(!!)
Но на том эпопея не закончилась — к ночи вчера выяснилось, что прежний владелец моего номера обнаружил, что его текущий, уже другой номер, тоже Билайн, не работает. При звонке в компанию он выяснил, что (находясь в Батуми) он произвел замену симкарты вчера днем в… Бинго! — Сибирском регионе Билайна! Тот же сотрудник, что выдал мою карту с разницей в час!

Понимаете ли Вы, друзья мои, что почта каждого из Вас, восстановление ее пароля, привязано к телефону? Что на свой номер Вы получаете пароли от всех Ваших интернет-банков и карт?
Что у каждого из Вас, кто абонент Билайна, могут вот также просто увести телефон, а за ним — почту, кошелек и все остальное?

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Unity — Концептуальные идеи и подсказки для новичков игродева. Простая процедурная генерация моделей для 2D игры

Введение в проблему

Здравствуйте, дорогие читатели!

Мысли о создании серии простых уроков «концептуальные идеи для новичков игродева» появились у меня спонтанно, где-то в 2:00 по Московскому времени во время создания своего нынешнего проекта. Ну нет, это так мне кажется, что спонтанно, но, наверное, это мое подсознание так среагировало. Среагировало потому, что все больше юных (коим я и сам являюсь) и очень юных программистов решают заняться созданием игр. Как мне кажется, общая тенденция молодежи-программистов (и людей, интересующихся сферой программирования) плавно перешла от создания сайтов и модных блогов к созданию развлекательных продуктов. Я начинаю замечать это и среди своих знакомых, которые одно время говорили, что, мол игры — это не серьезное программирование, но теперь уже проявляют настоящий интерес к этой среде.

Я объясняю это для себя следующим, очевидным образом. Любые информационные направления приобретает массовые тенденции к изучению при выполнении двух условий: наличие простого и адекватного инструмента осуществления конкретных задач в выбранной информационной сфере и легкость получения прибыли при продаже ваших выполненных задач. В пример же опять можно привести сферу веб-технологий (когда-то сайты было создавать ультра-хардкорно, а сейчас, наверное, даже моя мама сможет поставить блог на WordPress или его аналогах. Опять же почему? Потому что WordPress открыл возможность создавать свои блоги всем мамам вокруг света, и потому что веб-сайты открыли доступ к быстрой популярности, славе, деньгам и рому).

Но пришла эра развлечений – я не буду упоминать с каким трудом делались первые игры, но прошли десятилетия, стали появляться платные игровые движки, через какое-то время они стали практически бесплатные (Unity, Unreal Engine4), причем не движки от Васи с соседнего подъезда в которых можно только сделать “грабеж корованов ”, а движки мастодонты который представляют из себя комплексные среды разработки, способные реализовать ваши проекты мечты. Однако есть и обратная сторона этих популярных технологий. А именно большое количество некачественных продуктов. Обленились придумывать что-то свое… “Лучше сделаю флеппи берд!” – подумал Вася.
И я решил, что надо сделать серию уроков состоящих из простых идей, которые могут использовать люди в своих самых первых проектах, люди, которые, может быть, не так давно начали изучать программирование вообще.

Случайная генерация 2D моделей (Unity)

Когда вы делаете игру в одиночку, не всегда бывает возможно нарисовать большое количество спрайтов для ваших персонажей, кораблей или зданий, вообще объектов.
Тут и приходит на помощь процедурная(случайная) генерация. Что значит этот термин в двух (шести) словах? «Модельку создает компьютер, а не вы».

На просторах интернета вы можете найти миллионы алгоритмов процедурной генерации в сфере геймдева (может быть, один из них даже описан моей мамой в собственном блоге). Одни из них будут просто сложные (как например генерация водной поверхности с использованием Nvidia Physics), другие из них будут экстремально сложные, как например сегментация рельефа с использованием нечеткой логики и нечетких множеств (Fuzzy Sets).

И что? Не думаю, что человек, который второй раз открывает юнити начнет думать, как ему понять, как реализовать и в какое место игры применить найденный алгоритм.

Проще реализовать свой! Пусть он будет простой, зато понятный вам. А это самый важный шаг во всем программировании.
Предлагаю вам свой вариант процедурной генерации модельки (применим к любой 2D игре). Предупреждаю, код экстремально простой! Две строчки! Но сначала, то, что вы должны подготовить перед осуществлением кода:

1. Понять какую модель (или объект) вы хотите создавать процедурно – это может быть ваш рыцарь, здание, космический корабль и тд.
2. Разбить на столько элементарных частей сколько вы хотите (например, для рыцаря это могут быть шлем, меч, щит, нагрудник).
Примечание: чем меньше отдельные элементы (например, меч вы разобьете на рукоять и лезвие), тем очевидно, что ваша сгенерированная модель будет выглядеть более натурально и уникально.
3. Нарисовать на каждый элемент столько различных спрайтов сколько считаете нужным.
4. Соберите свою модель в редакторе Unity, так, как она должна выглядеть. Я буду использовать в виде примера модельку корабля из своего нынешнего проекта.

image

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

image

И настает время кода!

using UnityEngine;
using System.Collections;
public class ChangeTextureF : MonoBehaviour {
      // в массиве Sprites будут находиться спрайты для каждой отдельной детали     
      public Sprite[] Sprites;                     

      void Start()
      {
           // вызываем функцию сразу после создания объекта
           ChangeTextureFunc();              
      }
      public void ChangeTextureFunc()                                                  
      {
           // Подбрасываем псевдокубик в диапазоне от 0 до 
           // длины нашего массива, причем Random.Range 
           // не включает последний элемент      
           int ChooseForTexture = Random.Range (0, Sprites.Length);  
           // обращение к компоненту SpriteRenderer, и передача ему               
           // спрайта из массива наших заготовленных спрайтов по индексу,
           // определенному рандомно строкой выше.        
           GetComponent<SpriteRenderer> ().sprite = Sprites[ChooseForTexture];  
      
      }
}


Функция ChangeTextureFunc() содержит всего две строчки кода, как и обещал.
Навесьте скрипт на каждый элемент вашего объекта как показано на скрине. Закиньте спрайты каждого элемента в массив прямо в эдиторе, и радуйтесь результату.

image

Эффектный результат:

imageimage

P.S Старайтесь спрайты для вашей модели делать одного размера чтобы не было смещений в модели, однако если вы все же хотите сделать какой-нибудь особо изысканный спрайт, который кардинально отличен по размерам от основного множества, то просто передвиньте в sprite editor'e точку вращения (Pivot point), которая будет определять центр спрайта, на столько сколько вам нужно. Иногда в Unity забывают про эту возможность.

image

Вывод:
Конечно я вас немного обманул сказав, что вы получите процедурную генерацию моделей, скорее это можно назвать быстрым комбинированием модели из заданных спрайтов. Но тут же хочу сказать в защиту этого подхода:
1) Ну кода нет, ты рисуешь три кораблика делишь каждый на три одинаковых элемента и на выходе получаешь 27 моделек кораблей. Ура.
2) Вы скажете, что вы крутой мозг и сможете написать алгоритм, который будет сам и контуры кораблей выбирать и расцветку подставлять свою и у вас будет 1000000 комбинаций, ну а я вам отвечу, что каждая ваша модель будет крякозяброй потому что не забывайте, что разработка игр в том числе и искусство. И 10000 ваших безвкусных кракозябр никому не запомнятся.
3) Для новичков это будет впечатляющим результатом, который может подтолкнуть их к развитию этой идеи вширь и вглубь.

Идеи:
Вот кстати примеры, которые я придумал прямо во время написания этой статьи, как это можно интересно использовать:
1) Навесьте на каждый элемент скрипт содержащий параметры, которые вписываются в сеттинг вашей игры, например для космического корабля это могут быть параметры: скорости движение корабля, его урона, кол-во хп или даже способности которые будут приобретаться только у данного вида детали. Далее вы кидаете на главный родительский объект, который держит в себе все детали, скрипт, который будет собирать параметры с каждой детали, и, например, суммировать их и таким образом будет получатся общая характеристика кораблика.
2) Идею из пункта 1 можно использовать геймплейно еще глубже, например, в какой-нибудь RPG игре, где вы сможете оценивать противника издалека не по надписи «моб 80 уровня» а по его одежке, потому что до этого вы уже видели, схожие элементы доспехов на предыдущем мобе, который имел иммунитет к огню и молнии. То есть, не используя никаких текстовых подсказок игрок будет опытным путем выяснять влияние определенных вещей на характеристики.

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

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Доступна Android Studio 1.4

Несколько дней назад стала доступнаAndroid Studio 1.4 на Stable Channel, привнёсшая ряд удобных новшеств в инструментарий Android разработчика. Тех, кто еще не успел ознакомиться с нововведениями, прошу под кат.


Обновлены шаблоны проектов


Первое, что бросается в глаза, это обновленные шаблоны типовых лэйаутов, доступных в New Project Wizard: Android Studio 1.4 привносит полноценную поддержку Material Design уже на этапе создания нового проекта:

Создадим демо приложение на базе Navigation Drawer Activity. Смотрим build.gradle для модуля приложения:

dependencies {
    compile fileTree(dir: 'libs', include: ['*.jar'])
    testCompile 'junit:junit:4.12'
    compile 'com.android.support:appcompat-v7:23.0.1'
    compile 'com.android.support:design:23.0.1'
}


Студия любезно позаботилась о нас, добавив библиотеки обратной совместимости Android Design Support Library и AppCompat Support library. Больше не нужно тащить в проект сторонние реализации Floating Action Button, Material Dialogs или Snackbar — все необходимые визульные компоненты доступны в подключённых support libraries. Также нам добавили JUnit 4-ой версии, чтобы мы не забыли написать юнит-тесты.

Примечание: напомню, что юнит-тесты живут в директориях src\test\<package_name>, а не в src\androidTest\<package_name>. Также стоит помнить, что тесты на JUnit 4 используют аннотацию @Test взамен extends TestCase.


В проекте у нас уже есть DrawerLayout, NavigationView, FloatingActionButton и даже CoordinatorLayout (подробней), который позаботится о том, чтобы приподнять FAB при появлении Toast Snackbar.
app_bar_mail.xml
<?xml version="1.0" encoding="utf-8"?>
<android.support.design.widget.CoordinatorLayout
    xmlns:android="http://ift.tt/nIICcg"
    xmlns:app="http://ift.tt/GEGVYd"
    xmlns:tools="http://ift.tt/LrGmb4"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:fitsSystemWindows="true"
    tools:context=".MainActivity">

    <android.support.design.widget.AppBarLayout
        android:layout_height="wrap_content"
        android:layout_width="match_parent"
        android:theme="@style/AppTheme.AppBarOverlay">

        <android.support.v7.widget.Toolbar
            android:id="@+id/toolbar"
            android:layout_width="match_parent"
            android:layout_height="?attr/actionBarSize"
            android:background="?attr/colorPrimary"
            app:popupTheme="@style/AppTheme.PopupOverlay"/>

    </android.support.design.widget.AppBarLayout>

    <include layout="@layout/content_main"/>

    <android.support.design.widget.FloatingActionButton
        android:id="@+id/fab"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_gravity="bottom|end"
        android:layout_margin="@dimen/fab_margin"
        android:src="@android:drawable/ic_dialog_email"/>

</android.support.design.widget.CoordinatorLayout>



Добавлен Theme Editor


Появился визуальный редактор тем, позволяющий за пару минут поправить внешний вид приложения с учётом специфики Material Design. Вызвать его можно через Tools → Android → Theme Editor или по кнопке Open Editor для уже открытого styles.xml:


Примечание: для полноценной работы Theme Editor с возможностью preview необходимо наличие SDK Platform для API 23.

Больше не нужно часами выгугливать нужные свойства темы, подбирать Primary/PrimaryDark/Accent цвета — Theme Editor любезно подскажет/сгенерирует нужную палитру. Так, PrimaryDark будет подобран на основе Primary цвета — удобно.

Инструмент Vector Assets, поддержка Vector Drawable


Если Вы еще не слышали про Vector Drawable, то рекомендую прочитать эту отличную статью. В Android Studio 1.4 появился визуальный интрумент под названием Vector Assets, который позволит с легкостью перейти на векторный формат графики в Вашем приложении как на Lollipop/Marshmallow, так и на предыдущих версиях API. Для этого необходимо воспользоваться обновленной версией Android Gradle плагина (на момент выхода статьи он в бете, но обещали «как только, так сразу»), поправив build.gradle для проекта:
dependencies {
        classpath 'com.android.tools.build:gradle:1.4.0-beta3'
}


Вызвать инструмент можно через диалог Android Project → New → Vector Assets:

Здесь нам предлагают выбрать векторную иконку из Material Design Icons Pack или импортировать сторонний *.svg файл.

Внимание: импорт находится в стадии разработки и не поддерживает всю спецификацию SVG. Проблемные элементы будут выведены в список, придётся вносить правки.


После этого Vector Assets сгенерирует xml ресурсы VectorDrawable и положит в res\drawable . Для обеспечения обратной совестимости с pre-Lollipop устройствами в момент билда android gradle plugin сгенерирует *.png под все плотности экранов в директории app\build\generated\res\pngs

Ограничения обратной совместимости:

minSdkVersion >= 21 (Lollipop)

  • Полная поддержка VectorDrawable API

minSdkVersion < 21
  • Автогенерация png взамен sml в момент билда
  • Урезанный VectorDrawable API
  • Не поддерживаются элементы <group> и <clip-path>
  • Использование BitmapDrawable вместо VectorDrawable в Java коде.


Два новых монитора: GPU Rendering, Network


Для анализа производительности приложения разработчику доступны два новых монитора: GPU Rendering Monitor и Network Monitor:


Чтобы заработал GPU Rendering монитор, его нужно включать на устройстве или эмуляторе: Setting → Developer Options → Profile GPU rendering → In adb shell dumpsys gfxinfo


На этом всё, приятно видеть, что любимый инструмент Android разработчиков развивается, спасибо за внимание.

Использованы материалы:
Блог Android Studio
Vector Drawable API. Возможности применения
Легко переходим на векторный формат картинок вместо нарезки под разные плотности экранов в Android 4.0+. Часть 1 из 2

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

пятница, 2 октября 2015 г.

[Перевод] Неконстантные константные выражения

// <какой-то код>
 
int main ()
{
        constexpr int a = f ();
        constexpr int b = f ();
 
        static_assert (!= b, "fail");
}

Можно ли в приведенном выше фрагменте вместо комментария вставить такое определение f (), чтобы a получила значение, отличное от b?

“Разумеется, нет!” — скажете вы, немного подумав. Действительно, обе переменные объявлены со спецификатором constexpr, а значит, f () тоже должна быть constexpr-функцией. Всем известно, что constexpr-функции могут выполняться во время компиляции, и, как следствие, не должны зависеть от глобального состояния программы или изменять его (иными словами, должны быть чистыми). Чистота означает, что функция при каждом вызове с одними и теми же аргументами должна возвращать одно и то же значение. f () оба раза вызывается без аргументов, поэтому должна оба раза вернуть одно и то же значение, которое и будет присвоено переменным a и b… правильно?

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

Я ошибался.

Содержание


Дисклеймер: Техника, описанная в этой статье, позиционируется как «очередной хитрый хак с погружением в темные глубины C++». Я никому не рекомендую использовать ее в продакшене без предварительного изучения всех подводных камней (которые будут подробно описаны в следующих статьях).

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

Зачем вообще может понадобиться подобное?


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

Прим. пер: Читатель может возразить, что императивность в метапрограммы можно легко добавить, используя изменяемые макросы-константы в качестве «переменных». Так, для решения нашей задачи можно использовать #define f() __COUNTER__ или что-то подобное.

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


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

Например:

Compile-time счетчик


using C1 = ...;
 
int constexpr a = C1::next (); // = 1
int constexpr b = C1::next (); // = 2
int constexpr c = C1::next (); // = 3


Compile-time контейнер метатипов


using LX = ...;
 
LX::push<void, void, void, void> ();
LX::set<0, class Hello> ();
LX::set<2, class World> ();
LX::pop ();
 
LX::value<> x; // type_list<class Hello, void, class World>


Другие идеи


Предварительные сведения


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

Замечание: Рекомендуется все же хотя бы бегло пролистать эту часть, если вам интересно, как именно и почему код решения работает (и является легальным с точки зрения стандарта).


Ключевое слово friend


Отношение дружбы в C++ может использоваться не только для простого предоставления другой сущности доступа к своим private и protected членам. Рассмотрим следующий (очень простой) пример:

class A;
void touch (A&);
 
class A
{
        friend void touch (A&);
        int member;
};
 
void touch (A& ref)
{
        ref.member = 123;       // OK, `void touch(A&)` является другом класса A
}
 
int main ()
{
        A a; a.member = 123;   // Некорректно, член `A::member` приватный
        A b; touch (b);      
}


Сначала мы объявляем функцию void touch (A&) в глобальной области видимости, затем объявляем ее дружественной классу A, и, наконец, определяем ее в глобальной области видимости.

С тем же успехом мы можем поместить объединенные объявление и определение void touch (A&) непосредственно внутри класса A, ничего больше не меняя — как в следующем примере:

class A
{
        friend void touch (A& ref)
        {
                ref.member = 123;
        }
 
        int member;
};
 
int main ()
{
        A b; touch (b); // OK
}


Очень важно, что эти два подхода к использованию friend не являются полностью эквивалентными (хотя в данном конкретном случае может показаться, что это так).

В последнем примере void touch (A&) будет неявно размещена в области видимости ближайшего объемлющего для класса A пространства имен, но доступ к ней будет возможен только при помощи поиска Кёнига (ADL).

Приведенная ниже выдержка из стандарта повторяет вышесказанное, но я хочу, чтобы вы сконцентрировались на том, что написано между строк (потому что это в равной степени важно):

7.3.1.2/3 Определения членов пространств имен [namespace.memdef]p3

Каждое имя, впервые объявленное внутри пространства имен, является членом этого пространства имен. Если friend-объявление внутри нелокального класса впервые объявляет класс, функцию, шаблон класса или шаблон функции, они становятся членами ближайшего объемлющего пространства имен. friend-объявление само по себе не делает имя видимым для неквалифицированного (3.4.1) или квалифицированного (3.4.3) поиска имен.


Обратите внимание, что нигде не утверждается, что имя, введенное посредством friend-объявления, должно иметь какое-либо отношение к имени класса, в котором это объявление находится, да и вообще какое-либо отношение к этому классу, если уж на то пошло.

#include <iostream>
 
class A
{ 
public:
        A (int) { } 
        friend void f (A);
};
 
void g (A);
 
class B
{ 
        friend void f (A)
        {
                std::cout << "hello world!" << std::endl;
        }
 
        class C
        {
                friend void g (A)
                {
                        std::cout << "!dlrow olleh" << std::endl;
                }   
        };  
};
 
int main ()
{
        A a (0);
        f (a);
        g (1);
}


Так, void f () никак не связана с классом B, за исключением того факта, что она определена как friend прямо внутри него, и такой код является абсолютно корректным.

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


Правила для константных выражений


Существует большое количество правил, связанных с constexpr, и можно было бы сделать это введение более строгим и детальным, но я буду краток:
  • Литеральным называется тип, который могут иметь constexpr-переменные и возвращаемые constexpr-функциями значения. Такими типами являются: скалярные типы (арифметические типы, указатели и перечисления), ссылочные типы и некоторые другие. Кроме того, классы, удовлетворяющие определенным ограничениям (constexpr-конструктор, тривиальный деструктор, типы всех членов-данных и базовые классы являются литеральными) также являются литеральными типами;
  • Переменная, объявленная со спецификатором constexpr, должна иметь литеральный тип и сразу быть инициализирована константным выражением;
  • Функция, объявленная со спецификатором constexpr, должна принимать в качестве параметров и возвращать только литеральные типы, а также не должна содержать конструкции, которые запрещены в константных выражениях (например, вызовы не constexpr-функций).
  • Константным называется выражение, в котором не встречаются:
    • Вызовы не constexpr-функций;
    • Вызовы функций, которые еще не определены;
    • Вызовы функций с аргументами, которые не являются константными выражениями;
    • Обращения к переменным, которые не были инициализированы константными выражениями и начали существовать до начала вычисления текущего константного выражения;
    • Конструкции, вызывающие неопределенное поведение;
    • Лямбда-выражения, возбуждения исключений и некоторые другие конструкции.

Замечание: Этот список является неполным и нестрогим, но дает представление о том, как ведут себя constexpr-сущности и константные выражения в большинстве случаев.


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

constexpr int f ();
void indirection ();
 
int main ()
{
        constexpr int n = f (); // Некорректно, `int f ()` еще не определена
        indirection ();
}
 
constexpr int f ()
{
        return 0;
}
 
void indirection ()
{
        constexpr int n = f (); // ОК
}


Здесь constexpr-функция int f () является объявленной, но не определенной в main, но имеет определение внутри indirection (поскольку к моменту начала тела indirection определение уже предоставлено). Поэтому внутри indirection вызов constexpr-функции f () будет константным выражением, а инициализация n — корректной.

Как проверить, что выражение является константным


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

Опытный C++-разработчик немедленно увидит здесь возможность удачно применить концепцию SFINAE (Substitution Failure Is Not An Error) и будет прав; но мощь, которую предоставляет SFINAE, сопровождается необходимостью написания довольно сложного кода.

Прим. пер:

Например, такого

constexpr int x = 7;
 
template <typename> 
std::false_type isConstexpr (...);
 
template <typename T, T test = (15*25 - x)> //Проверяемое выражение
std::true_type isConstexpr (*);
 
constexpr bool value = std::is_same <decltype (isConstexpr <int> (nullptr)), std::true_type>::value; //true


Гораздо проще для решения нашей задачи использовать оператор noexcept. Этот оператор возвращает true для выражений, которые не могут возбуждать исключения, и false в противном случае. В частности, все константные выражения считаются не выбрасывающими исключения. На этом мы и сыграем.

constexpr int f (); 
void indirection (); 
 
int main ()
{
        // `f()` не является константным выражением,
        // пока ее определение отсутствует
 
        constexpr bool b = noexcept ( f()); // false
}
 
constexpr int f ()
{
        return 0;
}
 
void indirection ()
{
        // А теперь является
 
        constexpr bool b = noexcept (()); // true
}


Замечание: в настоящее время clang содержит баг, из-за которого noexcept не возвращает true, даже если проверяемое выражение является константным. Обходной путь можно найти в приложении к этой статье.


Семантика инстанцирования шаблонов


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

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

Замечание: Учтите, что содержимое этого раздела не является полным справочником по инстанцированию шаблонов. Из упомянутых в нем правил есть исключения, кроме того, я намеренно опустил некоторые факты, которые выходят слишком далеко за рамки статьи.


Основные принципы


Словарик для самых маленьких
  • Специализация шаблона — реализация, полученная из шаблона заменой шаблонных параметров на конкретные аргументы. template <typename T> class Foo — шаблон. Foo <int> — его специализация. Программист может самостоятельно предоставить полную или частичную специализацию шаблона для определенных наборов аргументов, если необходимо, чтобы ее поведение отличалось от обобщенного. Частичная специализация недоступна для шаблонов функций.
  • Инстанцирование специализации шаблона — получение компилятором кода специализации из обобщенного кода шаблона. Для краткости часто говорят об инстанцировании шаблона с определенными аргументами, опуская слово «специализация».
  • Инстанцирование может быть явным или неявным. При явном инстанцировании программист самостоятельно сообщает компилятору о необходимости инстанцировать шаблон с определенными аргументами, например: template class Foo <int>. Кроме того, компилятор может самостоятельно неявно инстанцировать специализацию, если ему это потребуется.

Далее следует сжатый перечень принципов, которые имеют самое прямое отношение к нашей задаче:
  • Специализация шаблона (как класса, так и функции) может быть неявно инстанцирована, только если она ранее не была явно инстанцирована, и пользователь не предоставил соответствующей полной специализации.
  • Специализация шаблона функции будет неявно инстанцирована, если она упоминается в контексте, требующем ее определения, и при этом выполнен первый пункт.
  • Специализация шаблона класса будет неявно инстанцирована, если она упоминается в контексте, который требует полностью определенного (complete) типа, либо в случае, когда эта полнота влияет на семантику программы, и при этом (в обоих случаях) выполнен первый пункт.
  • Инстанцирование шаблона класса вызывает неявное инстанцирование объявлений всех его членов, но не их определений, за исключением случаев, когда член является:
    • Статическим членом-переменной, в случае которой объявление также не будет инстанцировано, или;
    • Перечислением без области видимости или анонимным объединением, в случае которых будут инстанцированы как объявление, так и определение.
  • Определения членов будут неявно инстанцированы, когда будут запрошены, но не раньше.
  • Если специализация шаблона класса содержит friend-объявления, имена этих друзей рассматриваются далее так, как будто их явные специализации были размещены в точке инстанцирования.

Точки инстанцирования


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

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

  • Если X является специализацией шаблона функции, точка инстанцирования будет совпадать с точкой инстанцирования Y.
  • Если X является специализацией шаблона класса, точка инстанцирования будет находиться непосредственно перед точкой инстанцирования Y.

Если же вложенных шаблонов нет, или контекст не зависит от параметров внешнего шаблона, точка инстанцирования будет привязана к точке D объявления/определения «наиболее глобальной» сущности, внутри которого упоминалась специализация X:
  • Если X является специализацией шаблона функции, точка инстанцирования будет находиться сразу после D.
  • Если X является специализацией шаблона класса, точка инстанцирования будет находиться непосредственно перед D.

Генерация специализации шаблона функции


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

Для простоты стандарт C++ предписывает считать, что у любой инстанцированной специализации шаблона функции есть дополнительная точка инстанцирования в конце единицы трансляции:

namespace N
{
        struct X { /* Специально оставлена пустой */ };
 
        void func (X, int);
}
 
template <typename T>
void call_func (T val)
{
        func (val, 3.14f);
}
 
int main ()
{
        call_func (N::X {});
}
 
//Первая точка инстанцирования
 
namespace N
{
        float func (X, float);
}
 
//Вторая точка инстанцирования


В этом примере у нас есть две точки инстанцирования функции void call_func <N::X> (N::X). Первая находится сразу после определения main (потому что call_func вызывается внутри нее), а вторая — в конце файла.

Приведенный пример является некорректным из-за того, что поведение call_func <N::X> изменяется в зависимости от того, в какой из них компилятор сгенерирует код специализации:

  • В первой точке call_func вызовет func (X, int), потому что другие перегрузки в этот момент еще отсутствуют.
  • Во второй точке call_func вызовет уже объявленную к этому моменту func (X, float), как наиболее подходящую из всех доступных перегрузок.

Генерация специализации шаблона класса


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

namespace N
{
        struct X { /* Специально оставлена пустой */ };
 
        void func (X, int);
}
 
template<typename  T> struct A { using type = decltype (func (T{}, 3.14f)); };
template<typename T> struct B { using type = decltype (func (T{}, 3.14f)); };
 
//Точка инстанцирования A
 
int main ()
{
        A<N::X> a;
}
 
namespace N
{
        float func (X, float);
}
 
//Точка инстанцирования B
 
void g ()
{
        A<N::X>::type a; // Некорректно, type будет `void`
        B<N::X>::type b; // OK, type будет `float`
}


Здесь точка инстанцирования A <N::X> будет находиться непосредственно перед main, в то время как точка инстанцирования B <N::X> — только перед g.

Собираем все воедино


Правила, связанные с friend-объявлениями внутри шаблонов классов, утверждают, что в следующем примере определения func (short) и func (float) генерируются и размещаются в точках инстанцирования соответственно специализаций A <short> и A <float>.

constexpr int func (short);
constexpr int func (float);
 
template <typename T>
struct A
{ 
        friend constexpr int func (T) { return 0; }
};
 
template <typename T>
<T> indirection ()
{
        return {};
}
 
// (1)
 
int main ()
{
        indirection <short> (); // (2)
        indirection <float> (); // (3)
}


Когда вычисляемое выражение содержит вызов специализации шаблона функции, возвращаемый тип этой специализации должен быть полностью определен. Поэтому вызовы в строках (2) и (3) влекут за собой неявное инстанцирование специализаций A вместе со специализациями indirection перед их точками инстанцирования (которые, в свою очередь, находятся перед main).

Важно, что до достижения строк (2) и (3) функции func (short) и func (float) объявлены, но не определены. Когда достижение этих строк вызовет инстанцирование специализаций A, определения этих функций появятся, но будут расположены не рядом с этими строками, а в точке (1).

Решение


Надеюсь, что предварительные сведения в достаточной мере раскрывают все аспекты языка, которые используются в решении, приведенном в этом разделе.

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

  • Ключевое слово friend, и;
  • Правила для константных выражений, и;
  • Семантика инстанцирования шаблонов.

Реализация


constexpr int flag (int);
 
template <typename Tag>
struct writer
{
        friend constexpr int flag (Tag)
        {
                return 0;
        }
};
 
template <bool B, typename Tag = int>
struct dependent_writer : writer <Tag> { };
 
template <
        bool B = noexcept (flag (0)),
        int = sizeof (dependent_writer <B>)
>
constexpr int f ()
{
        return B;
}
 
int main ()
{
        constexpr int a = f ();
        constexpr int b = f ();
 
        static_assert (!= b, "fail");
}


Замечание: clang демонстрирует некорректное поведение с этим кодом, обходной путь доступен в приложении.

Прим. пер: static_assert и визуальные подсказки в Visual Studio 2015 также «не замечают» изменений в f (). Тем не менее, после компиляции значения a и b различаются.


Но как это работает?


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

В этом разделе пошагово разбирается исходный код и дается краткое описание и обоснование для каждого его фрагмента.

“Переменная”


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

Обычно constexpr-функции рассматриваются и используются именно как функции, однако благодаря вышесказанному мы можем думать о них как о “переменных”, которые имеют тип, похожий на bool. Каждая такая “переменная” находится в одном из двух состояний: “определена” или “не определена”.

constexpr int flag (int);


В нашей программе функция flag является просто подобным триггером. Мы нигде не будем вызывать ее как функцию, интересуясь только ее текущим состоянием как “переменной”.

Модификатор


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

template <typename Tag>
struct writer
{
        friend constexpr int flag (Tag)
        {
                return 0;
        }
};


Если мы, как и собирались, будем рассматривать constexpr-функции как “переменные”, то инстанцирование writer с аргументом шаблона T вызовет безусловный перевод “переменной” с сигнатурой int func (T) в положение “определена”.

Прокси


template <bool B, typename Tag = int>
struct dependent_writer : writer <Tag> { };


Я не удивлен, если вы решили, что dependent_writer выглядит как бессмысленная прослойка, добавляющая косвенности. Почему бы напрямую не инстанцировать writer <Tag> там, где мы хотим изменить значение “переменной”, вместо обращения к нему через dependent_writer?

Дело в том, что прямое обращение к writer <int> не гарантирует, что первый аргумент шаблона функции f будет вычислен раньше второго (и функция при первом вызове успеет “запомнить”, что нужно вернуть false, а уже потом изменит значение “переменной”).

Чтобы задать нужный нам порядок вычисления аргументов шаблона, можно добавить дополнительную зависимость при помощи dependent_writer. Первый шаблонный аргумент dependent_writer должен быть вычислен до его инстанцирования, и, следовательно, до инстанцирования самого writer. Поэтому, передавая B в dependent_writer в качестве аргумента, мы можем быть уверены, что к моменту инстанцирования writer возвращаемое функцией f значение уже будет вычислено.

Замечание: При написании реализации я рассматривал множество альтернатив, пытаясь найти наиболее простую для понимания. Я искренне надеюсь, что этот фрагмент получился не слишком запутанным.


Магия


template <
        bool B = noexcept (flag (0)),            // (1)
        int = sizeof (dependent_writer <B>) // (2)
>
constexpr int f ()
{
        return B;
}


Этот фрагмент может показаться немного странным, но на самом деле он очень прост:
  • (1) устанавливает B равным true, если flag (0) является константным выражением, и равным false, если нет;
  • (2) неявно инстанцирует dependent_writer <B> (оператор sizeof требует полностью определенного типа). При этом инстанцируется и writer <B>, что, в свою очередь, вызывает генерацию определения int flag (int) и изменение состояния нашей “переменной”.

Поведение можно выразить следующим псевдокодом:
ЕСЛИ [ `int flag (int)` еще не определена ]:
        УСТАНОВИТЬ `B` = `false`
        ИНСТАНЦИРОВАТЬ `dependent_writer <false>`
        ВЕРНУТЬ `B`
ИНАЧЕ:
        УСТАНОВИТЬ `B` = `true`
        ИНСТАНЦИРОВАТЬ `dependent_writer <true>`
        ВЕРНУТЬ `B`

Таким образом, при первом вызове f шаблонный аргумент B будет равен false, но побочным эффектом вызова f станет изменение состояния “переменной” flag (генерация и размещение ее определения перед телом main). При дальнейших вызовах f “переменная” flag будет уже в состоянии “определена”, поэтому B будет равно true.

Заключение


То, что люди продолжают открывать сумасшедшие способы сделать при помощи C++ новые вещи (которые раньше считались невозможными), является одновременно удивительным и ужасным. — Морис Бос


В этой статье объясняется базовая идея, позволяющая добавить состояние константным выражениям. Иными словами, общепринятая теория (к которой часто обращался и я сам) о том, что константные выражения являются “константными”, теперь разрушена.

Прим. пер: На мой взгляд, «разрушена» — чересчур сильное слово. Все таки, несмотря на идентичность имен, в решении вызываются две различные специализации шаблонной функции f (), каждая из которых является полноценно «константной». Разумеется, это не умаляет общей полезности идеи.


При написании статьи я не мог не думать об истории шаблонного метапрограммирования и том, как странно, что язык позволяет сделать больше, чем когда-либо предполагалось делать с его помощью.
Что дальше?

Я написал библиотеку для императивного шаблонного метапрограммирования, названную smeta, которая будет опубликована, объяснена и обсуждена в предстоящих статьях. Среди тем, которые будут охвачены:

  • Как реализовать compile-time счетчик
  • Как реализовать compile-time контейнер метатипов
  • Как проверять разрешения перегрузок и управлять ими
  • Как добавить рефлексию в C++

Прим. пер: Автор сообщает, что решил отменить релиз smeta, т.к. эта и последующие статьи содержат (либо будут содержать) практически все ее фичи, и, следовательно, самостоятельная реализация читателем ее функциональности для себя будет практически тривиальна. Я, например, уже (вопреки предостережению Филиппа, ага) внедрил некоторые идеи и собираюсь собрать их в нечто библиотекоподобное в перспективе.

Приложение


Из-за этого (и связанных с ним) бага в clang приведенное выше решение вызывает неправильное поведение программы при правильной реализации. Ниже приведена альтернативная реализация решения, написанная специально для clang (которая по-прежнему является корректным C++-кодом и может использоваться с любыми компиляторами, хоть и несколько усложнена).

namespace detail
{
        struct A
        {
                constexpr A () { }
                friend constexpr int adl_flag (A);
        };
 
        template <typename Tag>
        struct writer
        {
                friend constexpr int adl_flag (Tag)
                {
                        return 0;
                }
        };
}
 
template <typename Tag, int = adl_flag (Tag {})>
constexpr bool is_flag_usable (int)
{
        return true;
}
 
template <typename Tag>
constexpr bool is_flag_usable (...)
{
        return false;
}
 
template <bool B, class Tag = detail::A>
struct dependent_writer : detail::writer <Tag> { };
 
template <
        class Tag = detail::A,
        bool B = is_flag_usable <Tag> (0),
        int = sizeof (dependent_writer <B>)
>
constexpr int f ()
{
        return B;
}
 
int main ()
{
        constexpr int a = f ();
        constexpr int b = f ();
 
        static_assert (!= b, "fail");
}


Замечание: В настоящее время я пишу соответствующие баг-репорты, которые будут показывать, почему именно такое обходное решение работоспособно в clang. Ссылки на них будут добавлены, как только репорты будут поданы (пока все глухо — прим. пер.).


Раздел благодарностей из оригинальной статьи

Благодарности


Есть много людей, без которых эта статья не была бы написана, но я особенно благодарен:
  • Морису Босу, за:
    • Помощь с формулировкой идей.
    • Предоставление мне средств на покупку контактных линз, что избавило меня от необходимости (буквально) писать вслепую.
    • Терпимость к моим приставаниям по поводу его мнения о статье.
  • Михаэлю Килпелайнену, за:
    • Корректуры, а также интересные мысли о том, как сделать эту статью более понятной.
  • Columbo, за:
    • Безуспешные попытки доказать, что описанная техника порождает некорректные программы (путем бросания параграфов стандарта C++ мне в лицо). Если что, я бы сделал то же самое для него.

От переводчика


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

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

Я собираюсь в ближайшее время перевести две оставшиеся статьи (о compile-time счетчике и о контейнере метатипов). Кроме того, Филипп сказал, что в обозримом будущем продолжит серию и разовьет идеи дальше (тогда, разумеется, будут и новые переводы).

Исправления, дополнения, пожелания приветствуются. Можете также написать самому Филиппу, я думаю, что он будет рад любым комментариям.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.