Подтвердить что ты не робот

Почему эта реализация strlen() работает?

(Отказ: я видел этот вопрос, и я не перепрошу его - меня интересует почему работает код, а не в как он работает.)

Итак вот эта реализация Apple (ну, FreeBSD's) strlen(). Он использует хорошо известный трюк оптимизации, а именно, он проверяет 4 или 8 байтов одновременно, вместо того, чтобы делать байтовое сравнение по сравнению с 0:

size_t strlen(const char *str)
{
    const char *p;
    const unsigned long *lp;

    /* Skip the first few bytes until we have an aligned p */
    for (p = str; (uintptr_t)p & LONGPTR_MASK; p++)
        if (*p == '\0')
            return (p - str);

    /* Scan the rest of the string using word sized operation */
    for (lp = (const unsigned long *)p; ; lp++)
        if ((*lp - mask01) & mask80) {
        p = (const char *)(lp);
        testbyte(0);
        testbyte(1);
        testbyte(2);
        testbyte(3);
#if (LONG_BIT >= 64)
        testbyte(4);
        testbyte(5);
        testbyte(6);
        testbyte(7);
#endif
    }

    /* NOTREACHED */
    return (0);
}

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

|<---------------- all your memories are belong to us --------------->|<-- not our memory -->
+-------------+-------------+-------------+-------------+-------------+ - -
|     'A'     |     'B'     |     'C'     |     'D'     |      0      |
+-------------+-------------+-------------+-------------+-------------+ - -
^                                                      ^^
|                                                      ||
+------------------------------------------------------++-------------- - -
                       long word #1                      long word #2

Когда читается второе длинное слово, программа обращается к байтам, на которые он фактически не должен обращаться... не так ли? Я уверен, что Apple и люди BSD знают, что они делают, поэтому кто-то может объяснить, почему это правильно?

Одна вещь, которую я заметил, это пивобой, утверждал, что это поведение undefined, и я также считаю, что это действительно так, но ему сказали, что это не 't, потому что "мы сопоставляем размер слова с начальным циклом" (здесь не показано). Тем не менее, я совсем не вижу, почему выравнивание будет иметь значение, если массив недостаточно длинный, и мы читаем его конец.

4b9b3361

Ответ 1

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

Ответ 2

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

Процедура начинается с выравнивания по границе слова по двум причинам: во-первых, чтение слов из выровненного адреса происходит быстрее на большинстве архитектур (а также обязательным для нескольких процессоров). Увеличение скорости достаточно, чтобы использовать один и тот же трюк в целом ряде подобных операций: memcpy, strcpy, memmove, memchr и т.д.

Во-вторых: если вы продолжаете читать слова, начинающиеся с границы слова, вы уверены, что остальная часть строки находится на той же странице памяти. Строка (включая ее завершающий нуль) не может оседлать границу страницы памяти, и ни одна из них не может читать слово. (1)

Таким образом, это всегда самый быстрый и безопасный, даже если зернистость страницы памяти sizeof (LONG_BIT) (а это не так).

Подбор целого слова в конце строки может забрать дополнительные байты после окончательного нуля, но чтение Undefined Bytes из действительной памяти не является UB - действие действует только на его содержимое (2). Если слово содержит нулевой ограничитель где-то внутри, отдельные байты проверяются с помощью test_byte, и это, как показано в исходном источнике, никогда не будет действовать на байты после терминатора.

(1) Очевидно, что они могут, но я имел в виду "никогда не запертую страницу" или что-то подобное.

(2) В разделе "Обсуждение". См. (Извините за это!) Под ответом Sneftel.