Bins & Memory Allocations
मूलभूत जानकारी
प्रत्येक अनसॉर्टेड, छोटे और बड़े बिन्स के लिए प्रारंभिक पता एक ही एरे में है। इंडेक्स 0 अप्रयुक्त है, 1 अनसॉर्टेड बिन है, बिन्स 2-64 छोटे बिन्स हैं और बिन्स 65-127 बड़े बिन्स हैं।
टीकैश (प्रति थ्रेड कैश) बिन्स
जब एक थ्रेड एक चंक फ्री करता है, अगर यह टीकैश में आवंटित करने के लिए बड़ा नहीं है और संबंधित टीकैश बिन भरा नहीं है (पहले से ही 7 चंक्स), तो वहां आवंटित किया जाएगा। अगर यह टीकैश में नहीं जा सकता है, तो यह हीप लॉक का इंतजार करना होगा ताकि वह वैश्विक बिन्स में फ्री ऑपरेशन कर सके।
जब एक चंक आवंटित किया जाता है, अगर टीकैश में आवश्यक आकार का एक फ्री चंक है तो यह उसका उपयोग करेगा, अगर नहीं, तो यह हीप लॉक का इंतजार करना होगा ताकि वह वैश्विक बिन्स में एक ढूंढ सके या एक नया बना सके। इस मामले में एक और अनुकूलन भी है, इस मामले में, हीप लॉक के साथ होते हुए, थ्रेड अपना टीकैश हीप चंक्स के साथ भरेगा (7) अनुरोधित आकार के, इसलिए यदि उसे अधिक चाहिए, तो वह उन्हें टीकैश में पाएगा।
Tcache संरचनाएँ और कार्य
निम्नलिखित कोड में अधिकतम बिन और प्रति सूची टुकड़े, tcache_entry
संरचना देखना संभव है जो डबल मुक्ति से बचने के लिए बनाई गई है और tcache_perthread_struct
, एक संरचना जिसका प्रत्येक धागा बिन के प्रत्येक सूची के पते को संग्रहित करने के लिए प्रयोग करता है।
Tcache Indexes
टीकैश में कई बिन होते हैं जो आकार और प्रारंभिक पॉइंटर्स के आधार पर निर्भर करते हैं प्रत्येक इंडेक्स के पहले चंक और प्रति इंडेक्स चंक की मात्रा एक चंक के अंदर स्थित होती हैं। इसका मतलब है कि इस जानकारी के साथ चंक को ढूंढ़ना (सामान्यत: पहला) संभव है ताकि सभी टीकैश प्रारंभिक बिंदुओं और टीकैश चंक की मात्रा पता लगा सकें।
Fast bins
फास्ट बिन्स को छोटे चंकों के लिए मेमोरी आवंटन की गति बढ़ाने के लिए डिज़ाइन किया गया है जिन्हें एक त्वरित पहुंच संरचना में हाल ही में फ्री किए गए चंक रखकर उपयोग करने की अनुमति देते हैं। ये बिन्स एक लास्ट-इन, फर्स्ट-आउट (LIFO) दृष्टिकोण का उपयोग करते हैं, जिसका मतलब है कि हाल ही में फ्री किया गया चंक सबसे पहला है जो एक नए आवंटन अनुरोध होने पर पुनः उपयोग किया जाएगा। यह व्यवहार गति के लिए फायदेमंद है, क्योंकि एक स्टैक (LIFO) से ऊपर से डालना और हटाना (LIFO) एक कतार (FIFO) की तुलना में तेज होता है।
इसके अतिरिक्त, फास्ट बिन्स में एकल लिंक्ड लिस्ट का उपयोग किया जाता है, डबल लिंक्ड लिस्ट नहीं, जो गति को और बढ़ाता है। क्योंकि फास्ट बिन्स में चंक आसपास के नेबर्स के साथ मर्ज नहीं होते, इसलिए मध्य से हटाने की अनुमति देने वाली एक जटिल संरचना की आवश्यकता नहीं है। एकल लिंक्ड लिस्ट इन ऑपरेशन के लिए इस सरल और तेज है।
मूल रूप से, यहाँ यह होता है कि हेडर (पहले चंक के पॉइंटर को जांचने के लिए) हमेशा उस आकार के नवीन फ्री किए गए चंक की ओर पॉइंट कर रहा है। तो:
जब उस आकार का नया चंक आवंटित किया जाता है, हेडर एक उपयुक्त चंक की ओर पॉइंट कर रहा है। क्योंकि यह फ्री चंक अगले उपयोग के लिए अगले चंक की ओर पॉइंट कर रहा है, इस पते को हेडर में संग्रहीत किया जाता है ताकि अगली आवंटन जाने की जानकारी हो कि उपलब्ध चंक कहां से प्राप्त करें
जब एक चंक मुक्त किया जाता है, तो मुक्त चंक वर्तमान उपलब्ध चंक के पते को सहेजेगा और इस नवीन फ्री किए गए चंक के पते को हेडर में डाल दिया जाएगा।
लिंक्ड लिस्ट का अधिकतम आकार 0x80
है और वे इस प्रकार से संगठित हैं कि आकार 0x20
का एक चंक इंडेक्स 0
में होगा, आकार 0x30
का एक चंक इंडेक्स 1
में होगा...
फास्ट बिन्स में चंक उपलब्ध के रूप में सेट नहीं किए गए हैं इसलिए वे कुछ समय तक फास्ट बिन चंक के रूप में बनाए रखे जाते हैं बजाय उन्हें उनके आसपास के अन्य फ्री चंक्स के साथ मर्ज करने की क्षमता होने की।
अव्यवस्थित बिन
अव्यवस्थित बिन एक कैश है जिस्मे हीप प्रबंधक द्वारा मेमोरी आवंटन को तेज़ बनाने के लिए उपयोग किया जाता है। यहाँ यह कैसे काम करता है: जब एक प्रोग्राम एक चंक को मुक्त करता है, और अगर यह चंक एक टीकैश या फास्ट बिन में आवंटित नहीं किया जा सकता है और यह ऊपरी चंक के साथ टकरा नहीं रहा है, तो हीप प्रबंधक इसे तुरंत किसी विशिष्ट छोटे या बड़े बिन में नहीं डालता है। बजाय इसके, यह पहले किसी भी पड़ोसी फ्री चंक के साथ मर्ज करने की कोशिश करता है ताकि एक अधिक बड़ा फ्री मेमोरी ब्लॉक बना सके। फिर, यह नया चंक एक सामान्य बिन में रखता है जिसे "अव्यवस्थित बिन" कहा जाता है।
जब एक प्रोग्राम मेमोरी के लिए मांग करता है, तो हीप प्रबंधक अव्यवस्थित बिन की जाँच करता है कि क्या कोई पर्याप्त आकार का चंक है। अगर वह एक पाता है, तो वह इसे तुरंत उपयोग करता है। अगर अव्यवस्थित बिन में एक उपयुक्त चंक नहीं मिलता है, तो यह सभी चंक्स को इस सूची से उनके संबंधित बिन में ले जाता है, या तो छोटे या बड़े, उनके आकार के आधार पर।
ध्यान दें कि अगर एक बड़ा चंक 2 हिस्सों में विभाजित किया गया है और बाकी भाग MINSIZE से अधिक है, तो यह अव्यवस्थित बिन में वापस रखा जाएगा।
इसलिए, अव्यवस्थित बिन एक तरीका है मेमोरी आवंटन को तेज़ करने के लिए हाल ही में मुक्त मेमोरी को तेज़ी से पुनः उपयोग करके और समय ग्राहक खोज और मर्ज की आवश्यकता को कम करके।
ध्यान दें कि यदि चंक्स विभिन्न श्रेणियों के होते हैं, अगर एक उपलब्ध चंक दूसरे उपलब्ध चंक के साथ टकरा रहा है (यदि वे मूल रूप से विभिन्न बिन्स में होते हैं), तो वे मर्ज किए जाएंगे।
छोटे बिन
छोटे बिन बड़े बिनों से तेज होते हैं लेकिन फास्ट बिन्स से धीमे होते हैं।
62 के प्रत्येक बिन में एक ही आकार के चंक्स होंगे: 16, 24, ... (32 बिट में 504 बाइट तक और 64 बिट में 1024 तक की अधिकतम आकार). यह बिन को ढूंढने, एक स्थान को आवंटित करने और इन सूचियों पर प्रविष्टियों को डालने और हटाने में गति में मदद करता है।
यहाँ छोटे बिन का आकार बिन के सूचकांक के अनुसार कैसे निर्धारित किया जाता है:
सबसे छोटा आकार: 2*4*सूचीकांक (उदाहरण: सूचीकांक 5 -> 40)
सबसे बड़ा आकार: 2*8*सूचीकांक (उदाहरण: सूचीकांक 5 -> 80)
छोटे और बड़े बिन्स के बीच चयन करने के लिए फ़ंक्शन:
बड़े बिन
छोटे बिनों की तरह, जो निश्चित आकारों के टुकड़ों का प्रबंधन करते हैं, प्रत्येक बड़े बिन एक चंक आकार की श्रेणी का प्रबंधन करता है। यह अधिक लचीला है, जिससे सिस्टम विभिन्न आकारों को अलग-अलग बिन की आवश्यकता के बिना समायोजित कर सकता है।
एक मेमोरी आवंटक में, बड़े बिन छोटे बिनों के समाप्त होने पर शुरू होते हैं। बड़े बिनों के लिए सीमाएँ प्रगतिशील रूप से बढ़ती हैं, जिसका मतलब है पहला बिन 512 से 576 बाइट तक के चंक को कवर कर सकता है, जबकि अगला 576 से 640 बाइट तक को कवर करता है। यह पैटर्न जारी रहता है, सबसे बड़े बिन में सभी 1MB से ऊपर के चंक शामिल होते हैं।
बड़े बिन छोटे बिनों की तुलना में ऑपरेट करने में धीमे होते हैं क्योंकि उन्हें एक भिन्न चंक आकार की सूची को क्रमबद्ध करना और खोजना पड़ता है ताकि आवंटन के लिए सर्वोत्तम फिट मिल सके। जब एक चंक को बड़े बिन में डाला जाता है, तो उसे क्रमबद्ध किया जाना चाहिए, और जब मेमोरी आवंटित की जाती है, तो सिस्टम को सही चंक ढूंढना पड़ता है। यह अतिरिक्त काम उन्हें धीमा बनाता है, लेकिन क्योंकि बड़े आवंटन छोटे से कम होते हैं, इसे स्वीकार्य व्यापार माना जाता है।
यहाँ हैं:
32 बिन 64B श्रेणी के (छोटे बिनों के साथ टकराते हैं)
16 बिन 512B श्रेणी के (छोटे बिनों के साथ टकराते हैं)
8 बिन 4096B श्रेणी के (कुछ हिस्सा छोटे बिनों के साथ टकराता है)
4 बिन 32768B श्रेणी के
2 बिन 262144B श्रेणी के
शेष आकारों के लिए 1 बिन
शीर्ष टुकड़ी
बुनियादी रूप से, यह एक टुकड़ा है जिसमें सभी वर्तमान मेमोरी है। जब एक malloc किया जाता है, अगर कोई उपलब्ध फ्री चंक उपयोग के लिए नहीं है, तो यह टॉप चंक अपने आकार को कम करके आवश्यक स्थान देगा। टॉप चंक का पॉइंटर malloc_state
स्ट्रक्चर में संग्रहीत होता है।
इसके अतिरिक्त, शुरुआत में, अनसॉर्टेड चंक का उपयोग टॉप चंक के रूप में किया जा सकता है।
अंतिम शेष
जब malloc का उपयोग किया जाता है और एक चंक विभाजित किया जाता है (अनुक्रमण से या उदाहरण के लिए शेष बिन से), तो शेष चंक से बनाई गई चंक को अंतिम शेष कहा जाता है और इसका पॉइंटर malloc_state
संरचि में संग्रहीत किया जाता है।
आवंटन प्रवाह
जांचें:
मुक्ति प्रवाह
जांचें:
हीप फ़ंक्शन सुरक्षा जांच
हीप में प्रयुक्त फ़ंक्शनों द्वारा की जाने वाली सुरक्षा जांच की जानकारी के लिए देखें:
संदर्भ
Last updated