Форк-бомба Фибоначчи

Эта форк-бомба работает так, что количество процессов на i-й секунде работы равно i-му числу Фибоначчи.

Код:
#include <unistd.h>

int main() {
sleep(1);
do {
sleep(1);
if (!fork()) sleep(1);
} while (1);
}

#prog #cpp #моё

В C++ есть такая вещь, как strict aliasing. Если коротко, то это предположение компилятора о том, что доступы по указателям (и ссылкам) существенно разных типов не пересекаются между собой. Подробнее про это можно прочитать, например, тут, ну а я покажу, как это влияет на (не)возможность оптимизировать код на C++. Все приведённые ниже примеры будут использовать компилятор GCC 12.2 с флагами --std=c++20 -O2 -pedantic (с -O3 компилятор векторизует код и делает его гораздо объёмнее и менее понятным).

Напишем вот такой код (где std::span<int> играет примерно ту же роль, что и &mut [i32] в Rust):

#include <span>

void increment(std::span<int> arr, const int* value) {
for (auto& x: arr) {
x += *value;
}
}

(в дальнейшем для экономии места я буду опускать #include <span>)

Смысл этого кода очень простой: увеличить все числа в данном диапазоне на данную величину. Казалось бы, тут в цикле есть доступ по указателю, который имеет смысл вынести из тела (loop-invariant code motion). Но во что этот код переводит компилятор?

lea rcx, [rdi+rsi*4]
cmp rdi, rcx
je .L1
.L3:
mov eax, DWORD PTR [rdx]
add DWORD PTR [rdi], eax
add rdi, 4
cmp rdi, rcx
jne .L3
.L1:
ret

Тело цикла располагается между метками .L1 и .L3. Конкретно сейчас нас интересуют две инструкции:

mov eax, DWORD PTR [rdx]
add DWORD PTR [rdi], eax

Выходит, что в регистре rdx располагается адрес, указатель value, а в регистре rdi — x, адрес текущего элемента спана. На каждой итерации процессор загружает значение из памяти и потом складывает со значением в другом месте в памяти. Почему же?

Дело в том, что переданный указатель может указывать на сам элемент внутри спана. increment может быть использована, например, так:

void use_increment(std::span<int> a) {
increment(a, &a[1]);
}

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

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

Попробуем, например, short:

void increment(std::span<int> arr, const short* value) {
// тело без изменений
}

Что генерирует компилятор?

lea rax, [rdi+rsi*4]
cmp rdi, rax
je .L1
movsx edx, WORD PTR [rdx]
.L3:
add DWORD PTR [rdi], edx
add rdi, 4
cmp rdi, rax
jne .L3
.L1:
ret

Ага, то есть доступ к value (с sign extension, разумеется) —

movsx edx, WORD PTR [rdx]

— вынесен за пределы цикла! Так в чём же разница по сравнению с предыдущими примерами?

Вот тут как раз и вступает в силу правила strict aliasing (aka последний параграф в [basic.lval]): не смотря на то, что сформировать указатель на short из указателя на int можно, эти два типа отличаются, и получение доступа к значению одного типа через указатель на другой является неопределённым поведением. Так как в корректной программе на C++ неопределённого поведения не может произойти, компилятор использует этот факт, чтобы обосновать корректность выноса доступа к памяти из цикла.

Однако! У правил strict aliasing есть нюансы насчёт того, по указателям (на самом деле glvalue, но не суть) каких типов можно получать доступ к значениям других типов. В частности, unsigned и signed варианты того же типа не считаются существенно отличными, и потому при передаче const unsigned* value компилятор оставляет доступ к value в теле цикла.

И ещё у этого правила есть совсем неожиданное исключение: доступ по указателю на char, unsigned char и std::byte. При передаче value по указателю на один из этих типов компилятор оставляет доступ в цикле.

Внимательные читатели могли заметить, что этот список не включает в себя signed char (и, кстати, в этом месте C++ отличается C, в котором алиаситься могут указатели любых вариантов char). Тем не менее, вариант increment с указателем на signed char последние версии и GCC (12.2), и clang (15.0.0) не могут скомпилировать с выносом доступа к value из цикла. Почему — не ясно. Наверное, это можно считать багом.

Поиграться со всеми упомянутыми вариантами: godbolt.org/z/8rr3hWTbf
(ссылка для расшаривания, к сожалению, потеряла все имена вкладок с кодом. Ну хоть имена вкладок с компиляторами оставила)

Для любителей ассемблера

Советую почитать книгу xchg rax, rax. В ней нет ничего, кроме 0x40 (т.е. 64) страниц, на каждой из которых расположен листинг ассемблерного кода без никаких пояснений. От читателя требуется понять написанный код и разгадать, что он делает. На просторах Интернетов есть подсказки, но лучше попытаться без них :)

[для тех, кто хочет подсказок: вот и вот, а лучше решайте сами :)]

Еще забавно, что автор продает бумажную версию.

Когда я обнаружил эту книгу, я залип и не мог больше ничего делать, пока не досмотрел до конца. Многое (однако не все) я смог решить, тогда пришлось смотреть подсказки. Загадкой остается лишь номер 0x16, про который даже в подсказках нет идей :( Но если кто-то здесь решил, можете смело писать в комментариях :)

Какая страна больше всего связана с языком программирования Rust?

Сербия 🇷🇸. У нее домен .rs :)

Все виды путей в Windows в одной статье

(спойлер: их там восемь разных видов!)

https://googleprojectzero.blogspot.com/2016/02/the-definitive-guide-on-win32-to-nt.html

Как хорошо, что в UNIX всего два вида путей: абсолютные и относительные 😌

А теперь поговорим, что не так с путями в UNIX

Проблема в том, что в именах файлов в UNIX-подобных ОС (в Linux в том числе) запрещены лишь два символа: '\0' (он же нулевой символ) и /, а все остальное разрешено. В имени файла может быть даже перевод строки!

И эта особенность мешает правильно отображать имена (мало кто, думаю, умеет правильно показывать многострочные имена файлов). К тому же, становится невозможно парсить вывод утилит вроде ls или find надежным образом. Действительно, ls обычно разделяет файлы переводом строки, а что если в самом имени файла встретится перевод строки? Правда, у find есть флаг -print0, который разделяет имена файлов нулевыми символами, но данные в таком формате надо как-то предобрабатывать, чтобы скормить в пайп другой программе.

Еще происходят веселые вещи, если в имени файла есть специальные символы. Например:
$ touch $'\033[31;1mredfile\033[0m.txt'
$ ls
''$'\033''[31;1mredfile'$'\033''[0m.txt'
$ find .
.
./?[31;1mredfile?[0m.txt
$ echo *
redfile.txt

(после выполнения последней команды redfile будет выделен красным цветом)

Здесь видно, что GNU'шные find и ls заменяют спецсимволы на ?, поэтому вы никак не узнаете истинное имя файла, если будете парсить вывод этих утилит. Это поведение еще не портируемо; например, find из busybox выдаст

$ busybox find .
.
./a
b.txt
./redfile.txt

(и redfile снова будет красным)

А еще имя файла — произвольная последовательность байт, а в какой кодировке ее интерпретировать — остается на усмотрение пользовательских программ. Обычно в GNU/Linux все имена файлов записаны в UTF-8, но если криво установить локаль, то все имена на русском рискуют превратиться в тыкву.

На месте авторов UNIX я бы, наверное, запретил все символы с кодом меньше 32 в именах файлов. Еще я бы запрещал называть файлы невалидным UTF-8, но появление Юникода, увы, авторы оригинального UNIX предугадать не смогли бы. А добавить такой запрет позже сложно, потому что надо тянуть обратную совместимость.

Еще про пути в UNIX

(пример честно украден из The UNIX-HATERS Handbook)

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

$ rm *

Как нетрудно догадаться, эта команда удаляет рекурсивно все содержимое... кроме одного файла с именем -r :)

Правильно было бы написать rm ./* или даже rm -- *, чтобы такого безобразия не произошло.

Windows и TerminateThread

Советую почитать замечательную статью: https://devblogs.microsoft.com/oldnewthing/20150814-00/?p=91811

tl;dr:
> Originally, there was no Terminate­Thread function. The original designers felt strongly that no such function should exist because there was no safe way to terminate a thread, and there’s no point having a function that cannot be called safely. But people screamed that they needed the Terminate­Thread function, even though it wasn’t safe, so the operating system designers caved and added the function because people demanded it. Of course, those people who insisted that they needed Terminate­Thread now regret having been given it.

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

В сломанности TerminateThread убедиться несложно. Достаточно запустить простой код, который запускает много потоков и сразу же их убивает. Не знаю, как у вас (кто может проверить, отпишитесь в комментах), а у меня на Windows 7 этот код наглухо зависал на какой-то итерации, не добегая до конца. И это при том, что здесь нет никаких примитивов синхронизации, а только создание потока!

Переполнение в Java, которое позволяет итерироваться после изменения массива

Как известно, если ArrayList<> поменять во время итерации, то Java кинет исключение java.util.ConcurrentModificationException. Однако это можно обойти. Рассмотрим такой код:

import java.io.*;
import java.util.*;

public class ExceptionHack {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>(List.of(1, 2, 3));
        Iterator<Integer> iter = arrayList.iterator();
        int item = iter.next();
        System.out.println(item);
        arrayList.add(0, 4);
        arrayList.add(1, 5);
        for (int i = 0; i < Integer.MAX_VALUE; ++i) {
            if ((i & 16777215) == 0) {
                System.out.println(i);
            }
            arrayList.add(0, 3);
            arrayList.remove(0);
        }
        iter.next();
        System.out.println(item);
    }
}

Он не кидает никаких исключений, хотя между увеличением и созданием итератора проходит много модификаций! Объяснение такое: у ArrayList<>, как и у итератора, хранится счетчик числа модификаций, при каждом изменении он увеличивается. Если счетчики не совпадают, то кидается исключение. Беда в том, что этот счетчик имеет тип int, поэтому его нетрудно переполнить. Чем, собственно, и занимается написанный выше код.

ААААААААА, ЭТО ОФИГЕННО!!!! 🤩 Клеточный автомат «Игра Жизнь» симулируется на самом себе бесконечно в обе стороны!!! Просто откройте!

https://oimo.io/works/life/

И еще в тему бесконечно-рекурсивных изображений:
https://xkcd.com/1416/

Впечатляет не так сильно, как рекурсивная игра «Жизнь», но тоже довольно залипательно. Можно поисследовать и отыскать всякие разные картинки. Увы, при слишком большом приближении все начинает лагать :(

Как погладить манула при помощи ChatGPT :)

(дисклеймер: не повторяйте описанные действия самостоятельно!)

Все основные кириллические раскладки делятся на три типа

1) ЙЦУКЕН-подобные
2) QWERTY-подобные
3) болгарская

Предположения о том, насколько плохо все со взломом LastPass

“Despite having her master password set to an astonishing 19 characters, our source claims to have experienced a wave of successful attacks against her through the sites and services she uses. These have included messing with her home thermostat to change the temperature to a sweltering 87F (About 30C for those who use sensible measurements).

As fun a prank as that sounds, our contact also reports the attackers used her Apple ID and ATT credentials to change the PIN on her phone, successfully simjacked her, and added a whole bunch of authorized devices to her LastPass account to bypass MFA.”

https://thecrow.uk/lastpass-data-breach-is-starting-to-look-truly-horrendous/

Немного комментариев по поводу предыдущего поста.

1) Подробности пугают, если здесь есть пользователи LastPass, то лучше срочно менять пароли, сбрасывать открытые сессии и смотреть, правда ли злоумышленник не успел зайти :)

2) Пока не очень понятно, как именно все описанное произошло, учитывая, что по заявлениям LastPass они шифруют все локально и не передают мастер-пароль на сервер (хотя я здесь не очень знаю их механику). Если описанное выше — правда, то будет интересно дождаться подробностей и почитать :)

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

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

Например, рассмотрим пароль из 12 случайных маленьких латинских букв — всего 26^12 = 9.54 × 10^12 вариантов. На проверку каждого пароля уходит примерно секунда: дело в том, что для шифрования используется не сам пароль, а его специальный хэш. Этот хэш специально спроектирован так, чтобы для его вычисления потребовалось много времени и памяти (типично порядка секунды времени и гигабайта памяти, но зависит от настроек хэша). Таким образом, на подбор пароля потребуется примерно 3 × 10^9 лет :) Этот процесс можно распараллелить, но из-за лимита по объему памяти на одном сервере можно считать порядка сотен хэшей одновременно, а распараллеливание на GPU не поможет.

Конечно же, наличие уязвимостей в коде (если они есть) сильно упрощает процесс взлома.

Из примеров таких локальных менеджеров паролей могу привести pass и KeePassXC.

4) Из пунктов выше следует, что история в посте очень странная, и стоит ждать подробностей. Но в любом случае лучше поменять пароли, если история со взломом LastPass вас как-либо затронула.

Про будущее канала

Сегодня последний день года, а это значит, что пора поговорить о будущем :) К тому же, каналу уже почти два месяца.

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

Тем не менее, я писать не прекращаю и постараюсь приносить что-то интересное раз в 2-4 дня. Делать каждый день по посту уже, вероятно, не получится. К тому же, все мы страдаем от информационного перенасыщения, и лучше чуть уменьшить объем информации, чтобы и успеть сделать все дела, и успеть внимательно прочитать все посты :) Но главная причина скорее в том, что генерить или даже репостить интересный контент каждый день сложно.

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

Stay tuned!