ipt-ratelimit
ipt-ratelimit copied to clipboard
aabc
alexk99 patches
const u32 tok = delta_ms * (car->cir / (BITS_PER_BYTE * MSEC_PER_SEC));
Раccчет tok не зависит от переменных, изменяемых внутри критической секции (cs). Он зависит от delte_ms, которая рассчитывается вне cs и от cir - фактически константа. Если в рассчет tok подставить формул delta_ms, пыполнить сокращения, то останется (now - car->last) * (car->cir / (HZ * BITS_PER_BYTE))
Можно выссчитывать вот эту часть заранее, избавившись от лишнего деления (он ведь дорогие, вроде дороже умножения).
car->cir_hz = (car->cir / (HZ * BITS_PER_BYTE))
В итоге получим const u32 tok = (now - car->last) * car->cir_hz;
Конечно, добавится умножение в выводе статистике, она же должна много реже выводиться.
критическую секцию можно еще упростить, вынести статистику во вне и переведя ее на atomic операции. Правда в случае включенного RATE_ESTIMATOR укоратить cs вроде не получается, но вот я бы у себя его выключил. Это ведь тоже только статистика, правильно?
переменная struct ratelimit_stat.first нигде не используется. просто удалил.
Спасибо! Выгладит всё корректно. Небольшие комментарии:
cir_hz назван не правильно, так как переменная не имеет отношения к Hz, там вместо bits/s становится bits/jiffies/8. Может лучше оставить старое название.
Не красиво выглядят "игры" с #ifndef RATE_ESTIMATOR #ifdef RATE_ESTIMATOR. Наверное, лучше сделать так:
#ifdef RATE_ESTIMATOR
if (!match)
rate_estimator(&ent->stat, now / RATEST_JIFFIES, len);
#endif
spin_unlock(&ent->lock_bh);
if (match) {
atomic64_add(len, &ent->stat.red_bytes);
atomic_inc(&ent->stat.red_pkt);
} else {
atomic64_add(len, &ent->stat.green_bytes);
atomic_inc(&ent->stat.green_pkt);
}
Надеюсь вы понимаете, что выигрыш по скорости на современных процах будет минимальный.
Можно оставить старое, не принципиально. C rate-estimator получилось отлично, я просто не смотрел, что он делает. Не думал двигать его. Если выигрышь есть, а его цена час времени упрощения кода, то почему нет.
код стал попроще и я разглядел в нем еще идею для проверки. первые тесты вроде проходят. сейчас сделаю набор тестов c iperf'ом, чтобы поточнее. Сразу понимаю вопрос а нафига? никто, вроде, и так не замечает влияние модуля в линуксе. Мне хочется получить реально быструю процедуру прохождения пакетами ведра, чтобы многопоточный код, в моем случае dpdk, где pps будет высоким и воркеры будут сильно конкурировать за доступ к ведру, не стал узким местом.
У вас патчи меняющие смысл кода. Например, не будет ли вредной race condition в последнем случае (e2f5d7f9bcd790bfb41262a962c67932f8d15c41)? Вероятно, надо обосновать в комментах или дескрипшене патча почему это не критично. Иначе, код выглядит на первый взгляд как ошибочный и через время у людей может возникать желание его исправлять.
А на второй взгляд, car->last читается до spin_lock, разве это не ошибка? Пакет учитывается в tc, а затем проверяется без лока, когда на него уже мог повлиять другой пакет - следовательно, наш пакет может отброситься из-за того, что другой пакет превысил ведерко.
(Да и код с локом нельзя назвать lockless.)
Например, не будет ли вредной race condition в последнем случае
race какой переменной?
А на второй взгляд, car->last читается до spin_lock, разве это не ошибка?
Она читается до лока в оригинальном коде.
Пакет учитывается в tc, а затем проверяется без лока, когда на него уже мог повлиять другой пакет - следовательно, наш пакет может отброситься из-за того, что другой пакет превысил >ведерко.
Да, тут у меня ошибка в случае racе переменной tc. Точно, могут отброситься оба пакета, хотя один из них еще мог бы пройти.
(Да и код с локом нельзя назвать lockless.)
В общем случае да. Но если большинству транзакций не нужны локи, то эти случаи и будут lockless. Идея в том, в этом алгоритме можно попробовать не на каждый пакет делать пополнения ведра, в dpdk библиотеке предлагают делать это по истечении заданного время, например. Вторая идея в том, что большая часть пакетов не должна отбрасываться как только скорость стабилизировалась, поэтом хочется для них сделать прохождение без локов, если это возможно, конечно.
Я еще подумаю на вторым патчем. Для этого и сделал пометку, debug. Идея была начать обсуждение.
А первый патч не меняет логику совсем. Еще раз его проглядел, результат должен быть один в один с оригинальным кодом.
Если не на каждом делать пополнение ведерка или наоборот 1 пакет может влиять на другие (из-за race condition), то это уже другой алгоритм. А люди ожидают от ipt-ratelimit алгоритм Cisco RED-like.
Первый патч меняет логику, но не ухудшает, так что ок.
Я абсолютно согласен, что алгоритм не должен меняться. Для второго патча еще есть идеи. А в чем изменение логики работы алгоритма у первого патча?
23 декабря 2016 г., 16:10 пользователь ABC [email protected] написал:
Если не на каждом делать пополнение ведерка или наоборот 1 пакет может влиять на другие (из-за race condition), то это уже другой алгоритм. А люди ожидают от ipt-ratelimit алгоритм Cisco RED-like.
Первый патч меняет логику, но не ухудшает, так что ок.
— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/aabc/ipt-ratelimit/pull/9#issuecomment-268987707, or mute the thread https://github.com/notifications/unsubscribe-auth/APS272IwwNqmBTw35nUO93QyYtr0upBsks5rK8hKgaJpZM4LUO6I .
--
Kiselev Alexander
Вода вытекала каждую миллисекунду, а стала каждый jiffy. Это могло повлиять на вид пропускаемого трафика.
А на второй взгляд, car->last читается до spin_lock, разве это не ошибка?
Она читается до лока в оригинальном коде.
(Только сейчас заметил этот комментарий.) Да, надо проанализировать это.
Про мсек и токены. Это некорректное утвержение.
Давайте смотреть.
было
const unsigned long delta_ms = (now - car->last) * (MSEC_PER_SEC / HZ); if (delta_ms) { const u32 tok = delta_ms * (car->cir / (BITS_PER_BYTE * MSEC_PER_SEC)); car->tc -= min(tok, car->tc); стало
const u32 tok = (now - car->last) * car->cir; if (tok) { car->tc -= min(tok, car->tc);
- конечный рассчет значения tok в обоих случаях идентичный, в это можно убедиться, просто развернув вычисления:
было
tok = delta_ms * (car->cir / (BITS_PER_BYTE * MSEC_PER_SEC)) = (now - car->last) * (MSEC_PER_SEC / HZ) * (car->cir / (BITS_PER_BYTE * MSEC_PER_SEC)) = (now - car->last) * cir / HZ / BITS_PER_BYTE;
стало const u32 tok = (now - car->last) * car->cir = (now - car->last) * val / (HZ * BITS_PER_BYTE) = = (now - car->last) * val / HZ / BITS_PER_BYTE; здесь надо учесть, что val и это есть сir из первого кода
т.е. рассчета tok совершенно идентичный 2) Если следовать утверждению, что второй вариант меняет алогоритм, то остается проанализировать условия if (delta_ms) и if (tok). т.е. чтобы алгоритм был разным, надо чтобы были случи когда в первом варианте условие выполняется, а во втором варианте кода - нет. Я таких случаев не вижу. В формулах второй множитель в обоих случаях всегда ненулевой, а первой в обоих формулах идентичный.
Поэтому вода и токены здесь суть одно и тоже, в итогде вычитаются токены. И срабатывают эти вычитания совершенно идентично.
Что я упустил? P.S. Бага, из последнего замечения про быстрее утекает, это возможно это не отменяет. Но тут я подумаю.
2016-12-23 16:48 GMT+03:00 ABC [email protected]:
Да, надо проанализировать это.
Баг. Токены могут вытекать быстрее чем нужно.
— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/aabc/ipt-ratelimit/pull/9#issuecomment-268992157, or mute the thread https://github.com/notifications/unsubscribe-auth/APS274-8HAZwdhqziYrb_fHHmHSoPwoAks5rK9EggaJpZM4LUO6I .
--
Kiselev Alexander
Да, надо проанализировать это.
я тоже к чужому коду отношусь порой критичнее, чем к своему. Т.е. так как чтение last показалось в моем коде, то сразу нашелся повод подумать сильнее. Ну это нормально ))
да, last чтение должно быть внутри cs, иначе поток прочитает его, зависнет в входе в cs, другой обновит last и вычтет токены, а затем первый вычтет теже токены еще раз, т.к. время старое
полностью lockless не выйдет, т.к. в случае переполнения корзины никуда не деться, надо добавлять в корзину накопившиеся токены и одновременно обновлять last time. Для двух операций, нужен dcas.
Если я ничего не упустил в своем последнем патче, должно быть уже хорошо. Думаю о том, как сделать тесты. Т.к. на живой сети совершенно не понятно сколько там параллельных воркеров linux запускает для двух iperf'ов на два разные dst ip. Хочу сделать синтетический, с 6 настоящими тредами. И замерить по времени разные варианты оригинальный и последний. Может вообще, оригинальный ничуть не медленнее.
Сделал тесты реализации последнего патча, назовем ее fast/slow (FS) версией.
Делал два теста: один на корректносить, второй на производительность.
Тест на корректность проверял, что решения для тестового набора пакетов принимаются одинаково исходной реализацией и FS версией. Тут все ок. Алгоритмы принимают решения одинаково.
С производительностью все совсем не очевидно. RW блокировки, точнее сказать Write блокировки оказались намного медленнее, чем я ожидал. pthread реализация этих блокировок вообще очень тормозная, FS версия работала в !3 раза медленней оригинальной. Переписал тест под dpdk там своя реализация и для спинлоков и для rw блокировок. FS стал работать намного быстрее, но все равно медленнее, чем оригинальная. Тут я понял, что мой синтический тест, в отличие от реального iperf, не имеет никакой обратной связи с потерями пакетов, и поток пакетов просто постоянно попадает в Slow path. Увеличил cir примерно до той скорости с которой сыпятся тестовые пакеты и тогда fs версия стала работать быстрее на 10-20% чем оригинальная.
Вывод, все очень неоднозначно и зависит от характера трафика, если в реальном трафике доля rejected пакетов небольшая, в районе 5 процентов, то будет профит, если же трафик будет иметь лавинный характер, то в итоге, такой подход будет медленней.
Это тест для 4 ядер, интересно, что будет с ростом числа ядер. Т.е. 4 потока трафика проходило через корзину.
процента red от общего числа пакетов -- profit 2%-6% -- profit 20% 14% -- profit 4%-10% 21% -- profit 5% 23% -- profit -3% -- 5% 33% -- profit -2% 47% -- profit -7% 59% -- profit -28%
Есть разброс в результатах, по-хорошему, его бы автоматизировать, сделать сотни прогонов и построить нормальную табличку.
Если интересны все эти размышления, то поделитесь пожалуйста статистикой, какие у реальных пользователей green/red счетчики.
RW блокировки, точнее сказать Write блокировки оказались намного медленнее, чем я ожидал.
Да, линуксе rwlocks очень медленные поэтому их не рекомендуют использовать. (Навскидку нагуглилось https://lwn.net/Articles/364583/) Про DPDK не знаю. Поэтому никакой реализацией с rwlocks не ускорить то что уже есть.
в хороших реализациях r-блокировки реализованы как lockless в отсутствии w блокировок. в dpdk, похоже, с ними все хорошо. но 20 процентов в лучших случаях - конечно маловато. я надеялся будет лучше. но все равно интересный опыт. заодно баг нашли в вашей реализации.
так что насчет статистики? не сложно сделать выборку по десятку другому пользователей на предмет red счетчиков? Попутно, а в чем смысл дополнительной логики с extended сir по сравнению с классическим tbf? пользователь может понять разницу? можно просто линк на какую-нибудь публикацию, если такие есть. Спасибо.
Мне не отчитываются по статистике. Но могу глянуть по одному юзеру позже.
extended сir это RED-like фишка циски.
- Про обычный RED: https://en.wikipedia.org/wiki/Random_early_detection
- Про что циско наворотила: http://www.cisco.com/c/en/us/td/docs/ios/12_2/qos/configuration/guide/fqos_c/qcfpolsh.html
Вам её не обязательно реализовывать, есть еще стандартные алгоритмы (RFC2697, RFC2698). https://www.freebsd.org/cgi/man.cgi?query=ng_car&apropos=0&sektion=4&manpath=FreeBSD+11-current&arch=default&format=html (Я смотрю там появился "Traffic shaping with RED", раньше этого не было.)
Мне не отчитываются по статистике. Но могу глянуть по одному юзеру позже.
под пользователями я имел ввиду не пользователей модуля, а пользователей-абонентов сети, предполагая, что у вас есть доступ к своей сети.
Вам её не обязательно реализовывать, есть еще стандартные алгоритмы (RFC2697, RFC2698).
они сложнее, цисковский как раз золотая середина.
ответ на свой вопрос я нашел в описании red, вроде не новый алгоритм, но только вот сейчас прочитал про реальные ситуации, где он помогает: https://en.wikipedia.org/wiki/TCP_global_synchronization
под пользователями я имел ввиду не пользователей модуля, а пользователей-абонентов сети, предполагая, что у вас есть доступ к своей сети.
Статистика у пользователей модуля, а не пользователей сети. Или я не понял что вам нужно.
именно ее, red и green счетчики пакетов. я имел ввиду, что было бы достаточно десяток-два таких счетчиков или их можно разом все вывести одной командой?
26 декабря 2016 г., 1:02 пользователь ABC [email protected] написал:
под пользователями я имел ввиду не пользователей модуля, а пользователей-абонентов сети, предполагая, что у вас есть доступ к своей сети.
Статистика у пользователей модуля, а не пользователей сети. Или я не понял что вам нужно.
— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/aabc/ipt-ratelimit/pull/9#issuecomment-269139034, or mute the thread https://github.com/notifications/unsubscribe-auth/APS279C_74OXqqWAzygmBoWezK2L9E5Mks5rLufkgaJpZM4LUO6I .
--
Kiselev Alexander
Я закоммитил ваш первый патч как b6b9a8a0195f094f5e4d6947e22c0b672ad0f1f7, и race-condition багфикс 579a8011e6f5b175e3184c76eddf616bee70201a.
(Если исключить пока из рассмотрения вычисление extended burst.)
полностью lockless не выйдет, т.к. в случае переполнения корзины никуда не деться, надо добавлять в корзину накопившиеся токены и одновременно обновлять last time. Для двух операций, нужен dcas.
Как вам такой вариант: Нужен cas, чтоб обновить last, после этого (А) этот тред знает пройденное время, может правильно рассчитать кол-во токенов, с помощью cas добавляет (отнимает) токены в ведро, и затем (Б) atomic add packet-len к ведерку. Появляется не детерминированность за-за race (в точках А и Б), но они не будут приводить к значительным ошибкам и в сумме все вычисления и полисирование должны быть "почти" корректны (средний rate не будет превышать установленные значения).
Эта не детерминированность может быть даже полезна как аналог RED.
Проще, конечно, на код смотреть. Пускай даже на псевдо код. Это размышления о простом tbf без extended cir?
Идея с CAS обновлением last мне очень нравится, тут никаких неточностей не будет. Каждый поток рассчитает свою долю пройденного корзиной времени, сумма этих значений должна быть в точности ровна действительно прошедшему времени с начала работы корзины - это будет гарантировать cas, неточности и race будут исключены. Здесь cas как раз отлично вписывается, понятно, что делать в его цикле. Понятна гонка, которую он исключает -- это гонка за время, так чтобы не посчитать некоторые его отрезки дважды.
А вот второй cas зачем? что будет перерассчитываться в его цикле в случае если cas видит конфликт, гонку чего он будет предотвращать? В этой точке пройденный отрезок времени, который еще никем не учтен, мы уже знаем, он уже не изменится никогда. Т.е. нам надо просто добавить токены в корзину, значение токенов зависит только от времени, т.е. уже тоже константа, новый цикл cas должен дать тотже рассчет. Тут просто нужно атомарное добавление, которое можно объединить с pkt_len.
В итоге тут даже неточностей не будет, но и RED не будет. Его просто так не получить за счет ошибок.
Хорошее предложение. Может сюда и extended burst дальше прикрутить получится.
продолжение, похоже pkt_len нельзя сюда замешивать с добавлением токенов в корзину. пополнение токенов-времени это безусловная операция. А вот вычитание pkt_len должно быть с помощью второго cas, по аналогии c моим последним патчем. Здесь нам надо понять хватало у нас токенов или нет, здесь должно быть условие, значит cas.
надо написать код, чтобы дальше говорить, а то запутаемся.
я все время путаю, что в текущем коде обратная логика, refill корзины - это вычитание, pkt_len - это добавление. В пред. комментарии у меня наоборот.
Второй cas нужен так как от tc надо отнимать до 0, но не больше (наполнять ведерко до максимума, но не больше). Поэтому просто atomic вычитание сделать нельзя.