Почему glibc strcspn() может безопасно обращаться к памяти, очевидно, за концом строки?

GNU libc имеет эта реализация strcspn(), который, цитата,

Returns the length of the maximum initial segment of S which contains no characters from REJECT.

Он умен в своей реализации, поскольку создает таблицу поиска из 256 записей, чтобы сделать операцию определения того, находится ли символ в наборе reject, простым поиском в массиве O (1), в отличие, например, от реализация OpenBSD, который использует вложенные циклы.

Однако мне любопытно, как приведенный ниже цикл c0/c1/c2/c3 может получить доступ к памяти после видимого конца str без ошибки страницы или чего-то подобного.

Гарантирует ли стандарт C, например, что все строки, находящиеся в стеке, куче или статически выделенные, выровнены до 4 байтов, поэтому безопасно обращаться к трем после последнего NUL?

Я добавил несколько комментариев в приведенный ниже код; в оригинале (как указано выше) вообще ничего нет.

/* Align a pointer by rounding down to closest size. */
#define PTR_ALIGN_DOWN(base, size) ...

size_t strcspn (const char *str, const char *reject)
{
  if ((reject[0] == '\0') || (reject[1] == '\0'))
    return __strchrnul (str, reject [0]) - str;

  // Build a lookup table containing all characters from `reject`;
  // due to the way the `do/while` loop below is constructed, `table`
  // will end up having `table[0] = 1` always, which works as an
  // exit condition.

  unsigned char p[256] = {0};
  unsigned char *s = (unsigned char*) reject;
  unsigned char tmp;
  do
    p[tmp = *s++] = 1;
  while (tmp);

  // Check the first 4 bytes "by hand".
  s = (unsigned char*) str;
  if (p[s[0]]) return 0;
  if (p[s[1]]) return 1;
  if (p[s[2]]) return 2;
  if (p[s[3]]) return 3;

  // Align the pointer (for whichever reason?)
  s = (unsigned char *) PTR_ALIGN_DOWN (s, 4);


  unsigned int c0, c1, c2, c3;
  do
    {
      s += 4;  // Loop over 4 characters at a time (the first 4 bytes were checked before)
      c0 = p[s[0]];
      c1 = p[s[1]];
      c2 = p[s[2]];
      c3 = p[s[3]];
    }
  // break if any of c0, c1, c2, or c3 is nonzero,
  // i.e. if we've either found one of the characters in `reject`, or a zero
  while ((c0 | c1 | c2 | c3) == 0);

  size_t count = s - (unsigned char *) str;
  // figure out the actual offset based on which of c0..3 is set
  return (c0 | c1) != 0 ? count - c0 + 1 : count - c2 + 3;
}

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

aschepler 28.05.2019 13:55

Связано: stackoverflow.com/a/57651888/918959

Antti Haapala -- Слава Україні 30.07.2020 10:44
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
3
468
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Этому циклу предшествует строка:

s = (unsigned char *) PTR_ALIGN_DOWN (s, 4);

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

Если вы строго придерживаетесь стандарта C, это приводит к неопределенному поведению. Но glibc предполагает, что на платформах, на которых он работает, размер страницы кратен 4 байтам, и что чтение после конца буфера не вызовет никаких проблем, если оно находится на той же странице.

Звучит правдоподобно! Интересно, документировано ли это предположение где-нибудь.

AKX 28.05.2019 14:14

Обратите внимание, что это предположение практически является данностью: страницы памяти обычно большие (4 КБ), всегда выровнены по своему естественному размеру и всегда содержат степень 2 байта. Это следует непосредственно из того, как работает постраничная адресация. Таким образом, вы можете так же легко прочитать всю кэш-линию (64 байта = 512 битов = один регистр AVX-512) из ​​выровненного адреса и быть в порядке: либо все 64 байта отображаются, либо нет, между ними ничего нет.

cmaster - reinstate monica 28.05.2019 14:22

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

Gem Taylor 28.05.2019 15:03

@GemTaylor Это правда. Я думаю, что valgrind предоставляет альтернативные реализации функций glibc, таких как strcspn, чтобы избежать этой проблемы.

interjay 28.05.2019 15:24

Другие вопросы по теме