x86과 x64의 동일한 페이지 내에서 버퍼의 끝을 지나서 읽는 것이 안전합니까?

x86과 x64의 동일한 페이지 내에서 버퍼의 끝을 지나서 읽는 것이 안전합니까?

고성능 알고리즘에서 발견되는 많은 방법들은 입력 버퍼의 끝을 지나 소량의 데이터를 읽을 수 있다면 단순화될 수 있습니다.여기서 "작은 양"은 일반적으로 다음을 의미합니다.W - 1바이트가 끝을 지나서, 어디에 있는지 여부W는 알고리즘의 단어 크기(바이트 단위)입니다(예: 64비트 청크로 입력을 처리하는 알고리즘의 경우 최대 7바이트).

일반적으로 입력 버퍼의 끝을 지나서 쓰는 것은 결코 안전하지 않습니다. 버퍼¹ 너머로 데이터를 이동할 수 있기 때문입니다.또한 버퍼 끝을 지나 다른 페이지로 판독하면 다음 페이지를 읽을 수 없기 때문에 분할 오류/액세스 위반이 발생할 수 있습니다.

그러나 정렬된 값을 읽는 특별한 경우에는 적어도 x86에서는 페이지 장애가 불가능한 것처럼 보입니다.이 플랫폼에서 페이지(및 메모리 보호 플래그)는 4K 세분성(예: 2MiB 또는 1GiB와 같이 더 큰 페이지도 가능하지만 4K의 배수)을 가지며 정렬된 읽기는 버퍼의 유효한 부분과 동일한 페이지의 바이트에만 액세스합니다.

다음은 입력을 정렬하고 버퍼 끝을 지나 최대 7바이트를 읽는 일부 루프의 표준 예입니다.

int processBytes(uint8_t *input, size_t size) {

    uint64_t *input64 = (uint64_t *)input, end64 = (uint64_t *)(input + size);
    int res;

    if (size < 8) {
        // special case for short inputs that we aren't concerned with here
        return shortMethod();
    }

    // check the first 8 bytes
    if ((res = match(*input)) >= 0) {
        return input + res;
    }

    // align pointer to the next 8-byte boundary
    input64 = (ptrdiff_t)(input64 + 1) & ~0x7;

    for (; input64 < end64; input64++) {
        if ((res = match(*input64)) > 0) {
            return input + res < input + size ? input + res : -1;
        }
    }

    return -1;
}

함수 내부함수int match(uint64_t bytes)표시되지 않지만 특정 패턴과 일치하는 바이트를 찾고, 발견되면 가장 낮은 위치(0-7)를 반환하며, 그렇지 않으면 -1을 반환합니다.

첫째, 크기가 8 미만인 케이스는 설명의 단순성을 위해 다른 함수로 전당포됩니다.그런 다음 처음 8개(비정렬 바이트)에 대해 단일 검사가 수행됩니다.그런 다음 나머지에 대해 루프가 수행됩니다.floor((size - 7) / 8)8바이트의² 덩어리이 루프는 버퍼의 끝을 지나 최대 7바이트까지 읽을 수 있습니다(7바이트의 경우는 다음과 같습니다.input & 0xF == 1그러나 반환 호출에는 버퍼 끝 이후에 발생하는 모든 가짜 일치를 제외하는 검사가 있습니다.

실제로, x86과 x86-64에서 그러한 기능이 안전합니까?

이러한 유형의 오버레딩은 고성능 코드에서 일반적입니다.이러한 과도한 읽기를 방지하기 위한 특수 테일 코드도 일반적입니다.때때로 당신은 후자의 유형이 전자를 발그랜드와 같은 침묵의 도구로 대체하는 것을 볼 수 있습니다.때때로 그러한 교체를 제안하는 것을 볼 수 있는데, 관용구가 안전하고 도구가 오류가 있다는 이유(또는 단순히 너무 ³보수적이라는 이유)로 거부됩니다.

언어 변호사를 위한 참고 사항:

할당된 크기를 초과하는 포인터를 읽는 것은 표준에서 허용되지 않습니다.저는 언어 변호사의 답변에 감사하며, 심지어 가끔 직접 작성하기도 합니다. 그리고 위의 코드가 정의되지 않은 행동이며 따라서 가장 엄격한 의미에서 안전하지 않다는 것을 보여주는 장과 절을 누군가가 파헤칠 때 행복할 것입니다(그리고 자세한 내용을 여기에 복사하겠습니다).하지만 궁극적으로, 그것은 제가 추구하는 것이 아닙니다.실질적인 문제로서 포인터 변환, 구조 액세스 등을 포함하는 많은 일반적인 관용구는 기술적으로 정의되지 않았지만 고품질 및 고성능 코드에 널리 퍼져 있습니다.대안이 없거나 대안이 절반 이하의 속도로 실행되는 경우가 많습니다.

원하는 경우 이 질문의 수정된 버전을 고려하십시오.

위의 코드가 x86/x86-64 어셈블리로 컴파일되고 사용자가 예상되는 방식으로 컴파일되었음을 확인한 후(즉, 컴파일러가 정말 영리한 일을 하기 위해 입증 가능한 부분적인 경계 밖 액세스를 사용하지 않았습니다. 컴파일된 프로그램을 실행하는 것이 안전합니까?

그런 점에서 이 질문은 C 질문이자 x86 어셈블리 질문입니다.제가 본 이 트릭을 사용하는 대부분의 코드는 C로 작성되었으며, C는 여전히 고성능 라이브러리의 지배적인 언어이며, sm과 같은 하위 레벨의 것과 <다른 모든 것>과 같은 상위 레벨의 것을 쉽게 능가합니다.적어도 포트란이 여전히 공을 치는 하드코어 수치 틈새 밖입니다.그래서 저는 C 컴파일러 아래의 질문에 관심이 있습니다. 이것이 제가 그것을 순수한 x86 어셈블리 질문으로 공식화하지 않은 이유입니다.

즉, 저는 이것이 UD임을 보여주는 표준에 대한 링크에만 관심이 있지만, 이 특정 UD를 사용하여 예기치 않은 코드를 생성할 수 있는 실제 구현의 세부 사항에 매우 관심이 있습니다.이런 일은 심층적인 교차 절차 분석 없이는 일어날 수 없다고 생각합니다. 하지만 gcc 오버플로는 많은 사람들을 놀라게 했습니다.

---

¹ 동일한 값이 반환되는 경우와 같이 명백하게 무해한 경우에도 동시 코드를 위반할 수 있습니다.

² 이 중복 작업을 위해서는 이 기능이 필요합니다.match()특히 반환 값이 중복 검사를 지원한다는 점에서 특정 동일한 방식으로 동작하는 함수입니다.그래서 "첫 번째 바이트 일치 패턴 찾기"는 모든 것이 가능하기 때문에 작동합니다.match()통화는 아직 진행 중입니다.그러나 일부 바이트는 이중으로 카운트될 수 있으므로 "바이트 일치 패턴 카운트" 방법은 작동하지 않습니다.별도로, "최소 바이트 반환" 호출과 같은 일부 기능은 순서 제한 없이도 작동하지만 모든 바이트를 검사해야 합니다.

³ 여기서 주목할 점은 발그린드의 멤체크를 위해 깃발이 있다는 것입니다.--partial-loads-ok이러한 읽기가 실제로 오류로 보고되는지 여부를 제어합니다.기본값은 yes입니다. 일반적으로 이러한 로드는 즉시 오류로 처리되지 않지만 로드된 바이트의 후속 사용을 추적하기 위해 노력합니다. 이 바이트 중 일부는 유효하고 일부는 유효하지 않으며 범위를 벗어난 바이트가 사용될 경우 오류가 플래그 지정됩니다.위의 예와 같은 경우, 전체 단어가 다음에서 액세스됩니다.match()이러한 분석을 통해 결과가 최종적으로 폐기되더라도 바이트에 액세스할 수 있다는 결론을 내릴 수 있습니다.Valgrind는 일반적으로 부분 로드의 잘못된 바이트가 실제로 사용되는지 여부를 확인할 수 없습니다(일반적으로 탐지는 매우 어려울 수 있습니다).

예, x86 ASM에서는 안전하며, 기존 libc 구현에서는 수기 ASM에서 이를 활용합니다.그리고 glibc의 폴백 C도 있지만 LTO 없이 컴파일하기 때문에 절대 인라인을 사용할 수 없습니다.기본적으로 C를 휴대용 조립기로 사용하여 하나의 기능에 대한 기계 코드를 만드는 것이지, 인라인이 있는 더 큰 C 프로그램의 일부가 아닙니다.하지만 그것은 대부분 그것이 잠재적인 엄격한 별칭 UB를 가지고 있기 때문입니다, 링크된 Q&A에서 제 답변을 참조하십시오.당신은 아마도 플레인 대신 GNU C typeef를 원할 것입니다.unsigned long넓타으로입은마치신,,, 치▁type▁wider▁▁as▁your로마으.__m128i이미 사용 중인 등.

정렬된 로드가 더 높은 정렬 경계를 넘지 않으므로 안전하며 정렬된 페이지에서 메모리 보호가 수행되므로 최소 4k 경계¹최소 1바이트의 유효한 바이트에 도달하는 자연스럽게 정렬된 로드는 문제가 될 수 없습니다.다음 페이지 경계에서 16바이트 로드를 수행할 수 있을 정도로 충분히 멀리 떨어져 있는지 확인하는 것도 안전합니다.if (p & 4095 > (4096 - 16)) do_special_case_fallback자세한 내용은 아래 섹션을 참조하십시오.

---

x86용으로 컴파일된 C에서도 일반적으로 안전한 것으로 알고 있습니다.개체 외부에서 읽는 것은 물론 C에서는 정의되지 않은 동작이지만 C-targeting-x86에서는 작동합니다.컴파일러가 명시적으로/의도적으로 동작을 정의하지는 않지만 실제로는 그렇게 작동합니다.

공격적인 컴파일러가 최적화하는 동안 발생할 수 없다고 가정하는 UB 유형은 아니라고 생각합니다. 하지만 이 점에 대한 컴파일러 작성자의 확인이 좋을 것입니다. 특히 컴파일 시 액세스가 개체의 끝을 지나갔다는 것을 쉽게 입증할 수 있는 경우에는 더욱 그렇습니다.(@RossRidge와의 의견 토론 참조: 이 답변의 이전 버전은 절대적으로 안전하다고 주장했지만 LLVM 블로그 게시물은 실제로 그런 식으로 읽지는 않습니다.)

sm에서 암시적 길이 문자열을 처리하는 데 한 번에 1바이트보다 빠르게 이동해야 합니다.C 이론에서는 컴파일러가 이러한 루프를 최적화하는 방법을 알 수 있지만 실제로는 그렇지 않으므로 이러한 해킹을 수행해야 합니다.그것이 바뀔 때까지, 나는 사람들이 관심을 갖는 컴파일러들이 일반적으로 이 잠재적인 UB를 포함하는 코드를 깨는 것을 피할 것이라고 생각합니다.

개체의 길이를 아는 코드에 오버레드가 보이지 않을 경우 위험이 없습니다.컴파일러는 우리가 실제로 읽는 한 배열 요소가 있는 경우에 사용할 수 있는 sm을 만들어야 합니다.가능한 미래 컴파일러에서 제가 볼 수 있는 그럴듯한 위험은 인라인화 후 컴파일러가 UB를 보고 이 실행 경로를 절대로 취하지 말아야 한다고 결정할 수 있다는 것입니다.또는 종료 조건을 최종 비풀 벡터 전에 찾아야 하며 완전히 풀 때는 제외해야 합니다.

---

여러분이 얻는 데이터는 예측할 수 없는 쓰레기이지만, 다른 잠재적인 부작용은 없을 것입니다.프로그램이 가비지 바이트의 영향을 받지 않는 한 괜찮습니다.(예: bitacks를 사용하여 a의 바이트 중 하나가 0인지 확인한 다음 바이트 루프를 사용하여 첫 번째 0 바이트를 찾습니다.)

---

x86 asm에서 안전하지 않은 비정상적인 상황

• 지정된 주소의 로드에서 트리거하는 하드웨어 데이터 중단점(워치포인트)입니다.배열 직후에 모니터링하는 변수가 있으면 스퓨리어스 히트를 칠 수 있습니다.일반 프로그램을 디버깅하는 사용자에게는 사소한 문제일 수 있습니다.x86 디버그 레지스터 D0-D3를 사용하는 프로그램의 일부로 기능을 사용하고 정확성에 영향을 줄 수 있는 예외를 적용하려면 이 작업에 주의해야 합니다.

  또는 마찬가지로 발그랜드와 같은 코드 검사기는 객체 외부에서 읽는 것에 대해 불평할 수 있습니다.

• 가상의 16비트 또는 32비트 OS에서는 분할을 사용할 수 있습니다.세그먼트 제한은 4k 또는 1바이트의 세분성을 사용할 수 있으므로 첫 번째 장애 오프셋이 홀수인 세그먼트를 만들 수 있습니다. (세그먼트의 기저부를 캐시 라인 또는 페이지에 정렬하는 것은 성능을 제외하고는 관련이 없습니다.)모든 메인스트림 x86 OS는 플랫 메모리 모델을 사용하며 x86-64는 64비트 모드에 대한 세그먼트 제한 지원을 제거합니다.

• 메모리 매핑된 I/O는 특히 동일한 64B 캐시 라인에서 넓은 로드로 루프오버하려는 버퍼 바로 다음에 등록됩니다.장치 드라이버(또는 일부 MMIO 공간을 매핑한 X 서버와 같은 사용자 공간 프로그램)에서 이와 같은 기능을 호출하더라도 이는 매우 불가능합니다.

버퍼를 4바이트 레지스터에서 것을 은 그것에 될 이고, 당신은 그것에 대해 알게 될 것이고, 당신은 MMIO 레지스터의 4번째 버퍼를 하게 될 입니다.volatile T*일반 코드에서는 이러한 상황이 발생하지 않습니다.

---

strlen 은 암시적 길이 버퍼를 처리하여 버퍼 끝을 읽지 않고는 벡터화할 수 없는 루프의 표준 예입니다.종료 후 판독을 피해야 하는 경우0바이트, 한 번에 한 바이트만 읽을 수 있습니다.

예를 들어 glibc의 구현은 프롤로그를 사용하여 첫 번째 64B 정렬 경계까지 데이터를 처리합니다.그런 다음 메인 루프(asm 소스에 대한 gitweb 링크)에서 4개의 SSE2 정렬 로드를 사용하여 전체 64B 캐시 라인을 로드합니다.(서명되지 않은 바이트의 최소값)을 가진 하나의 벡터로 병합되므로 네 개의 벡터 중 하나가 0인 경우에만 최종 벡터가 0 요소를 가집니다.문자열의 끝이 캐시 라인의 어딘가에 있다는 것을 발견한 후, 그것은 위치를 확인하기 위해 네 개의 벡터 각각을 다시 확인합니다. (모두 0인 벡터에 대한 표준 사용, 그리고pmovmskbglibc는 벡터 내의 위치를 찾기 위해 선택할 수 있는 몇 가지 다른 스트렐렌 전략을 가지고 있었지만, 현재의 전략은 모든 x86-64 CPU에서 좋습니다bsf.

일반적으로 이와 같은 루프는 glibc의 스트렐렌과 같은 성능상의 이유로 페이지뿐만 아니라 만질 필요가 없는 추가 캐시 라인을 건드리지 않습니다.

자연스럽게 정렬된 액세스는 캐시 라인이나 페이지 라인 경계를 통과할 수 없기 때문에 한 번에 64B를 로드하는 것은 64B 정렬 포인터에서만 안전합니다.

---

버퍼의 길이를 미리 알고 있는 경우 버퍼의 마지막 바이트에서 끝나는 정렬되지 않은 로드를 사용하여 마지막 전체 정렬 벡터를 초과하는 바이트를 처리하여 끝까지 읽는 것을 방지할 수 있습니다.

(다시 말하지만, 이것은 memcpy와 같은 동일한 알고리즘에서만 작동합니다. memcpy는 저장소를 대상에 겹치더라도 상관하지 않습니다.위치 수정 알고리즘은 SSE2를 사용하여 문자열을 대문자로 변환하는 것과 같은 경우를 제외하고는 이러한 작업을 수행할 수 없습니다. SSE2에서는 이미 대문자로 변환된 데이터를 재처리해도 문제가 없습니다.마지막 정렬된 저장소와 겹치는 정렬되지 않은 로드를 수행하는 경우 스토어 포워딩 스톨을 제외합니다.)

따라서 알려진 길이의 버퍼를 통해 벡터화하는 경우에는 항상 과도한 읽기를 피하는 것이 가장 좋습니다.

컴파일러가 컴파일할 때 볼 수 없는 UB의 종류는 확실히 손상될 수 없습니다.결과 합계는 추가 바이트가 어떤 개체의 일부인 것처럼 작동합니다.

그러나 컴파일 시에 볼 수 있더라도 일반적으로 현재 컴파일러에서는 문제가 되지 않습니다.

---

PS: 이 답변의 이전 버전은 다음과 같이 정렬되지 않은 deref를 주장했습니다.int *x86용으로 컴파일된 C에서도 안전했습니다.그것은 사실이 아닙니다.저는 3년 전에 그 부분을 쓸 때 너무 까불었습니다.GNU C의 typeef가 필요합니다.__attribute__((aligned(1),may_alias))또는memcpy그것을 안전하게 하기 위해.그may_alias서명/미서명을 통해서만 액세스하는 경우 부품이 필요하지 않습니다.int*및/또는 'char*'(즉, 일반적인 엄격한 별칭 지정 규칙을 위반하지 않는 방식).

ISO C가 정의되지 않은 상태로 유지하지만 컴파일러가 정의해야 하는 Intel 내재성에는 정렬되지 않은 포인터(최소한 다음과 같은 유형)를 생성하는 것이 포함됩니다.__m128i*), 하지만 직접 참조를 취소하지는 않습니다.하드웨어 SIMD 벡터 포인터와 해당 유형 사이의 'reinterpret_casting'은 정의되지 않은 동작입니까?

---

포인터가 4k 페이지 끝에서 충분히 멀리 떨어져 있는지 확인

이것은 strlen의 첫 번째 벡터에 유용합니다; 이 후에 당신은 할 수 있습니다.p = (p+16) & -16다음 정렬된 벡터로 이동합니다.이는 다음과 같은 경우 부분적으로 겹칩니다.p16바이트가 정렬되지는 않았지만 중복 작업을 수행하는 것이 효율적인 루프를 설정하는 가장 간단한 방법일 수 있습니다.이를 피한다는 것은 정렬 경계까지 한 번에 1바이트씩 루프하는 것을 의미할 수 있으며, 이는 확실히 더 나쁜 것입니다.

예: 수표((p + 15) ^ p) & 0xFFF...F000 == 0(LEA / XOR / TEST) - 16바이트 로드의 마지막 바이트가 첫 번째 바이트와 동일한 페이지 주소 비트를 가지고 있음을 알려줍니다.또는p+15 <= p|0xFFF(LEA / OR / CMP with better ILP)는 로드의 마지막 바이트 주소가 첫 번째 바이트를 포함하는 페이지의 마지막 바이트인지 확인합니다.

아니면 더 간단히 말하면,p & 4095 > (4096 - 16)(MOV / AND / CMP), 즉,p & (pgsize-1) < (pgsize - vecwidth)페이지 내 오프셋이 페이지 끝에서 충분히 멀리 떨어져 있는지 확인합니다.

높은 비트는 중요하지 않으므로 32비트 피연산자 크기를 사용하여 이 검사 또는 다른 검사의 코드 크기(REX 접두사)를 저장할 수 있습니다.일부 컴파일러는 이 최적화를 인식하지 못하므로 다음으로 캐스트할 수 있습니다.unsigned int대신에uintptr_t64비트가 깨끗하지 않은 코드에 대한 경고를 잠재우려면 캐스트해야 할 수도 있습니다.(unsigned)(uintptr_t)p코드 크기를 추가로 절약할 수 있습니다.((unsigned int)p << 20) > ((4096 - vectorlen) << 20)(MOV / SHL / CMP), 이유shl reg, 203바이트입니다.and eax, imm32다른 레지스터의 경우 5 또는 6입니다.(EAX를 사용하면 다음에 대한 no-modrm 단축형도 사용할 수 있습니다.cmp eax, 0xfff.)

GNU C에서 이것을 한다면, 아마도 당신은 원할 것입니다.typedef unsigned long aliasing_unaligned_ulong __attribute__((aligned(1),may_alias));정렬되지 않은 액세스를 안전하게 수행할 수 있습니다.

CPU가 아닌 디바이스를 고려할 수 있는 경우 잠재적으로 안전하지 않은 작업의 한 예로 PCI 매핑된 메모리 페이지의 Out of Bound 영역에 액세스하는 것이 있습니다.대상 장치가 기본 메모리 하위 시스템과 동일한 페이지 크기 또는 정렬을 사용한다는 보장은 없습니다.주소(예: 주소)에 액세스하려고 시도하는 중[cpu page base]+0x800장치가 2KiB 페이지 모드인 경우 장치 페이지 결함을 트리거할 수 있습니다.이로 인해 일반적으로 시스템 버그 검사가 발생합니다.

언급URL : https://stackoverflow.com/questions/37800739/is-it-safe-to-read-past-the-end-of-a-buffer-within-the-same-page-on-x86-and-x64