Задача с LeetCode.

Дан массив слов words. Слово содержит латинские буквы в нижнем регистре a-z. Проверить пары смежных слов и удалить , когда и - анаграммы.

Найдем группы смежных анаграмм и оставим в массиве первую строку каждой группы.

Я не математик, но люблю решать задачи. Я люблю трудные задачи, которые не знаешь, как решать, а если и знаешь, трудно написать код верно.

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

Говорят "У человека феноменальная память - он помнит все". Он записывает. Не помните, что делали три дня назад? Ведите дневник, а не покупайте "таблетки для памяти".

Давным-давно, когда F11 и F12 еще не придумали, F1-F10 располагались слева, Ctrl жил на месте CapsLock, а IBM продавала компьютеры с гарантией на 90 дней, владельцы компьютеров работали в MS-DOS. Процессор еще не знал, что такое защищенный режим, память не делилась на области пользователя и ядра, виртуальной памяти не было, как не было и многозадачности. MS-DOS программа на счет "раз" нарушала работу ядра и компьютер приходилось перезагружать. Программы скромно умещались в 64 Кб, а, если превышали это ограничение, жизнь их становилась труднее.

Дизассемблируем 16-битную программу: InDuLgEo V3-B горит пламенем на экране, печатает текст и трезвонит, как старый телефон.

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

Мы не станем вредить, а вирус напишем в компьютерной игре BitBurner. Писать вирусы - плохо, но изучать - интересно.

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

Научим xv6 работать с виртуальными страницами размера 2 Мб, узнаем, как компоновщик создает образ памяти программы и научим файловую систему xv6 справляться с большими файлами.

Пример: Пусть программа занимает 4 Мб памяти. Размер страницы - 4 Кб. Программа займет (1024 * 1024 * 4) / (1024 * 4) = 1024 страницы памяти. ОС избавит процессор от лишней работы, если увеличит размер страницы до 2 Мб - тогда программа займет 2 страницы.

Xv6 - учебная ОС - рассказывает об идеях, что лежат в основе операционных систем.

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

Книга рассказала об идеях, что лежат в основе операционных систем, на примере xv6. Одна часть кода xv6 выражает основные идеи и каждая строка кода важна - переключение потоков, пространства пользователя и ядра, блокировки и т.д. Другая часть кода воплощает алгоритмы и структуры данных, которые легко заменить на другие - политика планирования процессов, структуры файлов на диске, устройство журнала файловой системы и т.д. Книга полагается на интерфейс системных вызовов Unix, который оказался успешным настолько, что идеи легли в основу и других современных ОС.

Книга об xv6 на русском языке в формате PDF, HTML и EPUB.

Трудно добиться быстродействия ядра, организовать параллельную работу потоков и при этом писать ясный код. Блокировки помогают параллельным потокам работать корректно, но иногда блокировки использовать трудно. Глава расскажет о хитрых сценариях с блокировками в xv6 и о сценариях без блокировок.

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

Файловая система xv6 предлагает Unix-подобные файлы, директории и пути и хранит данные на virtio-диске.

Глава расскажет, какие задачи решает файловая система xv6.

Глава расскажет, что такое мультиплексирование процессов, как xv6 переключает процессы, как xv6 синхронизирует процессы с помощью sleep и wakeup, как работает семафор, как работает канал (pipe), как случаются инверсии приоритетов и образуются конвои процессов, как правильно убить процесс и укротить грохочущее стадо процессов.

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

Потоки конкурируют за доступ к структуре данных. Ядро кишит структурами, которые потоки используют совместно. Блокировки защищают данные при конкурентном доступе.

Глава расскажет, зачем нужны блокировки, как xv6 реализует и использует блокировки.

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

Устройство прерывает процессор, когда требует внимания. Обработчик прерывания опознает устройство и вызовет процедуру драйвера. В xv6 это делает процедура devintr.

Файл kernel/console.c содержит код драйвера терминала. Драйвер обрабатывает символы из последовательного порта UART на RISC-V, которые человек вводит на клавиатуре.

QEMU эмулирует микросхему 16550 UART и подключает клавиатуру и экран к UART. На реальном компьютере 16550 управляет портом RS232, который работает с терминалом или другим компьютером.

Драйвер накапливает символы в кольцевом буфере cons.buf. Индекс cons.r указывает на первый символ, который прочтет функция consoleread. Буфер хранит строки символов, а индекс cons.w указывает на начало последней строки, которую еще вводит человек. Индекс cons.e указывает позицию курсора в последней строке для ввода следующего символа.

Глава расскажет, как xv6 обрабатывает прерывания на RISC-V и о хитростях виртуальной памяти: как использовать ошибки доступа к страницам, чтобы оптимизировать работу ОС.

Глава расскажет о копировании страниц при записи, ленивой выдаче страниц, выдаче страниц по необходимости и сбросе страниц на диск.

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

Глава рассказывает, как xv6 работает с виртуальной памятью и об устройстве виртуальной памяти RISC-V.

Эта инструкция - приложение к книге об учебной ОС xv6.

Xv6 работает на RISC-V. Для сборки кода xv6 и запуска под QEMU понадобятся RISC-V версии инструментов: QEMU 5.1+, GDB 8.3+, GCC, и Binutils.

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

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

ОС позволяет процессам взаимодействовать - обмениваться данными и работать совместно.

Глава 2 рассказывает, как xv6 выполняет эти требования, о процессах xv6 и как xv6 запускает первый процесс.

Эта книга рассказывает о принципах работы операционных систем на примере xv6. Операционная система xv6 реализует базовый интерфейс, который Кен Томпсон и Деннис Ритчи предложили в операционной системе Unix, и подражает внутреннему устройству Unix. Комбинации простейших механизмов Unix дают удивительную свободу действий. Современные операционные системы признали успех Unix и реализуют похожие интерфейсы - BSD, Linux, macOS, Solaris, и даже Microsoft Windows. Изучение xv6 поможет понять работу и других операционных систем.

Два года назад взялся писать программу, что помогает выставлять счета за аренду ковров. Прежде бухгалтер держал текст договоров в Word, расписание в Excel, а три дня каждого месяца убивал на подсчеты. Теперь программа сама рассчитает суммы и загрузит счета в 1С.

Компания такая не одна: защищу программу - продам ключи.

Защита программы - трудное дело. Исследую защитные алгоритмы на практике: вытащу из готовых программ, а чтобы никому не вредить, исследую программы, что специально написаны для взлома - crackme или keygenme.

Жребий пал на q_keygenme_1.0 by quetz.

Жив еще Visual Basic: программы еще живы. Байт-код VB выполняется виртуальной машиной msvbvm60.dll , которая до сих пор живет в каталоге C:\Windows .

Задача - разгадать алгоритм проверки ключей.
zira's ZittoKeygenme https://crackmes.one/crackme/648b452233c5d4393891390d

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

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

Посмотрим, как справиться с противодействием отладке на примере 1337ReverseEngineer's The Junkrat https://crackmes.one/crackme/62dc0ecd33c5d44a934e9922 .