[פוסט זה התפרסם במקור בפייסבוק ואחר כך בלינקדאין.]

מסיכות זה דבר מאוד חשוב היום. לכן, בקוד שלנו בגארדיקור, יש פונקציה שמקבלת מסיכת רשת משנה (subnet mask) ומחזירה את אורך תחילית CIDR שלה. אבל עזבו רגע מושגים של רשתות: בשפת פשוטי העם, הפונקציה מקבלת מספר 32-ביט, שמורכב מגוש של 1-ים ואחריו גוש של 0-ים (בעצם יש בדיוק 33 קלטים אפשריים כאלה), ומחזירה מספר בין 0 ל-32 שמציין את כמות ה-1-ים.

לדוגמה, עבור קלט 0x00000000 יוחזר 0, עבור קלט 0xFFFFFFFF יוחזר 32 ועבור קלט 0xFC000000 יוחזר 6.

איך עושים את זה באופן יעיל?

דרך טבעית לממש פונקציה כזו היא בעזרת האצת מעבד.
במעבדים רבים אפשר לעשות את זה עם אופקוד אחד, למשל ctz (שעושה count trailing zeroes).
מעשית, זה הפתרון הטוב ביותר: זה נותן בדיוק את מה שאנחנו רוצים, ואי-אפשר באמת להתחרות בתוכנה עם חישוב שמבוצע בחומרה.

אבל לפעמים, אין אפשרות להשתמש בהאצת מעבד - למשל, אם המעבד ישן ולא תומך, או שהקומפיילר לא תומך (ונמנעים מאסמבלי), או שהקוד בשפה קצת יותר מדי עילית (כמו פייתון, או גו, או ג’אווהסקריפט) ואין בשפה את האפשרות. במקרים כאלה, צריך לממש בתוכנה, כאשר אנחנו מוגבלים לפעולות חשבון ופעולות ביטים בסיסיות בלבד. ואז, צריך להתחיל לחשוב מחשבות אלגוריתמיות, כמו: מה הדרך הטובה ביותר לעשות את זה?

בזמן שחושבות - נצא לפרסומות

אני מגייס לצוות שלי בגארדיקור! אנחנו מפתחים קרנל דרייבר ללינוקס ולווינדוס שכתוב ב-C ומטרתו לחסום חיבורים לפי חוקת ה-firewall שמוגדרת על ידי המשתמש באופן מרכזי, ומחלחלת באופן דינאמי ואוטומטי לכל שרתי הקצה (גם לנוכח שינויים תכופים ברשת).

האתגרים הם רבים:

• אנחנו מריצים דרייבר על שרתים קריטיים של לקוחות, ולכן הקוד שלנו חייב להיות ברמת יציבות מקסימלית.
• פייפליין הטיפול בפקטות נמדד בסקאלה של נאנו-שניות, ולכן הקוד שלנו חייב להיות ברמת יעילות מקסימלית.
• בנוסף לזה אנחנו מטפלים בבעיות קשות אצל לקוחות - כאלה שבהן הלקוח עולה באש בגלל סיבה לא ברורה, ואנחנו מתחילים מאפס ומהר מאוד מוצאים את עצמנו בתוך הקוד של הקרנל מחפשים את השדה הנכון ב-struct הנכון שאפשר להשתמש בו כדי להציל את המצב.

המשרדים נמצאים בתל אביב (לא שזה משנה כל כך בתקופה הזו…), גייסנו סה"כ קצת יותר מ-100 מיליון דולר, יש כ-200 עובדים בעולם, אנחנו מוכרים את המוצר כבר כמה שנים, הולך לנו מצויין (גם ב-2020) ואנחנו רוצים להמשיך לגדול. נשמע מעניין לכן או לחבריכם - דברו איתי!

ונחזור לשידורינו

אוקי, אז על מה דיברנו? ספירת ביטים ב-subnet mask בלי האופקוד הקסום שעושה את זה בשבילנו.

כמה מחשבות פשוטות שאולי חשבתם:

1. אפשר לעשות לולאה: למשל, להסתכל על הביט התחתון, וכל עוד הוא אפס, לעשות שיפט.
2. אפשר להיעזר בטבלאות lookup: למשל, לעבור בייט-בייט (יש סה"כ 4…), וכשנתקלים בבייט שאינו אפס, לבדוק בטבלה (למשל בגודל 255) שיש בה את התשובה ללא חישוב נוסף.

אז איך זה ממומש אצלנו בקוד? ובכן, ככה:

1
2
3
4
5

table = [0, 5, 9, 30, 6, 31, 32, -1, 14, 13,
         24, 12, 27, 23, 18, 11, -1, 26, 20, 22,
         3, 17, 1, 10, 7, -1, 15, 25, 28, 19,
         -1, 21, 4, 2, 8, 16, 29]
return table[mask % 37]

במילים אחרות, אנחנו לוקחים את המסיכה, מחשבים את השארית שלה מודולו….. 37 (???), ואז מביאים את התשובה מטבלה סטטית קטנה.

את האלגוריתם (שאותו אסביר בהמשך הפוסט) פיתחנו אצלי בצוות, בהשראת אחד האלגוריתמים מהאתר של Sean Eron Anderson ממעבדת הגרפיקה הממוחשבת באונ' סטאנפורד (חפשו Mod37).

האלגוריתם של הבחור מסטאנפורד נותן מימוש כללי של “ctz”, שזה יותר ממה שאנחנו צריכים. אנחנו פישטנו וייעלנו אותו קצת על ידי ניצול העובדה שהקלט אצלנו הוא רק subnet mask, ולא כל קלט אפשרי.

למיטב ידיעתי אף אחד אחר לא מימש את הפתרון הספציפי הזה לבעיה הזו עם subnet mask (חיפשתי קטעים מהטבלה בגוגל ולא מצאתי תוצאות), ולכן אני חושב שזו אדפטציה מקורית שלנו 🙂

מה לעזאזל?

העקרון הבסיסי מוכר ופשוט: מדובר על hash table!
פונקציית ה-“hash” כאן היא מודולו 37, והטבלה, שגודלה בדיוק 37, מכילה את 33 התשובות (מ-0 עד 32), ועוד ארבעה “מינוס-אחדים” שמציינים “כניסה ריקה”.

אבל בבירור זה לא כל הסיפור. מסתתר פה קסם:
ב-hash table, אנחנו מצפים לראות התנגשויות… הרבה התנגשויות!

אם ה-hash פונקציה מערבבת אקראית סבירה ולגיטימית, אנחנו נצפה לפחות להתנגשות אחת בסיכוי טוב, ברגע ש-“ממלאים אותה” בכמות ערכים שהיא בערך שורש כמות הכניסות (כלומר, 6) - זה נובע מ-"פרדוקס יום ההולדת".

אבל כאן הטבלה מלאה, עם 33 ערכים, ולא התבלבלתם - אין פה קוד טיפול בהתנגשויות - כי אין התנגשויות בכלל!

אז איך הקסם הזה קורה? ומאיפה מגיע המספר 37? כדי להבין, נעזוב את עולם הקוד ונעבור לעולם המתמטיקה.

מבוא מזורז למתמטיקה הרלוונטית

לאורך הדיון המתמטי, נסכים ש-$p$ הוא מספר ראשוני כלשהו (למעלה דיברנו על המספר הראשוני $p=37$, אבל עכשיו נדבר על ראשוני כללי).

טענה א': בהכרח קיים מספר $a$ שנקרא “שורש פרימיטיבי מודולו $p$” (אולי יש יותר מאחד כזה - הטענה היא שקיים לפחות אחד).

המשמעות של זה: זהו מספר, שאם נסתכל על החזקות שלו מ-$0$ עד $p-2$, מודולו $p$:

$$ \begin{aligned} a^0 & \thinspace\operatorname{mod}\thinspace p = 1 \\ a^1 & \thinspace\operatorname{mod}\thinspace p \\ a^2 & \thinspace\operatorname{mod}\thinspace p \\ a^3 & \thinspace\operatorname{mod}\thinspace p \\ & \vdots & \\ a^{p-2} & \thinspace\operatorname{mod}\thinspace p \end{aligned} $$

אז התוצאות יהיו כולן שונות זו מזו. (הערה: כאן אני משתמש בסימן $\operatorname{mod}$ “כאופרטור” כמקובל במדעי המחשב ולא כשקילות כפי שמקובל במתמטיקה.)

דוגמה ראשונה - האם 2 הוא שורש פרימיטיבי מודולו 5?

נקח את הראשוני $p=5$. האם המספר $a=2$ הוא שורש פרימיטיבי מודולו $5$?
צריך לבדוק חזקות מ-$0$ עד $3$ (שהוא $p-2$).

$$ \begin{aligned} a^0 & \thinspace\operatorname{mod}\thinspace p = 1 \\ a^1 & \thinspace\operatorname{mod}\thinspace p = 2 \thinspace\operatorname{mod}\thinspace 5 = 2 \\ a^2 & \thinspace\operatorname{mod}\thinspace p = 4 \thinspace\operatorname{mod}\thinspace 5 = 4 \\ a^3 & \thinspace\operatorname{mod}\thinspace p = 8 \thinspace\operatorname{mod}\thinspace 5 = 3 \end{aligned} $$

דוגמה שנייה - האם 2 הוא שורש פרימיטיבי מודולו 7?

עכשיו נקח את הראשוני $p=7$. האם המספר $a=2$ הוא שורש פרימיטיבי מודולו $7$?

$$ \begin{aligned} a^2 & \thinspace\operatorname{mod}\thinspace p = 4 \thinspace\operatorname{mod}\thinspace 7 = 4 \\ a^5 & \thinspace\operatorname{mod}\thinspace p = 32 \thinspace\operatorname{mod}\thinspace 7 = 4 \end{aligned} $$

דוגמה שלישית - האם 3 הוא שורש פרימיטיבי מודולו 7?

אבל האם $a=3$ הוא שורש פרימיטיבי מודולו $7$? צריך לבדוק חזקות מ-$0$ עד $5$ (שהוא $p-2$).

$$ \begin{aligned} a^0 & \thinspace\operatorname{mod}\thinspace p = 1 \\ a^1 & \thinspace\operatorname{mod}\thinspace p = 3 \thinspace\operatorname{mod}\thinspace 7 = 3 \\ a^2 & \thinspace\operatorname{mod}\thinspace p = 9 \thinspace\operatorname{mod}\thinspace 7 = 2 \\ a^3 & \thinspace\operatorname{mod}\thinspace p = 27 \thinspace\operatorname{mod}\thinspace 7 = 6 \\ a^4 & \thinspace\operatorname{mod}\thinspace p = 81 \thinspace\operatorname{mod}\thinspace 7 = 4 \\ a^5 & \thinspace\operatorname{mod}\thinspace p = 243 \thinspace\operatorname{mod}\thinspace 7 = 5 \end{aligned} $$

כן!

לא אוכיח כאן את טענה א'. ההוכחה נמצאת בכל קורס בסיסי בתורת החבורות, ומי שמעוניינת בה מוזמנת גם לדון בתגובות 🙂

טענה ב': $2$ הוא שורש פרימיטיבי מודולו $37$.
(הדרך הכי קלה שאני מכיר להוכיח את זה היא פשוט לבדוק במחשב את כל 36 החזקות.)

מסקנה: כל החזקות של $2$, מ-$2^0$ עד $2^{32}$ (למעשה אפילו מ-$2^0$ עד $2^{35}$), נותנות תוצאות שונות זו מזו מודולו $37$!

איך מגיעים מכאן למה שרצינו?

טענה ג': כל subnet mask הוא פשוט $2^{32}$ פחות חזקה כלשהי של $2$. (תרגיל לקורא.)

מטענה ג', אפשר לכתוב

$$m = c - q$$

כאשר $c$ הוא קבוע אבסולוטי ($c=2^{32}$), ו-$q$ הוא חזקה כלשהי של $2$ בין $2^0$ ל-$2^{32}$.
לכן המשוואה הזו מתקיימת גם באופן מודולרי:

$$m \thinspace\operatorname{mod}\thinspace 37 = (c - q) \thinspace\operatorname{mod}\thinspace 37$$

לכן, אם $q \thinspace\operatorname{mod}\thinspace 37$ כולם שונים זה מזה (טענה ב'), אז גם $m \thinspace\operatorname{mod} 37$ כולם שונים זה מזה! (מש"ל.)

אפשר לחפור עוד קצת ולהגיע לבעיה לא פתורה במתמטיקה?

ברור!!! אז ככה:

כל מה שעשינו למעלה טוב ל-IPv4, שם הכתובות (והמסיכות) הן בגודל 32 ביט.
אבל מה קורה ב-IPv6? שם הכתובות (והמסיכות) הן בגודל 128 ביט. מה נעשה אז?

נעיין ב-OEIS, אנציקלופדיית סדרות המספרים, ונראה לאיזה ראשוניים $p$ אחרים מתקיימת “טענה ב'” (כלומר $2$ הוא שורש פרימיטיבי מודולו $p$).

אנחנו מחפשים משהו שיותר גדול מ-128. ואכן, כתוב באנציקלופדיה ש-131 הוא סבבה לנו. אז אפשר לקחת את מסיכת ה-IPv6, לעשות לה מודולו 131, ולהביא את התוצאה מטבלה בגודל 131 שנבנתה לבעיה.

ומה עם… IPv8?
אז IPv8 לא קיים עדיין, אני חושב, אבל אני עושה אקסטרפולציה: אם ב-IPv4 יש כתובות בגודל 32 ביט, וב-IPv6 יש כתובות בגודל 128 ביט, אז ב-IPv8 יש כמובן… כתובות בגודל 512 ביט.
גם עבור IPv8 אפשר לעיין באנציקלופדיה ולראות שהראשוני המתאים הוא 523.

ומה לגבי IPv10? ו-IPv12? ובאופן כללי, IPvK (גרסת IP שבה יש $2^{K+1}$ ביטים בכל כתובת)?
כדי לפתור את הבעיה עבורם, נצטרך למצוא מספרים ראשוניים גדולים יותר ויותר שמקיימים את “טענה ב'”, כלומר ש-$2$ הוא שורש פרימיטיבי עבורם.

האם נצליח? אנחנו לא יודעים:

השערת ארטין (1927): יש אינסוף ראשוניים ש-$2$ הוא שורש פרימיטיבי עבורם.

אם השערת ארטין נכונה, אז תמיד יהיה ראשוני שיאפשר לנו לעשות את הטריק הזה גם עבור מסיכות מאוד גדולות.
אם לא, אז החל מגודל מסויים (כנראה מאוד גדול) זה יהיה בלתי אפשרי, ונצטרך למצוא אלגוריתם אחר.
השאלה הזו כאמור לא פתורה, והחודש היא תחגוג 93 שנים מאז שהיא נשאלה.