8.4 יישור זיכרון ו SSE הרצאה

עד עכשיו בפרק הזה עסקנו בקבצים ארוזים, בארכיטקטורות זרות ובבינארים זעירים - כל אלה מקרים שבהם ההנדסה ההפוכה נתקלת בקוד שנראה מוזר. הפעם ניגע במשהו שנראה מוזר לגמרי כשפוגשים אותו בפעם הראשונה: תוכנית שקורסת לא בגלל overflow, לא בגלל מצביע פגום, אלא פשוט כי כתובת זיכרון לא הייתה מיושרת נכון. בשביל להבין למה זה קורה נצטרך לדבר על יישור זיכרון - alignment, על הרחבות SSE ועל הוראות ההעתקה שלהן, ובסוף על memcpy מהיר שמתרסק ברגע שנותנים לו כתובת או גודל לא נוחים. זה בדיוק הרעיון שמאחורי אתגר memcpy של pwnable.kr.

היכולת הזו חשובה גם להנדסה הפוכה טהורה: כשתראו movdqa בדיסאסמבלי ותבינו שהיא דורשת alignment, פתאום הרבה קוד שנראה קסום (memcpy, memset, strlen מואצים) יתבהר.

---

מהו יישור זיכרון - alignment

הalignment של זיכרון הוא כלל פשוט: כתובת p נחשבת מיושרת ל-N בתים אם p מתחלק ב-N ללא שארית, כלומר p % N == 0. מכיוון ש-N הוא כמעט תמיד חזקה של 2, אפשר לנסח את זה גם דרך הביטים: כתובת מיושרת ל-16 בתים היא כתובת שארבעת הביטים התחתונים שלה הם אפס.

Alignment to 16 bytes - the four low bits are zero:
0x601000   ->  ...0000 0000   aligned (0x601000 % 16 == 0)
0x601008   ->  ...0000 1000   not aligned (remainder is 8)
0x60100f   ->  ...0000 1111   not aligned (remainder is 15)

לכל טיפוס נתונים יש יישור טבעי - natural alignment, שבדרך כלל שווה לגודל שלו:

+-----------+--------+-----------------+
| type      | size   | natural alignment|
+-----------+--------+-----------------+
| char      | 1      | 1               |
| short     | 2      | 2               |
| int       | 4      | 4               |
| long/ptr  | 8      | 8  (on 64-bit)  |
| __m128    | 16     | 16 (SSE vector) |
+-----------+--------+-----------------+

הקומפיילר דואג לalignment הזה בשבילנו: הוא מרפד מבנים - struct padding, הוא בוחר כתובות מיושרות למשתנים על המחסנית, והוא מיישר משתנים גלובליים. ברוב המקרים אנחנו אפילו לא שמים לב שזה קורה. הבעיה מתחילה כשמישהו כותב קוד שמניח alignment מסוים - ואז מקבל כתובת שלא עומדת בהנחה.

---

למה למעבד אכפת מalignment

המעבד קורא וכותב זיכרון ביחידות של שורת מטמון - cache line, בדרך כלל 64 בתים. גישה מיושרת נופלת בתוך שורת מטמון אחת, וגישה לא מיושרת עלולה להתפרש על פני שתי שורות מטמון או אפילו שני דפי זיכרון - שזה יקר יותר, ולפעמים בלתי אפשרי לבצע אטומית.

64-byte cache lines:
| line 0 (0x00-0x3f) | line 1 (0x40-0x7f) |
                  ^^^^^^^
                  a 16-byte read from address 0x38 crosses the boundary -
                  touches both line 0 and line 1

בארכיטקטורות מסוימות (חלק מ-ARM ישן, MIPS, SPARC) גישה לא מיושרת פשוט זורקת חריגה - alignment fault - וקורסת. ארכיטקטורת x86 סלחנית יותר: הוראת mov רגילה תבצע גישה לא מיושרת בלי להתלונן, רק קצת יותר לאט. אבל - וזה הלב של השיעור - חלק מהוראות SSE דורשות alignment בכוח, וזורקות חריגת חומרה אם הכתובת לא מיושרת ל-16 בתים. שם נופלים.

---

הרחבות SSE ואוגרי xmm - SSE and xmm registers

הרחבת SSE - Streaming SIMD Extensions הוסיפה למעבד אוגרים רחבים בני 128 ביט בשם xmm0 עד xmm7 (במצב 32 ביט) או xmm0 עד xmm15 (במצב 64 ביט). הרעיון של SIMD - Single Instruction Multiple Data הוא לעבד כמה ערכים במקביל: אוגר xmm בן 128 ביט יכול להחזיק ארבעה מספרים שלמים של 32 ביט, או שני מספרים של 64 ביט, או 16 בתים - ולהעביר או לחשב את כולם בהוראה אחת.

בגלל זה מימושים מהירים של memcpy, memset ו-strlen משתמשים ב-SSE: במקום להעתיק בית-בית, מעתיקים 16 בתים בכל הוראה, או אפילו 64 בתים בלולאה שמשתמשת בארבעה אוגרי xmm.

כדי להזיז 128 ביט בין זיכרון לאוגר xmm יש כמה הוראות, וההבדל ביניהן הוא בדיוק עניין הalignment:

+----------+--------------------------------+------------------+
| instruction | what it does                | alignment req.   |
+----------+--------------------------------+------------------+
| movdqa   | copy 128 bits (integers)       | required, 16 bytes |
| movdqu   | copy 128 bits (integers)       | no requirement   |
| movaps   | copy 128 bits (float)          | required, 16 bytes |
| movups   | copy 128 bits (float)          | no requirement   |
| movntdq  | non-temporal write of 128 bits | required, 16 bytes |
| movdqa   | (a = aligned, u = unaligned)   |                  |
+----------+--------------------------------+------------------+

ה-a בסוף movdqa ו-movaps הוא ראשי התיבות של aligned, וה-u ב-movdqu/movups הוא unaligned. ההוראות עם a, וגם movntdq (כתיבה לא-זמנית שעוקפת את המטמון), דורשות שהאופרנד בזיכרון יהיה מיושר ל-16 בתים. אם לא - המעבד זורק חריגת הגנה כללית - #GP, ובלינוקס זה מתורגם ל-SIGSEGV.

בעולם AVX המצב דומה: vmovdqa דורשת alignment (16 בתים לאוגר xmm, 32 בתים לאוגר ymm), ו-vmovdqu לא.

---

ההוראות movdqa מול movdqu - aligned versus unaligned

בואו נראה את זה בפועל. נכתוב תוכנית קצרה שמנסה לקרוא 16 בתים מכתובת לא מיושרת עם movdqa:

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    // allocate 32 bytes, then deliberately point to an address that isn't aligned to 16
    char *base = aligned_alloc(16, 32);
    char *bad  = base + 8;   // 8 modulo 16 - not aligned!

    __asm__ volatile (
        "movdqa (%0), %%xmm0\n\t"   // aligned read - will crash on address bad
        :: "r"(bad) : "xmm0", "memory");

    printf("survived\n");
    return 0;
}

מקמפלים ומריצים:

gcc -O0 -o align_demo align_demo.c
./align_demo
# Segmentation fault (core dumped)

אם נחליף את movdqa ב-movdqu, אותו קוד בדיוק ירוץ בלי בעיה ויודפס survived. אותה כתובת, אותו נתון - ההבדל היחיד הוא ההוראה. תחת gdb / pwndbg נראה את הקריסה מדויקת:

pwndbg> run
Program received signal SIGSEGV, Segmentation fault.
0x... in main ()
=> 0x...  movdqa xmm0, xmmword ptr [rax]
pwndbg> p/x $rax & 0xf
$1 = 0x8          <-- the address is 8 modulo 16, hence the fault

הנה הטריק שכדאי לזכור: כשאתם עושים הנדסה הפוכה ורואים movdqa/movaps/movntdq ונופלים על SIGSEGV בדיוק שם - כמעט תמיד הבעיה היא כתובת שאיננה מיושרת ל-16 בתים, לא מצביע שגוי. בדקו את ארבעת הביטים התחתונים של האופרנד.

---

יישור בהקצאות זיכרון - allocation alignment

עכשיו השאלה המעניינת: מאיפה מגיעה כתובת מיושרת (או לא) מלכתחילה? זה תלוי איפה הזיכרון מוקצה.

על המחסנית - stack

הקומפיילר מיישר משתנים מקומיים לפי הalignment הטבעי שלהם. אם צריך alignment חזק יותר לוקטור SSE, מבקשים אותו במפורש:

__attribute__((aligned(16))) char buf[64];   // aligned to 16 bytes
_Alignas(16) char buf2[64];                   // equivalent C11 syntax

בלי הבקשה הזו, מערך char על המחסנית עלול להתחיל בכתובת שאיננה מיושרת ל-16, ואז movdqa עליו יקרוס.

בהקצאה דינמית - heap

וכאן הנקודה הכי חשובה לשיעור הזה. הפונקציה malloc מבטיחה alignment מינימלי שנקרא MALLOC_ALIGNMENT, וגודלו תלוי בארכיטקטורה:

+-----------------+---------------------+
| architecture    | MALLOC_ALIGNMENT    |
+-----------------+---------------------+
| 64-bit          | 16 bytes            |
| 32-bit          | 8 bytes  (2 * 4)    |
+-----------------+---------------------+

במערכת 64 ביט malloc מחזירה כתובות מיושרות ל-16 בתים, ולכן movdqa על buffer מ-malloc יעבוד. אבל במערכת 32 ביט הערך הוא 2 * SIZE_SZ = 2 * 4 = 8 בלבד. כלומר malloc ב-32 ביט מבטיחה alignment ל-8 בתים בלבד, ולא ל-16.

למה זה יוצר בעיה? נסתכל על מבנה נתח - chunk של glibc במערכת 32 ביט. המצביע שהמשתמש מקבל (mem) מתחיל 8 בתים אחרי בסיס הנתח (אחרי שדות prev_size ו-size):

Chunk address in a 32-bit allocation:
+------------------+  <- chunk base (aligned to 16)
| prev_size (4)    |
+------------------+
| size (4)         |
+------------------+  <- the returned mem pointer = base + 8
| user data...     |     i.e. 8 modulo 16 - not aligned to 16!
+------------------+

התוצאה: במערכת 32 ביט, malloc מחזירה בדרך כלל כתובות שהן 8 מודולו 16. הן מיושרות ל-8 אבל לא ל-16. אם ניקח כתובת כזו ונריץ עליה movdqa - קריסה מיידית. ואפשר לוודא את זה בקלות:

char *p = malloc(64);
printf("p = %p, p %% 16 = %lu\n", p, (unsigned long)p & 0xf);
// on 32-bit you'll usually see "p % 16 = 8"

הקצאה מיושרת מפורשת

אם באמת צריך buffer מיושר ל-16 בתים ב-heap, לא סומכים על malloc הרגילה אלא מבקשים alignment במפורש:

char *p1 = aligned_alloc(16, 64);           // C11
char *p2;
posix_memalign((void**)&p2, 16, 64);        // POSIX
char *p3 = memalign(16, 64);                 // older

שלושתן מחזירות כתובת שמובטח שהיא מיושרת ל-16 בתים, ולכן movdqa עליהן בטוח. שימו את שני העולמות האלה בראש - הקצאה רגילה שאולי לא מיושרת מול הקצאה מיושרת מפורשת - כי בדיוק בפער הזה נופל אתגר memcpy.

---

פונקציית memcpy מהירה עם SSE - a fast memcpy

בואו נחבר את הכול. הנה מימוש של memcpy שמנסה להיות מהיר: אם יש לפחות 64 בתים להעתיק, הוא מעתיק אותם בבלוקים של 64 בתים בעזרת ארבעה אוגרי xmm, ורק את השארית הקטנה מעתיק בית-בית.

#include <stddef.h>

char* slow_memcpy(char* dest, const char* src, size_t len) {
    for (size_t i = 0; i < len; i++)
        dest[i] = src[i];
    return dest;
}

char* fast_memcpy(char* dest, const char* src, size_t len) {
    if (len >= 64) {
        size_t i = len & ~(size_t)63;   // round down to a multiple of 64
        __asm__ volatile (
            "1:\n\t"
            "sub $0x40, %%ecx\n\t"
            "movdqa 0x00(%%esi,%%ecx,1), %%xmm0\n\t"
            "movdqa 0x10(%%esi,%%ecx,1), %%xmm1\n\t"
            "movdqa 0x20(%%esi,%%ecx,1), %%xmm2\n\t"
            "movdqa 0x30(%%esi,%%ecx,1), %%xmm3\n\t"
            "movntdq %%xmm0, 0x00(%%edi,%%ecx,1)\n\t"
            "movntdq %%xmm1, 0x10(%%edi,%%ecx,1)\n\t"
            "movntdq %%xmm2, 0x20(%%edi,%%ecx,1)\n\t"
            "movntdq %%xmm3, 0x30(%%edi,%%ecx,1)\n\t"
            "jne 1b\n\t"
            :: "S"(src), "D"(dest), "c"(i)
            : "xmm0", "xmm1", "xmm2", "xmm3", "memory");
        dest += i; src += i; len &= 63;
    }
    return slow_memcpy(dest, src, len);   // small remainder, safe byte-by-byte copy
}

שימו לב מה קורה כאן. הלולאה קוראת עם movdqa וכותבת עם movntdq - שתי הוראות שדורשות alignment ל-16 בתים. הכתובות שנוגעים בהן הן src + כפולה של 16 ו-dest + כפולה של 16, כלומר הalignment של כל גישה נקבע כולו על ידי הalignment של src ושל dest עצמם. המימוש הזה מניח בשקט מוחלט ששני המצביעים מיושרים ל-16 בתים.

מה קורה אם ההנחה נשברת? נריץ אותו על חוצץ מ-malloc במערכת 32 ביט:

gcc -m32 -O0 -o fast_demo fast_demo.c

char *dest = malloc(4096);          // 8 modulo 16 on 32-bit
char *src  = aligned_alloc(16, 4096);
fast_memcpy(dest, src, 4096);       // len >= 64 -> enters the SSE loop
// movntdq on dest which isn't aligned to 16 -> SIGSEGV

התוכנית קורסת. לא בגלל overflow, לא בגלל דריסת return address - אלא כי dest היה 8 מודולו 16, ו-movntdq דורשת 16. זו בדיוק המלכודת של אתגר memcpy.

יש כאן גם תובנה שנייה, על הגודל: הלולאה רצה רק אם len >= 64. אם נעביר גודל קטן מ-64, נדלג על כל בלוק ה-SSE ונרד ישר ל-slow_memcpy הבטוחה שמעתיקה בית-בית בלי שום דרישת alignment. הגודל שנבחר קובע אם בכלל נכנסים לקוד המסוכן.

---

אתגר memcpy של pwnable.kr - הצורה של האתגר

אתגר memcpy בונה על שני הרעיונות האלה - alignment ההקצאה וסף ה-64. מבנה התוכנית (במערכת 32 ביט) הוא בערך כזה:

int main() {
    // ... opening prints ...
    int order = 2;
    while (order != 22) {              // runs order from 2 to 21
        int alloc_size = pow(2, order);
        char *dest = malloc(alloc_size);
        char *src  = mmap(0, 0x1000, PROT_READ|PROT_WRITE,
                          MAP_ANON|MAP_PRIVATE, -1, 0);
        size_t sizes;
        printf("Order %d! : ", order);
        scanf("%d", &sizes);           // we control the copy size
        fast_memcpy(dest, src, sizes); // the same fast_memcpy with movdqa/movntdq
        order++;
    }
    printf("Well done! you are ready to code the assignment :)\n");
    system("/bin/cat flag");           // the flag is printed only if we survived all the rounds
}

נפרק את מה שיש לנו ביד:

+----------------------------------------------------------------+
| dest = malloc(2^order)   -> on 32-bit: 8 modulo 16 (not aligned!) |
| src  = mmap(...)         -> aligned to a full page, hence aligned to 16 (fine) |
| sizes = our input          -> determines whether we enter the SSE loop |
| the flag is printed after order == 22, i.e. after 20 rounds without crashing |
+----------------------------------------------------------------+

המלכודת ברורה: השחקן התמים מזין את alloc_size עצמו כגודל ההעתקה. עבור order >= 6 הגודל הוא 64 ומעלה, לכן נכנסים ללולאת ה-SSE, ו-movntdq פוגעת ב-dest שהוא 8 מודולו 16 - SIGSEGV, האתגר נגמר בסיבוב הראשון שחוצה את 64.

המטרה שלנו: לעבור את כל 20 הסיבובים בלי קריסה, כדי להגיע ל-system("/bin/cat flag"). את הפתרון המלא, כולל למה בחירת הגדלים הנכונה מדלגת על הקוד המסוכן, נעשה בתרגול ובפתרון. כרגע רק תחזיקו את התובנה: src מיושר, dest לא, וסף ה-64 הוא הידית שאנחנו שולטים בה.

---

סיכום

• יישור זיכרון - alignment: כתובת מיושרת ל-N אם p % N == 0. לalignment ל-16 בתים, ארבעת הביטים התחתונים אפס.
• המעבד קורא ביחידות של שורת מטמון. ב-x86 גישה רגילה לא מיושרת רק איטית, אבל הוראות SSE מסוימות זורקות חריגה.
• אוגרי xmm הם 128 ביט. movdqa/movaps/movntdq דורשות alignment ל-16 בתים; movdqu/movups לא. ב-AVX: vmovdqa דורשת, vmovdqu לא.
• הalignment בהקצאה: malloc מבטיחה 16 בתים ב-64 ביט אבל רק 8 בתים ב-32 ביט, ולכן ב-32 ביט buffer מ-malloc הוא לרוב 8 מודולו 16 - לא מיושר ל-movdqa. לalignment מובטח יש aligned_alloc, posix_memalign, memalign.
• memcpy מהיר מבוסס SSE מניח ש-src ו-dest מיושרים ל-16. אם לא, או אם הגודל דוחף אותנו ללולאת SSE על כתובת לא מיושרת - קריסה.
• אתגר memcpy של pwnable.kr: src מ-mmap מיושר, dest מ-malloc (32 ביט) לא, וסף ה-64 הוא מה שאנחנו שולטים בו. לעבור את כל הסיבובים בלי לגעת בקוד ה-SSE על כתובת לא מיושרת - זה מדפיס את הדגל.