memmove vs memcpy

¿Cómo implementar memmove en C estándar sin una copia intermedia?

Question

Desde la página de manual en mi sistema:

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

DESCRIPCIÓN
La función memmove () copia los bytes len de string src a string dst.
Las dos cadenas pueden superponerse ; la copia siempre se hace de una forma no destructiva
manera.

Del estándar C99:

6.5.8.5 Cuando se comparan dos punteros, el resultado depende de las ubicaciones relativas en el espacio de direcciones de los objetos apuntados. Si dos punteros a objeto o tipos incompletos apuntan al mismo objeto, o ambos señalan uno pasado el último elemento del mismo objeto de matriz, comparan igual. Si los objetos apuntados son miembros del mismo objeto agregado, los punteros a los miembros de estructura declarados posteriormente comparan mayor que los punteros con los miembros declarados anteriormente en la estructura, y los punteros a los elementos de matriz con valores de subíndices más grandes comparan mayor que los punteros a elementos de la misma matriz con valores de subíndice más bajos Todos los apuntadores a miembros del mismo objeto de unión se comparan iguales. Si la expresión P apunta a un elemento de un objeto de matriz y la expresión Q apunta al último elemento del mismo objeto de matriz, la expresión de puntero Q+1 compara mayor que P En todos los demás casos, el comportamiento no está definido .

El énfasis es mío

Los argumentos dst y src se pueden convertir a punteros en char para aliviar los problemas de alias estrictos, pero es posible comparar dos punteros que pueden apuntar dentro de bloques diferentes, para hacer la copia en el orden correcto en caso de que señalen dentro el mismo bloque?

La solución obvia es if (src < dst) , pero eso no está definido si src y dst apuntan a diferentes bloques. "Indefinido" significa que ni siquiera debe suponer que la condición devuelve 0 o 1 (esto se habría llamado "no especificado" en el vocabulario del estándar).

Una alternativa es if ((uintptr_t)src < (uintptr_t)dst) , que al menos no está especificado, pero no estoy seguro de que el estándar garantice que cuando se define src < dst , es equivalente a (uintptr_t)src < (uintptr_t)dst) . La comparación del puntero se define a partir de la aritmética del puntero. Por ejemplo, cuando leo la sección 6.5.6 sobre la adición, me parece que la aritmética del puntero podría ir en la dirección opuesta a uintptr_t arithmetic, es decir, que un compilador compatible podría tener, cuando p es de tipo char* :

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

Esto es solo un ejemplo. En general, parece muy poco garantizado al convertir punteros a enteros.

Esta es una pregunta puramente académica, porque memmove se proporciona junto con el compilador. En la práctica, los autores del compilador pueden simplemente promover la comparación indefinida de punteros con un comportamiento no especificado, o usar el pragma relevante para obligar a su compilador a compilar su memmove correctamente. Por ejemplo, esta implementación tiene este fragmento:

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);
    }

Me gustaría utilizar este ejemplo como prueba de que el estándar va demasiado lejos con comportamientos indefinidos, si es cierto que memmove no se puede implementar de manera eficiente en el estándar C. Por ejemplo, nadie marcó cuando respondió esta pregunta .

Answer 1

Me gustaría utilizar este ejemplo como prueba de que el estándar va demasiado lejos con comportamientos indefinidos, si es cierto que Memmove no se puede implementar de manera eficiente en C estándar.

Pero no es una prueba. No hay forma de garantizar que pueda comparar dos punteros arbitrarios en una arquitectura de máquina arbitraria. El comportamiento de dicha comparación de puntero no puede ser legislado por el estándar C o incluso por un compilador. Me podría imaginar una máquina con una arquitectura segmentada que podría producir un resultado diferente dependiendo de cómo los segmentos están organizados en la RAM o incluso podría optar por lanzar una excepción cuando se comparan punteros en diferentes segmentos. Es por eso que el comportamiento es "indefinido". El mismo programa exactamente en la misma máquina puede dar resultados diferentes de ejecución a ejecución.

La "solución" frecuente de memmove () usando la relación de los dos punteros para elegir si copiar desde el principio hasta el final o desde el final hasta el principio solo funciona si todos los bloques de memoria se asignan desde el mismo espacio de direcciones. Afortunadamente, este suele ser el caso, aunque no fue en los días del código x86 de 16 bits.

Answer 2

Aquí hay otra idea, pero no sé si es correcta. Para evitar el bucle O(len) en la respuesta de Steve, uno podría ponerlo en la cláusula #ifdef UINTPTR_MAX de un #ifdef UINTPTR_MAX con la implementación cast-to- uintptr_t . Siempre que el uintptr_t unsigned char * a uintptr_t conmute con la adición de desplazamientos de enteros siempre que el desplazamiento sea válido con el puntero, esto hace que la comparación del puntero esté bien definida.

No estoy seguro de si esta conmutatividad está definida por el estándar, pero tendría sentido, ya que funciona incluso si solo los bits más bajos de un puntero son una dirección numérica real y los bits superiores son una especie de caja negra.

Answer 3

Creo que tienes razón, no es posible implementar memmove eficiente en la norma C.

La única manera verdaderamente portátil de probar si las regiones se superponen, creo, es algo como esto:

[Editar: mirando esto mucho más tarde, creo que debería ser dst+len-1 al final de la segunda línea. Pero no me molesto en probarlo, así que me iré como está por ahora, es posible que supiera de lo que estaba hablando la primera vez.]

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);

No puede implementar ni memcpy ni memmove todo eso de manera eficiente en un código portátil, porque la implementación específica de la plataforma es probable que le patee el trasero sin importar lo que haga. Pero una memcpy portátil al menos parece plausible.

C ++ introdujo una especialización de puntero de std::less , que se define para trabajar con dos punteros del mismo tipo. En teoría podría ser más lento que < , pero obviamente en una arquitectura no segmentada no lo es.

C no tiene tal cosa, por lo tanto, en cierto sentido, el estándar de C ++ concuerda contigo en que C no tiene suficiente comportamiento definido. Pero luego, C ++ lo necesita para std::map y así sucesivamente. Es mucho más probable que desee implementar std::map (o algo similar) sin el conocimiento de la implementación que el que desea implementar memmove (o algo así) sin el conocimiento de la implementación.

Answer 4

Para empezar, el estándar C es notorio por tener problemas en detalles como este. Parte del problema se debe a que C se utiliza en múltiples plataformas y el estándar intenta ser lo suficientemente abstracto como para abarcar todas las plataformas actuales y futuras (que podrían usar un diseño de memoria intrincado más allá de cualquier cosa que hayamos visto). Hay un comportamiento indefinido o específico de implementación para que los compiladores "hagan lo correcto" para la plataforma de destino. Incluir detalles para cada plataforma sería poco práctico (y constantemente desactualizado); en cambio, el estándar C le deja al escritor del compilador documentar lo que sucede en estos casos. El comportamiento "no especificado" solo significa que el estándar C no especifica qué sucede, no necesariamente que el resultado no puede predecirse. El resultado generalmente es aún predecible si lee la documentación de su plataforma de destino y su compilador.

Desde determinar si dos punteros apuntan al mismo bloque, segmento de memoria o espacio de direcciones depende de cómo se presenta la memoria para esa plataforma, la especificación no define una manera de hacer esa determinación. Supone que el compilador sabe cómo hacer esta determinación. La parte de la especificación que citó dijo que el resultado de la comparación del puntero depende de la ubicación relativa de los punteros en el espacio de direcciones. Tenga en cuenta que el "espacio de direcciones" es singular aquí. Esta sección solo se refiere a punteros que se encuentran en el mismo espacio de direcciones; es decir, punteros que son directamente comparables. Si los punteros están en espacios de direcciones diferentes, entonces el resultado no está definido por el estándar C y, en su lugar, está definido por los requisitos de la plataforma objetivo.

En el caso de memmove , el implementador generalmente determina primero si las direcciones son directamente comparables. De lo contrario, el resto de la función es específica de la plataforma. La mayoría de las veces, estar en diferentes espacios de memoria es suficiente para garantizar que las regiones no se superpongan y la función se convierta en una memcpy . Si las direcciones son directamente comparables, entonces se trata simplemente de un proceso simple de copia de bytes comenzando desde el primer byte y avanzando o desde el último byte y yendo hacia atrás (lo que uno copiará con seguridad los datos sin golpear nada).

En general, el estándar C deja mucho sin especificar intencionalmente donde no puede escribir una regla simple que funciona en cualquier plataforma de destino. Sin embargo, los escritores estándar podrían haber hecho un mejor trabajo al explicar por qué algunas cosas no están definidas y usar términos más descriptivos como "dependiente de la arquitectura".

Answer 5

Para que dos áreas de memoria sean válidas y superpuestas, creo que debería estar en una de las situaciones definidas de 6.5.8.5. Es decir, dos áreas de una matriz, unión, estructura, etc.

La razón por la que otras situaciones no están definidas se debe a que dos objetos diferentes podrían no estar en el mismo tipo de memoria, con el mismo tipo de puntero. En las arquitecturas de PC, las direcciones generalmente son solo direcciones de 32 bits en la memoria virtual, pero C admite todo tipo de arquitecturas extrañas, donde la memoria no es nada de eso.

La razón por la que C deja las cosas indefinidas es dar espacio a los escritores del compilador cuando la situación no necesita ser definida. La forma de leer 6.5.8.5 es un párrafo que describe cuidadosamente las arquitecturas que C desea admitir cuando la comparación de punteros no tiene sentido a menos que esté dentro del mismo objeto.

Además, la razón por la que el compilador proporciona memmove y memcpy es que a veces se escriben en un ensamblaje sintonizado para la CPU de destino, utilizando una instrucción especializada. No están destinados a ser implementados en C con la misma eficacia.