Memory Barriers: a Hardware View for Software Hackers

Paul E. McKenney
Linux Technology Center
IBM Beaverton
2010

== Лекция 13. Шаблоны || программирования. Консенсус
https://youtu.be/C_v800s4Axs

чем меньше шаред мемори - тем лучше

лучше иммутабельность, дублирование

1) pipeline
2( double check

== Лекция 14. Транзакционная память
https://youtu.be/HgRGGKqeod8
i/o
- блокирующий = ждет заполнения буфера
- не блокирующий = если в буфере ничего нет на момент опроса - просто вернет что ничего нет

i/o
- синхронный - детерменированно ждет завершения опирации
- асинхронный - работа через событие

если можно сделать аналогию с сигналами - то асинхронно, если нет - это синхронный случай

>
callback -> eventQueue -> demultiplexor -> proactor -> callback

select это функция POSIX в которую передется набор дескрипторов (сокетов), а обратно получашь набор тех которые сработали

epoll использует eventQueue ОС

== Обзор архитектуры x86
https://youtu.be/POiuH3sue3M
модель памяти
- сегментация, ретрансляция адресов
виртуальная память это и есть страничная организация памяти

ассемблер
- все что начинается с точки - это не к процессору а к ассемблеру
- часть команд зависит от состояния регистров флагов
- command, soruce, dest
- операнды

== x86 Protected mode overview
https://youtu.be/BW6C6dFByKQ

- логический адрес (селектор, смещение)
- линейный адрес (таблица, страница, смещение)
- физический адрес (на шине памяти)

GDTR
IDTR

чтобы получить данные 2 шага:
каталог страниц -> поулчить страницу
страница -> получить данные по оффсету

регистры
cr0 - системные контрольные флаги
cr2 -
cr3 - физический адрес базы каталога страниц и 2 флага ( PageLevelCaceheDisable, PageLevelWritesTransparentL1L2)
cr4 - флаги SIMD

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

процессору нужен контроллер прерываний (в составе чипсета)

- немаскируемые прерывания
- маскируемые прерывания (каскадируемые многоуровневые)

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

при обработке прерывания проверяется уровень привелегий

== Создание первого процесса. Инициализация операционной системы
https://youtu.be/DFdNMXNoWn8

процесс
- обладает потоками
- работает до тех пор пока есть что исполнять
- НЕТ стэка (он есть у потока)

PID - Process ID
TGID - Thread Group ID

любой процесс создается (кроме Саааамого первого init процесса)
- через fork
- через exec
- через clone (куча флагов настройки)
- через unshare (может создавать свое пространство процессов, став аля init процессом)

fork полностью копирует родительский. передает PID родителю. НО адресное пространство другое.
регистры общего назначения не сохраняются (это гарантирует уже юзер код)

ответсвенный за уборку мусора после смерти процесса - родитель

Состояние:
- running
- ready (runnable)
- wait (ждет исполнения IO или другого от ОС)

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

switchuvm() переключает контексты. сохраняется текущий стэк

syscall
- fork
- exit
- wait
- pipe
- read
- kill
- exec
- fstat
- chdir
- dup
- getpid
- sbrk
- sleep
- uptime
- open
- write
- mknod
- unlink
- link
- mkdir
- close

How do debuggers (really) work?

== Как работает процессор
https://youtu.be/kIrKeKiJt90

RAM:
- шина адреса
- шина данных
- шина управления (установить/получить)

- Управляющее устройство
- АЛУ
- регистр
- шина процессора
- временный буфер
- регистр инструкций

== Безопасность интернет-приложений
https://youtu.be/c9k3WUdDMpo

Угрозы
Spoofing - подмена данных
Tampering - перехват
Repudiation - нарушение апелируемости, попытка скрыть источник запроса
Information Disclosure
Denial of service
Elevation of privilege

Оценка рисков
- damage
- reproducibility
- Exploitability
- Affected users
- discoverability

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

== Безопасность интернет-приложений №2
https://youtu.be/0zIgTtXkMWk
иньекции
- XSS
- XSF
- XM... XXE
- HTTP headers
- SQL
- NoSQL
- OS Command
....

XSS
- Stored
- reflected
- DOM-based

Cross-Site Request Forgery
- выполнение запросов к приложению от имени и без ведома пользователя (невозможность отличить источник запроса)

== Безопасность интернет-приложений #3
https://youtu.be/8I9fDF-r0E0

Аутентификация
- no pass
- ID + pass
- webAuthn (устроство подтверждения)
- email, sms
- totp (time based one time password)
- hotp (HMAC-based one time password)
- клиентский сертификат

авторизация (права)
- для каждого вызова (function level)
- для каждого обьекта (object level) -insecure direct object reference (IDOR)

Server Side Request Forgery (SSRF)
заставить сервер сервиса сделать запрос на произвольный урл

XXE - xml extra entities

конфигурация
- читать документацию
- логи
- лимиты
- обновление версий

== Безопасность интернет-приложений #4 / Криптографические средства
https://youtu.be/B8ID_t7q4Uc

https://www.crypto101.io/ -

- блочные / поточные
- симметричные / асимметричные
- хэш функции

https://github.com/owasp/owasp-masvs
https://github.com/0xmachos/iOS-Security-Guides

Ios / android
- каждое приложение изолировано
- есть приватное хранилище
- есть секреты
- ОС обеспечивает изоляцию при выполнении

== Безопасность интернет-приложений #5 / Моделирование угроз. SDLC
https://youtu.be/Rq_eAWbCqUc

Crypto 101
https://www.crypto101.io/

- XOR
- Block ciphers
- Stream ciphers
- Key exchange
- public-key encryption
- hash functions
- message authentication codes
- signature algorithms
- key derivation functions
- random number generators
- ssl & tls
- openPGP & GPG
- Off the record messaging (OTR)
- Modular arothmetic
- elliptic curves
- side-channel attacks

== Базы данных. Лаборатория Tarantool. Введение в современные СУБД
https://youtu.be/ejS2DE-ar3A
достойный преподаватель из кор тимы Тарантула
acid - atomic, consistency, isolation, durability

== Базы данных. Лаборатория Tarantool. Современные алгоритмы для двухуровневой памяти
https://youtu.be/0A4_SdNEH8c
- диск-память-кэш-процессор
- стоимостная модель
- проблема memory-layout матрицы
- транспонирование матриц
- log-structured-merge дерево
- bloom фильтр
- двойная буфиризация (пишем в один, сбрасываем на диск второй, чередуем)
LSM БД юзаются для частого обновлеющихся данных
- Fractional Cascading - способ уменьшить затраты для упорядоченных структур
- bit-cask. Append only file (AOF) - нет спаек при записи как у LSM. Надо переписывать индекс каждый раз в конец вместе с изменениями
- page-index сохраняет мин-макс в ячейке, что бы сократить время поиска

== Базы данных. Лаборатория Tarantool. Кэширование
https://youtu.be/jhAOFFUVSjk

Least Recently Used - вытеснение давноиспользуемых (одновязанный список, например)
- былали изменена страница?
- завершена ли транзакция, кот модифицировала страницу ?
- физический порядок страниц на диске
- вытеснение осуществляется превентивно в другом потоке

для Index Scan лучше MRU

Midpoint insertion strategy
- LRU разбивается на тёплую и горячую зоны
- Граница между зонами плавающая
- index scan более не «вымывает» кэш

Идея
Балансировать между малыми и большими издержками до тех пор пока сумма малых издержек не превысит большие

LFD - longest forward distance (~clairvoyant algorithm, ~Belady's algorithm)
выталкиваем страницу которая будет запрошена позже всего в будущем

Для любого другого алгоритма А, cost(A) не ухудшается если мы, в случаях когда A отличается от LFD, выталкиваем страницу в
соответствии с LFD, а не с A

для онлайн алгоритмов худший случай это загрузить все страницы

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

Рандомизированный алгоритм: MARK
- Помечает страницу при использовании (они не выталкиваются)
- Когда все страницы помечены, и нужна страница, все пометки снимаются (кроме пометки на новой странице)
- Для выталкивания выбирается случайная страница из непомеченных
====> const(MARK) = lg(k) * cost(LFD)

LRU таким образом в целом не хуже чем MARK (на случайных данных)

== Caching and Cache-Efficient Algorithms
https://youtu.be/xDKnMXtZKq8
Fully Associative Cache
Direct-Mapped Cache
Set-Associative Cache

Taxonomy of Cache Misses
- cold miss
- capacity miss
- conflict miss
- sharing miss
Conflict Misses for Submatrices

Ideal-Cache Model
How Reasonable Are Ideal Caches?
Cache-Miss Lemma
Tall Caches
What's Wrong with Short Caches?
Submatrix Caching Lemma
Multiply Square Matrices
Analysis of Cache Misses
Swapping Inner Loop Order
Tiled Matrix Multiplication
Two-Level Cache

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

но насколько же круто они преподают... захотелось быть студентом у них на курсе

== Bit Hacks
https://youtu.be/ZusiKXcz_ac

0b10010110
signed int -106 = 2 + 4 + 16 - 128
unsigned int 150 = 2 + 4 + 16 + 128
0b11111111 => -1

x + ~x = -1
-x = ~x + 1



A    = 0b10110011
B    = 0b01101001
A&B = 0b00100001
A^B = 0b11011010
A|B = 0b11111011
A >> 3 = 0b00010110
A << 2 = 0b11001100

- set
- clear
- flip
- extract
- set x to y
- swap without temp var
(x ^ y) ^ y
- min x and y
m = y ^ ((x ^ y) & -(x < y))
NO BRANCHES -> no performance leaks!
- branchless merging sorted arrays
- power of 2
- kog base 2 of power of 2

ну просто шикарные преподы в MIT. даже то что знаешь хорошо просто приятно послушать

== Assembly Language & Computer Architecture
https://youtu.be/L1ung0wil9Y

data movement
- mov, cmov
- sigh or zero extension: movs, movz
- stack: push, pop
arithmetic and logic
- int logic: add, sub, mul, imul, div, idiv, lea, sal, sar, shl, shr, rol, ror, dec, neg
- bin logic: and, or, xor, not
- bool logic: test, cmp
Control transfer
- unconditional jump: jmp
- conditional jumps: j<condition>
- subroutines: call, ret

for fetching something from memory - x*100 тактов

compiler generates NOP lines for optimize instruction memory (code, size, alignment....)

SSE and AVX supports x64 fpu
sufixies: ss, sd, ps, pd

pipelininig improves processor throughput !
but
- structural hazard (one instruction for one tact)
- data hazard (depends from result):
- i writes a location that j reads
- j reads location that j writes
- i and j write to the same location
- control hazard (fetching/loading/storing etc operators)

== Seaborn - лучшая data science библиотека для визуализации на Python
https://youtu.be/gMSQMLeQ4UI

🆖 Nginx common useful configuration - вдруг кто-то найдёт для себя что-то полезное для работы с Nginx. Там ещё и ссылок приличное количество имеется, по ним тоже имеет смысл пройти.

#nginx #будничное