Heap management

[Giorgos Keramidas]

On 2006-06-03 00:53, Pistiolis Konstantinos <kpistiolis at hellug.gr> wrote:
>> ...
>> Διάβασα για πιθανόν caching που κάνει η μνήμη, οπότε φτιάχνω ένα
>> προγραμματάκι που κάνει malloc όση ελεύθερη έχει απομείνει ώστε να το
>> στρεσάρω όσο μπορώ, μπας και την δώσει την άτιμη. Το αποτέλεσμα είναι
>> οτι δεν την δίνει αυτή την μνήμη.
>>
>> Χρησιμοποιώ το top & ps για τα συμπεράσματα καθώς και την δομή
>> mallinfo()[1] για πιο ακριβή συμπεράσματα. Επίσης χρησιμοποίησα και το
>> nmap και είδα οτι όλη αυτή η μνήμη που δεσμεύεται είναι στο heap.
>
> Τη μνήμη τη ζητάει το πρόγραμμά σου από το λειτουργικό και μετά τη
> διαχειρίζεται η malloc(), πράγμα που σημαίνει ότι γενικά πάντα θα
> έχει πάρει περισσότερη μνήμη απ' αυτή που χρησιμοποιείς.  Όταν τώρα
> κάνεις free() αυτό δε σημαίνει ότι η μνήμη θα πρέπει να αποδοθεί
> αμέσως (ή σήμερα...) στο λειτουργικό. Αυτό το αποφασίζει η υλοποίηση
> της malloc() και μάλιστα οι διαπραγματεύσεις με το λειτουργικό
> γίνονται σε μεγαλύτερα κομάτια (που σημαίνει, ότι αν μετά τις free()
> υπάρχουν πολλά σκόρπια κομάτια χρησιμοποιημένης μνήμης ίσως και να
> μη γίνεται)
>
> Δεν ξέρω πάντως αν η malloc() λαμβάνει υπ' όψιν το φόρτο του
> συστήματος για να επισπεύσει την απελευθέρωση μνήμης, δηλαδή ίσως να
> μην πετυχαίνεις τίποτε αν ένα άλλο προγραμματάκι ζητάει μνήμη.

Ναι, σε μερικές υλοποιήσεις της malloc() αυτό γίνεται.  Συνήθως, η
μνήμη που είναι over-allocated επιστρέφεται στον πυρήνα μόνο όταν το
σύστημα αποτύχει να κάνει allocate άλλη μνήμη.

Για παράδειγμα...

Πρόσφατα ξεκίνησα να κάνω port σε FreeBSD την libumem() του Solaris 9,
οπότε μπορώ να σου πώ τι κάνει αυτή.  Ενα thread καλεί περιοδικά
την umem_reap() function, η οποία κανονίζει ώστε κάποια στιγμή στο
μέλλον να τρέξει ένας reaping (free) αλγόριθμος σε κάθε umem cache από
allocated pages.  Η ίδια umem_reap() τρέχει όταν κάποιο allocation
αποτύχει, ελπίζοντας ότι έτσι θα ελευθερωθεί αρκετή μνήμη ώστε να
ικανοποιηθεί το allocation που απέτυχε.  Υστερα το failed allocation
ξανατρέχει, με την ελπίδα ότι η umem_reap() έχει ελευθερώσει αρκετή
μνήμη ώστε να δουλέψουν όλα σωστά.

Ο slab allocator πάνω στον οποίο βασίστηκε η libumem, έχει ενδιαφέρον
όνομα και πρόσφατα ο Jeff Bonwick αποκάλυψε από που πήρε την ιδέα για το
όνομα 'slab' allocator:

    http://blogs.sun.com/roller/page/bonwick?entry=now_it_can_be_told

Δεν έχω τελειώσει ακόμα το διάβασμα του jemalloc allocator, που έγραψε
ο Jason Evans για multi-threaded FreeBSD εφαρμογές (αύριο λογικά
θα έχω τελειώσει με το src/lib/libc/stdlib/malloc.c του FreeBSD
7.0-CURRENT) ή τη μελέτη της malloc() που έχει η glibc του Linux,
οπότε δε μπορώ να σου πω ακριβώς πώς γίνεται το ίδιο πράγμα σε αυτούς
τους allocators, αλλά αν ακόμα υπάρχιε ενδιαφέρον για το θέμα ελπίζω
σύντομα να έχω στοιχεία και γι αυτούς.

Για όποιον ενδιαφέρεται περισσότερο για το θέμα, προτείνω τα παρακάτω
publications.  Σε [brackets], ύστερα από το reference των κειμένων,
υπάρχει και το URL από το οποίο μπορείτε να διαβάσετε το κείμενο:

---------------------------------------------------------------------------

[1]  Berger ED and Feng Y (2005) A locality-improving dynamic memory
     allocator.  Technical Report TR09-05, Department of Computer
     Science, University of Massachusetts Amherst, 2005.
     [ http://citeseer.ist.psu.edu/727427.html ]

[2]  Bohra A, Gabber E (2001). Are Mallocs Free of Fragmentation?
     In USENIX 2001 Annual Technical Conference: FREENIX Track
     [ http://citeseer.ist.psu.edu/440671.html ]

[3]  Bonwick J (1994) The Slab Allocator: An Object-Caching Kernel Memory
     Allocator.  In USENIX Summer 1994 Technical Conference, 1994.
     [ http://citeseer.ifi.unizh.ch/bonwick94slab.html ]

[4]  Bonwick J, Adams J (2001) Magazines and Vmem: Extending the Slab
     Allocator to Many CPUs and Arbitrary Resources. In Proceedings of
     the 2001 USENIX Annual Technical Conference
     [ http://citeseer.ifi.unizh.ch/bonwick01magazines.html ]

[5]  Evans J (2006) A Scalable Concurrent malloc(3) Implementation for
     FreeBSD.  In BSDCAN 2006.
     [ http://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf ]

[6]  Kamp PH (1998) Malloc(3) revisited. In USENIX 1998 Annual Technical
     Conference: Invited Talks and FREENIX Track, 193­198
     [ http://phk.freebsd.dk/pubs/malloc.pdf ]

[7]  Larson P, Krishnan M (1998) Memory allocation for long-running
     server applications. In Proceedings of the International Symposium
     on Memory Management (ISSM), 176­185
     [ http://citeseer.ist.psu.edu/221661.html ]

[8]  Lever C, Boreham D (2000) malloc() Performance in a Multithreaded
     Linux Environment. In USENIX 2000 Annual Technical Conference:
     FREENIX Track
     [ http://citeseer.ist.psu.edu/lever00malloc.html ]

[9]  Wilson PR, Johnstone MS, Neely M, Boles D (1995) Dynamic Storage
     Allocation: A Survey and Critical Review. In Proceedings of the 1995
     International Workshop on Memory Management
     [ http://citeseer.ist.psu.edu/wilson95dynamic.html ]

---------------------------------------------------------------------------