Προς το περιεχόμενο
  • 0
Star_Light

Overlap και memmove / memcpy

Ερώτηση

Δημοσ. (επεξεργασμένο)

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

 

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

 
#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 ?

Επεξ/σία από Star_Light

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

8 απαντήσεις σε αυτή την ερώτηση

Προτεινόμενες αναρτήσεις

  • 0

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

  • Like 1

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

 

  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, κτλ.

  • Like 1

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Η κληση της 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 ακομη και αν αυτο δεν ειναι εγγυηση. Μπορει καποιος να δωσει ολοκληρωμενο παραδειγμα ????

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Λοιπόν επειδή μου άρεσε αυτό έκατσα και το έψαξα στον κώδικα τις 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

 

 

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

  • Like 1

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Λοιπόν επειδή μου άρεσε αυτό έκατσα και το έψαξα στον κώδικα τις 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

  • Like 1

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Λοιπόν επειδή μου άρεσε αυτό έκατσα και το έψαξα στον κώδικα τις 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 αν γ..θεί ο Δίας.

  • Like 1

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

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

  • Like 1

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Δημιουργήστε έναν λογαριασμό ή συνδεθείτε για να σχολιάσετε

Πρέπει να είστε μέλος για να αφήσετε σχόλιο

Δημιουργία λογαριασμού

Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι εύκολο!

Εγγραφείτε για έναν νέο λογαριασμό

Σύνδεση

Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.

Συνδεθείτε τώρα
×
×
  • Δημιουργία νέου...

Χρήσιμες πληροφορίες

Με την περιήγησή σας στο insomnia.gr, αποδέχεστε τη χρήση cookies που ενισχύουν σημαντικά την εμπειρία χρήσης.