Overlap και memmove / memcpy

[Star_Light]

Καλησπέρα σε ολους τους συναδέλφους

 

Μπαινω κατευθειας στο θέμα ...

 
#include<stdio.h>
#include<string.h>

int main(void)
{
    char str[20] = "HELLOSIR";
    
    memcpy( str + 2 , str + 1 , 4 );
    
    puts( str );
    
    return 0;
                  
}

Aν εχω καταλαβει καλά ο παραπανω κώδικας ειναι ένα τυπικο παράδειγμα που μπορει να περιγράψει ενα memory overlap. Κάποια δεδομένα στον προορισμό (str + 2 ) θα υπερεγγραφούν πριν την αντιγραφή τους.

  void *memcpy( void * restrict s1, const void * restrict s2, size_t n );

Νομιζω συμφωνα με το παράδειγμα που έδωσα δεν υπάρχει εγγυηση παρα το restrict στον δεικτη οτι δεν θα γινει το overlap καταρχην ειναι νομιμο αυτο που κάνω επειδη χρησιμοποιώ τον ιδιο τον restricted και οχι άλλον για να έχω προσβαση στα δεδομένα.Επομεως ως προς αυτο η συμπεριφορα δεν ειναι απροσδιοριστη.

 

> Πως καταφερνει και δουλευει η συνάρτηση memcpy ομως? Θα περιμένα κάτι της μορφής :

HEEEEEIR

αντι

HEELLOIR

  που παιρνω τώρα....

 

η συμπεριφορα εδω ειναι απροσδιοριστη?

 

Ευχαριστω.

 

EDIT: Το const στο const void * restrict s2 δηλωνει οτι τα δεδομενα δεν μπορουν να αλλάξουν ουτε απο τον ιδιο τον s2 ?

Επεξ/σία 21 Ιουλίου 2013 από Star_Light

[παπι]

Εχει να κανει με την υλοποιηση της memcpy. Πχ στο msvrc110d η memcpy ειναι memmov.

[imitheos]

 

  void *memcpy( void * restrict s1, const void * restrict s2, size_t n );

Νομιζω συμφωνα με το παράδειγμα που έδωσα δεν υπάρχει εγγυηση παρα το restrict στον δεικτη οτι δεν θα γινει το overlap καταρχην ειναι νομιμο αυτο που κάνω επειδη χρησιμοποιώ τον ιδιο τον restricted και οχι άλλον για να έχω προσβαση στα δεδομένα.Επομεως ως προς αυτο η συμπεριφορα δεν ειναι απροσδιοριστη.

 

Το restrict δεν είναι εγγύηση για σένα ότι δεν θα γίνει overlap αλλά εγγύηση για τον compiler ώστε να μπορεί να παράξει καλύτερο κώδικα. Αν τώρα ο προγραμματιστής το παραβεί και δώσει περιοχές μνήμης που μπλέκονται, κακό του κεφαλιού του

 

> Πως καταφερνει και δουλευει η συνάρτηση memcpy ομως? Θα περιμένα κάτι της μορφής :

HEEEEEIR

αντι

HEELLOIR

  που παιρνω τώρα....

 

Όπως είπε και ο παπί, εξαρτάται από την υλοποίηση. Υπάρχουν υλοποιήσεις της memcpy που αντιγράφουν από την αρχή προς το τέλος και άλλες από το τέλος προς την αρχή, υπάρχουν υλοποιήσεις που ελέγχουν στην αρχή αν src+n πέφτει μέσα στο dest, υλοποιήσεις που τρέχουν κατευθείαν την memmove, κτλ.

[Star_Light]

Η κληση της memcpy οπως την δινω ειναι απροσδιοριστη επειδη οι str + 2 και str + 1 δειχνουν στο ιδιο πράγμα. Κατι τέτοιο δεν ειναι συνεπές με τον ορισμο ενος restrict δεικτη.

 

Οταν λεμε overlap εννοουμε αυτο που εγραψα πριν ετσι? οχι οποιαδηποτε αντιγραφη του ενος πανω στο αλλο για παράδειγμα το

 
char s1[] = "Hi";
char s2[]= "Bye";
 
memcpy( s1 , s2 , 3);
 

δεν νομιζω και αυτο να ειναι overlap.

 

Παντως δεν ξερω αμα αξιζει να συνεχισω αλλο με αυτο ή οχι αλλα ισως και να μην ειμαι σιγουρος οτι εχω καταλαβει γιατι μπαινει restrict στα ορισματα της memcpy αν δηλαδη το s2 αντιγραφει σε μια περιοχη που το s1 δειχνει τοτε δεν θεωρειται οτι αλλαζει απο τον s2? αρα απροσδιοριστη συμπεριφορα?

 

Δεν ειμαι σιγουρος οτι εχω καταλαβει πως το restrict ενημερωνει και δειχνει στον προγραμματιστη οτι δεν θα υπάρχει overlap ακομη και αν αυτο δεν ειναι εγγυηση. Μπορει καποιος να δωσει ολοκληρωμενο παραδειγμα ????

[moukoublen]

Λοιπόν επειδή μου άρεσε αυτό έκατσα και το έψαξα στον κώδικα τις glibc (2.17)

 

Παραθέτω τον κώδικα της memcpy

# define memcpy(dest, src, n)              \
    (__extension__ (__builtin_constant_p (n)            \
        ? __memcpy_c ((dest), (src), (n))               \
        : __memcpy_g ((dest), (src), (n))))

Κάνει μια διακλάδωση που δεν καταλαβαίνω όμως παραθέτω με τη σειρά των κώδικα των άλλων 2 συναρτήσεων

 

Η __memcpy_c είναι η παρακάτω

# define __memcpy_c(dest, src, n) \
   ((n) == 0								      \
   ? (dest)								      \
   : (((n) % 4 == 0)							      \
      ? __memcpy_by4 (dest, src, n)					      \
      : (((n) % 2 == 0)							      \
         ? __memcpy_by2 (dest, src, n)					      \
         : __memcpy_g (dest, src, n))))

Κάνει λοιπόν έναν διαχωρισμό στο αν το σύνολο των θέσεων (bytes) που πρόκειται να αντιγραφούν είναι ακαριαίο πολλαπλάσιο του 4 και αν ναι τότε καλεί μια memcpy που κάνει την αντιγραφή (υποθέτω από το τίτλο) ανα blocks των 4ων bytes.

 

Αντίστοιχα κάνει το ίδιο και με το 2 διαφορετικά καταλήγει στην g που απ ότι καταλαβαίνω αντιγράφει byte-byte.

 

 

Στο παρπάνω παράδειγμα λοιπόν το n = 4. Οπότε όλη η αντιγραφή γίνεται σε έναν κύκλο μηχανής - σε ένα block των 4 byte.

 

Έτσι απο το

 

HELLOSIR

 

παίρνει τα 4 byte απο το δεύτερο και μετά, δηλαδή το: ELLO

 

και τα τοποθετεί από το 3ο byte και μετά. Δηλαδή

 

HE LLOS IR -> HE ELLO IR -> HEELLOIR

 

 

Όλο το παραπάνω με κάθε επιφύλαξη φυσικά. Υπόθεση είναι με βάση αυτά που βλέπω.

[παπι]

Λοιπόν επειδή μου άρεσε αυτό έκατσα και το έψαξα στον κώδικα τις glibc (2.17)

 

Παραθέτω τον κώδικα της memcpy

# define memcpy(dest, src, n)              \
    (__extension__ (__builtin_constant_p (n)            \
        ? __memcpy_c ((dest), (src), (n))               \
        : __memcpy_g ((dest), (src), (n))))

Κάνει μια διακλάδωση που δεν καταλαβαίνω όμως παραθέτω με τη σειρά των κώδικα των άλλων 2 συναρτήσεων

 

Κανει ελεγχο για const. Η memcpy_c δεν μπορει να δουλεψει με μη const τιμη, διοτι εχει πραξη με το n σε macro

[imitheos]

Λοιπόν επειδή μου άρεσε αυτό έκατσα και το έψαξα στον κώδικα τις glibc (2.17)

 

Κάνει λοιπόν έναν διαχωρισμό στο αν το σύνολο των θέσεων (bytes) που πρόκειται να αντιγραφούν είναι ακαριαίο πολλαπλάσιο του 4 και αν ναι τότε καλεί μια memcpy που κάνει την αντιγραφή (υποθέτω από το τίτλο) ανα blocks των 4ων bytes.

Σχεδόν όλες οι libc υλοποιούν τις συναρτήσεις αντιγραφής (memcpy, strcpy, κτλ) ως word-copy. Αντιγράφουν πρώτα ένα-ένα όσα bytes χρειάζονται μέχρι ο δείκτης να γίνει aligned (αν υπάρχουν τέτοια bytes και δεν είναι από την αρχή aligned), μετά αντιγράφουν μαζικά (ανά 4, 8 ή και 16) όσα bytes είναι aligned και τέλος αντιγράφουν και πάλι ένα-ένα όσα bytes μένουν. Επίσης υπάρχουν για κάθε αρχιτεκτονική hand-crafted υλοποιήσεις σε assembly που είναι πιο γρήγορες και χρησιμοποιούνται όποτε γίνεται.

 

Η glibc έχει συνήθως πολύ optimized συναρτήσεις με πολύπλοκο κώδικα και ένα κάρο gnu-isms οπότε αν θέλεις να δεις μια συνάρτηση, για ευκολία μπορείς να δεις αυτήν του NetBSD ή του FreeBSD. Εδώ είναι η υλοποίηση σε c που χρησιμοποιείται αν δεν υπάρχει optimized έκδοση και εδώ ή assembly έκδοση για x86_64 αρχιτεκτονική. Οι συγκεκριμένες είναι λίγο παραπάνω πολύπλοκες από ό,τι πρέπει γιατί υλοποιούν με μία συνάρτηση τις memcpy, bcopy, κτλ αλλά γενικά το NetBSD έχει τις πιο απλές υλοποιήσεις για αυτό και ενδείκνυται για ανάγνωση του κώδικα.

 

Οι αντίστοιχες εκδόσεις της glibc είναι εδώ για την απλή και εδώ για x86_64 assembly.

 

Οταν λεμε overlap εννοουμε αυτο που εγραψα πριν ετσι? οχι οποιαδηποτε αντιγραφη του ενος πανω στο αλλο για παράδειγμα το

 

char s1[] = "Hi";
char s2[]= "Bye";

δεν νομιζω και αυτο να ειναι overlap.

 

Το s1 και s2 επικαλύπτει το ένα το άλλο ? Όχι. Άρα γιατί να υπάρχει "overlap" ?

 

Παντως δεν ξερω αμα αξιζει να συνεχισω αλλο με αυτο ή οχι αλλα ισως και να μην ειμαι σιγουρος οτι εχω καταλαβει γιατι μπαινει restrict στα ορισματα της memcpy αν δηλαδη το s2 αντιγραφει σε μια περιοχη που το s1 δειχνει τοτε δεν θεωρειται οτι αλλαζει απο τον s2? αρα απροσδιοριστη συμπεριφορα?

 

Δεν ειμαι σιγουρος οτι εχω καταλαβει πως το restrict ενημερωνει και δειχνει στον προγραμματιστη οτι δεν θα υπάρχει overlap ακομη και αν αυτο δεν ειναι εγγυηση. Μπορει καποιος να δωσει ολοκληρωμενο παραδειγμα ????

Είπαμε και πριν ότι το restrict δεν μπαίνει για σένα αλλά για τον compiler. Για τον προγραμματιστή υπάρχει η τεκμηρίωση της συνάρτησης που αναφέρει ότι δεν πρέπει να υπάρχει overlap. Απλά η C θεωρεί ότι ο προγραμματιστής ξέρει τι κάνει οπότε δεν του βάζει περιορισμούς και του επιτρέπει να δώσει στην memcpy και περιοχές που επικαλύπτονται.

 

Το παράδειγμα της wikipedia δηλαδή δεν είναι ολοκληρωμένο ? Παρακάτω είναι το ίδιο παράδειγμα λίγο αλλαγμένο και με δοσμένη την x86 assembly με Intel syntax για να είναι πιο εύκολη στην ανάγνωση.

 

#include <stdio.h>
#include <string.h>

void myfunc(int *a, int *b, int *val);

int main(void)
{
	int sum = 0;
	int prod = 1;
	int i;

	for (i = 1; i <= 5; i++) {
		myfunc(&sum, &prod, &i);
	}

	printf("sum=%d product=%d\n", sum, prod);

	return 0;
}

void myfunc(int *a, int *b, int *val)
{
	*a += *val;
	*b *= *val;
}
Έξοδος:
% ./a.out 
sum=15 product=120

% gcc -std=c99 -Wall -O0 -masm=intel -m32 -S tmp.c
Χωρίς restrict:
        /* πέρνα στον eax τη διεύθυνση του a που έχει περαστεί στην stack */
	mov	eax, DWORD PTR [ebp+8]
	/* πέρνα στον edx την τιμή της παραπάνω διεύθυνσης (δηλαδή του *a) */
	mov	edx, DWORD PTR [eax]
        /* πέρνα στον eax τη διεύθυνση του val */
	mov	eax, DWORD PTR [ebp+16]
	/* πέρνα στον eax την τιμή του *val */
	mov	eax, DWORD PTR [eax]
	/* πρόσθεσε τις δύο αυτές τιμές */
	add	edx, eax
	/* βάλε την νέα τιμή πίσω στο a */
	mov	eax, DWORD PTR [ebp+8]
	mov	DWORD PTR [eax], edx

	/* εδώ αρχίζει το ίδιο για τον υπολογισμό του b. όπως βλέπουμε
	ξαναφορτώνεται η τιμή του val στον eax */
	mov	eax, DWORD PTR [ebp+12]
	mov	edx, DWORD PTR [eax]
	mov	eax, DWORD PTR [ebp+16]
	mov	eax, DWORD PTR [eax]
	imul	edx, eax
	mov	eax, DWORD PTR [ebp+12]
	mov	DWORD PTR [eax], edx

Με restrict:
myfunc:
	mov	eax, DWORD PTR [ebp+8]
	mov	edx, DWORD PTR [eax]
	/* φορτώνει στον ecx την τιμή του val */
	mov	ecx, DWORD PTR [ebp+16]
	mov	ecx, DWORD PTR [ecx]
	add	edx, ecx
	mov	eax, DWORD PTR [ebp+8]
	mov	DWORD PTR [eax], edx
	mov	eax, DWORD PTR [ebp+12]
	mov	edx, DWORD PTR [eax]
	/* χρησιμοποιείται απευθείας ο ecx χωρίς να ξαναφορτωθεί από τη μνήμη */
	imul	edx, ecx
	mov	eax, DWORD PTR [ebp+12]
	mov	DWORD PTR [eax], edx

Στην πρώτη έκδοση που δεν έχουμε το restrict, έχουμε μια συνάρτηση με ορίσματα τρεις δείκτες. Επειδή οι δείκτες είναι όλοι τύπου int μπορεί κάλλιστα η συνάρτηση να τρέξει με την ίδια περιοχή μνήμης και για τα τρία ορίσματα. Δηλαδή με άλλα λόγια μπορεί όταν θέσουμε τιμή στο a να αλλάξει η τιμή του val. Για αυτό το λόγο στον υπολογισμό του b, ο compiler είναι υποχρεωμένος να ξαναφορτώσει την τιμή του val από την μνήμη και έτσι εκτελεί παραπανίσιο κώδικα.

 

Στην 2η περίπτωση που έχουμε δηλώσει ως restrict τις μεταβλητές, ο compiler ξέρει ότι αυτές δείχνουν σε διαφορετικές περιοχές οπότε όσες φορές και να γράψουμε στο a και στο b, το val δεν θα αλλάξει και έτσι μπορεί να παράξει καλύτερο κώδικα. Εφόσον όμως ο προγραμματιστής επέλεξε να πει στον compiler ότι δεν θα δώσει επικαλυπτόμενες περιοχές είναι και υποχρεωμένος να το τηρεί αλλιώς δεν θα φταίει ο compiler αν γ..θεί ο Δίας.

[Star_Light]

Και στην assembly που το έχει στην Wiki παντως μια χαρα ευανάγνωστο το βρίσκω.

[cyberrobot]

+1 στο θέμα, πρόσφατα έψαχνα για τις διαφορές τους όσον αφορά την ταχύτητα. Τελικά προτίμησα την memmove(). Αν και ιδιαίτερη διαφορά δεν είδα...