¿Es posible almacenar punteros de memoria compartida sin necesidad de utilizar las compensaciones?

Question

Cuando se utiliza la memoria compartida, cada proceso puede mmap la región compartida en un área diferente de su respectivo espacio de direcciones. Esto significa que al almacenar punteros dentro de la región compartida, es necesario almacenarlos como compensaciones del inicio de la región compartida. Por desgracia, esto complica el uso de las instrucciones atómicas (por ejemplo, si usted está tratando de escribir una bloquear algoritmo libre ). Por ejemplo, supongamos que tiene un grupo de nodos de referencia contados en la memoria compartida, creados por un solo escritor. El escritor actualiza periódicamente atómicamente un puntero 'p' para apuntar a un nodo válido con el recuento de referencia positiva. Los lectores quieren escribir atómicamente a 'p' porque señala el comienzo de un nodo (una estructura) cuyo primer elemento es un contador de referencia. Como p siempre apunta a un nodo válido, incrementando el contador ref es seguro, y hace que sea seguro para eliminar la referencia de 'p' y el acceso a otros miembros. Sin embargo, todo esto sólo 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 = lectura p
2. y = x + offset
3. refcount Incremento en Y

Durante la etapa 2, p puede cambiar y X puede ya no apuntan a un nodo válido. La única solución que se me ocurre alguna manera está obligando a todos los procesos de ponerse de acuerdo sobre dónde trazar la memoria compartida, por lo que los punteros reales en lugar de las compensaciones pueden ser almacenados en la región mmap'd. ¿Hay alguna forma de hacer eso? Veo MAP_FIXED en la documentación mmap, pero no sé cómo pude recoger una dirección que sería seguro.

Editar: El uso de ensamblado en línea y el prefijo 'bloqueo' en x86 tal vez es posible construir un "incremento ptr X con el offset Y por valor Z"? opciones equivalentes en otras arquitecturas? no han escrito una gran cantidad de ensamblaje, no sé si se dan las instrucciones necesarias.

Answer 1

En el bajo nivel inctruction atómica x86 puede hacer todo esto los pasos de los árboles a la vez:

1. x = lectura p
2. y = x + offset Incremento
3. refcount a 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

Esto es trivial en un 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 () atribuye la memoria compartida   segmento identificado por shmid a la   espacio de direcciones del proceso de llamada.   La dirección de pegado se especifica en   shmaddr con una de las siguientes   criterios:

     

Si shmaddr es NULL, el sistema elige   un (sin usar) dirección adecuada a la cual   para unir el segmento.

Sólo especifique su propio correo electrónico 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 los mismos en todos los procesos. El núcleo no importa qué rango de direcciones que utilice, siempre y cuando no entre en conflicto con dondequiera que normalmente se asigna cosas. (Si se omite la dirección, se puede ver la región general que le gusta poner las cosas;. También, comprobar las direcciones en la pila y volver de malloc () / new [])

En Linux, asegúrese de que la raíz establece SHMMAX en / proc / sys / kernel / shmmax en un número lo suficientemente grande como para dar cabida a sus segmentos de memoria compartida (por defecto es de 32 MB).

En cuanto a las operaciones atómicas, se puede llegar a todos ellos desde el código fuente del núcleo de Linux, por ejemplo,

  

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 3

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

Answer 4

Usted no debe tener miedo de hacer una dirección al azar, debido a que el kernel que acaba rechazará direcciones que no le gustan (los que están en conflicto). Véase mi respuesta shmat() anteriormente, utilizando 0x20000000000

Con mmap:

  

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

     

Si addr no es NULL, entonces el núcleo   lo toma como una pista sobre dónde   colocar el mapeo; En Linux, el   mapeo se creará en la próxima   alto límite de página. 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   otros procesos de mapeo de la misma   región, y si hay actualizaciones   llevado a través de la subyacente   archivo. Este comportamiento está determinado por   incluyendo exactamente una de las siguientes   valores en las banderas:

     

MAP_SHARED Compartir este mapeo.   Las actualizaciones de la cartografía son visibles para   otros procesos que se asignan este   archivo, y se llevan a través de la   de archivos subyacente. El archivo no puede   en realidad ser actualizado hasta msync (2) o   munmap () es llamado.

     

ERROR

     

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

La adición de la compensación al puntero no crea el potencial para una carrera, que ya existe. Desde por lo menos dos ramas ni x86 pueden leer atómicamente un puntero a continuación, acceder a la memoria se refiere a lo que necesita para proteger el acceso puntero con una cerradura con independencia de si se agrega un offset.