Posix-style regeх now in kernel

Мне лично кажется, что такое надо апстримить. Добавить патчем сборку через Kbuild и ifdef’ами (или более утончёнными костылями) обеспечить сборку в ядерном варианте без поломки юзерспейсного. Иначе потом окажется, что в апстриме нашли какие-то баги, уязвимости и т.п., а форки давно разошлись. Ну и больше народу узнает о такой опции.

Надо. Ну там всех переделок-то — это изолировать userspace #include через #ifdef__KERNEL__ ну и пару макросов заменить, потому как в ядре такое же имя встречается. Ну и malloc -> kalloc и все такое. Отладится — солью, ели автор буде не против.

Кстати, для справки. Есть такой язык программирования Lua, так вот у них в основной реализации есть своя миниатюрная библиотека регэкспов. Код там максимально портабельный, и когда я последний раз видел он был на C89. Разница в том, что их регулярки ближе к perl-style, к которому все привыкли, чем posix’овые. Я лично последними вообще ни разу в жизни не пользовался (но в ядре, понятное дело, не до жиру).

Я смотрел на pcre первым делом, она сильно большая. По сравнению с TRE, там кода в разы больше. Типа поддержка EBCDIC, UTF во всех вариантах.... В общем, страшно мне стало такое в ядро тащить :) Но на Lua посмотрю, да. Я знаю, что это такое. Что-то вот не догадался туда глянуть.

Позиксными регексами я пользовался в тех случаях, когда у моих проектов были ограничения на использование внешних библиотек. А это типа «искаропки», ну и ладно.

нет поддержки «широких символов» и прочего юникода.

У Белларда в quickjs есть. Но спецификация регэкспов – Javascript ES2023, конечно.

https://github.com/kokke/tiny-regex-c

Всё не буду цитировать. :)

Supports a subset of the syntax and semantics of the Python standard library implementation (the re-module).

No use of dynamic memory allocation (i.e. no calls to malloc / free).

To avoid call-stack exhaustion, iterative searching is preferred over recursive by default (can be changed with a pre-processor flag).

В TRE поддержка широких символов тоже есть. И под виндой она тоже работает. Я обрезал поддержку wchar_t при компиляции.

https://github.com/kokke/tiny-regex-c

Меня настораживает его TODO list. :)

Самая малость осталась до чтения почты.

А в реальном сценарии использования регулярные выражения неизвестны в compile time? Потому что если известны, то всю эту конструкцию можно (и нужно) заменить кодогенератором, re2c например.

настораживает его TODO list.

Тут TODO нет :) https://github.com/tylov/regexp9.

Regular expressions based on Plan9 code.
Compiles with C99, C++.
Reduced total source code size from about 1600 to 1200 lines.

Реальный сценарий похож на аппрамор — есть куча правил типа путь - правило действия с ним. Аппармор только ограничивает, а мне еще с этим путем много чего сделать надо, включая послать размер и хеш нового содержимого файла, буде его кто-то из юзерспейса изменил.

Представь себе смесь аппармора и коммерческого монитора от tripware. Правила формируются в юзерспейсе и могут периодически меняться централизовано. Соответственно, их надо перегружать в ядро в произвольный момент времени. Сравнивать список правил с целевым путем долго и утомительно (длина пути помножить на сумму длин правил). Так вот я хочу, что бы они до регекс-автомата компилировались в юзерспейсе и в ядро грузился автомат разбора. Так делает аппармор и так делает selinux.

Статические генераторы регексов типа re2c, ragel, или lex не годятся. Можно, конечно, задействовать компилятор от bpf и грузить bpf-апплеты, но, боюсь, возни там будет больше. Или налетим на какие-то ограничения bpf-песочницы.

Я сделал так. Ну сделай то же самое и сравним. Я ж не против.

Но на Lua посмотрю, да.

Я вспомнил про Lunatik и их форк https://github.com/luainkernel/lua.

Почему «осталось»? Уже! Иногда даже приходится авиасообщение с фондовой биржей останвливать.

У меня реально мало опыта взаимодействия с сообществом. Конечно надо апстримить, но надо бы отладить получше, потом налечу на грабли, так стыда ж не оберешься.

Да чего тут стыдиться, лучше сразу показать и предупредить, что это прототип. Это же маленький проект, а не LKML, где твою поделку увидят тысячи людей, включая Линуса, который может и обматерить :)

Тоже нефигово! :)

Да и ладно, если пошлет — считай орден :)

Нельзя ли нетривальную логику отдать в юзерспейс через нетлинк и тп? И не пихать жит-компилятор в ринг0?

Тогда надо еще и сборку под autoconf затаскивать. Затащу — тогда можно сливать. Будет красиво, хош библиотеку, хош — ядерный модуль.

Тогда надо еще и сборку под autoconf затаскивать.

Мне кажется, что не надо, модули ядра автотулзами обычно не собирают. А вообще, это именно тот случай, когда лучше сначала спросить, а потом делать.

Долго и плохо. Отдавать что-то из сисколла в юзерспейс и ждать ответа оракула оттуда — это задерживать сисколл на неопределенное время. Комилятор регекса — это не jit, там на выходе таблицы переходов по символам. И можно ли регекс так написать, что бы конечный автомат сделал что-то не то? Это надо думать.

Нельзя ли нетривальную логику отдать в юзерспейс через нетлинк и тп? И не пихать жит-компилятор в ринг0?

Линус бы такое одобрил. Но реализация системы в целом станет сложнее.

Ну, как бы, у configure одна опция — --with-kernel. Там есть засада. Если сборщик библиотеки захочет собрать все и сразу, то из одного дерева исходников объектники под ядро все равно перекомпилировать придется.

Отдавать что-то из сисколла в юзерспейс и ждать ответа оракула оттуда — это задерживать сисколл на неопределенное время.

Я думаю, что имелось в виду совсем другое. Когда правила меняются, то парсить их в юзерспейсе и загружать в каком-то виде через AF_NETLINK. А при выполнении сисколлов уже использовать загруженную таблицу. Другой вопрос, в каком именно виде. В виде списка каталогов, соответствующих паттерну - точно не подойдёт, так как состояние ФС может измениться в любой момент. Скомпилировать регулярки в байткод, который выполнять в ядре — да, годится, но это уже сложная конструкция.

И можно ли регекс так написать, что бы конечный автомат

Современные регексы - это не «регулярые выражения», как изначально они были задуманы, и не отображаются на (детерминированные) конечные автоматы.

Ну так и делается, тащемта. Но пока грузим просто список правил, только не через нетлинк, а через securityfs тупо записью в файл :) Вот хочется грузить уже автомат для скорости.

Скомпилировать регулярки в байткод, который выполнять в ядре — да, годится, но это уже сложная конструкция.

Ну вот к этому и стремимся :)

Такую штуку видел? https://github.com/G-Core/linux-regex-module

Аудит бы к этому всему сделать. В либах регулярок часто уязвимости находят да и во всяких исполнялках байт-кода типа того же bpf, а здесь комбо

Если защита не ломается, то что делать, если защита перестанет пускать (настоящего) хозяина?

Видел, конечно. Сделано на интелловском гиперскане с интелловскими SSE-инструкциями. И что делать на другом процессоре? А потом у него регекс очень специфичен. Он заточен под разбор сетевых пакетов.

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

Ну вот это тоже меня волнует. Ну как-то аппармор с селинуксом со своими загружаемыми из юзерспейса автоматами разбора правил живут...

Типа звезда действует до ближайшего слеша, а две звезды — на любую глубину.

Так это совсем не регэкс. Для таких паттернов можно сделать простенький лексер на re2c и хранить в памяти в виде списка токенов.

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

О! Я в процессе отладки так стрелял себе в ногу :) Чо делать, чо делать... На кнопку питания жать и перегружаться в сейф-моде без модулей :)

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

Если я теперь правильно всё понял, то тут уже не важно, какой у регулярок синтаксис, их всё равно пишет не пользователь.

Что касается re2c — я имел в виду лексер для самих паттернов. Типа побить пути на элементы по слэшам и распознать особые токены ‘*’ и ‘**’.

Ну примерно так оно и делается. Вот как оно выглядит у аппармора:

/tmp/** rwk,
  owner @{HOME}/** rwk,
  owner /var/lib/libvirt/swtpm/** rwk,
  /run/libvirt/qemu/swtpm/*.sock rwk,
  owner /var/log/swtpm/libvirt/qemu/*.log rwk,
  owner /run/libvirt/qemu/swtpm/*.pid rwk,
  owner /dev/vtpmx rw,
  owner /etc/nsswitch.conf r,
  owner /var/lib/swtpm/** rwk,
  owner /run/swtpm/sock rw,

из этого apparmor_compile генерит регулярку в синтаксисе pcre (в доке написано как именно, типа * -> [^\0/]*), ну а потом нормализация - NFA-DFA-минимизация DFA - бандл - загрузка в ядро.

В том, то и дело что эту «нормализация - NFA-DFA-минимизация DFA - бандл» надо делать в юзерспейсе. А в ядре тупо бегать по таблице DFA.

А не компилить регекс в ядре ядерными модулем TRE, в NFA, в котором можно зависнуть на недерминированное вермя.

И да, глобы (*,**,?) проще чем «регулярные выражения», незачем тащить для этого регекс-компиляторы

вот как раз различие именно в * и **. И это уже регекс. Звезда — это все кроме слеша, а ** — глоб в смысле баша. Так что регексы, это, регексы... И да, не волнуйтесь. Я ваш троллинг вижу, но отвечаю только по делу.

У Белларда в quickjs есть. Но спецификация регэкспов – Javascript ES2023, конечно.

Осталось внести js в ядро. С целью обидного смеха, конешшшно.

re2c

Вот же любители тащить ненужные зависимости в проект. Парсер и сопоставлятор шелл-паттернов (*, ** и ?) на Си занимает максимум пару страниц без каких бы то ни было зависимостей.

Никакой это не регэкс. И троллинга у него не было, он всё по делу написал.

на Си занимает максимум пару страниц

С багами и уязвимостями.

А что есть тогда регекс и что есть маска, она же шаблон, она же паттерн? А троллинг мелкий чуть выше был. Этот коммент как раз по делу.

Шелл не имеет двух звезд. Или не всякий шелл. Кстати, с интересом посмотрю на обработку маски **, если где найдешь.

Регэкс это штука где есть перечисления с помощью квадратных скобок, диапазоны, опциональные блоки с заданным шаблоном, указанные количества повторений итд, либо из соответстующего posix стандарта, либо из перла (не знаю стандарт там или что), либо ещё что-то похожее. И оно сложное, намного сложнее чем wildcard-паттерны.

Читаем Драгонбук. Там нет ничего про всякие квадратные скобки, диапазоны, опциональные блоки с заданным шаблоном, указанные количества повторений итд, Регекс определяется рекурсивно следующим образом:

БАЗИС: Базис образован двумя правилами. 1. e является регулярным выражением, а L (e) представляет собой {e}, т.е. язык, единственный член которого — пустая строка. 2. Если a — символ в Σ, то a представляет собой регулярное выражение, а L (a) = {a}, т.е. язык с одной строкой единичной длины, с символом a в единственной позиции.

ИНДУКЦИЯ: Имеется четыре правила индукции, посредством которых регулярные выражения строятся из более мелких. Предположим, что r и s являются регуляр- ными выражениями, описывающими соответственно языки L (r) и L (s). 1. (r) | (s) — регулярное выражение, описывающее язык L (r) ∪ L (s). 2. (r) (s) — регулярное выражение, описывающее язык L (r) L (s). 3. (r)∗ — регулярное выражение, описывающее язык (L (r))∗ . 4. (r) — регулярное выражение, описывающее язык L (r). Это правило го- ворит о том, что можно заключить выражение в скобки без изменения описываемого им языка.

И все!

После этого придумали кучу расширений. Сейчас под регексом обычно понимается некий шаблон (англ. pattern), состоящий из символов и метасимволов и задающий правило поиска.

Из этого следует, что *, **, ? являются частными случаями таких паттернов, пусть и самыми простыми.

И да, в терминах позикса, * == [^/\0]*, ** == *, ? = .

Все остальное — это каша в голове, вызванная множественностью терминологии и стилевыми особенностями.

Шелл не имеет двух звезд.

Ну где-то я их видел.

Кстати, с интересом посмотрю на обработку маски **, если где найдешь.

Вот написал. Вроде работает. Кстати, ox55ff, найди тут обещаные уязвимости. Возможность переполнить стек слишком длинным вводом таковой не является, на этот случай можно лимит на длину паттерна предусмотреть ну или сделать самодельный стек через malloc.

/* (c) firk 2024; feel free to use this code for anything */
#include <stdio.h>
#include <string.h>

static size_t strpos(char const *s, char c) {
  char const *p;
  if(p=strchr(s,c)) return p-s; else return strlen(s);
}

static int part_match(char const *pat, size_t plen, char const *name, size_t nlen) {
  char c;
  while(plen) {
    c = *pat;
    if(c=='*') {
      do { pat++; plen--; } while(plen && *pat=='*');
      while(nlen) {
        if(part_match(pat, plen, name, nlen)) return 1;
        name++; nlen--;
      }
      return !plen;
    }
    if(!nlen || c!='?' && c!=*name) return 0;
    name++; nlen--; pat++; plen--;
  }
  return !nlen;
}

static int xx_match(char const *pat, char const *s);
extern int full_match(char const *pat, char const *s) {
  size_t j, k, l;
  char const *pp;
  if(strstr(pat,"***")) return -1;
  while(*pat=='/' && *s=='/') { pat++; s++; }
  while(*pat && *s) {
    j = strpos(pat,'/');
    k = strpos(s,'/');
    if(s[k]=='/' && (pp=strstr(pat,"**")) && (l=pp-pat)<j && part_match(pat,l+1,s,k) && xx_match(pat+l+1,s+k+1)) return 1;
    if(!part_match(pat,j,s,k)) return 0;
    pat+=j; s+=k;
    while(*pat=='/' && *s=='/') { pat++; s++; }
  }
  return !(*pat || *s);
}

static int xx_match(char const *pat, char const *s) {
  while(1) {
    if(full_match(pat,s)) return 1;
    if(!(s = strchr(s,'/'))) return 0;
    s++;
  }
}

int main(int argc, char **argv) {
  if(argc!=3) { fprintf(stderr, "Usage: patcheck 'pattern' 'string'\n"); return -1; }
  if(full_match(argv[1], argv[2])) { printf("string matches pattern\n"); return 0; }
  else { printf("string doesn't match pattern\n"); return 1; }
}

Там нет ничего про всякие квадратные скобки, диапазоны, опциональные блоки с заданным шаблоном, указанные количества повторений итд, Регекс определяется рекурсивно следующим образом:

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

1. (r) | (s) — регулярное выражение, описывающее язык L (r) ∪ L (s)

Если я правильно понял что это значит, то wildcard-паттерны уже тут нарушают и это определение регэкспа.

И да, в терминах позикса

Выразить wildcard-ы через регэкспы можно, я и не спорил.

Парсер и сопоставлятор шелл-паттернов (*, ** и ?) на Си занимает максимум пару страниц без каких бы то ни было зависимостей.

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

Вот же любители тащить ненужные зависимости в проект.

Максимальная упоротость. Это даже не рантайм-зависимость.