Хабр Курсы для бэкендеров
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 74
Закреплённые комментарии
Проверить за одно сравнение, что ASCII-код символа не совпадает с кодами \n, \r или пробела.
Но получилось, что сравнивались только последние 6 бит кода (особенность Джавы). И у букв J, M последние 6 бит совпадают с \n, \r.
прикол в том, что этот код появился не для перформанса, а для безопасности. И сам по себе вызвал падение производительности.
https://github.com/netty/netty/commit/2f2e437f10267277d0369eb1f81be89dd4654168
Отличное исследование-расследование, хорошо, что проблему удалось найти. Глядя на isEncodingSafeStartLineToken()я бы сразу проблему не обнаружил, вроде все красиво делается, и пакетная обработка, и отсутствие лишних if, а использование битовых масок. Трюк когда long chars = ... | ... | ... | ... мне тоже понравился, хотя несколько лишних секунд на подумать "почему это работает" он съедает. Но есть стойкое ощущение, что его написала ИИ, потому что человек, освоивший все остальное, вряд ли бы "забыл", как работает битовый сдвиг. Признаться, это дает какое-то такое ощущение, пугающее, что ли; сколько еще подобных багов, где они еще могут быть...
Причем фикс говорящий за себя. Такое ощущение, что за дело взялся человек, но либо у него совсем не хватало времени, либо квалификации, потому что все красивые идеи изначального подхода упустили, "как будто испугались". Я бы предложил так:
Скрытый текст
private static final long ILLEGAL_REQUEST_LINE_TOKEN_OCTET_MASK =
(1L << '\n') | (1L << '\r') | (1L << ' ');
public static boolean isEncodingSafeStartLineToken(CharSequence token) {
int i = 0;
int lenBytes = token.length();
int lenInts = lenBytes - (lenBytes % 4);
for (; i < lenInts; i += 4) {
char c0 = token.charAt(i);
char c1 = token.charAt(i + 1);
char c2 = token.charAt(i + 2);
char c3 = token.charAt(i + 3);
// All chars >= 64 means the whole group is safe
// Only one switch per 4 bytes in most cases
if ((c0 & c1 & c2 & c3) >= 64) {
continue;
}
// Avoid bitshift overflow. Still one switch per character
if (c0 < 64 && ((1L << c0) & ILLEGAL_REQUEST_LINE_TOKEN_OCTET_MASK) != 0) return false;
if (c1 < 64 && ((1L << c1) & ILLEGAL_REQUEST_LINE_TOKEN_OCTET_MASK) != 0) return false;
if (c2 < 64 && ((1L << c2) & ILLEGAL_REQUEST_LINE_TOKEN_OCTET_MASK) != 0) return false;
if (c3 < 64 && ((1L << c3) & ILLEGAL_REQUEST_LINE_TOKEN_OCTET_MASK) != 0) return false;
}
for (; i < lenBytes; i++) {
char ch = token.charAt(i);
if (ch < 64 && ((1L << ch) & ILLEGAL_REQUEST_LINE_TOKEN_OCTET_MASK) != 0) {
return false;
}
}
return true;
}Но на бенчмарки пока времени нет.
вот таких трюкачей всегда на кодревью заворачивал. 99% что всплывет баг. Он ещё и время на бенчмарки собирается потратить и доказывать что его код на 20% быстрее.
Для 0.5 RPS систем вполне приемлемый подход. А я почему-то всегда оказывался в местах, где 90% работы это и есть написание не наивных решений, тестирования их производительности, и, конечно же, нетривиальных тестов, которые не дают этим 99% багов оказаться в проде. Фигней какой-то в общем. Да, KISS рулит. А если что, просто еще один сервер купим (за счет моей зарплаты в общем-то, вот и вся проблема).
Но это в общем плане. А конкретно про эту функцию, ну хз. У меня вот есть подозрения, что она вообще не нужна, как минимум название у нее странное, и самодостаточно она не выглядит полезной. Просто цикломатическую сложность хотели понизить и сделали первое, что пришло на ум.
Ох уж эти веберы. Главное чтобы код писать было просто, а на скорость без разницы😂
Задолго до веберов было сказано, что premature optimization is the root of all evil. Правильно выше написали про трату времени. Гораздо больше смысла было бы потратить время не на бенчмарки, а на профилирование и выяснение, какую долю роутинг занимает от общего процесса запроса к серверу (подозреваю, что в обычном веб-приложении — ничтожную). Морочиться так имеет смысл, если писать что-то типа nginx.
Главное чтобы код работал корректно, а не как в анекдоте про быстрый счёт в уме
Без тестов - завернуть, а с хорошими тестами можно попробовать. В библиотечном коде такие вещи более оправданы.
if ((c0 & c1 & c2 & c3) >= 64) {
Такое себе. Это сработает, не когда все 4 символа больше 64, а когда у них у всех есть какой-то общий старший бит. Код все еще работет корректно, но не соответствует комментарию.
Лично я пару раз паподался на эту особенность. Залолго еще до пришестсия ИИ.
Причем интересно, что это фишка железа (на ASM x86 она же есть), а не java. И потому встречается во множестве языков )
Больше пугает то что в таком масштабном проекте как Netty эта функция не была покрыта юнит-тестами, прогоняющими весь спектр ASCII-символов, а не то что разработчик ошибся в сдвиге
Какой-то бред в оригинальном коде. Чего пытались вообще добиться выполняя " 1L << token.charAt(i)" ?
Надо спросить у LLM, которая это писала.
Проверить за одно сравнение, что ASCII-код символа не совпадает с кодами \n, \r или пробела.
Но получилось, что сравнивались только последние 6 бит кода (особенность Джавы). И у букв J, M последние 6 бит совпадают с \n, \r.
Но получилось, что сравнивались только последние 6 бит
это абсолютно не верное утверждение. Сравниваются именно 63 бита после сдвига.
Строго говоря особенность джавы в том что для int32 :
1 << n == 1 << ( n & 31 )
а для int64 ( он же long ) будет :
1L << n == 1L << ( n & 63 )
это судя по всему было сделано чтобы UB избежать ( как в C++ ) так как размерность long 64 бита и 1 << 64 это за границами long
поэтому корректное утверждение звучать должно так
для
intберутся только 5 младших бит количества сдвигадля
longберутся только 6 младших бит количества сдвига
token.charAt(i) имеет размерность char 0-255 и выходит за границы допустимого количества сдвига после 63 это ? (question mark).
поэтому все что после ? - это ошибочный результат
В утверждении неверно только слово "последние".
Не последние, а младшие.
В остальном всё верно, а вы упустили исходную задачу, состоявшую в сравнении символов.
Так-то char в Java не byte, размерность у него 16 бит.
Т.е. чел писавший этот код попутал сдвиг с вращением (shr vs ror). В яве видимо реализовано вращение
Это особенность даже не джавы, а архитектуры x86. Там инструкции сдвига работают именно так. А языки (Java, C) наследуют такое поведение и записывают себе в спецификацию.
Я как-то для удобства написал микробиблиотечку с макросами, которые позволяют делать сдвиги на произвольное количество бит, в том числе допускают отрицательный сдвиг (это значит, что меняется направление сдвига). Наверно стоит откопать этот код и выложить. Тогда их код 1L << token.charAt(i) можно было бы безопасно переписать так: shift_any(<<, 1L, token.charAt(i)).
Хм. А ведь и правда. В моей вселенной говнокода (не не джавового) даже такого понятия нет - сдвинуть влево на неизвестное число бит, явно большее и 16 и 32...
Я угадаю этот символ за 8 сравнений!
А я за 7!
Ни разу не видел джаву, но полагаю что это нужно для того чтобы искать/сравнивать инты а не стринги. Это дешевле.
Вот если бы кто бенчмарки сделал... на isEncodingSafeStartLineToken до и после фикса.
Кто-то ведь портировал сишный код ради производительности. Жаль только, что с косячком.
Это даже не сишный код; в С сдвиг 64-битного числа на 64 или более битов — это undefined behavior со всеми вытекающими из этого последствиями. А вот зачем особенности реализации инструкций сдвига на x86_64 занесли прямо в спецификацию JVM — вопрос интересный.
всё-таки unspecified behaviour, а не undefined
Не, N3220: Bitwise shift operators ... If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.
Clang его использует: https://godbolt.org/z/ndK8q83qn
В C# тоже специфицировано такое же поведение, как в Java
Меня больше всего удивляет, что это дожило до релиза и не всплыло в тестах. Хотя, если у тебя нет роутов с J/M, ты это никогда и не поймаешь
Вообще, учитывая реализацию функции, можно было написать unit-test — пробежаться по алфавиту и проверить.
Зато теперь у них в CI/CD пайплайне появится тест, который перебирает все буквы английского алфавита. Памятник этому багу будет жить в кодовой базе вечно)
Посмотрел на своём проекте: если бы я использовал эту библиотеку, то баг бы затронул лишь 3% эндпойнтов. А буквы "j", кажется, вообще нет. Неожиданно.
Парень у карты с безумным взглядом джпг
...4.1.130.Final
Обычно после такого бывает 4.1.130.Final1, 4.1.130.Final2... 4.1.130.FinalLast итд.
зы. Вот скажите на милость, если я вставляю текст, как неформатированный текст, почему вставляется ссылка?
У меня тоже ссылка сломаная была. Поправил. Я статьи в markdown пишу, сюда вставляю. Баг на habr.
Мне кажется, это браузер должен очищать формат при вставке. Меню-то его. Хотя..
4.1.130.Final
Скопипастил из блокнота, там-то точно plain text )) А вставилась как ссылка.
А если руками набрать, то нет.
В данном случае .final - это домен верхнего уровня (не очень понял, действующий ли, но вполне валидный, браузерами распознается) и редактор воспринимает это как ссылку. Ну а отформатировать plain text во что угодно WYSIWYG редактор способен и самостоятельно, форматирование из буфера тут ни при чем.
То есть, все-таки не баг, а фича)
БУКВУ " " АСТРОИЛ, Е ЧАЙ ИК
Тут не бойтесь буквы "М", а бойтесь извращенцев, которые простое сравнение превращают в неочевидный код.
В метро 2033 в библиотеке имени Ленина обитали монстры. Их называли библиотекарями.
Писатели библиотек для программ не отстают.
Вот так и получается
false, из-за того, что разработчики не учли, что сдвиг на Long учитывает только 6 битов.
эта фраза абсолютно кривая и вводит в заблуждение не знакомых с джавой. Сдвиг на long сдвигает на 63 бита не более. И при сравнении учитываются все 63 бита результата.
по факту первичный код был эквиваленте этой записи:
long ch = 1L << ( token.charAt(i) & 63 );во избежание UB ( привет С++ )
Но при этом token.charAt(i) имеет размерность char ( он же uint8_t ) и естественно может быть больше чем 63. так как его диапазон [ 0x00, 0xFF]
Стало на много понятнее, как будто разные люди писали
пока было только про M было загадочно. но как только добавилась J
\r \n да это же CR LF они же Ctrl-M Ctrl-J
а ctrl это и есть маскировка соответствующего бита в кодировке ascii
Написать функцию для проверки валидности символов и не проверить её даже до середины алфавита - это уровень продакшн!!!
Написать извращенную функцию проверки.
Открываем классиков «язык программирования С» и пытаемся найти там подобный изврат - его там нет. Потому что не надо.
Открываем классиков «язык программирования С» и пытаемся найти там подобный изврат - его там нет. Потому что не надо.
Из личного - иногда все же стоит приводить примеры как не стоит делать и почему это так.
его там нет. Потому что не надо.
Его там нет, потому что книжка не про оптимизации. Ручную оптимизацию из поста сейчас, например, LLVM делает, судя по Clang. Он первое преобразует во второе:
switch(c) {
case '\n':
case '\r':
case ' ':
return true;
default:
return false;
}
const uint64_t ref =
(1L << '\n') | (1L << '\r') | (1L << ' ');
return (c <= ' ') & (ref >> c);https://godbolt.org/z/c45z7j9rY
Дальше можно SIMD-в-регистре... только не как там на godbolt с векторами 3x9бит, а как ниже, где сравнивается по 8 символов строки с векторами типа broadcast('\n'), ...
https://news.ycombinator.com/item?id=35052423
Это один из примеров, когда мистика оказывается совсем не мистикой, а вполне очевидной битовой багой
Ловил подобные баги в JS (там аргумент метода просачивался как индекс в массив при push, вида (array.push(some.func(1,2,3,4,5)))) и в 1с и при формировании xlsx и в php и это только что сразу на ум пришло. Причем первое самое жесткое, я тогда помню чуть головой не двинулся, потому что такого просто быть не может.
прикол в том, что этот код появился не для перформанса, а для безопасности. И сам по себе вызвал падение производительности.
https://github.com/netty/netty/commit/2f2e437f10267277d0369eb1f81be89dd4654168
коммент тестера
Уверен, что с прекрасной буквой `c` то же у всех были приколы, но скорее всего это быстро отлавливалось самой IDE
у меня был случай, когда в одном из конифгов вместо латинской `c`, была по-ошибке русская `с`. к сожалению, на тот момент конифг не мог валидировать такие опечатки, тк в принципе в конфиг можно было писать произвольные символы и это было допустимо
пришлось провести небольшое расследование (естессно не такое глубокое, как у автора статьи!) и все же найти кривую букву и поправить поведение
Ох уж эти погони за микрооптимизациями (побитовые сдвиги вместо массива или обычного switch), которые приводят к багам, которые валят релизы. Разрабы Netty сэкономили пару наносекунд на парсинге URI, а бизнес потерял часы работы целой команды на дебаг)
Они не сэкономили. Та реализация, что в итоге у них есть, быстрее раза в 3 (коллега лениво погонял, без jmh).
Я закрепил комментарий, изначально они это писали не ради оптимизаций: https://habr.com/ru/articles/1006164/comments/#comment_29617370
Мне кажется, что в таких крупных библиотеках это оправдано: безусловно в моменте бизнес потерял денег на этом релизе, но зато сколько ресурсов экономит каждая такая оптимизация всему человечеству (и в плане электроэнергии, и в плане компонент для железа, а это в перспективе и бизнесу издержки сокращает). Лично я сам всегда стараюсь при отправке PR в реально крупную библиотеку заморочиться с оптимизацией так, чтобы в большинстве случае выиграть даже несколько тактов процессора,- уже начиная с сотен тысяч использований это делает наш мир чуточку лучше во многих аспектах.
Совсем другое дело коммерческие внутренние проекты компаний: если вы пишете код, который будет использоваться только у вас внутри компании или на малом числе экземпляров, то простота и читаемость намного важнее производительности (в противном случае это зачастую экономия на спичках).
Более традиционно было бы сделать массив (без учёта производительности и памяти), и проверять в нём:
static boolean illegalChars[] = new boolean[65536];
static {
illegalChars['\n']=true; illegalChars['\r']=true; illegalChars[' ']=true;
}
...
if (illegalChars[token.charAt(i)]) { ... }
в таком случае по крайней мере код не прошёл бы тесты с ArrayIndexOutOfBoundsException. Но нет, биты упаковываем в long и не проверяем на выход за его пределы. Т.е. ломаем защиту, из-за которой java и задумывалась.
Может, BigInteger помогло бы?... Хотя BitSet здесь подходит более прямо:
static BitSet illegalChars[] = new BitSet();
static {
illegalChars.set('\n'); illegalChars.set('\r'); illegalChars.set(' ');
}
...
if (illegalChars.get(token.charAt(i))) { ... }
А я не понял, а русские буквы в урле не могут быть? Т.е. по стандарту не могут, но метод же валидирует корректность, а тут он радостно пропустит их. Или на это у них другой метод есть? Даже если не русские, то какая-нибудь банальная ¼ попавшая по ошибке
сервера с двумя ручками
Для переноски?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Бойтесь буквы «M». Самый странный баг в моей жизни