Linux memory management 32-bit x86
Η μνήμη RAM αποτελεί έναν απο τους σημαντικότερους πόρους του συστήματος. Αν και τα σημερινά μεγέθη θα φαίνονταν τεράστια 20 χρόνια πριν, τα προγράμματα τείνουν να καταλαμβάνουν όλο και περισσότερο χώρο. Το ιδανικό σενάριο θα ήταν, για κάθε πρόγραμμα να υπάρχει η δική του ιδιωτική μνήμη, κάτι το οποίο (προς το παρών;) δεν είναι εφικτό. Οπότε κάπως πρέπει να χωρίσουμε την πίτα ώστε κανείς να μην μείνει παραπονεμένος. Εδώ έρχεται το λειτουργικό σύστημα το οποίο κάνει αυτή την δουλεία για εμάς. Θα δούμε πως γίνεται αυτό σε ένα σύστημα Linux 32-bit x86.
[:.Διεργασίες.:]
Κάθε διεργασία όταν φορτώνεται στην μνήμη, μέσω του λειτουργικού συστήματος, εκτελείται σε ένα πλήρως αποκομμένο περιβάλλον: δεν γνωρίζει την ύπαρξη άλλων διεργασιών, και το μόνο που βλέπει, είναι πως όλη η μνήμη της ανήκει. Ο χώρος αυτός ονομάζεται χώρος εικονικών διευθύνσεων (4Gb σε συστήματα 32-bit) και αποτελείται από τρία τμήματα: τμήμα κώδικα (code segment), τμήμα δεδομένων (data segmanet) και τμήμα στοίβας (stack segment).
[:code/text segment:]
Το code segment ή αλλιώς text segment, περιέχει τις εντολές μηχανής που παράχθηκαν από τον μεταγλωτιστή και τον συμβολομεταφραστή κατά την μετάφραση ενός προγράμματος, και αποτελούν τον εκτελέσιμο κώδικα του προγράμματος. Το τμήμα αυτό είναι read only, συνεπώς και το μέγεθός του σταθερό.
[:data segment:]
Το data segment παρέχει χώρο για την αποθήκευση των δεδομένων του προγράμματος. Χωρίζεται σε τρία μέρη: Initialized data (περιοχή δεδομένων με αρχικές τιμές), BSS (Block Started by Symbol) και την heap.
Initialized data: Ο χώρος αυτός περιέχει μεταβλητές και σταθερές μεταγλωττιστή οι οποίες έχουν αρχική τιμή όταν ξεκινάει το πρόγραμμα.
BSS: Οι global και static μεταβλητές που δεν έχουν αρχικοποιηθεί, εισάγωνται στο τμήμα BSS και αρχικοποιούνται σε μηδέν. Είναι ενδιαφέρον να αναφέρω πως αν ορίσουμε ένα πίνακα πχ static char buff[4048] ο μεταγλωτιστής τοποθετεί μία κεφαλίδα (ένα header) αμέσως μετά τον κώδικα και τα αρχικοποιημένα δεδομένα, η οποία λέει στο σύστημα πόσος χώρος πρέπει να εκχωριθεί. Στην περίπτωσή μας 4Kb. Με αυτό τον τρόπο αποφεύγεται η αποθήκευση 4Kb με μηδενικά στην μνήμη.
Heap: Σε αντίθεση με το text segment, το data segment μπορεί να αλλάξει μέγεθος. Αυτό γιατί τα οι τιμές των μεταβλητών τροποποιούνται συνεχώς και τα προγράμματα θέλουν να εκχωρίσουν δυναμικά μνήμη κατά την εκτέλεσή τους (πχ κλήση malloc). Η heap συνήθως αυξάνει “προς τα πάνω”, δηλαδή η μνήμη των δεδομένων που προσθετονται στην heap έχουν αριθμιτική τιμή μεγαλύτερη από τα προηγούμενα δεδομένα.
[:stack segment:]
Τέλος, στο stack segment αποθηκεύονται όλες οι τοπικές μεταβλητές. H στοίβα μεγαλώνει “προς τα κάτω” (αντίθετα με την heap) και συνήθως ξεκινάει από την κορυφή των εικονικών διευθύνσεων -0xC0000000- . Αρχικά το stack segment δεν είναι κενό. Περιέχει όλες τις μεταβλητές κελύφους και τις εντολές που δόθηκαν στο κέλυφος και ξεκίνησε το πρόγραμμα. Πχ όταν δίνουμε mkdir test στην στοίβα υπάρχει η συμβολοσειρά “mkdir test”.
Στον εικονικό χώρο διευθύνσεων κάθε διεργασίας υπάρχει ένα σταθερά δεσμευμένο κομμάτι από τον πυρήνα -kernel space- (συγκεκριμένα ένα κομμάτι μεγέθους 1Gb). Ο kernel space είναι μαρκαρισμένος ως privilaged code (ring0), αν δηλαδή κάποιο πρόγραμμα τον αγγιξει έχουμε page fault. Ο κώδικας του πυρήνα είναι πάντα παρών στην φυσική μνήμη του συστήματος, αντίθετα με τον κώδικα των διεργασιών ο οποίος φορτώνεται στην μνήμη όταν συμβαίνει μια εναλλαγή διεργασιών, και δεν είναι ορατός σε επίπεδο χρήστη παρα μόνο όταν η διεργασία “παγιδευτεί” στον πυρήνα.
Ακόμα, υπάρχει η δυνατότητα χαρτογράφησης ενός αρχείου (πχ κοινόχρηστες βιβλιοθήκες) στον χώρο διευθύνσεων της διεργασίας ώστε να μπορεί να διαβαστεί και να γράφεται σαν να ήταν byte στην μνήμη. Αυτό διευκολύνει πολύ την τυχαία πρόσβαση σε αυτό, αντίθετα με τις κλήσεις συστήματος.
Όλα αυτά μπορούμε να τα δούμε πρακτικά σε ένα απλό προγραμμα. Έστω το memory.c
#include
static int a = 1;static char buffer[4048];
int main(void)
{
int z = 0;
}
mpekatsoula@mpekatsospito:~/Desktop$ ls -l memory-rwxr-xr-x 1 mpekatsoula mpekatsoula 7149 2010-10-17 15:44 memorympekatsoula@mpekatsospito:~/Desktop$ size --format=SysV memorymemory:
section size addr
.interp 19 134512948
.note.ABI-tag 32 134512968
.note.gnu.build-id 36 134513000
.hash 36 134513036
.gnu.hash 32 134513072
.dynsym 64 134513104
.dynstr 69 134513168
.gnu.version 8 134513238
.gnu.version_r 32 134513248
.rel.dyn 8 134513280
.rel.plt 16 134513288
.init 48 134513304
.plt 48 134513352
.text 364 134513408
.fini 28 134513772
.rodata 8 134513800
.eh_frame 4 134513808
.ctors 8 134520588
.dtors 8 134520596
.jcr 4 134520604
.dynamic 208 134520608
.got 4 134520816
.got.plt 20 134520820
.data 12 134520840
.bss 4080 134520864
.comment 35 0
Total 5231
Αρχικά βλέπουμε το πρόγραμμα το οποίο καταλαμβάνει χώρο 7149bytes στον δίσκο, αλλά τελικά φορτώνονται 5231. Αυτός ο extra χώρος καταλαμβάνεται από τις ονομασίες των μεταβλητών και των συναρτήσεων που έχει δώσει ο προγραμματιστής, και από πληροφορίες σχετικά με κοινόχρηστες βιβλιοθήκες που μπορεί να χρησιμοποιεί το πρόγραμμα.
Ο πυρήνας κάνει randomize τις περιοχές της stack, της heap και του memory mapping segment(όσο αυτό είναι εφικτό στον χώρο των 32-bit διευθύνσεων), προσθέτοντας ένα random offset στην αρχική τους διεύθυνση, για κάθε διεργασία ξεχωριστά (για αυξημένη προστασία και ασφάλεια). Ο κώδικας που κάνει randomize την stack, την heap και το memory mapping segment είναι ο εξής:
Stack (/fs/binfmt_elf.c)
static unsigned long randomize_stack_top(unsigned long stack_top) {
unsigned int random_variable = 0;
if ((current->flags & PF_RANDOMIZE) && !(current->personality & ADDR_NO_RANDOMIZE)) { random_variable = get_random_int() & STACK_RND_MASK;
random_variable <<= PAGE_SHIFT;
}
#ifdef
CONFIG_STACK_GROWSUP
return PAGE_ALIGN(stack_top) + random_variable;
#else
return PAGE_ALIGN(stack_top) - random_variable;
#endif
}
Heap (/arch/x86/kernel/process_32.c)
unsigned long arch_randomize_brk(struct mm_struct *mm){
unsigned long range_end = mm->brk + 0x02000000;
return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
}
Memory mapping segment (/arch/x86/mm/mmap.c)
static unsigned long mmap_base(void){
unsigned long gap = current->signal->rlim[RLIMIT_STACK].rlim_cur;
if (gap < MIN_GAP)
gap = MIN_GAP;
else if (gap > MAX_GAP)
gap = MAX_GAP;
return PAGE_ALIGN(TASK_SIZE - gap - mmap_rnd());
}
Είναι λογικό να αναρωτηθεί κανείς τι συμβαίνει στην περίπτωση που η stack μεγαλώσει πάρα πολύ και ξεπεράσει το stack limit. Αν γίνει αυτό, έχουμε page fault και καλείτε η
expand_stack() (/mm/mmap.c)
int expand_stack(struct vm_area_struct *vma, unsigned long address){
return expand_downwards(vma, address);
}
η οποία με την σειρά της καλέι την
acct_stack_growth() (/mm/mmap.c)
static int acct_stack_growth(struct vm_area_struct * vma, unsigned long size, unsigned long grow)
{
struct mm_struct *mm = vma->vm_mm;
struct rlimit *rlim = current->signal->rlim;
unsigned long new_start;
/* address space limit tests */
if (!may_expand_vm(mm, grow))
return -ENOMEM;
/* Stack limit test */
if (size > rlim[RLIMIT_STACK].rlim_cur)
return -ENOMEM;
/* mlock limit tests */
if (vma->vm_flags & VM_LOCKED) {
unsigned long locked;
unsigned long limit;
locked = mm->locked_vm + grow;
limit = rlim[RLIMIT_MEMLOCK].rlim_cur >> PAGE_SHIFT;
if (locked > limit && !capable(CAP_IPC_LOCK))
return -ENOMEM;
}
/* Check to ensure the stack will not grow into a hugetlb-only region */
new_start = (vma->vm_flags & VM_GROWSUP) ? vma->vm_start : vma->vm_end - size;
if (is_hugepage_only_range(vma->vm_mm, new_start, size))
return -EFAULT;
/* * Overcommit.. This must be the final test, as it will * update security statistics. */
if (security_vm_enough_memory(grow))
return -ENOMEM;
/* Ok, everything looks good - let it rip */
mm->total_vm += grow;
if (vma->vm_flags & VM_LOCKED)
mm->locked_vm += grow;
vm_stat_account(mm, vma->vm_flags, vma->vm_file, grow);
return 0;
}
για να τσεκάρει αν μπορεί να μεγαλώσει η stack. Αν έχει φτάσει στο μέγιστο μέγεθος και προσπαθήσει να μεγαλώσει τότε έχουμε stack overflow και επομένως Segmentation Fault.
Εδώ βλέπουμε πως δύο διεργασίες μπορεί να βρίσκονται στην μνήμη (σκεφτείτε το για πολλές):
[.:Κλήσεις Συστήματος:.]
Τα περισσότερα συστήματα Linux διαθέτουν κλήσεις συστήματος για την διαχείρηση μνήμης. Οι πιο συνηθισμένες είναι οι εξής:
brk:
Καθορίζει το μέγεθος του τμήματος δεδομένων(data segment) της διεργασίας, αλλάζοντας την θέση της program break, η οποία δηλώνει σε ποιο σημείο τελειώνει το data segment. Αν αυξήσουμε την program break εκχωρούμε περισσότερη μνήμη στην διεργασία και αντίστοιχα αν την μειώσουμε, αφαιρούμε.
#include <unistd.h>
int brk(void *addr);
mmap:
Η mmap χαρτογραφεί ένα αρχείο στην μνήμη. Η αρχική διεύθυνση του αρχείο προσδιορίζεται στην addr, η οποία αν είναι 0 τότε το σύστημα προσδιορίζει μόνο του την διεύθυνση. Η παράμετρος len προσδιορίζει πόσα byte πρέπει να χαρτογραφηθούν, η prot την προστασία, η flags αν το αρχείο θα έιναι ιδιωτικό η κοινόχρηστο και τέλος η offset την θέση του αρχείου όπου θα ξεκινήσει η χαρτογράφηση.
#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
munmap:
Αντίθετα με την mmap η munmap αποχαρτογραφεί ένα αρχείο.
#include <sys/mman.h>
int munmap(void *addr, size_t length);
Για παράδειγμα ας δουμε τι γίνεται όταν καλούμε την malloc. Η malloc παίρνει ως όρισμα το μέγεθος της μνήμης που θέλουμε να δεσμεύσουμε και αν δεν υπάρχει ήδη αρκετός χώρος στην heap, προσπαθεί να δεσμεύσει μνήμη μέσω της κλήσης sbrk (αυξάνει το data segment κατα increment bytes). Ας δούμε ένα προγραμματάκι, έστω το..:
memory2.c
#include <stdio.h>
#include <sys/types.h>
main()
{
int *x;
printf("sbrk(0) before malloc(4): 0x%x\n", sbrk(0)); //τιμή της program break πριν την κλήση τρης malloc
x = (int *) malloc(4);
printf("sbrk(0) after `x = (int *) malloc(4)': 0x%x\n", sbrk(0)); //τιμή της program break μετά την κλήση τρης malloc
printf("x = 0x%x\n", x); //διεύθυνση της x}[/code]
mpekatsoula@mpekatsospito:~/Desktop$ ./memory2
sbrk(0) before malloc(4): 0x94e4000
sbrk(0) after `x = (int *) malloc(4)': 0x9505000x = 0x94e4008
Σημείωση: αν το όρισμα της sbrk είναι 0, μας επιστρέφει την τρέχουσα τιμή της program break.
[.:Υλοποίηση της διαχείρησης μνήμης στον πυρήνα:.]
Αφού είδαμε όλα τα παραπάνω, το πως βλέπει μία διεργασία την μνήμη, πως δεσμεύει περισσότερη μνήμη κλπ, ήρθε η ώρα να περάσουμε στο επίπεδο του πυρήνα. Πως διαχειρίζετε δηλαδή την φυσική μνήμη. Πριν ξεκινήσω, να τονίσω πως ο πυρήνας βρίσκεται πάντα στην μνήμη "καρφιτσωμένος" (pinned), και κανένα τμήμα του δεν αφαιρείται ΠΟΤΕ από την μνήμη.
Όπως είπαμε, ο πυρήνας χωρίζει τα 4Gb του εικονικού χώρου διευθύνσεων σε 1Gb για αυτόν και 3Gb για την διεργασία. Δεν σημαίνει πως ο πυρήνας χρειάζεται τόση μνήμη για αυτόν, αλλά με αυτό τον τρόπο μπορεί να διαχειρίζεται όλη την φυσική μνήμη. Ο πυρήνας μπορεί να διευθετίσει μόνο 1Gb μνήμης, δηλαδή μέγιστο 1Gb φυσικής μνήμης (γιατί χαρτογραφεί απευθείας όλο το τμήμα εικονικών του διευθύνσεων στην φυσική μνήμη). Όμως υπάρχουν λύσεις για την χρησιμοποίηση έως και 64Gb μνήμης. Αναλυτικότερα, η φυσική μνήμη διακρίνει τρεις ζώνες:
ZONE_DMA:Χρησιμοποιείται από μερικές συσκευές (πχ [url=http://en.wikipedia.org/wiki/Industry_Standard_Architecture]ISA cards[/url]) για μεταφορά δεδομένων, και βρίσκεται στο χαμηλότερο μέρος της φυσικής μνήμης , μεταξύ 0-16Mb
ZONE_NORMAL:Τα 16 έως τα 896Mb αποτελούν την ZONE_NORMAL. Περιέχει δεδομένα τα οποία ο πυρήνας χρειάζεται συχνά να προσπελάζει.Η ZONE_NORMAL μαζί με την ZONE_DMA είναι οι μόνες που μπορούν να χαρτογραφηθούν απευθείας στον πυρήνα.
ZONE_HIGHMEM:Η ζώνη HIGHMEM βρίσκεται πάνω από τα 896Mb.
Μία περιοχή της μνήμης του πυρήνα(128Μb), χρησιμοποιείται για να αποθηκευθούν δομές του πυρήνα, πληροφορίες για τον πίνακα περιγραφέα σελίδας (mem_map) και πίνακες σελίδων. Τα 128Mb αυτά, δεν χαρτογραφούνται στην μνήμη, οπότε μας μένουν 896Mb για την ZONE_NORMAL.
Για να χρησιμοποιήσει λοιπόν ο πυρήνας μνήμη άνω του 1Gb,χαρτογραφεί σελίδες από την ΖΟΝΕ_HIGHMEM στην ZONE_NORMAL. Χαρτογραφεί δηλαδή σελίδες στον εικονικό χώρο διευθύνσεων του πυρήνα. Αυτό γίνεται με τις συναρτήσεις kmap(), kunmap(), kmap_atomic() και kunmap_atomic().
H συνάρτηση kmap σου δίνει μόνιμη χαρτογράφηση ακόμα και αν μεταφερθείς σε άλλη CPU (χρσιμοποιεί global lock). Δεν συνηθίζεται όμως, λόγο του ότι σε συστήματα SMP, μπορεί να προκαλέσει bottleneck. Έτσι συνηθως χρησιμοποιούνται οι kmap_atomic() και kunmap_atomic().
Όπως ανέφερα και πριν, ο πυρήνας διατηρεί ένα πίνακα περιγραφέων σελίδων (page descriptors), ή αλλιώς mem_map. Κάθε page descriptor έχει ένα δείκτη προς το χώρο διευθύνσεων στον οποίο ανήκει, και στην περίπτωση που η σελίδα είναι ελεύθερη, ένα ζεύγος δεικτών επιτρέπει την δημιουργία διπλά συνδεδεμένων λιστών με άλλους page descriptors έτσι ώστε να διατηρούνται μαζί όλα τα πλαίσια των ελεύθερων σελίδων. Το μέγεθος του mem_map συνήθως καταλαμβάνει λιγότερο από 1% της φυσικής μνήμης.
Ακόμα ο πυρήνας διατηρεί και ένα περιγραφέα ζώνης (zone descriptor), ο οποίο περιέχει πληροφορίες για την σωστή αξιοποίηση την μνήμης μέσα σε κάθε ζώνη. Δηλαδή πληροφορίες όπως ο αριθμός ενεργών ή ανενεργών σελίδων κλπ. Τέλος υπάρχει και ένας περιγραφέας κόμβου οποίος περιέχει πληροφορίες σχετικά με τη χρήση της μνήμης.
[:Σελιδοποίηση:]
Η ιδέα πίσω από την σελιδοποίηση στο Linux είναι η εξής: Μία διεργασία δεν χρειάζεται να έιναι ολόκληρη στην μνήμη για να εκτελεστεί. Αρκεί να βρίσκονται οι πίνακες σελίδων της και η user structure. Αν αυτά μεταφερθούν στην μνήμη, η διεργασία θεωρείται ότι βρίσκεται στην μνήμη και μπορεί να χρονοπρογραμματιστεί η εκτέλεσή της. Η σελιδοποίηση υλοποιείται εν μέρη από τον πυρήνα και εν μέρη από μία διεργασία, την page daemon,η οποία όταν αφυπνίζεται ελένχει αν υπάρχει κάποια διεργασία προς εκτέλεση.
Το Linux χρησιμοποιεί μια μέθοδο σελιδοποίησης τεσσάρων επιπέδων (από τον 2.6.11). Οι πίνακες σελίδων ονομάζονται:
Καθολικός κατάλογος σελίδων - Page Global DIr
Άνω κατάλογος σελίδων - Page Upper Dir
Μεσαίος κατάλογος σελίδων - Page Middle Dir
Πίνακας σελίδων σελίδων - Page table
Ο καθολικός κατάλογος σελίδων περιέχει αρκετές διευθύνσεις του άνω καταλόγου, ο άνω του μεσαίου κοκ.(πιστεύω η εκόνα αυτή είναι αρκετά χαρακτηρηστική και δεν χρειάστηκε να κάνω κάποια δικιά μου)
Έτσι αν θέλουμε να μεταφράσουμε μία λογική διεύθυνση σε μία φυσική, πρέπει πρώτα να βρούμε την λεγόμενη linear address (γραμμική διεύθυνση(;)). Την linear address την βρίσκουμε μέσω της MMU(Memory Management Unit - Μονάδα Διαχείρισης Μνήμης). Από εκεί, η linear address μεταφράζεται στην physical address μέσω του Paging Unit. Επιπλέον αν το σύστημα δεν είναι σε κατάσταση PAE, δύο επίπεδα σελίδων είναι αρκετά. Έτσι απενεργοποιείται ο άνω κατάλογος και ο μεσαίος κατάλογος (απλά λέμε ότι περέχουν 0bits).Τέλος τα τμήματα κώδικα και τα αρχεία που χαρτογραφούνται στην μνήμη, σελιδοποοιούνται και στον δίσκο. Ότιδήποτε άλλο, σελιδοποιείται και στην περιοχή εναλλαγής, κοινώς swap area.
Γενικά το όλο θεμα είναι τεράστιο για να καληφθεί σε 5-6 σελίδες (ολόκληρα βιβλία υπάρχουν). Πιστεύω ότι κάποιος θα πάρει μία γενική ιδέα και φυσικά όποιον τον ενδιαφέρει περισσότερο μπορεί να ακολουθήσει τα λινκς από κάτω. Προσωπικά ήθελα μία όσο το δυνατόν καλύτερη άποψη για το πως διαχειρίζεται το Linux την μνήμη (κυρίως για προγραμματισμό), και παράλληλα έιπα να γράψω αυτό το αρθράκι. That's all ;)
Πηγές:
[1]: Modern Operating Systems, 3rd Edition by Andrew S. Tanenbaum
[2]: Understanding the Linux Kernel By Daniel Pierre Bovet, Marco Cesatí
[3]: man pages
[4]: http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory by Gustavo Duarte
[5]: http://wikipedia.org/
[6]: http://lxr.linux.no/
[7]:http://linux-mm.org/
[8]: http://kerneltrap.org/node/2450
[9]: http://www.informit.com/articles/article.aspx?p=173438 by Arnold Robbins