ну тогда надо говорить так — между числом которогоне существует и порядковым номером, которого не существует.
Число Pi/4 мы уточняем знак за знаком, это бесконечный итеративный процесс. По мере получения очередного знака, мы получаем конкретное число и вычисляем для него порядковый номер.
Т.е. бесконечную непереодическую дробь — можно рассматривать как несуществующее число, а можно рассматривать, как результат работы некоторого бесконечного алгоритма, который на каждом шаге выдает очередную цифру и в этом смысле порядковый номер можно тоже рассматривать как некое число, являющееся результатом работы бесконечного алгоритма.
Но мы же можем последовательно вычислять последовательность знаков после запятой, после чего алгоритмически вычислять порядковый номер для Pi/4. Просто это будет бесконечный процесс, т.к. у числа бесконечно много знаков после запятой. Но т.к. есть алгоритм, то и есть взаимо-однозначное соответсвие.
, то CPU читает кэш-линию (размером 64 байта) из RAM. После чего, при обращении к любому из этих байтов, время чтения будет минимально, т.к. они уже в кэше, что, собственно, и вызвало мой вопрос )) Но на самом деле нас интересуют только те индексы, которые кратны 4096.
CPU читает из RAM не побайтно, а кэш-линиями. Допустим CPU прочитал кэш-линию. Во время цикла
for (i = 0; i < 256; i++) {
if (is_in_cache(userspace_array[i*4096])) {
// Got it! *kernel_space_ptr == i
}
}
мы определяем индекс массива, который читается быстро, но в то же время рядом с ним находятся еще несколько байтов из этой же кэш-линии и которые тоже будут быстро читаться.
Вопрос: как нам понять какой именно из этих индексов — нужное нам значение из закрытой области RAM?
Рассказывать о технологиях, не упоминая области их применимости — это как рассказывать про инженерное устройство мостов, не рассказав перед этим про сопромат :-) Поэтому «сопромат» в статьях такого уровня необходим.
Не совсем согласен, т.к. у любой статьи всегда имеется определенный уровень абстракции, на который она изначально рассчитана.
Про мосты можно тоже по-разному рассказывать, можно «на-пальцах», а можно так глубоко свалиться в детали, что вообще уйти в петлевую квантовую гравитацию. :-)
Чтобы понимать зачем нужен син-флуд и вчем его смысл, нужно понимать что такое listen socket, что такое syn-received socket, что такое established socket.
Системный вызов listen() инициализирует syn_table, accept_queue, переводит сокет в состояние LISTEN и помещает его в хэш таблицу listening сокетов.
Определяется размер accept_queue: sk_max_ack_backlog = min(somaxconn, backlog).
Определяется размер syn_table:
1. nr_table_entries = max(8, min(sysctl_max_syn_backlog, somaxconn, backlog)).
2. Далее значение nr_table_entries округляется до ближайшей степени двойки вверх (даже если оно уже степень двойки), а значение степени для нового значения сохраняется в max_qlen_log.
Когда приходит новый SYN, то ищется соответствующий listening сокет в хэш таблице listening сокетов, после чего проверяется, что текущий
размер syn_table (qlen) не превышает максимальный размер syn_table: 2 ^^max_qlen_log.
Если превышает, то проверяется включены ли tcp_syncookies, если вЫключены, то SYN дропается.
Если НЕ превышает либо tcp_syncookies включены, то текущий размер sk_ack_backlog сравнивается с sk_max_ack_backlog.
Если sk_ack_backlog > sk_max_ack_backlog то проверяется размер qlen_young.
Если qlen_young > 1, то SYN дропается, если qlen_young <= 1, то создается request_sock.
request_sock считается young, пока не был отправлен повторный SYN/ACK и используется для того, чтобы в случае заполнения
accept_queue была возможность принимать новые SYN.
Когда приходит финальный ACK (если для сокета включена опция TCP_DEFER_ACCEPT, то сокет ожидает ACK с данными), то создается
tcp_sock, адрес на него сохраняется в поле sk структуры request_sock и кастится в struct sock, после чего tcp_sock подвязывается в
хэш таблицу для established сокетов (но не подвязывается в VFS), удаляется из syn table и помещается в accept_queue.
Сокеты, находящиеся в accept_queue ожидают пока приложение выполнит системный вызов accept(). После вызова accept(), request
sock удаляется из accept_queue, создается BSD сокет struct socket, к нему подвязывается данный connected сокет после чего BSD
сокет подвязывается в VFS, а приложению возвращается файловый дескриптор.
Когда включены tcp_syncookies, если syn_table не заполнена полностью, то SYN проходит классический путь по стэку, если заполнена,
то SYN не дропается, а обрабатывается и на него отправляется SYN/ACK содержащий специальным образом сформированный ISN, но при
этом request sock не создается: request sock создается после получения финального ACK и валидации acknowledgement number и
сразу помещается в accept_queue.
Если включена опция TCP_DEFER_ACCEPT, то она работает только для сокетов, проходящих классический путь.
Если syn_table заполняется более чем на половину, количество повторных передач для SYN/ACK уменьшается до 1-3 (точный алгоритм в
см. коде), чтобы сокеты в состоянии SYN_RECV как можно быстрее освобождали syn_table.
______________________
CONCLUSION:
Т.о. до появления син-кук либо при выключенных син-кука смысл син-флуда в том, чтобы постоянно держать syn table заполненной. Что позволит уронить сервер атакой в 1 мбит/с даже при наличии канала 10Г (при не оттюненом сервере и tcp/ip стэке).
После появления син-кук задача син-флуда сделать так, чтобы CPU уходил в 100% при расчете куки, но в этом случае должно быть много пакетов. А если отправлять син с данными, то на выходе будет меньше пакетов. В чем смысл?
1. Очевидно, со стороны роутера (который, под управлением оператора) тоже должен быть выставлен такой же mtu, иначе фрагментация до пресловутых 1500 байт.
2. На сетевом оборудовании Jumbo-frame обычно не превшает 9000 байт.
3. Может я отстал от жизни, но, зачем нужен син-флуд большими пакетами?
MSS — это порция байт, которую tcp передает ip уровню, и очевидно, она не может превышать MTU.
В линуксе MSS вычисляет вот такая функция: __tcp_mtu_to_mss().
Вот что выдает gdb (если зайти на 192.168.10.10:80/sla_status):
gdb /usr/local/nginx/bin/nginx /usr/local/nginx/logs/coredump/core
Program terminated with signal 11, Segmentation fault.
#0 ngx_shmtx_lock (mtx=0x28) at src/core/ngx_shmtx.c:78
78 if (*mtx->lock == 0 && ngx_atomic_cmp_set(mtx->lock, 0, ngx_pid)) {
(gdb) bt
#0 ngx_shmtx_lock (mtx=0x28) at src/core/ngx_shmtx.c:78
#1 0x080c7fe7 in ngx_http_sla_status_handler (r=0x9e35908) at /home/fervid/distrib/src/modules/sla/ngx_http_sla.c:793
#2 0x0807d2a9 in ngx_http_core_content_phase (r=0x9e35908, ph=0x9e47098) at src/http/ngx_http_core_module.c:1410
#3 0x080784c3 in ngx_http_core_run_phases (r=r@entry=0x9e35908) at src/http/ngx_http_core_module.c:888
#4 0x080785d4 in ngx_http_handler (r=r@entry=0x9e35908) at src/http/ngx_http_core_module.c:871
#5 0x08083780 in ngx_http_process_request (r=r@entry=0x9e35908) at src/http/ngx_http_request.c:1852
#6 0x08083dfb in ngx_http_process_request_headers (rev=rev@entry=0xb26ee070) at src/http/ngx_http_request.c:1283
#7 0x08084331 in ngx_http_process_request_line (rev=rev@entry=0xb26ee070) at src/http/ngx_http_request.c:964
#8 0x08084924 in ngx_http_wait_request_handler (rev=0xb26ee070) at src/http/ngx_http_request.c:486
#9 0x0806571e in ngx_event_process_posted (cycle=cycle@entry=0x9e30798, posted=0x81132cc) at src/event/ngx_event_posted.c:40
#10 0x0806524d in ngx_process_events_and_timers (cycle=cycle@entry=0x9e30798) at src/event/ngx_event.c:275
#11 0x0806c96a in ngx_worker_process_cycle (cycle=cycle@entry=0x9e30798, data=data@entry=0x0) at src/os/unix/ngx_process_cycle.c:816
#12 0x0806b013 in ngx_spawn_process (cycle=cycle@entry=0x9e30798, proc=proc@entry=0x806c88f <ngx_worker_process_cycle>, data=data@entry=0x0, name=name@entry=0x80e502d «worker process», respawn=respawn@entry=-3)
at src/os/unix/ngx_process.c:198
#13 0x0806bd27 in ngx_start_worker_processes (cycle=cycle@entry=0x9e30798, n=4, type=type@entry=-3) at src/os/unix/ngx_process_cycle.c:364
#14 0x0806d23b in ngx_master_process_cycle (cycle=cycle@entry=0x9e30798) at src/os/unix/ngx_process_cycle.c:136
#15 0x0804e539 in main (argc=1, argv=0xbf8e2f14) at src/core/nginx.c:407
А вы тестировали модуль для случае, когда количество виртуальных хостов > 4?
У вас в модуле есть баг на эту тему. Когда инициализируется конфигурация main, то создается array на 4 элемента типа pool: ngx_array_init(&config->pools, cf->pool, 4, sizeof(ngx_http_sla_pool_t).
Когда встречается директива sla_pool, вызывается ngx_http_sla_pool(), вконце которой происходит следующее:
shm_zone = ngx_shared_memory_add(cf, &pool->name, size, &ngx_http_sla_module);
shm_zone->data = pool;
shm_zone->init = ngx_http_sla_init_zone;
т.е. адрес очередного пула ngx_http_sla_pool_t добавляется в описатель зоны. НО, как только количество виртуальных серверов становится больше чем было инициализировано в ngx_http_sla_create_main_conf, то создается новый array, а старый уничтожается, при этом все ранее созданные описатели зоны хранят указатели на старые пулы…
и начинает происходить SIGSEGV.
Что касается практического использования данного материала…
Код можно оптимизировать на уровне алгоритма, а можно и на уровне архитектурных особенностей конкретного процессора. Знания принципов работы кэша позволяют оптимальнее размещать данные в памяти.
В качестве примера я написал тестовую программу. Ключевой в этой программе является функция: void xchg (uint8_t slow_factor, uint32_t step). slow_factor — количество сегментов памяти, step — разнос адресов между обрабатываемыми байтами. Увеличивая slow_factor — мы смоделируем ситуацию, когда для обработки одного байта будет считываться новая кэш-линия целиком.
root@proliant:~/cahe# ./cache
xchg() complited in 3 sec, k = 1400000000.
xchg() complited in 3 sec, k = 1400000000.
xchg() complited in 14 sec, k = 1400000000.
xchg() complited in 13 sec, k = 1400000000.
Отсюда видно что при использовании функции xchg() со slow_factor большим, чем 1, производительность сильно проседает, хотя количество итераций постоянно и не зависит от slow_factor!
А все дело в том, что xchg() со slow_factor большим, чем 1, сильно нагружает системную шину, т.к. через каждые 7 итераций вложенного цикла происходит считывание новой кэш-линии, т.к. после первых 7 итераций сэт кэша забивается.
#include <stddef.h>
#include <inttypes.h>
#include <sys/types.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#define WAY_N 8U // number of ways
#define LINE_SIZE 64U // cache line size
#define LINE_N 64U // number of cache line
#define SPARSE WAY_N*LINE_SIZE*LINE_N
#define DENSE LINE_SIZE*LINE_N
#define AREA 29U*WAY_N*LINE_SIZE*LINE_N // allocated memory size
static uint8_t *p, *el, tmp;
void xchg (uint32_t slow_factor, uint32_t step) {
uint32_t i, j, k;
struct timeval start, end, diff;
gettimeofday(&start, NULL);
for (i = 0U, k = 0U, el = p; i < 200000000U/slow_factor; ++i) {
for (j = 0U; j < 7U*slow_factor; ++j, el += step, ++k) {
tmp = *el;
*el = *(el + step);
*(el + step) = tmp;
}
el = p;
}
gettimeofday(&end, NULL);
diff.tv_sec = end.tv_sec - start.tv_sec;
printf (" xchg() complited in %ld sec, k = %u.\n", diff.tv_sec, k);
}
int main(int argc, char const **argv) {
uint32_t i;
p = el = calloc (1, AREA);
for (i = 0U; i < AREA; ++i) {
*el++ = (uint8_t) rand();
}
xchg (1U, SPARSE);
xchg (1U, DENSE);
xchg (4U, SPARSE);
xchg (4U, DENSE);
return 0;
}
Число Pi/4 мы уточняем знак за знаком, это бесконечный итеративный процесс. По мере получения очередного знака, мы получаем конкретное число и вычисляем для него порядковый номер.
Т.е. бесконечную непереодическую дробь — можно рассматривать как несуществующее число, а можно рассматривать, как результат работы некоторого бесконечного алгоритма, который на каждом шаге выдает очередную цифру и в этом смысле порядковый номер можно тоже рассматривать как некое число, являющееся результатом работы бесконечного алгоритма.
Когда мы делаем , то CPU читает кэш-линию (размером 64 байта) из RAM. После чего, при обращении к любому из этих байтов, время чтения будет минимально, т.к. они уже в кэше, что, собственно, и вызвало мой вопрос )) Но на самом деле нас интересуют только те индексы, которые кратны 4096.
мы определяем индекс массива, который читается быстро, но в то же время рядом с ним находятся еще несколько байтов из этой же кэш-линии и которые тоже будут быстро читаться.
Вопрос: как нам понять какой именно из этих индексов — нужное нам значение из закрытой области RAM?
Не совсем согласен, т.к. у любой статьи всегда имеется определенный уровень абстракции, на который она изначально рассчитана.
Про мосты можно тоже по-разному рассказывать, можно «на-пальцах», а можно так глубоко свалиться в детали, что вообще уйти в петлевую квантовую гравитацию. :-)
вот примерная схема того, что такое syn table и accept queue:
Чтобы понимать зачем нужен син-флуд и вчем его смысл, нужно понимать что такое listen socket, что такое syn-received socket, что такое established socket.
Системный вызов listen() инициализирует syn_table, accept_queue, переводит сокет в состояние LISTEN и помещает его в хэш таблицу listening сокетов.
Определяется размер accept_queue: sk_max_ack_backlog = min(somaxconn, backlog).
Определяется размер syn_table:
1. nr_table_entries = max(8, min(sysctl_max_syn_backlog, somaxconn, backlog)).
2. Далее значение nr_table_entries округляется до ближайшей степени двойки вверх (даже если оно уже степень двойки), а значение степени для нового значения сохраняется в max_qlen_log.
nr_table_entries = roundup_pow_of_two(nr_table_entries + 1)
7 -> 8 -> 16
8 -> 16
9 -> 16
15 -> 16
16 -> 32
31 -> 32
32 -> 64
99 -> 128
128 -> 256
511 -> 512
512 -> 1024
Когда приходит новый SYN, то ищется соответствующий listening сокет в хэш таблице listening сокетов, после чего проверяется, что текущий
размер syn_table (qlen) не превышает максимальный размер syn_table: 2 ^^max_qlen_log.
Если превышает, то проверяется включены ли tcp_syncookies, если вЫключены, то SYN дропается.
Если НЕ превышает либо tcp_syncookies включены, то текущий размер sk_ack_backlog сравнивается с sk_max_ack_backlog.
Если sk_ack_backlog > sk_max_ack_backlog то проверяется размер qlen_young.
Если qlen_young > 1, то SYN дропается, если qlen_young <= 1, то создается request_sock.
request_sock считается young, пока не был отправлен повторный SYN/ACK и используется для того, чтобы в случае заполнения
accept_queue была возможность принимать новые SYN.
Когда приходит финальный ACK (если для сокета включена опция TCP_DEFER_ACCEPT, то сокет ожидает ACK с данными), то создается
tcp_sock, адрес на него сохраняется в поле sk структуры request_sock и кастится в struct sock, после чего tcp_sock подвязывается в
хэш таблицу для established сокетов (но не подвязывается в VFS), удаляется из syn table и помещается в accept_queue.
Сокеты, находящиеся в accept_queue ожидают пока приложение выполнит системный вызов accept(). После вызова accept(), request
sock удаляется из accept_queue, создается BSD сокет struct socket, к нему подвязывается данный connected сокет после чего BSD
сокет подвязывается в VFS, а приложению возвращается файловый дескриптор.
Когда включены tcp_syncookies, если syn_table не заполнена полностью, то SYN проходит классический путь по стэку, если заполнена,
то SYN не дропается, а обрабатывается и на него отправляется SYN/ACK содержащий специальным образом сформированный ISN, но при
этом request sock не создается: request sock создается после получения финального ACK и валидации acknowledgement number и
сразу помещается в accept_queue.
Если включена опция TCP_DEFER_ACCEPT, то она работает только для сокетов, проходящих классический путь.
Если syn_table заполняется более чем на половину, количество повторных передач для SYN/ACK уменьшается до 1-3 (точный алгоритм в
см. коде), чтобы сокеты в состоянии SYN_RECV как можно быстрее освобождали syn_table.
______________________
CONCLUSION:
Т.о. до появления син-кук либо при выключенных син-кука смысл син-флуда в том, чтобы постоянно держать syn table заполненной. Что позволит уронить сервер атакой в 1 мбит/с даже при наличии канала 10Г (при не оттюненом сервере и tcp/ip стэке).
После появления син-кук задача син-флуда сделать так, чтобы CPU уходил в 100% при расчете куки, но в этом случае должно быть много пакетов. А если отправлять син с данными, то на выходе будет меньше пакетов. В чем смысл?
2. На сетевом оборудовании Jumbo-frame обычно не превшает 9000 байт.
3. Может я отстал от жизни, но, зачем нужен син-флуд большими пакетами?
В линуксе MSS вычисляет вот такая функция: __tcp_mtu_to_mss().
Ссылка: http://lxr.free-electrons.com/source/net/ipv4/tcp_output.c#L1300
Александр, это ваше личное открытие?
На самом деле от количества вирт. хостов не зависит, зависит от количества созданных пулов.
Вот пример конфига:
http {
sla_pool one;
sla_pool two;
sla_pool three;
sla_pool four;
sla_pool five;
sla_pool six;
server {
listen 192.168.10.10:80 default_server;
server_name "";
location /one {
sla_pass one;
}
location /two {
sla_pass two;
}
location /three {
sla_pass three;
}
location /four {
sla_pass four;
}
location /five {
sla_pass five;
}
location /six {
sla_pass five;
}
location /sla_status {
sla_status;
sla_pass off;
}
}
}
Вот что выдает gdb (если зайти на 192.168.10.10:80/sla_status):
gdb /usr/local/nginx/bin/nginx /usr/local/nginx/logs/coredump/core
Program terminated with signal 11, Segmentation fault.
#0 ngx_shmtx_lock (mtx=0x28) at src/core/ngx_shmtx.c:78
78 if (*mtx->lock == 0 && ngx_atomic_cmp_set(mtx->lock, 0, ngx_pid)) {
(gdb) bt
#0 ngx_shmtx_lock (mtx=0x28) at src/core/ngx_shmtx.c:78
#1 0x080c7fe7 in ngx_http_sla_status_handler (r=0x9e35908) at /home/fervid/distrib/src/modules/sla/ngx_http_sla.c:793
#2 0x0807d2a9 in ngx_http_core_content_phase (r=0x9e35908, ph=0x9e47098) at src/http/ngx_http_core_module.c:1410
#3 0x080784c3 in ngx_http_core_run_phases (r=r@entry=0x9e35908) at src/http/ngx_http_core_module.c:888
#4 0x080785d4 in ngx_http_handler (r=r@entry=0x9e35908) at src/http/ngx_http_core_module.c:871
#5 0x08083780 in ngx_http_process_request (r=r@entry=0x9e35908) at src/http/ngx_http_request.c:1852
#6 0x08083dfb in ngx_http_process_request_headers (rev=rev@entry=0xb26ee070) at src/http/ngx_http_request.c:1283
#7 0x08084331 in ngx_http_process_request_line (rev=rev@entry=0xb26ee070) at src/http/ngx_http_request.c:964
#8 0x08084924 in ngx_http_wait_request_handler (rev=0xb26ee070) at src/http/ngx_http_request.c:486
#9 0x0806571e in ngx_event_process_posted (cycle=cycle@entry=0x9e30798, posted=0x81132cc) at src/event/ngx_event_posted.c:40
#10 0x0806524d in ngx_process_events_and_timers (cycle=cycle@entry=0x9e30798) at src/event/ngx_event.c:275
#11 0x0806c96a in ngx_worker_process_cycle (cycle=cycle@entry=0x9e30798, data=data@entry=0x0) at src/os/unix/ngx_process_cycle.c:816
#12 0x0806b013 in ngx_spawn_process (cycle=cycle@entry=0x9e30798, proc=proc@entry=0x806c88f <ngx_worker_process_cycle>, data=data@entry=0x0, name=name@entry=0x80e502d «worker process», respawn=respawn@entry=-3)
at src/os/unix/ngx_process.c:198
#13 0x0806bd27 in ngx_start_worker_processes (cycle=cycle@entry=0x9e30798, n=4, type=type@entry=-3) at src/os/unix/ngx_process_cycle.c:364
#14 0x0806d23b in ngx_master_process_cycle (cycle=cycle@entry=0x9e30798) at src/os/unix/ngx_process_cycle.c:136
#15 0x0804e539 in main (argc=1, argv=0xbf8e2f14) at src/core/nginx.c:407
А вы тестировали модуль для случае, когда количество виртуальных хостов > 4?
У вас в модуле есть баг на эту тему. Когда инициализируется конфигурация main, то создается array на 4 элемента типа pool: ngx_array_init(&config->pools, cf->pool, 4, sizeof(ngx_http_sla_pool_t).
Когда встречается директива sla_pool, вызывается ngx_http_sla_pool(), вконце которой происходит следующее:
shm_zone = ngx_shared_memory_add(cf, &pool->name, size, &ngx_http_sla_module);
shm_zone->data = pool;
shm_zone->init = ngx_http_sla_init_zone;
т.е. адрес очередного пула ngx_http_sla_pool_t добавляется в описатель зоны. НО, как только количество виртуальных серверов становится больше чем было инициализировано в ngx_http_sla_create_main_conf, то создается новый array, а старый уничтожается, при этом все ранее созданные описатели зоны хранят указатели на старые пулы…
и начинает происходить SIGSEGV.
Код можно оптимизировать на уровне алгоритма, а можно и на уровне архитектурных особенностей конкретного процессора. Знания принципов работы кэша позволяют оптимальнее размещать данные в памяти.
В качестве примера я написал тестовую программу. Ключевой в этой программе является функция: void xchg (uint8_t slow_factor, uint32_t step). slow_factor — количество сегментов памяти, step — разнос адресов между обрабатываемыми байтами. Увеличивая slow_factor — мы смоделируем ситуацию, когда для обработки одного байта будет считываться новая кэш-линия целиком.
Результаты:
root@proliant:~/cahe# gcc cache.c -O3 -o cache
root@proliant:~/cahe# ./cache
xchg() complited in 3 sec, k = 1400000000.
xchg() complited in 3 sec, k = 1400000000.
xchg() complited in 14 sec, k = 1400000000.
xchg() complited in 13 sec, k = 1400000000.
Отсюда видно что при использовании функции xchg() со slow_factor большим, чем 1, производительность сильно проседает, хотя количество итераций постоянно и не зависит от slow_factor!
А все дело в том, что xchg() со slow_factor большим, чем 1, сильно нагружает системную шину, т.к. через каждые 7 итераций вложенного цикла происходит считывание новой кэш-линии, т.к. после первых 7 итераций сэт кэша забивается.