Come implementare memmove in C standard senza una copia intermedia?

StackOverflow https://stackoverflow.com/questions/4023320

Domanda

Dalla pagina man sul mio sistema:

void *memmove(void *dst, const void *src, size_t len);

DESCRIZIONE
La funzione memmove() copia len byte dalla stringa src alla stringa dst.
Le due stringhe potrebbero sovrapporsi;la copia viene sempre eseguita in modo non distruttivo
maniera.

Dalla norma C99:

6.5.8.5 Quando vengono confrontati due puntatori, il risultato dipende dalle posizioni relative nello spazio di indirizzi degli oggetti a cui indicati.Se due puntatori a oggetto o incompleto entrambi i tipi puntano allo stesso oggetto, o entrambi i punti uno dopo l'ultimo dello stesso oggetto array, si confrontano uguali.Se gli oggetti sono membri dello stesso aggregato, puntatori a membri della struttura dichiarati in seguito confronta i puntatori maggiori di a membri dichiarati in precedenza nel struttura e puntatori a array Elementi con valori di pedice più grandi confronta i puntatori maggiori di a elementi della stessa matrice con valori pedice.Tutti i puntatori a Membri dello stesso oggetto dell'unione Confronta uguale.Se l'espressione P punta a un elemento di una matrice object e l'espressione Q punta a l'ultimo elemento dello stesso array object, l'espressione puntatore Q+1confronta maggiore di P.In tutto in altri casi, il comportamento è non definito.

L'enfasi è mia.

Gli argomenti dst E src può essere convertito in puntatori a char in modo da alleviare i problemi di aliasing, ma è possibile confrontare due puntatori che possono puntare all'interno di blocchi diversi, in modo da eseguire la copia nell'ordine corretto nel caso in cui puntino all'interno dello stesso blocco?

La soluzione ovvia è if (src < dst), ma non è definito se src E dst puntare a blocchi diversi."Non definito" significa che non dovresti nemmeno presumere che la condizione restituisca 0 o 1 (questo sarebbe stato chiamato "non specificato" nel vocabolario dello standard).

Un'alternativa è if ((uintptr_t)src < (uintptr_t)dst), che almeno non è specificato, ma non sono sicuro che la norma garantisca quando src < dst è definito, è equivalente a (uintptr_t)src < (uintptr_t)dst).Il confronto dei puntatori è definito dall'aritmetica dei puntatori.Ad esempio, quando leggo la sezione 6.5.6 sull'addizione, mi sembra che l'aritmetica dei puntatori potrebbe andare nella direzione opposta a uintptr_t aritmetica, cioè, che un compilatore conforme potrebbe avere, quando p è di tipo char*:

((uintptr_t)p)+1==((uintptr_t)(p-1)

Questo è solo un esempio.In generale sembra che sia garantito molto poco quando si convertono i puntatori in numeri interi.

Questa è una questione puramente accademica, perché memmove viene fornito insieme al compilatore.In pratica, gli autori del compilatore possono semplicemente promuovere il confronto di puntatori non definiti con un comportamento non specificato, o utilizzare il pragma rilevante per forzare il proprio compilatore a compilare il proprio memmove correttamente.Ad esempio, questa implementazione ha questo frammento:

if ((uintptr_t)dst < (uintptr_t)src) {
            /*
             * As author/maintainer of libc, take advantage of the
             * fact that we know memcpy copies forwards.
             */
            return memcpy(dst, src, len);
    }

Vorrei comunque usare questo esempio come prova che la norma si spinge troppo oltre con comportamenti indefiniti, se è vero memmove non può essere implementato in modo efficiente nello standard C.Ad esempio, nessuno ha spuntato la risposta questa domanda SO.

È stato utile?

Soluzione

Penso che tu abbia ragione, non è possibile implementarlo memmove efficientemente nello standard C.

L'unico modo veramente portabile per verificare se le regioni si sovrappongono, penso, è qualcosa del genere:

[Modificare:guardandolo molto più tardi, penso che dovrebbe esserlo dst+len-1 alla fine della seconda riga.Ma non posso prendermi la briga di provarlo, quindi per ora lo lascerò così com'è, è possibile che sapessi di cosa stavo parlando la prima volta.]

for (size_t l = 0; l < len; ++l) {
    if (src + l == dst) || (src + l == dst + len) {
      // they overlap, so now we can use comparison,
      // and copy forwards or backwards as appropriate.
      ...
      return dst;
    }
}
// No overlap, doesn't matter which direction we copy
return memcpy(dst, src, len);

Non puoi nemmeno implementarlo memcpy O memmove Tutto Quello in modo efficiente nel codice portabile, perché è probabile che l'implementazione specifica della piattaforma ti dia a calci qualunque cosa tu faccia.Ma un portatile memcpy almeno sembra plausibile.

C++ ha introdotto una specializzazione del puntatore di std::less, che è definito per funzionare con due puntatori qualsiasi dello stesso tipo.In teoria potrebbe essere più lento di <, ma ovviamente su un'architettura non segmentata non lo è.

C non ha nulla del genere, quindi in un certo senso lo standard C++ concorda con te sul fatto che C non ha un comportamento sufficientemente definito.Ma poi, il C++ ne ha bisogno std::map e così via.È molto più probabile che tu voglia implementarlo std::map (o qualcosa del genere) senza conoscere l'implementazione di quella che vorresti implementare memmove (o qualcosa del genere) senza la conoscenza dell'implementazione.

Altri suggerimenti

Affinché due aree di memoria siano valide e sovrapposte, credo che dovresti trovarti in una delle situazioni definite in 6.5.8.5.Cioè, due aree di un array, unione, struttura, ecc.

Il motivo per cui altre situazioni non sono definite è perché due oggetti diversi potrebbero non trovarsi nemmeno nello stesso tipo di memoria, con lo stesso tipo di puntatore.Sulle architetture PC, gli indirizzi sono solitamente solo indirizzi a 32 bit nella memoria virtuale, ma C supporta tutti i tipi di architetture bizzarre, dove la memoria non è niente del genere.

La ragione per cui il C lascia le cose indefinite è dare margine di manovra agli autori del compilatore quando la situazione non ha bisogno di essere definita.Il modo di leggere 6.5.8.5 è un paragrafo che descrive attentamente le architetture che il C vuole supportare dove il confronto dei puntatori non ha senso a meno che non sia all'interno dello stesso oggetto.

Inoltre, il motivo per cui memmove e memcpy sono forniti dal compilatore è che a volte sono scritti in assembly ottimizzato per la CPU di destinazione, utilizzando un'istruzione specializzata.Non sono pensati per poter essere implementati in C con la stessa efficienza.

Per cominciare, lo standard C è noto per avere problemi nei dettagli come questo.Parte del problema è perché C viene utilizzato su più piattaforme e lo standard tenta di essere sufficientemente astratto da coprire tutte le piattaforme attuali e future (che potrebbero utilizzare un layout di memoria contorto che va oltre qualsiasi cosa abbiamo mai visto).Esistono molti comportamenti indefiniti o specifici dell'implementazione affinché gli autori del compilatore possano "fare la cosa giusta" per la piattaforma di destinazione.Includere i dettagli per ogni piattaforma sarebbe poco pratico (e costantemente obsoleto);invece, lo standard C lascia allo scrittore del compilatore il compito di documentare cosa succede in questi casi.Il comportamento "non specificato" significa solo che lo standard C non specifica cosa accade, non necessariamente che il risultato non può essere previsto.Il risultato è solitamente ancora prevedibile se leggi la documentazione per la tua piattaforma di destinazione e il tuo compilatore.

Poiché determinare se due puntatori puntano allo stesso blocco, segmento di memoria o spazio di indirizzi dipende da come è strutturata la memoria per quella piattaforma, le specifiche non definiscono un modo per effettuare tale determinazione.Si presuppone che il compilatore sappia come effettuare questa determinazione.La parte delle specifiche che hai citato afferma che il risultato del confronto dei puntatori dipende dalla "posizione relativa dei puntatori nello spazio degli indirizzi".Si noti che "spazio indirizzo" qui è singolare.Questa sezione si riferisce solo ai puntatori che si trovano nello stesso spazio di indirizzi;cioè puntatori direttamente confrontabili.Se i puntatori si trovano in spazi di indirizzi diversi, il risultato non è definito dallo standard C ed è invece definito dai requisiti della piattaforma di destinazione.

In caso di memmove, l'implementatore generalmente determina prima se gli indirizzi sono direttamente confrontabili.In caso contrario, il resto della funzione è specifico della piattaforma.Nella maggior parte dei casi, trovarsi in spazi di memoria diversi è sufficiente per garantire che le regioni non si sovrappongano e la funzione si trasformi in a memcpy.Se gli indirizzi sono direttamente confrontabili, allora è solo un semplice processo di copia di byte che inizia dal primo byte e va avanti o dall'ultimo byte e va indietro (a seconda di quale dei due copierà in modo sicuro i dati senza rovinare nulla).

Tutto sommato, lo standard C lascia molte cose intenzionalmente non specificate laddove non può scrivere una regola semplice che funzioni su qualsiasi piattaforma di destinazione.Tuttavia, gli autori standard avrebbero potuto fare un lavoro migliore nello spiegare Perché alcune cose non sono definite e vengono utilizzati termini più descrittivi come "dipendente dall'architettura".

Ecco un'altra idea, ma non so se è corretta.Per evitare il O(len) loop nella risposta di Steve, si potrebbe inserirlo nel file #else clausola di un #ifdef UINTPTR_MAX con il cast-to-uintptr_t implementazione.A condizione che il cast di unsigned char * A uintptr_t commuta con l'aggiunta di offset interi ogni volta che l'offset è valido con il puntatore, questo rende il confronto del puntatore ben definito.

Non sono sicuro che questa commutatività sia definita dallo standard, ma avrebbe senso, poiché funziona anche se solo i bit inferiori di un puntatore sono un indirizzo numerico effettivo e i bit superiori sono una sorta di scatola nera.

Vorrei comunque usare questo esempio come prova che lo standard si spinge troppo oltre con comportamenti indefiniti, se è vero che memmove non può essere implementato in modo efficiente nello standard C

Ma non è una prova.Non esiste assolutamente alcun modo per garantire che sia possibile confrontare due puntatori arbitrari su un'architettura di macchina arbitraria.Il comportamento di un simile confronto di puntatori non può essere regolato dallo standard C e nemmeno da un compilatore.Potrei immaginare una macchina con un'architettura segmentata che potrebbe produrre un risultato diverso a seconda di come i segmenti sono organizzati nella RAM o potrebbe anche scegliere di generare un'eccezione quando vengono confrontati i puntatori in segmenti diversi.Questo è il motivo per cui il comportamento è "indefinito".Lo stesso identico programma sulla stessa identica macchina potrebbe fornire risultati diversi da un'esecuzione all'altra.

La "soluzione" spesso fornita di memmove() che utilizza la relazione tra i due puntatori per scegliere se copiare dall'inizio alla fine o dalla fine all'inizio funziona solo se tutti i blocchi di memoria sono allocati dallo stesso spazio di indirizzi.Fortunatamente, di solito è così, anche se non era ai tempi del codice x86 a 16 bit.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top