C -> malloc: Wann gilt Speicher als belegt?

Das hat nichts mit C zu tun sondern mit der Speicherverwaltung Deines 
Betriebssystems. Insofern kann man die Frage auch nicht abschließend 
beantworten, ohne zu wissen, mit welchem OS Du arbeitest. In der Regel 
ist es aber so, dass Du keinen physischen Speicher anfordern kannst, 
sondern nur virtuellen. Die Zuordnung zwischen physischem und virtuellem 
Speicher ist nicht fest und kann sich jederzeit ändern. Das passiert zum 
Beispiel, wenn Speicherinhalte in den Swap ausgelagert werden. Es ist 
durchaus möglich, dass Dein OS eine Zuordnung erst vornimmt, wenn auf 
den Speicher tatsächlich zugegriffen wird.

Kaj G. schrieb:
> Wodran liegt das?

Nennt sich "lazy allocation". Damit Programme, die "auf Vorrat" große 
Speichermengen allokieren, diese nicht unnötig belegen, wird der 
Speicher ihnen erst zugewiesen, wenn sie ihn auch tatsächlich benutzen.
Ein anderes Stichwort in dem Zusammenhang ist "memory overcommit".

Rolf M. schrieb:
> Nennt sich "lazy allocation".
Ah, okay. Danke.

Rolf M. schrieb:
> Damit Programme, die "auf Vorrat" große
> Speichermengen allokieren, diese nicht unnötig belegen, wird der
> Speicher ihnen erst zugewiesen, wenn sie ihn auch tatsächlich benutzen.
Funktioniert ja aber auch nur begrenzt. Wenn ich den Speicher mit 
calloc() anfordere, wird er direkt intialisiert und gilt damit als 
belegt, auch wenn ich ihn niemals benutze. Aber ja, ich verstehe den 
Sinn hinter dieser Strategie. Danke.

Grüße

Linuxer schrieb:
> Kaj G. schrieb:
>> calloc() anfordere, wird er direkt intialisiert
>
> Nicht zwingend. Er könnte auch erst beim ersten Lesezugriff tatsächlich
> reserviert und initialisiert werden.

Oder beim ersten Schreibzugriff (copy-on-write on zero-filled page).

https://en.wikipedia.org/wiki/Copy-on-write

Mikro 7. schrieb:
> Linuxer schrieb:
>> Kaj G. schrieb:
>>> calloc() anfordere, wird er direkt intialisiert
>>
>> Nicht zwingend. Er könnte auch erst beim ersten Lesezugriff tatsächlich
>> reserviert und initialisiert werden.
>
> Oder beim ersten Schreibzugriff (copy-on-write on zero-filled page).

Wozu sollte man bei einem Schreibzugriff vor diesem erst noch eine Null 
reinschreiben, die dann sofort überschrieben wird?

Rolf M. schrieb:
>> Oder beim ersten Schreibzugriff (copy-on-write on zero-filled page).
>
> Wozu sollte man bei einem Schreibzugriff vor diesem erst noch eine Null
> reinschreiben, die dann sofort überschrieben wird?

Anders:

Das Betriebssystem teilt neuen Speicher implizit als mit Nullen
gefüllt zu (damit verhindert man, dass sensible Daten anderer Prozesse
„lecken“).  Das kann es erst einmal virtuell machen: es merkt sich
bei der Anforderung (erster Teil des calloc()), dass später hier eine
mit Nullen zu füllende Seite anzubieten ist.  Dann kommt der zweite
Teil von calloc(), das Schreiben eines großen Blocks Nullen.  Das
Betriebssystem stellt fest, dass diese Operation am aktuellen Zustand
(später wird mal eine mit Nullen gefüllte Seite bereitgestellt) gar
nichts ändert – und tut erstmal nichts.

Erst, wenn entweder von 0 verschiedene Daten in die Seite geschrieben
werden sollen oder aus der Seite was gelesen, wird sie physisch
bereitgestellt.

Setzt natürlich voraus, dass das OS eine effiziente Möglichkeit hat,
das Beschreiben mit ausschließlich Nullen durch den Prozess zu
erkennen.

Es ging ja darum, einen Schreibzugriff mit nur Nullen gar nicht erst
auszuführen.

Jörg W. schrieb:

> Erst wenn [...] aus der Seite was gelesen, wird sie physisch
> bereitgestellt.

Es wird eine zero-filled page bereitgestellt. Warum sollte beim Lesen 
eine neue physische Zuordnung durchgeführt werden? Diese sollte erst 
beim Schreibzugriff passieren. Das ist doch gerade die Idee des 
copy-on-write, oder nicht?

jockel schrieb:

> Ja. aber du solltest mal nachgucken, was calloc macht ;)

Erleuchte mich.

jockel schrieb:
> jockel schrieb:
>> Danach kann der Schreibzugriff ausgeführt werden, auch wenn er 0 ist. So
>> ist wenig Speicher verschwendet und die Zugriffe sind trotzdem
>> effizient.
>
> Ergänzung: Setzt natürlich voraus, dass die calloc-implementierung das
> weiß und die entsprechende null-Alloziierung aufruft, statt alles mit
> memset zu nullen.

Wenn sie das wüßte könnte man sicher noch ein paar kleine Prozente 
rausquetschen. Aber eigentlich geht es ja darum, nur reservierten 
Speicher nicht nullen zu müssen, sondern dies erst bei Zugriff zu tun. 
Sozusagen "demand clearing". Damit kann man auch nicht sehen, was vorher 
in der Seite stand. Aber man muß auch nicht den Stack einer Thread (gilt 
für jedes Multithreading-OS) von teils mehreren MB vorab nullen.
Und man darf auch nicht erwarten, daß ein "memory_allocate" ans OS, wie 
auch immer es heißt, Speicher sofort zur Verfügung stellen würde. Da 
werden nur die Verwaltungsstrukturen angelegt, die dann erstmal "nicht 
vorhandene" Speicherseiten beinhalten. Bei Zugriff wird dann physischer 
Speicher zugeordnet und diese Speicherseite(n) dann initialisiert. Zu 
Null, oder bei gemapped Fileimages (z.B. auch Programmen), mit dem 
zugehörenden Inhalt des Files.

Peter II schrieb:
> Wenn es wirklich um Schutz von Daten geht, müsse er mit 0 überschrieben
> werden, wenn man ihn freigibt.

Nein, musst du nicht.  Er kann ja kernel-intern auch noch „schmutzig“
bleiben.  Wenn der Kernel ihn später bspw. als disk buffer benutzen
will und sich sicher ist, dass er durch anderweitige Daten geplättet
wird (von der Platte gelesen), dann wäre es Verschwendung, ihn
bereits „vorsorglich“ ausgenullt zu haben.

Erst, wenn man ihn an eine nicht mehr vertrauenswürdige Instanz
vergibt (einen Prozess halt), muss er genullt werden.

> Ein "böser" Prozess braucht einfach nur malloc aufzurufen und nicht
> calloc um an fremde Daten zu kommen.

Nein, du hast das nicht verstanden: das OS gibt immer nur ausgenullte
Seiten neu an einen Prozess.  Auch, wenn dieser dann nur malloc()
macht, wenn er darauf zugreift (und der Bereich nicht innerhalb des
Prozesses bereits vorher genutzt worden ist) ist er mit Nullen gefüllt
(es sei denn, das malloc() füllt ihn mit was anderem, das steht ihm
natürlich frei).

Jörg W. schrieb:
> Das Betriebssystem teilt neuen Speicher implizit als mit Nullen
> gefüllt zu (damit verhindert man, dass sensible Daten anderer Prozesse
> „lecken“).  Das kann es erst einmal virtuell machen: es merkt sich
> bei der Anforderung (erster Teil des calloc()), dass später hier eine
> mit Nullen zu füllende Seite anzubieten ist.  Dann kommt der zweite
> Teil von calloc(), das Schreiben eines großen Blocks Nullen.

Wenn calloc() den Speicher vom Betriebssystem anfordert und das ihn mit 
Nullen vollschreibt, wozu sollte calloc() das dann nochmal machen?
Ich sehe da zwei Fälle in calloc(): Entweder es stellt Speicher bereit, 
den es quasi von früher noch hat. Dann muss es den explizit nullen. Oder 
es fordert vom Betriebssystem neuen Speicher an. Dann ist er von diesem 
schon genullt, und calloc muss nichts mehr tun.

Rolf M. schrieb:
> Oder
> es fordert vom Betriebssystem neuen Speicher an. Dann ist er von diesem
> schon genullt, und calloc muss nichts mehr tun.

Damit hatte ich eigentlich gerechnet. Linux scheint das allerdings nicht 
zu machen (gestern auf amd64 und RPi ausprobiert: malloc+memset = 
calloc).

Das Auslesen von mit malloc() allokierten Speicher löst (wie erwartet) 
keinen Page Fault aus. Erst das Schreiben. Das spricht für die shared 
zero-filled Page mit COW Flag.

Was ich überraschend fand, dass die Erstbeschreibung sehr langsam ist. 
Klar löst sie die Page Faults aus, aber ein gefühlter Faktor von 10 
ist schon beachtlich.

Der Faktor "steht zum lesen schon im Cache" zu "muß erst im Speicher 
geholt werden" ist eher eine Größenordnung größer.

Ein Pagefault beim ersten Zugriff auf die Seite, einmal komplett 
ausnullen und den Userspace den Rest der Seite nach Belieben behandeln 
zu lassen mit nur Faktor 10 ist da doch OK.

Nett. :-)

Allerdings ist mein Ergebnis "etwas" anders:

1

16177283 µs

2

275559 µs

3

250035 µs

4

256237 µs

5

257660 µs

Beim zweiten Mal:

1

6409789 µs

2

277707 µs

3

255244 µs

4

276881 µs

5

274949 µs

Linux 3.19.0-59-generic #66~14.04.1-Ubuntu SMP x86_64 GNU/Linux

(i3-2120, 12GB RAM)

Interessant.  Desktop-Linux:

1

2910609 µs

2

123538 µs

3

126064 µs

4

125684 µs

5

138005 µs

FreeBSD 10.x:

1

4 µs

2

1 µs

3

1 µs

4

1 µs

5

1 µs

FreeBSD scheint da wohl etwas andere Strategien zu fahren …

Jörg W. schrieb:
> Desktop-Linux:

> 2910609 µs
> 123538 µs
> 126064 µs
> 125684 µs
> 138005 µs


Ist das Dual Channel? Dann würde das zu meinen Werten passen.

Norbert schrieb:

> Oder der Compiler hat in "main" fast alles zwischen { und }
> wegoptimiert.

So ist es.  Clang schmeißt das alles raus.  Mit GCC sieht's anders
aus:

1

994627 µs

2

229823 µs

3

223184 µs

4

224453 µs

5

226044 µs

Mikro 7. schrieb:
> Ist das Dual Channel?

Ein Quadcore i5.

Jörg W. schrieb:

>> Ist das Dual Channel?

> Ein Quadcore i5.

Ok. Meinetwegen auch ein i7. ;-) Das war nicht die Frage.

Mikro 7. schrieb:
> Das war nicht die Frage.

Dann frag' mal so, dass ich es verstehe. ;-)

Norbert schrieb:
> Clang sollte nun ein wenig entradikalisiert sein;-)

Ja, damit sind die Ergebnisse zwischen clang und gcc48 ähnlich (wie
oben schon gepostet).

Aso. Ich meinte das hier: 
https://en.wikipedia.org/wiki/Multi-channel_memory_architecture#Dual-channel_architecture

Jörg W. schrieb:
> Mikro 7. schrieb:
>> Das war nicht die Frage.
>
> Dann frag' mal so, dass ich es verstehe. ;-)

Mikro 7. schrieb:
> Aso. Ich meinte das hier

Hmm, kann ich dir nicht sagen.  Ist ein Dell Optiplex 7010, vielleicht
findest du ja technische Details dazu im Netz.  Es sind alle vier
DIMM-Plätze belegt, aber farblich gekennzeichnet (wie im Bild bei
Wikipedia) sind sie nicht.

Rolf M. schrieb:
> Wenn calloc() den Speicher vom Betriebssystem anfordert und das ihn mit
> Nullen vollschreibt, wozu sollte calloc() das dann nochmal machen?
> Ich sehe da zwei Fälle in calloc(): Entweder es stellt Speicher bereit,
> den es quasi von früher noch hat. Dann muss es den explizit nullen. Oder
> es fordert vom Betriebssystem neuen Speicher an. Dann ist er von diesem
> schon genullt, und calloc muss nichts mehr tun.

malloc fordert den Speicher nicht vom Betriebssystem an, sondern 
zunächst einmal vom Heap des Prozesses. Dabei kann durchaus Speicher 
zurück gegeben werden, der vorher innerhalb des Prozesses bereits 
verwendet und dann mit free wieder freigegeben wurde. Daher gibt es 
calloc, falls das Programm den Speicher initialisiert haben möchte. 
Erst wenn der Heap erschöpft ist wird neuer Speicher vom Betriebssystem 
angefordert. In welchem Zustand der ist, ist erst einmal nicht 
definiert. Das Initialisieren seitens des Betriebssystem dient der 
Sicherheit, ist ein relativ neues Feature und kann seitens des Prozesses 
meines Wissens nach auch nicht vorausgesetzt werden. Es wäre daher 
schlecht, sich darauf zu verlassen.

A. H. schrieb:
> Es wäre daher schlecht, sich darauf zu verlassen.

Nun, Bibliothek und Kernel dürfen natürlich aufeinander abgestimmt
sein.  Allerdings würde das voraussetzen, dass calloc() selbst die
Allozierung des Speichers vornimmt (und nicht einfach malloc() ruft),
denn nur dann kann es sich sicher sein, gerade „frischen“ Speicher
vom OS bekommen zu haben.

A. H. schrieb:
> malloc fordert den Speicher nicht vom Betriebssystem an, sondern
> zunächst einmal vom Heap des Prozesses. Dabei kann durchaus Speicher
> zurück gegeben werden, der vorher innerhalb des Prozesses bereits
> verwendet und dann mit free wieder freigegeben wurde.

... wie ich ja auch schrieb.


> In welchem Zustand der ist, ist erst einmal nicht definiert. Das
> Initialisieren seitens des Betriebssystem dient der Sicherheit, ist ein
> relativ neues Feature und kann seitens des Prozesses meines Wissens nach
> auch nicht vorausgesetzt werden. Es wäre daher schlecht, sich darauf zu
> verlassen.

Ich habe gerade mal in die glibc-Sourcen reingeschaut, und da wird genau 
das getan. Das kann natürlich abhängig vom Betriebssystem variieren, 
aber unter Linux geht calloc immer davon aus, dass frisch allokierter 
Speicher schon genullt ist. Laut Changelog ist das mindestens seit 1999 
so.

Das Spannende ist hier, wie sich die (scheinbar?) ähnlichen 
Architekturen (Amd64) so unterschiedlich verhalten. Einmal der Faktor 
+20 bei der Erstzuweisung, im anderen Extremfall ist die Erstzuweisung 
(etwas) schneller. ¯\_(ツ)_/¯ Schön, was sich aus anfangs so "trivial" 
erscheinenden Fragen entwicklet. :-)