¿Es posible almacenar punteros en la memoria compartida sin utilizar desplazamientos?

Question

Al usar la memoria compartida, cada proceso puede mapear la región compartida en un área diferente de su espacio de direcciones respectivo. Esto significa que cuando almacena punteros dentro de la región compartida, necesita store them as offsets del inicio de la región compartida. Desafortunadamente, esto complica el uso de las instrucciones atómicas (por ejemplo, si está intentando escribir un lock free algorithm). Por ejemplo, supongamos que tiene un grupo de nodos de referencia contados en la memoria compartida, creados por un solo escritor. El autor periódicamente actualiza atómicamente un puntero 'p' para apuntar a un nodo válido con recuento de referencia positivo. Los lectores quieren escribir atómicamente a 'p' porque apunta al comienzo de un nodo (una estructura) cuyo primer elemento es un recuento de referencia. Como p siempre apunta a un nodo válido, incrementar el recuento de ref es seguro, y hace que sea seguro quitar la referencia 'p' y acceder a otros miembros. Sin embargo, todo esto solo funciona cuando todo está en el mismo espacio de direcciones. Si los nodos y el puntero 'p' se almacenan en la memoria compartida, los clientes sufren una condición de carrera:

1. x = leer p
2. y = x + compensado
3. refcount Incremento en y

Durante el paso 2, p puede cambiar y x ya no apunta a un nodo válido. La única solución que se me ocurre es obligar de algún modo a todos los procesos a ponerse de acuerdo sobre dónde asignar la memoria compartida, de modo que puedan almacenarse punteros reales en lugar de desplazamientos en la región mmap'd. ¿Hay alguna forma de hacer eso? Veo MAP_FIXED en la documentación de mmap, pero no sé cómo podría elegir una dirección segura.

Editar: Usando el ensamblaje en línea y el prefijo 'candado' en x86 tal vez sea posible construir un "incremento ptr X con desplazamiento Y por valor Z"? Opciones equivalentes en otras arquitecturas? No he escrito mucho montaje, no sé si existen las instrucciones necesarias.

Answer 1

El bajo nivel del inctruction atómica x86 puede hacer todos estos pasos de árboles a la vez:

1. x = leer p
2. y = x + compensado Incremento
3. refcount en y

// 
     mov edi, Destination 
     mov edx, DataOffset 
     mov ecx, NewData 
@Repeat: 
     mov eax, [edi + edx] //load OldData 
//Here you can also increment eax and save to [edi + edx]   
     lock cmpxchg dword ptr [edi + edx], ecx 
     jnz @Repeat 
// 

Answer 2

Tenemos un código que es similar a la descripción del problema. Utilizamos un archivo mapeado en memoria, compensaciones y bloqueo de archivos. No hemos encontrado una alternativa.

Answer 3

Esto es trivial en una Sistema UNIX; sólo tiene que utilizar las funciones de memoria compartida:

shgmet, shmat, shmctl, shmdt

void * shmat (int shmid, const void * shmaddr, int shmflg);

shmat() une el segmento de memoria compartida identificado por shmid al espacio dirección del proceso de llamada. La dirección de pegado se especifica en shmaddr con uno de los siguientes criterios:

Si shmaddr es NULL, el sistema elige una dirección adecuada (no se utiliza) en la que para unir el segmento.

Simplemente especifique su dirección aquí; p.ej. 0x20000000000

Si shmget() utilizando la misma clave y tamaño en cada proceso, obtendrá el mismo segmento de memoria compartida. Si shmat() en la misma dirección, las direcciones virtuales serán las mismas en todos los procesos. Al kernel no le importa qué rango de direcciones use, siempre y cuando no entre en conflicto con el lugar donde normalmente asigna cosas. (Si omite la dirección, puede ver la región general en la que le gusta poner las cosas; también, compruebe las direcciones en la pila y regresó de malloc()/new [].)

En Linux, asegúrese de que la raíz establece SHMMAX en/proc/sys/kernel/shmmax en un número suficientemente grande para acomodar sus segmentos de memoria compartida (el valor predeterminado es 32MB).

En cuanto a las operaciones atómicas, puede obtenerlas todas de la fuente del kernel de Linux, p.

include/asm-x86/atomic_64.h

/* 
* Make sure gcc doesn't try to be clever and move things around 
* on us. We need to use _exactly_ the address the user gave us, 
* not some alias that contains the same information. 
*/ 
typedef struct { 
     int counter; 
} atomic_t; 

/** 
* atomic_read - read atomic variable 
* @v: pointer of type atomic_t 
* 
* Atomically reads the value of @v. 
*/ 
#define atomic_read(v)   ((v)->counter) 

/** 
* atomic_set - set atomic variable 
* @v: pointer of type atomic_t 
* @i: required value 
* 
* Atomically sets the value of @v to @i. 
*/ 
#define atomic_set(v, i)    (((v)->counter) = (i)) 


/** 
* atomic_add - add integer to atomic variable 
* @i: integer value to add 
* @v: pointer of type atomic_t 
* 
* Atomically adds @i to @v. 
*/ 
static inline void atomic_add(int i, atomic_t *v) 
{ 
     asm volatile(LOCK_PREFIX "addl %1,%0" 
        : "=m" (v->counter) 
        : "ir" (i), "m" (v->counter)); 
} 

versión de 64 bits:

typedef struct { 
     long counter; 
} atomic64_t; 

/** 
* atomic64_add - add integer to atomic64 variable 
* @i: integer value to add 
* @v: pointer to type atomic64_t 
* 
* Atomically adds @i to @v. 
*/ 
static inline void atomic64_add(long i, atomic64_t *v) 
{ 
     asm volatile(LOCK_PREFIX "addq %1,%0" 
        : "=m" (v->counter) 
        : "er" (i), "m" (v->counter)); 
} 

Answer 4

Usted no debe tener miedo de hacer una dirección al azar, porque el kernel simplemente rechazará las direcciones que no le gustan (las que entran en conflicto). Véase mi respuesta anterior shmat(), utilizando 0x20000000000

Con mmap:

void * mmap (void * addr, size_t length, int prot, int banderas, int fd, off_t offset);

Si addr no es NULO, entonces el kernel lo toma como una pista sobre dónde ubicar la asignación; en Linux, la asignación se creará en el siguiente límite de página superior . La dirección de la nueva asignación se devuelve como el resultado de la llamada.

El argumento flags determina si cambios a la cartografía son visibles para otra procesos de mapeo la misma región, y si las actualizaciones se realizan a través de a la de archivos subyacente. Este comportamiento está determinado por incluyendo exactamente uno de los valores siguientes en banderas:

MAP_SHARED Compartir esta asignación. Las actualizaciones de la asignación son visibles para otros procesos que mapean este archivo , y se transfieren al archivo subyacente .El archivo no puede realmente actualizarse hasta que se llame a msync (2) o munmap().

ERRORES

EINVAL No nos gusta addr, longitud o desplazamiento (por ejemplo, son demasiado grandes, o no alineados en un límite de página).

Answer 5

Agregar el desplazamiento al puntero no crea el potencial para una carrera, ya existe. Dado que al menos ni ARM ni x86 pueden leer atómicamente un puntero y acceder a la memoria a la que se refiere, debe proteger el acceso del puntero con un bloqueo independientemente de si agrega un desplazamiento.