Comments 92
Проверить за одно сравнение, что 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). В яве видимо реализовано вращение
Нет, не вращение. Просто так работает сдвиг. На самом деле так во всех языках, и об этом много кто не знает. Я например, думал это UB в C++ и никогда так не делал. Но оказывается, это инструкция x86 принимает только 5-6 бит для сдвига.
Табличка была
как архитектуры обрабатывают сдвиги влево-вправо на ширину регистра и больше - только Itanium честно себя ведёт и позволяет так занулять регистры.
PS: неужели честный сдвиг слишком дорого реализуется? Вот это вот:
(a << (b & 0b0011'1111L)) * !(b & ~0b0011'1111L)
^^^^^^^^^^^^^^^^^^^^^^Или это как ошибка в BSF/BSR, которые пришлось дополнять инструкциями TZCNT/LZCNT. Только закрепившаяся везде?
Видимо, изначально дизайнеры x86 не думали, что кому-то может понадобиться сдвигать надеясь, что переполнение все занулит. Если кому-то, надо, есть сотня других способов занулить регистр. Поэтому сдивгать нужно только на 31 позицию максимум, а значит можно сэкономить на транзисторах делая для схемы только 5 битов втогого аргумента. Или это с какой-то еще более ранней архитектуры пошло.
Наверное, экономия, которая превратилась в традицию.
Если кому-то, надо, есть сотня других способов занулить регистр.
Если в эту сторону думать (и дополнительно вдохновиться BSF/BSR), то можно даже сделать неопределённым сдвиг на ноль позиций... в книжке про 68k написали: "for a shift of from 1 to 63 bits", но скорее всего ошибка.
Понятно, что честное поведение пригодилось бы для заранее неизвестных сдвигов - для избавления от особых случаев в алгоритмах, для удобного детерминизма в случае ошибок. При делении на ноль странного не происходит, при нулевых сдвигах тоже, про как-не-потерять-информацию-об-ошибке в конце 70-х задумывались достаточно (NaN'ы были в 8087).
Это особенность даже не джавы, а архитектуры x86. Там инструкции сдвига работают именно так. А языки (Java, C) наследуют такое поведение и записывают себе в спецификацию.
Я как-то для удобства написал микробиблиотечку с макросами, которые позволяют делать сдвиги на произвольное количество бит, в том числе допускают отрицательный сдвиг (это значит, что меняется направление сдвига). Наверно стоит откопать этот код и выложить. Тогда их код 1L << token.charAt(i) можно было бы безопасно переписать так: shift_any(<<, 1L, token.charAt(i)).
Кстати, 1L — это они нехорошо написали. Если потом зачем-нибудь понадобится сдвигать вправо, то это будет арифметический сдвиг, а не логический, и потом тоже придется кому-то кровь-мясо-кишки собирать. Надо 1UL.
Опять легаси помешало полёту фантазии :)
Почему легаси? Честный сдвиг на произвольное количество разрядов стоит в аппаратуре дороже, чем этот урезанный.
Хм. А ведь и правда. В моей вселенной говнокода (не не джавового) даже такого понятия нет - сдвинуть влево на неизвестное число бит, явно большее и 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]
эта фраза абсолютно кривая и вводит в заблуждение
Согласен, поправил.
token.charAt(i) имеет размерность char 0-255
token.charAt(i) имеет размерность char ( он же uint8_t )
На дворе не 1970 год, однобайтные кодировки давно уже вышли из моды.
Тип char в Java никогда не был 8-битным. В Java тип char представляет 16-битное беззнаковое. А так как на уровне JVM такого типа нет, то при операциях над типом char как над числом последний расширяется до 32-битного знакового типа.
Учитывая, что Юникод давно уже вышел за пределы BMP, то и использование charAt() вместо codePointAt() может подарить несколько часов увлекательной отладки.
Стало на много понятнее, как будто разные люди писали
пока было только про 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`, была по-ошибке русская `с`. к сожалению, на тот момент конифг не мог валидировать такие опечатки, тк в принципе в конфиг можно было писать произвольные символы и это было допустимо
пришлось провести небольшое расследование (естессно не такое глубокое, как у автора статьи!) и все же найти кривую букву и поправить поведение
Я в своё время долго бился лбом о баг в одном легаси, пока не догадался пробежаться с отладчиком. Оказалось, что в таблице с названиями стран были значения типа POCCИЯ, в которых все буквы, какие только можно было написать латиницей, были написаны латиницей, чего мой код не ожидал.
Хех, подержите мое пиво. Году эдак в 11м появился в нашем, сейчас уже легаси, проекте, баг-коллега по запаре в имени переменной по моему "а" кириллической обьявил. И прикол в том что все работало, билдилось, причем работало сутками и неделями под нагрузкой. Проект на шарпе. И все было ок, пока не начали деплоить новым заказчикам(DB). Что то там пошло не так, чемодан-сво-берлин, в общем собираем уже на целевой машине, а оно не собирается). Вот так вот, у меня (на русской) винде собирается, а там(на немецкой) - нет)). Я помню эту ночь))
Самое неприятное, что IDE иногда это подсвечивает только в коде, а в yaml/json или конфиге легко пропустить
Ох уж эти погони за микрооптимизациями (побитовые сдвиги вместо массива или обычного 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))) { ... }
А я не понял, а русские буквы в урле не могут быть? Т.е. по стандарту не могут, но метод же валидирует корректность, а тут он радостно пропустит их. Или на это у них другой метод есть? Даже если не русские, то какая-нибудь банальная ¼ попавшая по ошибке
сервера с двумя ручками
Для переноски?
Это тест, как распознать «скрипт кидс» у «нормальных пацанов» либо «хендлер» , либо «обработчик»- как писали в советской компьютерной литературе.
«скрипт кидс»
Скрипт кидс тут вообще не при чем, ручки это терминология пошла от яндекс/вк/одноклассники(МЯСО) разработчиков не особо причем привязанная к их возрасту либо скиллам.
Какое-то время назад можно было со 100% гарантией утверждать что если разработчик говорит ручка то он когда-то работал в Яндексе. Сейчас выходцы оттуда размазались и заразили всю сферу.
Один ИИ-код заменили на другой ИИ-код. Хорошо, что заново сгенерили, а не попросили просто исправить граничные случаи)))
Dial M for murder.
Вот поэтому иногда проще написать обычную проверку символов, чем пытаться ускорить её побитовыми операциями
Бойтесь буквы «M». Самый странный баг в моей жизни