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

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

אינפורמציה מתחת לאפס

סיפורנו מתחיל בשאלה קטנה יותר אך מסתורית לא פחות. כשאנחנו כותבים פקודת malloc, אנחנו מציינים את מספר הבייטים שברצוננו לקבל, ומקבלים בחזרה אך ורק מצביע למקום מסוים בזיכרון. לאחר מכן, כשאנחנו שולחים את אותו המצביע לפקודת free, כל הבייטים שביקשנו מתפנים. איפה בדיוק נשמר מספר הבייטים שמשויכים למצביע הספציפי הזה? איך המיקרו-בקר יודע, על סמך כתובת בזיכרון בלבד, שהוא צריך לפנות שם X או Y בייטים?

התשובה היא שכאשר אנחנו מבקשים X בייטים ב-malloc, הקוד (והכוונה כאן לקוד שמיוצר על ידי הקומפיילר) דואג להקצות למעשה X+2. בשני הבייטים הראשונים נשמר מספר הבייטים שביקשנו, והשאר הם הנתונים עצמם; המצביע שמוחזר לנו הוא הכתובת של אזור הנתונים בלבד.

כאשר אנחנו קוראים ל-free עם מצביע לנתונים, הקוד הולך שני בייטים אחורה, קורא מהם את המספר שצריך לשחרר ופועל בהתאם. עכשיו, מה זה אומר "לפעול בהתאם"?

הקצאה בלי שחרור

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

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

משוחרר בכאילו

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

אם זה לא המצביע האחרון, אנחנו מוסיפים אותו ל"freelist" – רשימה מקושרת של מקומות פנויים, שמנוהלת על ידי הקוד מאחורי הקלעים.

לדוגמה, נניח שהקצינו ארבעה אזורים בזיכרון בעזרת malloc – אזורים A, B, C ו-D לפי סדר האלפבית. עכשיו אנחנו קוראים לפונקציה free כדי לשחרר את אזור C. הוא לא האחרון שהוקצה, אז אי אפשר סתם "להעלים" אותו. במקום זה, freelist מאותחלת כך שתצביע אליו. שני הבייטים של המספר נשארים כמו שהם, ושני הבייטים הבאים בשטח שהיה של C הופכים להיות מצביע לכתובת של המקום המשוחרר הבא. בינתיים אין כזה, אז הם יהיו 0.

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

וסוף כל סוף אנחנו מגיעים לרגע האמת: המשתמש קורא שוב ל-malloc כדי להקצות שטח חדש.

מיחזור פשוט

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

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

כמובן, אם לא נמצא שום מקום משוחרר מתאים, מתבצעת הקצאה "רגילה" אחרי פרמטר הקצה.

מיחזור מתקדם

אם נקצה ונשחרר שוב ושוב אזורים בגודל שונה בזיכרון, הכללים הנ"ל יביאו בסופו של דבר למצב לא רצוי: זיכרון שמחולק כמעט כולו לאזורים קטנטנים, תפוסים או ברשימה freelist. גם אם בפועל כמעט כל הזיכרון פנוי לשימוש חוזר, במצב כזה לא ניתן יהיה להקצות אזורים גדולים. בשפה המקצועית זה נקרא פרגמנטציה (Fragmentation), ואם אי פעם ביצעתם defragment לדיסק הקשיח שלכם כדי שיעבוד יותר טוב, זה דומה – קבצים שמפוזרים על פני הרבה אזורים קטנים ונפרדים מאוחדים למיקומים גדולים ורציפים.

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

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