Баг в ядре?

Предположу, что раз речь о группах, то их 65536 максимум. Переменная 4-х байтовая, значит переполнения не будет.

Переменная 4-х байтовая

если ты не эмбдеддщик

ОК, лезем в драфт стандарта C http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf Страница 44-45:

Their implementation-defined values shall be equal or greater in magnitude

maximum value for an object of type unsigned int UINT_MAX 65535 // 2^16-1

Так что стандарт допускает двухбайтный unsigned int

ты хочешь сказать 2 байт не хватит?

именно

sizeof(int) == 4 на всех поддерживаемых линуксом архитектурах, насколько я понимаю

А как насчет uclinux?

Это вроде бы уже не форк linux.

А как насчет uclinux?

Он для процов без MMU, а не для 16-и битных.

Понятно, буду знать.

maximum value for an object of type unsigned int UINT_MAX 65535 // 2^16-1

В коде речь идёт не о GID, а о kgid_t, а это 32-битный идентификатор, представляющий собой отображение пользовательских 16-битных идентификаторов в ядерные и который, насколько я вижу по коду, может выходить за пределы 16 бит, но вот насколько далеко может выходить - не совсем ясно.

Ну например uclinux работает на m68k проце, а он I16LP32 т.е. инты у него 16-битные, а указатели и лонги 32-битные

Во-первых, про проблему с переполнением там упоминают в связи с знаковым mid и выходом за границу массива в результате, тут mid беззнаковый и выхода не будет, максимум будет бесконечный цикл в случае right > 2^31 и искомого gid'е, близкого к right.
Во-вторых, NGROUPS_MAX в линуксе установлено в 65536 и подобная ситуация встретиться в нормальной ситуации (без патчинга ядра) не может.

Переменная 4-х байтовая

если ты не эмбдеддщик

Эмбеддед - не обязательно 8-битовое убожество.

Переполнение может быть и с беззнаковым mid, и это тоже будет баг

но именно там «8-битовое убожествоЭ встречается чаще, чем в других местах.

Конечно.

Но лучше скажи, почему ты считаешь, что на проце m68k под управлением Linux sizeof(int) == 2. Вики Debian так не считает.

почему ты считаешь

нет, я не SZT

А, извини. У SZT я бы спрашивать не стал.

4.2

Если group_info->ngroups может быть более, чем MAX_INT/2+1, то при right>MAX_INT/2 будет переполнение независимо от sizeof(int), имхо.

Если число групп точно ограничено 65536, то проблема всплывёт только при sizeof(int)<3.

Предположу, что раз речь о группах, то их 65536 максимум.

Нет, нифига подобного

root@user-MS-7519:~# chown 4294967294:4294967294 test1
root@user-MS-7519:~# ls -la test1
-rw-r--r-- 1 4294967294 4294967294 0 Авг 13 10:45 test1

Нет, нифига подобного

redgremlin выше всё правильно сказал. Указанный код работает не с номером группы, а с индексом массива, размер которого не может превышать 65535.

А например если сделать sysctl kernel.ngroups_max=4294967294 или echo 4294967294 > /proc/sys/kernel/ngroups_max ? Только на моем ядре это не работает. Надо на других дистрах/ядрах проверить. В любом случае это баг т.к. NGROUPS_MAX в будущих ядрах вполне может поменяться, и тогда это все может заглючить

если сделать sysctl kernel.ngroups_max=4294967294

Это значение read only.

В любом случае это баг т.к. NGROUPS_MAX в будущих ядрах вполне может поменяться

Разве что compilation assert вставить (BUILD_BUG_ON). В сам код в это место вставить дополнительный набор бесполезных инструкций вряд ли позволят: если посмотреть историю изменений, то предыдущее исправление в этом месте - это замена типов индексов с int на unsigned int, но не по причине переполнений, а по причине производительности (были приведены бенчмарки, согласно которым вычисление среднего значения беззнаковых величин быстрее вычисления среднего значения знаковых).

В любом случае это баг т.к. NGROUPS_MAX в будущих ядрах вполне может поменяться, и тогда это все может заглючить

Тогда любая операция с типом time_t является багом, ведь каким бы не был размер этого типа, все равно в стодекальйонный год будет переполнение. «Баг» начнёт проявляться только когда число созданных групп перевалит за 2 миллиарда с хвостиком. Это только /etc/group на десятки гигабайт потянет.

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

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

Для 64-битных архитектур вообще никаких дополнительных накладных расходов не будет. Можно тупо сделать unsigned int mid = ((uint64_t)left+(uint64_t)right)/2 и переполнения уже не будет. А если архитектура 32-битная, это делается через mid = left + (right - left) / 2; т.е. всего одна дополнительная операция

Вам мнение ЛОРовских аналитиков важнее мнения разработчиков ядра? Напишите в баг-трекер.

Уже

Можно тупо сделать unsigned int mid = ((uint64_t)left+(uint64_t)right)/2 и переполнения уже не будет.

Можно, только это может замедлить работу для некоторых архитектур.

т.е. всего одна дополнительная операция

всего одна дополнительная бесполезная операция. :) Я за BUILD_BUG_ON, если очень хочется.

Уже

Они на патчи быстрее реагируют, по-моему.

Ну пусть они уже сами решают как это патчить, если им там важна производительность

Тогда любая операция с типом time_t является багом, ведь каким бы не был размер этого типа, все равно в стодекальйонный год будет переполнение.

Ну это не проблема. Можно выбрать настолько большой time_t что тепловая смерть вселенной наступит раньше, чем он переполнися

Кстати, раз уж говорить об оптимизации кода, то там много мест, которые можно переделать. Вот взять например оттуда же

http://lxr.free-electrons.com/source/kernel/groups.c#L104

109         for (stride = 1; stride < gidsetsize; stride = 3 * stride + 1)
110                 ; /* nothing */
111         stride /= 3;

stride(1) = 1;
stride(n) = 3 * stride(n-1) + 1

Решаем через maxima:

(%i1) display2d:false$

(%i2) load(solve_rec)$

(%i3) solve_rec(stride[n]=3*stride[n-1]+1, stride[n], stride[1]=1);

(%o3) stride[n] = 3^n/2-1/2

(%i4) solve ([3^n/2-1/2=x], [n]);

(%o4) [n = log(2*x+1)/log(3)]

Записываем получившиеся формулы через double. Сначала находим n (оно скорее всего получится нецелым) Получаем целую часть часть через http://www.cplusplus.com/reference/cmath/modf/ и считаем ей по формуле 3^n/2-1/2. Думаю что точности double вполне должно хватить. На всякий случай можно сравнить выдаваемые через вычисления по формулам значения с вычислением через цикл на всем интервале допустимых значений.

Таким образом можно сократить много всяких примитивных циклов, но что-то я сомневаюсь что такой патч будет принят разрабами ядра

в ядре floating point избегают использовать

Теперь надо найти такой n для stride(n), чтобы stride(n) = gidsetsize;

Вот этого не понял. Зачем? Просто же считаем 3^gitsetsize/2-1/2.

UPD: А, понял. Да, надо, но так ещё медленнее получается.

Таким образом можно сократить много всяких примитивных циклов

Надо ещё посмотреть на количество итераций в цикле. Для текущего NGROUPS_MAX максимальное число итераций равно 11. Вряд ли вычисления с плавающей точкой по этой формуле будут быстрее 11 операций умножения и 11 инкрементов.

А для такого количества итераций можно ещё и заготовить массив всех промежуточных значений, так что даже умножать не потребуется. Далее в алгоритме происходят постоянные деления полученного значения на 3, их тоже можно все заранее предвычислить. Вот такую оптимизацию если сделаете, то вполне могут и принять.

Просто же считаем 3^gitsetsize/2-1/2

Нет же. Там ищется максимальное число из ряда (3^k-1)/2, не большее gidsetsize/3. https://en.wikipedia.org/wiki/Shellsort
Ты прав в том, что на флоатах будет дольше (те более, что на практике до NGROUPS_MAX никто не добирается и количество итераций в 99.999% будет не больше 3х (у меня ни на одной машине нет не то что 120, но и 100 групп)) и код станет нечитаемый (потребуется, как минимум, развёрнутый комментарий, откуда все эти логарифмы берутся). Ну и про плавающую точку анонимус прав — math.h в ядре нет.

Предположу, что раз речь о группах, то их 65536 максимум.

Нет, нифига подобного
root@user-MS-7519:~# chown 4294967294:4294967294 test1

Ты просто не знаешь, что такое NGROUPS_MAX.

sent it to LKML, please!

Есть вопрос. Подсказать можешь?

Звиняй, хрустальный шар разбил, так что без вопроса затрудняюсь ответить, смогу ли я по нему подсказать.

ахах.... точно.... это сложно будет, без шара то.