Как стать автором
Обновить
140
Карма
0.2
Рейтинг

пишу финтех (не блокчейн) и криптографию на Rust

  • Подписчики 46
  • Подписки 23

Приёмы неблокирующего программирования: введение в compare-and-swap

Программирование *C++ *C *Разработка под Linux *
Перевод

В первой части этого цикла статей мы рассмотрели теорию, стоящую за одновременным доступом в моделях памяти, а также применение этой теории к простым чтениям и записям в память. Правда, этих примитивов оказывается недостаточны для построения высокоуровневых механизмов синхронизации вроде спинлоков, мьютексов и условных переменных. Хоть и полные барьеры памяти позволяют синхронизировать потоки с помощью приёмов, рассмотренных в предыдущей части (алгоритм Деккера), современные процессоры позволяют получить нужный эффект проще, быстрее и гибче — да, всё сразу! — с помощью операций compare-and-swap.


Для программистов ядра Linux операция обмена compare-and-swap выглядит так:


    T cmpxchg(T *ptr, T old, T new);

где T может быть либо числовым типом не больше указателя, либо указателем на что-нибудь. Так как в C нет обобщённых функций, то подобный полиморфизм реализуется макросами. cmpxchg() — это очень аккуратно реализованный макрос, который ведёт себя как функция (например, вычисляет аргументы только один раз). В Linux также есть макрос cmpxchg64(), который работает с 64-битными целыми числами и недоступен на 32-битных платформах.


cmpxchg() читает значение по указателю *ptr и, если оно равно old, то заменяет его на new. Иначе же после чтения ничего не происходит. Считанное значение возвращается как результат операции, независимо от того, произошла ли запись. И всё это выполняется атомарно: если другой поток одновременно с cmpxchg() записывает что-то по адресу *ptr, то cmpxchg() ничего не меняет. Либо old становится new, либо текущее значение остаётся нетронутым. Поэтому cmpxchg() называют атомарной операцией read-modify-write.

Читать дальше →
Всего голосов 12: ↑9 и ↓3 +6
Просмотры 3.8K
Комментарии 0

Приёмы неблокирующего программирования: полные барьеры памяти

Программирование *C++ *C *Разработка под Linux *
Перевод

В первых двух статьях цикла мы рассмотрели четыре способа упорядочить доступ к памяти: load-acquire и store-release операции в первой части, барьеры чтения и записи в память — во второй. Теперь пришла очередь познакомиться с полными барьерами памяти, их влиянием на производительность, и примерами использования полных барьеров в ядре Linux.


Рассмотренные ранее примитивы ограничивают возможный порядок исполнения операций с памятью четырьмя различными способами:


  • Load-acquire операции выполняются перед последующими чтениями и записями.
  • Store-release операции выполняются после предыдущих чтений и записей.
  • Барьеры чтения разделяют предыдущие и последующие чтения из памяти.
  • Барьеры записи разделяют предыдущие и последующие записи в память.

Внимательный читатель заметил, что одна из возможных комбинаций в этом списке отсутствует:

Чтение выполняется... Запись выполняется...
… после чтения smp_load_acquire(), smp_rmb() smp_load_acquire(), smp_store_release()
… после записи ??? smp_store_release(), smp_wmb()
Оказывается, обеспечить глобальный порядок записей и последующих чтений из памяти гораздо сложнее. Процессоры вынуждены прилагать отдельные усилия для этого. Сохранение такого порядка стоит недёшево и требует явных инструкций. Чтобы понять причину этих особенностей, нам придётся спуститься на уровнь ниже и присмотреться к тому, как процессоры работают с памятью.
Читать дальше →
Всего голосов 10: ↑10 и ↓0 +10
Просмотры 5.2K
Комментарии 4

Приёмы неблокирующего программирования: атомарные операции и частичные барьеры памяти

Программирование *C++ *C *Разработка под Linux *
Перевод

В первой статье цикла мы познакомились с простыми неблокирующими алгоритмами, а также рассмотрели отношение “happens before”, позволяющее их формализовать. Следующим шагом мы рассмотрим понятие «гонки данных» (data race), а также примитивы, которые позволяют избежать гонок данных. После этого познакомимся с атомарными примитивами, барьерами памяти, а также их использованием в механизме “seqcount”.


С барьерами памяти некоторые разработчики ядра Linux уже давно знакомы. Первый документ, содержащий что-то похожее на спецификацию гарантий, предоставляемых ядром при одновременном доступе к памяти — он так и называется: memory-barriers.txt. В этом файле описывается целый зоопарк барьеров вместе с ожидаемым поведением многопоточного кода в ядре. Также там описывается понятие «парных барьеров» (barrier pairing), что похоже на пары release-acquire операций и тоже помогает упорядочивать работу потоков.


В этой статье мы не будем закапываться так же глубоко, как memory-barriers.txt. Вместо этого мы сравним барьеры с моделью acquire и release-операций и рассмотрим, как они упрощают (или, можно сказать, делают возможной) реализацию примитива “seqcount”. К сожалению, даже если ограничиться лишь наиболее популярными применениями барьеров — это слишком обширная тема, поэтому о полных барьерах памяти мы поговорим в следующий раз.

Читать дальше →
Всего голосов 11: ↑11 и ↓0 +11
Просмотры 6.8K
Комментарии 3

Введение в неблокирующие алгоритмы

Программирование *C++ *C *Разработка под Linux *
Перевод

Неблокирующие алгоритмы широко применяются в ядре Linux когда традиционные примитивы блокировки либо не могут быть использованы, либо недостаточно быстры. Эта тема многим интересна и время от времени всплывает на LWN. Из недавнего — вот эта июльская статья, которая собственно и сподвигла меня написать свою серию. Ещё чаще разговор заходит про механизм read-copy-update (RCU — руководство 2007 года всё ещё актуально), подсчёт ссылок, и способы сделать более понятные, высокоуровные API ко всему этому разнообразию. Ну а сейчас вас ждёт погружение в идеи, стоящие за неблокирующими алгоритмами, а также их использованием в ядре.


Знание низкоуровневой модели памяти в целом считается продвинутым уровнем понимания, которого страшатся даже опытные программисты-ядерщики. Словами нашего редактора (из его июльской статьи): «Понять модель памяти можно лишь правильно повёрнутым мозгом». Говорят, что моделью памяти Linux (и файлом memory-barriers.txt в частности) можно пугать детей. Порой для достижения эффекта достаточно всего лишь рявкнуть “acquire” или “release”.


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

Читать дальше →
Всего голосов 39: ↑36 и ↓3 +33
Просмотры 15K
Комментарии 60

Невменяемый, необъятный масштаб браузеров

Firefox Разработка веб-сайтов *Open source *Google Chrome Браузеры
Перевод

Увидев вот эту публикацию про браузерные войны, я хотел бы представить альтернативное наблюдение за тем, как мы докатились до такой жизни. Но Дрю ДеВолт уже всё сказал за меня.

Начиная с первых войн между Netscape и IE, главным инструментом в конкуретной борьбе браузеров стала функциональность. Вот только стратегия неограниченного роста и расширения — совершенно безумная. Слишком долго мы позволяли ей продолжаться.

С помощью wget я скачал все 1217 спецификаций W3C, опубликованных на текущий момент. Существенная часть из них должна быть реализована в браузере, чтобы современный веб работал. Я подсчитал объём этих спецификаций. Как думаете, насколько сложен современный веб?

Читать далее
Всего голосов 210: ↑200 и ↓10 +190
Просмотры 69K
Комментарии 693

CreateRemoteThread для Linux

Ненормальное программирование *Системное программирование *C *Разработка под Linux *
Tutorial

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


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


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


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

Читать дальше →
Всего голосов 76: ↑75 и ↓1 +74
Просмотры 11K
Комментарии 27

Как не переписать проект на Rust

Программирование *C *Rust *
Перевод
Tutorial

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


Гораздо полезнее будет предоставить безопасный интерфейс для оригинальной библиотеки, повторно используя её код.

Читать дальше →
Всего голосов 58: ↑57 и ↓1 +56
Просмотры 15K
Комментарии 88

Тесты на Си без SMS и регистрации

Программирование *C++ *C *

скришот Cutter Недавно zerocost написал интересную статью «Тесты на C++ без макросов и динамической памяти», в которой рассматривается минималистический фреймворк для тестирования Си++ кода. Автору (почти) удалось избежать использования макросов для регистрации тестов, однако вместо них в коде появились «волшебные» шаблоны, которые лично мне кажутся, простите, невообразимо уродскими. После прочтения статьи у меня оставалось смутное чувство неудовлетворённости, так как я знал, что можно сделать лучше. Я сразу не смог вспомнить где, но я точно видел код тестов, который не содержит ни единого лишнего символа для их регистрации:


void test_object_addition()
{
    ensure_equals("2 + 2 = ?", 2 + 2, 4);
}

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

Читать дальше →
Всего голосов 32: ↑32 и ↓0 +32
Просмотры 8.9K
Комментарии 9

Перехват функций в ядре Linux с помощью ftrace

Системное программирование **nix *C *Разработка под Linux *
Tutorial
ниндзя-пингвин,  En3lВ одном проекте, связанном с безопасностью Linux-систем, нам потребовалось перехватывать вызовы важных функций внутри ядра (вроде открытия файлов и запуска процессов) для обеспечения возможности мониторинга активности в системе и превентивного блокирования деятельности подозрительных процессов.

В процессе разработки нам удалось изобрести довольно неплохой подход, позволяющий удобно перехватить любую функцию в ядре по имени и выполнить свой код вокруг её вызовов. Перехватчик можно устанавливать из загружаемого GPL-модуля, без пересборки ядра. Подход поддерживает ядра версий 3.19+ для архитектуры x86_64.
Читать дальше →
Всего голосов 20: ↑20 и ↓0 +20
Просмотры 7.6K
Комментарии 4

Интерпретация во время компиляции, или Альтернативное понимание лямбд в C++11

Ненормальное программирование *Программирование *C++ *
Yo dawg, I heard you like programming. So we put a language in you language, so you can program while you programНа Хабре недавно проскочила ещё одна статья про вычисления на шаблонах C++ от HurrTheDurr. В комментариях к ней лично я увидел вызов:

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


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

Чуть раньше AveNat опубликовала введение в лямбда-исчисление в двух частях, так что вдохновение пришло мгновенно. Хотелось, чтобы можно было (образно) писать так:
#include <iostream>

#include <LC/kernel.h>
#include <LC/church_numerals.h>

int main()
{
    // Представление натуральных чисел в виде лямбда-абстракций
    typedef ChurchEncode<2> Two;    // 2 = λfx.f (f x)
    typedef ChurchEncode<3> Three;  // 3 = λfx.f (f (f x))

    // * = λab.λf.a (b f)
    typedef Lambda<'a', Lambda<'b', Lambda<'f',
                Apply<Var<'a'>, Apply<Var<'b'>, Var<'f'> > >
        > > > Multiply;

    // Вычисление (* 2 3)
    typedef Eval<Apply<Apply<Multiply, Two>, Three>> Output;

    // Переход обратно от лямбда-абстракций к натуральным числам
    typedef ChurchDecode<Output> Result;

    std::cout << Result::value;
}

А на выходе получать такое:
ilammy@ferocity ~ $ gcc cpp.cpp
ilammy@ferocity ~ $ ./a.out
6

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

Под катом находится очередное прокомментированное конструктивное доказательство Тьюринг-полноты шаблонов C++ в виде compile-time интерпретатора бестипового лямбда-исчисления (плюс печеньки в виде макросов и рекурсии).
Читать дальше →
Всего голосов 102: ↑98 и ↓4 +94
Просмотры 30K
Комментарии 13

«Lisp in Small Pieces» на русском

Lisp *Компиляторы *
Из песочницы
( Parentheses ) – Elegant weapons, for a more civilized ageЭта книга французского профессора Кристиана Кеннека об интерпретаторах Лиспа и Scheme довольно хорошо известна в англоязычном мире. Даже пару раз проскакивала на Хабре. Но в русскоязычном сообществе Scheme чаще всего ассоциируется со «Структурой и интерпретацией компьютерных программ» (aka SICP). Это хороший учебник для новичков, где целых две главы посвящены реализации используемого языка, однако в нём не рассматривается реализация довольно интересных и важных для Лиспа вещей вроде макросов, продолжений, динамических вычислений.

Однажды «Lisp in Small Pieces» попался мне в руки, и через несколько десятков страниц я осознал, что подобному бриллианту негоже пропадать в безвестности. А так как лучший способ получить больше адептов в секту популяризовать иностранную книгу — это перевести её на родной язык целевой аудитории, то этим я и занялся вместо того, чтобы нормально читать. Наконец, перевод, вёрстка и вычитка были завершены; результаты усилий представляются вашему вниманию.

Внутри читателя ожидают:
  • более 37000 скобок!
  • разбор по косточкам семантики всех конструкций Scheme, а также его родственников;
  • в том числе разбор его денотационной семантики — формального математического описания языка в терминах лямбда-исчисления;
  • 11 интерпретаторов и 2 компилятора (в машинный код описываемой там же VM и транслятор в код на Си);
  • объяснение сути рекурсии, замыканий и окружений, продолжений и стека вызовов, реализации макросов и метаязыков, а также чуть рефлексии и самомодифицирующегося кода;
  • множество экскурсов в историю Лиспа и причины принятых решений в дизайне языка;
  • собственная CLOS-подобная объектная система автора (и её реализация, разумеется);
  • время от времени возникающее чувство: «Да это же X из языка Y»;
  • список литературы по теме на 230 наименований.
В общем, отличный учебник по основам реализации языков программирования, с которым стоит ознакомиться не только любителям скобочек.
Ещё чуть-чуть и ссылки на PDF и EPUB
Всего голосов 55: ↑52 и ↓3 +49
Просмотры 31K
Комментарии 18

Информация

В рейтинге
1,807-й
Зарегистрирован
Активность