java - para - que es jvm en programacion

Reordenamiento de instrucciones en Java JVM.

Question

Estaba leyendo este blogpost: http://jeremymanson.blogspot.hk/2008/12/benign-data-races-in-java.html

Y el autor estaba hablando de romper el hashCode() en String en un entorno multihilo.

Por tener:

public int hashCode() {
     int h = hash;
     if (h == 0) {
         int off = offset;
         char val[] = value;
         int len = count;

         for (int i = 0; i < len; i++) {
             h = 31*h + val[off++];
         }
         hash = h;
     }
     return h;
 }

Cambiado a:

public int hashCode() {
     if (hash == 0) {
         int off = offset;
         char val[] = value;
         int len = count;

         int h = 0;
         for (int i = 0; i < len; i++) {
             h = 31*h + val[off++];
         }
         hash = h;
     }
     return hash;
 }

Lo que el autor dice y cito:

"Lo que he hecho aquí es agregar una lectura adicional: la segunda lectura de hash, antes de la devolución . Por extraño que parezca, y por muy improbable que sea, la primera lectura puede devolver el valor de hash calculado correctamente, y la segunda lectura puede devolver 0. Esto se permite en el modelo de memoria porque el modelo permite una reordenación extensa de las operaciones. La segunda lectura se puede mover realmente, en su código, ¡para que su procesador lo haga antes de la primera! "

Así que más allá de los comentarios, alguien dice que se puede reordenar a

int h = hash;
if (hash == 0) {
  ...
}
return h;

¿Cómo es eso posible? Pensé que reordenar solo implica mover las declaraciones del programa hacia arriba y hacia abajo. ¿Qué reglas sigue? Busqué en Google, leí las preguntas frecuentes sobre JSR133, revisé el libro de Java Concurrencia en la práctica, pero parece que no puedo encontrar un lugar que me ayude a entender, especialmente en lo que respecta a reordenar. Si alguien me puede orientar en la dirección correcta, realmente lo apreciaría.

Edit: gracias a Louis que aclara el significado de "Reordenar", no estaba pensando en términos de "byteCode"

Sin embargo, todavía no entiendo por qué está permitido mover la segunda lectura al frente, este es mi ingenuo intento de traducirlo a un formato "bytecode".

Para simplificar, las operaciones que se utilizan para calcular el calchash() se expresan como calchash() . Por lo tanto, expreso el programa como:

if (hash == 0)  {       
    h = calchash();
    hash = h;
}
return hash;

Y mi intento de expresarlo en "bytecode" forma:

R1,R2,R3 are in the operands stack, or the registers
h is in the array of local variables

En orden del programa:

if (hash == 0)  {       ---------- R1 = read hash from memory (1st read)
                        ---------- Compare (R1 == 0)
    h = calchash();     ---------- R2 = calchash()
                        ---------- h = R2 (Storing the R2 to local variable h)
    hash = h;           ---------- Hash = h (write to hash)
}
return hash             ---------- R3 = read hash from memory again(2nd read)
                        ---------- return R3

Transformación reordenada (Mi versión basada en comentarios):

                        ---------- R3 = read hash from memory (2nd read) *moved*
if (hash == 0)  {       ---------- R1 = read hash from memory (1st read)
                        ---------- Compare (R1 == 0)
    h = calchash();     ---------- R2 = calchash()
                        ---------- h = R2 (Storing the R2 to local variable h)
    hash = h;           ---------- hash = h (write to hash)
}
return hash             ---------- return R3

Edit: revisando los comentarios otra vez, encontré esto contestado por el autor

Transformación reordenada (del blog)

r1 = hash;
if (hash == 0) {
  r1 = hash = // calculate hash
}
return r1;

Este caso realmente funciona en un solo hilo, pero es posible fallar con varios hilos.

Parece que las JVM están haciendo simplificaciones basadas en

h = hash y simplifica el uso de R1, R2, R3 a R1 único

Por lo tanto, JVM hace más que reordenar las instrucciones, también parece reducir la cantidad de registros que se utilizan.

¿Alguna idea?

Answer 1

Creo que la clave a tener en cuenta es que en el subproceso que recibe la respuesta incorrecta (devuelve 0), el cuerpo de la sentencia if no se ejecuta, ignorarlo, podría ser cualquier cosa.

El hilo de lectura incorrecto lee el campo no volátil dos veces, pero nunca lo escribe. Así que estamos hablando de la ordenación de dos lecturas. El reclamo es que estos no están ordenados. En situaciones más complicadas puede haber aliasing, y no sería trivial que el compilador compruebe si esta era la misma ubicación de memoria o no. Tomar la ruta conservadora podría evitar optimizaciones.

Answer 2

En su código modificado:

public int hashCode() {
     if (hash == 0) { // (1)
         int off = offset;
         char val[] = value;
         int len = count;

         int h = 0;
         for (int i = 0; i < len; i++) {
             h = 31*h + val[off++];
         }
         hash = h;
     }
     return hash; // (2)
 }

(1) y (2) se podrían reordenar: (1) podría leer un valor no nulo mientras que (2) se leería 0. Eso no puede suceder en la implementación real en la clase String porque el cálculo se realiza en la variable local y el valor de retorno también es esa variable local, que, por definición, es segura para subprocesos.

El problema es que el modelo de memoria Java no ofrece ninguna garantía cuando se accede a una variable compartida ( hash ) sin la sincronización adecuada, en particular, no garantiza que todas las ejecuciones sean coherentes de forma secuencial. Si el hash hubiera sido volátil, no habría ningún problema con el código modificado.

ps: el autor de ese blog, creo, es uno de los escritores del Capítulo 17 (Modelo de Memoria de Java) del JLS, así que tendería a creerle de todos modos ;-)

ACTUALIZAR

Siguiendo las diversas ediciones / comentarios, veamos el código de bytes con más detalles con estos dos métodos (asumo que el código de hash es siempre 1 para mantener las cosas simples):

public int hashcode_shared() {
    if (hash == 0) { hash = 1; }
    return hash;
}

public int hashcode_local() {
    int h = hash;
    if (h == 0) { hash = h = 1; }
    return h;
}

El compilador java en mi máquina genera el siguiente bytecode:

public int hashcode_shared();
   0: aload_0                           //read this
   1: getfield      #6                  //read hash (r1)
   4: ifne          12                  //compare r1 with 0
   7: aload_0                           //read this
   8: iconst_1                          //constant 1
   9: putfield      #6                  //put 1 into hash (w1)
  12: aload_0                           //read this
  13: getfield      #6                  //read hash (r2)
  16: ireturn                           //return r2

public int hashcode_local();
   0: aload_0                           //read this
   1: getfield      #6                  //read hash (r1)
   4: istore_1                          //store r1 in local variable h
   5: iload_1                           //read h
   6: ifne          16                  //compare h with 0
   9: aload_0                           //read this
  10: iconst_1                          //constant 1
  11: dup                               //constant again
  12: istore_1                          //store 1 into h
  13: putfield      #6                  //store 1 into hash (w1)
  16: iload_1                           //read h
  17: ireturn                           //return h

En el primer ejemplo, hay 2 lecturas de la variable compartida hash : r1 y r2. Como se mencionó anteriormente, debido a que no hay sincronización y la variable se comparte, se aplica el Modelo de Memoria Java y se permite que un compilador / JVM reordene las dos lecturas: la línea # 13 podría insertarse antes de la línea # 1 *.

En el segundo ejemplo, todas las operaciones en h , la variable local, deben ser secuencialmente coherentes debido a la semántica intra-hilo y la garantía de orden del programa en variables no compartidas.

Nota: como siempre, el hecho de que se permita la reordenación no significa que se llevará a cabo. En realidad, es poco probable que ocurra en las combinaciones actuales de x86 / hotspot. Pero podría suceder en otras arquitecturas actuales o futuras / JVM.

* Eso es un atajo, lo que podría suceder en la práctica es que el compilador podría reescribir hashcode_shared esta manera:

public int hashcode_shared() {
    int h = hash;
    if (hash != 0) return h;
    return (hash = 1);
}

El código es estrictamente equivalente en un entorno de un solo hilo (siempre devolverá el mismo valor que el método original), por lo que se permite la reordenación. Pero en un entorno de múltiples subprocesos, está claro que si hash cambia de 0 a 1 por otro subproceso entre las dos primeras líneas, este método reordenado devolverá incorrectamente 0.

Answer 3

En términos sencillos, creo que este problema tiene que ver con el reordenamiento de lectura (búsqueda).

Cada subproceso, T1 y T2, desea obtener todas sus "entradas" para hacer el procesamiento (y sin la marcación volatile estricta) se les da cierta libertad en cuanto a cómo / cuándo leer sus datos.

El mal caso:

Cada hilo debe leer la variable (instancia) dos veces , una para comprobar if y una vez el valor de retorno. Digamos, para argumentar, que T1 elige hacer la lectura en primer lugar y T2 elige hacer la lectura de return primero.

Esto crea la condición de carrera en la que la variable hash se cambia (por T1) entre la actualización de hash por T1 y la segunda lectura de T2 (que T2 usa para verificar la condición if ). Así que ahora la prueba de T2 es falsa, no hace nada y devuelve lo que leyó (originalmente) para la variable de instancia, 0.

El caso fijo:

Cada hilo solo necesita leer la variable (instancia) una vez , y luego la almacena inmediatamente en su propia variable local. Esto evita que ocurra el problema de lectura de reordenación (ya que solo hay una lectura).

Answer 4

Primero el código malo :

int hash = 0;

public int hashCode() {
     if (hash == 0) {
         int off = offset;
         char val[] = value;
         int len = count;

         int h = 0;
         for (int i = 0; i < len; i++) {
             h = 31*h + val[off++];
         }
         hash = h;
     }
     return hash;
 }

Claramente podemos reducir esto a sus huesos desnudos como:

int hash = 0;

public int hashCode() {
     if (hash == 0) {
         // Assume calculateHash does not return 0 and does not modify hash.
         hash = calculateHash();
     }
     return hash;
 }

ahora la teoría sugiere que un reordenamiento en un hilo entrelazado de una manera particular con un segundo hilo puede resultar en un retorno de cero. El único escenario que puedo imaginar sería algo como:

// Pseudocode for thread 1 starts with <1>, thread 2 with <2>. 
// Rn are local registers.
public int hashCode() {
     <2> has not begun
     <1> load r1 with hash (==0) in preparation for return for when hash is != 0
     <2> begins execution - finds hash == 0 and starts the calculation
     <2> modifies hash to contain new value.
     <1> Check hash for zero - it is not so skip the contents of the if
     if (hash == 0) {
         // Assume calculateHash does not return 0 and does not modify hash.
         hash = calculateHash();
         <2> got here but at a time when <1> was up there ^^
     }
     <1> return r1 - supposedly containing a zero.
     return hash;
 }

pero luego, para mí, se puede hacer un tratamiento similar con el código bueno:

public int hashCode() {
     int h = hash;
     if (h == 0) {
         hash = h = calculateHash();
     }
     return h;
 }

y entonces

public int hashCode() {
     <2> has not begun
     <1> load r1 with hash (==0) in preparation for return for when h is != 0
     <2> begins execution - finds h == 0 and starts the calculation
     <2> modifies hash to contain new value.
     <1> load r2 with hash - from now on r2 is h
     int h = hash;
     <1> Check r2 for zero - it is not so skip the contents of the if
     if (h == 0) {
         hash = h = calculateHash();
     }
     <1> we know that when hash/h are non-zero it doesn''t matter where we get our return from - both r1 and r2 must have the same value.
     <1> return r1 - supposedly containing a zero.
     return h;
 }

No entiendo por qué uno es una posibilidad real y el otro no lo es.