Eine Frage zur C-Library: Ich muss den Inhalt eines Puffers um einige Bytes nach unten verschieben. Da Quell- und Zielbereich überlappen, ist memcpy() nicht nutzbar. Als Alternative gibt es in der Clib die Funktion memmove(). Allerdings scheint die recht aufwändig implementiert zu sein. Die Daten werden zunächst in einen temporären Zwischenspeicher kopiert und dann ins Zielarray geschrieben: https://pubs.opengroup.org/onlinepubs/000095399/functions/memmove.html Warum wird das nicht in situ gemacht? Man muss doch nur schauen, ob man beim Kopieren oben oder unten beginnt: Ist die Zieladresse kleiner als die Quelladresse, wird von niedrigen zu hohen Adressen hin ietriert, sonst umgekeht.
Fritz G. schrieb: > Warum wird das nicht in situ gemacht? Natürlich wird das in situ gemacht. Du verstehst wohl kein Englisch Copying takes place as if heisst nicht, DASS es so gemacht, sondern ALS OB es so gemacht werden würde. memmove entscheidet je nach Überlappung von vorne oder hinten zu kopieren
In der tat, memmove wird meisten so umgesetzt, dass es jenachdem von hinten kopiert. Wobei, wenn ich die selbe Page mit mmap mehrfach hintereinander Mappe, würde das ja nicht mehr immer so herauskommen als ob man das in ein Zwischenarray kopiert hätte. Ist diese Art es zu Implementieren also technisch gesehen falsch?
Fritz G. schrieb: > Man muss doch nur schauen, ob man > beim Kopieren oben oder unten beginnt Genau: https://github.com/bminor/glibc/blob/master/string/memmove.c
Fritz G. schrieb: > Ich muss den Inhalt eines Puffers um einige Bytes nach unten > verschieben. Da Quell- und Zielbereich überlappen, ist memcpy() nicht > nutzbar. Als Alternative gibt es in der Clib die Funktion memmove(). > Allerdings scheint die recht aufwändig implementiert zu sein. Die Daten > werden zunächst in einen temporären Zwischenspeicher kopiert und dann > ins Zielarray geschrieben: Warum schreibst Du die paar Zeilen Code nicht einfach selber?
Mi N. schrieb: > Warum schreibst Du die paar Zeilen Code nicht einfach selber? Wenn du dir ein mal die Implementierung von memmove in einer seriösen Library angesehen hättest, dann wüsstest du, warum die komplex sind. Es wird, je nach Blocklänge, versucht eine optimal schnelle Kopiermethode zu finden, ob man also Einzelbytetransfer oder 32/64 bit Worttransfer nutzt und wie man an Anfang und Ende paddet. Ich erinnere mich beim 8088 auch wie man segment aliasing erkannt hat, und bei virtual memory wie man page aliasing erkannt hat.
Das ganze scheint noch etwas komplexer zu sein, als ich es mir vorgestellt habe. Ich habe mal ein Programm erstellt, bei dem das Vorgehen zu checken, ob src < dest + Kopierrichtung, nicht ausreichend ist, um falsche Resultate zu vermeiden. Zusätzlich hab ich auch noch eine eigene memmove Variante mit Zwischenpuffer erstellt: https://godbolt.org/z/bT8vbje6d Beim Intel Compiler tritt der erwartete Fehler auf. Bei GCC und Clang nicht. Bei clang ist noch interessant, dass es meine memmove Funktion durch einen Call zu seiner eigenen ersetzt. Ich weiss nicht, wie das GCC und Clang machen. Hat mich ziemlich überrascht, das Resultat.
Daniel A. schrieb: > Ich weiss nicht, wie das GCC und Clang machen. Das kann man ja nachschauen. Oliver
Daniel A. schrieb: > Bei clang ist noch interessant, dass es meine memmove Funktion > durch einen Call zu seiner eigenen ersetzt. Kann man ja machen bei einer Hosted Implementation. Zum Abstellen dann sowas wie -fno-builtin-memmove.
Daniel A. schrieb: > Ich weiss nicht, wie das GCC und Clang machen. Hat mich ziemlich > überrascht, das Resultat. Ich habe es mal schnell getestet. Bei mir liefern alle Compiler (cl, clang-cl, clang und gcc) ein falsches Ergebnis wenn memcpy verwendet wird. Wegen mmap: Das ist etwa so wie wenn ein zweiter Prozess den Speicher klaut. Da gibt es sicher eine Klausel im Standard, die dir sagt dass du fair spielen sollst.
1 | #include <stdlib.h> |
2 | #include <string.h> |
3 | #include <stdio.h> |
4 | |
5 | int validate(const char *p) |
6 | {
|
7 | return p[0] == 'X' && p[1] == 'Y' && p[2] == 'Z'; |
8 | }
|
9 | |
10 | int main() |
11 | {
|
12 | int i, j; |
13 | char a[12]; |
14 | |
15 | for (i = 0; i < 9; i++) |
16 | {
|
17 | a[0] = '0'; |
18 | a[1] = '1'; |
19 | a[2] = '2'; |
20 | |
21 | a[3] = 'X'; |
22 | a[4] = 'Y'; |
23 | a[5] = 'Z'; |
24 | |
25 | a[6] = '6'; |
26 | a[7] = '7'; |
27 | a[8] = '8'; |
28 | |
29 | /* Guard space */
|
30 | a[9] = '9'; |
31 | a[10] = 'A'; |
32 | a[11] = 'B'; |
33 | |
34 | memcpy(a+i, a+3, 3); |
35 | //memmove(a+i, a+3, 3);
|
36 | |
37 | if (!validate(a+i)) |
38 | {
|
39 | printf("Error i=%d a[0]=%c a[1]=%c a[2]=%c\n", i, a[i], a[i+1], a[i+2]); |
40 | return -1; |
41 | }
|
42 | }
|
43 | |
44 | printf("OK\n"); |
45 | return 0; |
46 | }
|
Mi N. schrieb: > Warum schreibst Du die paar Zeilen Code nicht einfach selber? Eine optimierte memcpy Funktion ist bei grösseren Blöcken deutlich schneller als eine C Schleife (bei 8kB Blöcken etwa 28x). Die asm Funktion braucht gerade mal 80 Bytes:
1 | memcpy: |
2 | push rdi |
3 | push rsi |
4 | //cld // direction flag (should always be clear) |
5 | mov rax, rcx |
6 | mov rdi, rcx |
7 | mov rsi, rdx |
8 | mov rcx, r8 |
9 | rep movsb |
10 | pop rsi |
11 | pop rdi |
12 | ret |
Udo K. schrieb: > Daniel A. schrieb: >> Ich weiss nicht, wie das GCC und Clang machen. Hat mich ziemlich >> überrascht, das Resultat. > > Ich habe es mal schnell getestet. Bei mir liefern alle Compiler (cl, > clang-cl, clang und gcc) ein falsches Ergebnis wenn memcpy verwendet > wird. Schon klar, aber hier geht es um memmove, nicht um memcpy. > Wegen mmap: Das ist etwa so wie wenn ein zweiter Prozess den Speicher > klaut. Da gibt es sicher eine Klausel im Standard, die dir sagt dass du > fair spielen sollst. Soweit ich weiss, gibt es das nicht. Es gibt das Aliasing Zeugs, das sich darauf bezieht, ob 2 Pointer auf das selbe Objekt zeigen können, aber meines Wissens steht nirgends, dass 2 Pointer auf das selbe Objekt auch den selben Wert enthalten müssen, oder dass sie eindeutig sein müssten, und auch nicht, dass sich zwei unterschiedliche Objekte nicht beeinflussen könnten. Man muss in der Regel sogar annehmen, das unter anderem 2 Pointer vom selben Typ auf das selbe Objekt zeigen könnte. Ausserdem würde ich doch meinen, das memory mapping etwas ziemlich fundamentales ist, womit allerhand C programme umgehen können müssen. Ob das jetzt für IPC ist, für embedded Sachen, in einem Kernel, oder sonst wo. Wenn da der Compiler einfach Blödsinn produzieren dürfte, sobald man etwas memory mapping macht, wäre das doch recht problematisch.
Michael B. schrieb: > Es wird, je nach Blocklänge, versucht eine optimal schnelle > Kopiermethode zu finden, Davon schreibt der TO nichts. Auch die Puffergröße wurde nicht genannt. Ich sehe keinen Grund, immer das maximal Aufwendige anzunehmen.
Udo K. schrieb: > Eine optimierte memcpy Funktion ist bei grösseren Blöcken deutlich > schneller als eine C Schleife (bei 8kB Blöcken etwa 28x). Wobei es eine echte Kunst ist, memcpy/memmove so zu schreiben, dass es unter allen Randbedingungen optimal arbeitet. Also ob im Cache, bzw in welchen Cache, oder lieber am Cache vorbei, mit Lookahead/Prefetch automatisch oder zu Fuss, Alignment berücksichtigend, ... Und das dann über alle x86-Implementierungen seit der Sintflut. Es ist/war auch nicht gesichert, dass der x86 Microcode das gut macht. Überlappende Kopien setzen da nochmal eins drauf, weil das Zugriffsverhalten in der Implementierung durch die Speicherhierarchie davon erheblich betroffen sein kann, zumal wenn Quelle und Ziel im gleichen Cacheblock oder Write-Buffer liegen.
:
Bearbeitet durch User
Daniel A. schrieb: > Beim Intel Compiler tritt der erwartete Fehler auf. Bei GCC und Clang > nicht. Bei clang ist noch interessant, dass es meine memmove Funktion > durch einen Call zu seiner eigenen ersetzt. > > Ich weiss nicht, wie das GCC und Clang machen. Hat mich ziemlich > überrascht, das Resultat. gcc (und sicherlich auch clang) hat einen ganzen Haufen Standardfunktionen bereits eingebaut und kann daher jeden Aufruf nochmal entsprechend den Gegebenheiten optimieren, ohne die Funktion aus der Library aufrufen zu müssen. Unter https://gcc.gnu.org/onlinedocs/gcc-15.1.0/gcc/Library-Builtins.html findet man eine Liste.
Daniel A. schrieb: >> Wegen mmap: Das ist etwa so wie wenn ein zweiter Prozess den Speicher >> klaut. Da gibt es sicher eine Klausel im Standard, die dir sagt dass du >> fair spielen sollst. > > Soweit ich weiss, gibt es das nicht. Das, was die MMU beim Memory Mapping tut, ist nicht Gegenstand des Standards und spielt sich deswegen außerhalb der "Abstract Machine" des Standards ab. Das ist vergleichbar mit I/O-Registern, deren Inhalte ebenfalls von außerhalb beeinflusst werden. Gleiches gilt auch für Shared Memory, der mit anderen Prozessen geteilt wird. Um die Zugriffe auf solche Dinge zu steuern, werden diese üblicherweise als volatile deklariert. Das kannst du auch bei den mgemappten Speicherbereichen tun, dann bekommst du bei den Aufrufen von memcpy() und memmove() sogar Warnungen angezeigt. Daniel A. schrieb: > Beim Intel Compiler tritt der erwartete Fehler auf. Bei GCC und Clang > nicht. Der ICC verwendet andere Bibliotheksfunktionen als GCC und Clang: ICC:
1 | call _intel_fast_memmove |
GCC und Clang:
1 | call memmove@PLT |
Letztere mündet in einen Aufruf der entsprechenden Funktion in glibc. Warum bei dieser Funktion der Effekt des Überschreibens der kopierten Daten nicht auftritt, weiß ich auch nicht. Ich könnte mir aber vorstellen, dass das Kopieren durch DMA im physikalischen Adressraum unterstützt wird. Wenn die Entscheidung, ob aufwärts oder abwärts kopiert werden soll, erst nach der Konvertierung der virtuellen Startadressen in physikalische erfolgt, wird nichts überschrieben.
Yalu X. schrieb: > Das, was die MMU beim Memory Mapping tut, ist nicht Gegenstand des > Standards und spielt sich deswegen außerhalb der "Abstract Machine" des > Standards ab. Soweit kann ich noch zustimmen. > Das ist vergleichbar mit I/O-Registern, deren Inhalte > ebenfalls von außerhalb beeinflusst werden. Gleiches gilt auch für > Shared Memory, der mit anderen Prozessen geteilt wird. Hier aber dann nicht mehr. Die Änderung des Speichers / des Objekts erfolgt hier nicht ausserhalb des Programms, sondern durch das Programm selbst. Der Compiler muss annehmen, dass a und b in meinem Beispiel auf das selbe Objekt verweisen könnten, gemäss den aliasing regeln. Dass das hier wegen dem memory mapping so ist, ist irrelevant. Ich sehe das ähnlich wie z.B. bei der x86 memory segmentation. Auch da können unterschiedliche Adressen auf das selbe Objekt zeigen, und auch das ist etwas, was ausserhalb des Scopes der "Abstract Machine" liegt. Das ändert aber nichts an den Regeln, die der Standard vorgibt, und an die sich der Compiler halten muss. Das Programm muss sich trotzdem so verhalten, wie die beschriebene "Abstract Machine". Der Fall mit den I/O-Registern ist anders. Denn der Fall wird ja genau vom Standard abgedeckt. Die Änderungen sind ausserhalb des Programms, also nimmt man dort volatile. Ich denke ausserdem, dass in meinem Beispiel mit mmap oben, volatile falsch wäre, aus den selben Gründen, warum volatile bei mehreren Threads statt _Atomic falsch wäre. Eben weil es keine Änderung ausserhalb des Programms ist, und daher all die üblichen Regeln weiterhin gelten.
Daniel A. schrieb: > Die Änderung des Speichers / des Objekts erfolgt hier nicht ausserhalb > des Programms, Doch, nämlich durch die MMU, die in diesem Zusammenhang als Peripherieeinheit betrachtet werden muss. > sondern durch das Programm selbst. Das Programm bzw. die CPU greift nicht direkt auf den Speicher zu, sondern veranlasst durch das Senden einer (virtuelle) Adresse und eines Datenworts an die MMU, das Datenwort in den Speicher zu schreiben. Entsprechend laufen auch Lesezugriffe auf den Speicher über die MMU. Die CPU sieht somit nur die MMU, nicht aber den eigentlichen Speicher. Jede einzelne Speicherzelle präsentiert sich der CPU damit als eine Art I/O-Register mit der Eigenschaft, dass das Beschreiben eines dieser Register möglicherweise die Änderung des Inhalts eines anderen Registers zu Folge hat. Übertragen auf die abstrakte Maschine des C-Standards bedeutet dies, dass dies gar keinen Speicher, sondern nur I/O-Space hat und deswegen auf einem Rechner mit MMU (scheinbar) gar kein konformer C-Compiler möglich ist. Dieses Problem zeigt sich nicht nur im Zusammenhang mit memmove, sondern auch schon in ganz banalen Dingen wie Pointer-Vergleichen. Laut Standard liefert der ==-Operator beim Vergleich zweier Pointer genau dann 1, wenn beide auf dasselbe Objekt zeigen. In deinem Beispiel von oben müsste also a==b gleich 1 sein, was aber weder beim ICC noch beim GCC noch beim Clang der Fall ist. Ein standardkonformer Compiler für eine Rechner mit MMU müsste dafür sorgen, dass bei Pointer-Vergleichen für die beiden Pointer die physikalischen Adressen aus der Page Table ausgelesen und und diese verglichen werden. Was aber, wenn das Programm gar keinen Zugriff auf die Page Table hat? Müssen wir dann auf modernen PCs auf C komplett verzichten? Eine praktikable Möglichkeit, dennoch ein standardkonformes C zu realisieren, besteht gemäß der as-if-Regel darin, alle für ein Programm zugänglichen Speicher-"I/O-Register" in ihrer Gesamtheit für die CPU wie ein direkt angeschlossener Speicher aussehen zu lassen und die MMU damit unsichtbar zu machen. Dazu muss die MMU so konfiguriert werden, dass innerhalb des virtuellen Adressraums des Programms eine eindeutige Zuordnung von physikalischen zu virtuellen Adressen besteht. Dieser Zustand wird beim Start des Programms durch das Betriebssystem garantiert, kann aber durch böswilliges Herumspielen mit mmap() zerstört werden. Deswegen lässt man dies besser bleiben :)
Ok, das mit dem ==-Operator ist ein guter Punkt. Deine Interpretation ist wohl doch die bessere.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.