Agregar Factor de ocupación del heap como problema del GC actual

[z.facultad/75.00/informe.git] / source / dgc.rst

diff --git a/source/dgc.rst b/source/dgc.rst
index 90192467994cf1e5f9e25bb6142a9d52e5ab8a9c..d6d5878777e44a82271781d8acc25dae2d2ba676 100644 (file)
--- a/source/dgc.rst
+++ b/source/dgc.rst
@@ -467,9 +467,9 @@ algoritmo::
       start_the_world()
 
 La variable **global** ``more_to_scan`` indica al algoritmo iterativo cuando
       start_the_world()
 
 La variable **global** ``more_to_scan`` indica al algoritmo iterativo cuando

-debe finalizar: la función ``mark()`` (que veremos más adelante) lo pone en
-``true`` cuando una nueva celda debe ser visitada, por lo tanto la iteración
-se interrumpe cuando no hay más celdas por visitar.
+debe finalizar: la función ``mark_range()`` (que veremos más adelante) lo pone
+en ``true`` cuando una nueva celda debe ser visitada, por lo tanto la
+iteración se interrumpe cuando no hay más celdas por visitar.

 
 Las funciones ``stop_the_world()`` y ``start_the_world()`` sencillamente
 pausan y reanudan todos los hilos respectivamente::
 
 Las funciones ``stop_the_world()`` y ``start_the_world()`` sencillamente
 pausan y reanudan todos los hilos respectivamente::


@@ -517,9 +517,7 @@ Primero se marca el área de memoria estática de manera :ref:`conservativa
 <gc_conserv>` (es decir, tomando cada *word* como si fuera un puntero)::
 
    function mark_static_data() is
 <gc_conserv>` (es decir, tomando cada *word* como si fuera un puntero)::
 
    function mark_static_data() is

-      foreach word in static_data
-         pointer = cast(void*) word
-         mark(pointer)
+      mark_range(static_data.begin, static_data.end)

 
 Para poder tomar los registros como parte del *root set* primero se apilan
 en el *stack* a través de la función::
 
 Para poder tomar los registros como parte del *root set* primero se apilan
 en el *stack* a través de la función::


@@ -533,9 +531,7 @@ los threads para terminar de marcar el *root set*::
 
    function mark_stacks() is
       foreach thread in threads
 
    function mark_stacks() is
       foreach thread in threads

-         foreach word in thread.stack
-            pointer = cast(void*) word
-            mark(pointer)
+         mark_range(thread.stack.begin, thread.stack.end)

 
 Dado que D_ soporta manejo de memoria manual al mismo tiempo que memoria
 automática, es posible que existan celdas de memoria que no estén en el *root
 
 Dado que D_ soporta manejo de memoria manual al mismo tiempo que memoria
 automática, es posible que existan celdas de memoria que no estén en el *root


@@ -546,20 +542,23 @@ estas nuevas raíces. Es por esto que para concluir el marcado del *root set*
 completo se procede a marcar las raíces definidas por el usuario::
 
    function mark_user_roots() is
 completo se procede a marcar las raíces definidas por el usuario::
 
    function mark_user_roots() is

-      foreach pointer in user_roots
-         mark(pointer)
+      foreach root_range in user_roots
+         mark_range(root_range.begin, root_range.end)

 
 El algoritmo de marcado no es recursivo sino iterativo por lo tanto al marcar
 una celda (o bloque) no se siguen sus *hijas*, solo se activa el bit de *scan*
 (a menos que la celda no contenga punteros, es decir, tenga el bit *noscan*)::
 
 
 El algoritmo de marcado no es recursivo sino iterativo por lo tanto al marcar
 una celda (o bloque) no se siguen sus *hijas*, solo se activa el bit de *scan*
 (a menos que la celda no contenga punteros, es decir, tenga el bit *noscan*)::
 

-   function mark(pointer) is
-      [pool, page, block] = find_block(pointer)
-      if block is not null and block.mark is false
-         block.mark = true
-         if block.noscan is false
-            block.scan = true
-            global more_to_scan = true
+   function mark_range(begin, end) is
+      pointer = begin
+      while pointer < end
+         [pool, page, block] = find_block(pointer)
+         if block is not null and block.mark is false
+            block.mark = true
+            if block.noscan is false
+               block.scan = true
+               global more_to_scan = true
+         pointer++

 
 Por lo tanto en este punto, tenemos todas las celdas inmediatamente
 alcanzables desde el *root set* marcadas y con el bit *scan* activado si la
 
 Por lo tanto en este punto, tenemos todas las celdas inmediatamente
 alcanzables desde el *root set* marcadas y con el bit *scan* activado si la


@@ -577,15 +576,11 @@ celdas para visitar (con el bit *scan* activo)::
                      if block.scan is true
                         block.scan = false
                         if page.block_size is PAGE // objeto grande
                      if block.scan is true
                         block.scan = false
                         if page.block_size is PAGE // objeto grande

-                           start = cast(byte*) page
+                           begin = cast(byte*) page

                            end = find_big_object_end(pool, page)
                            end = find_big_object_end(pool, page)

-                           foreach word in start..end
-                                 pointer = cast(void*) word
-                                 mark(pointer)
+                           mark_range(begin, end)

                         else // objeto pequeño
                         else // objeto pequeño

-                           foreach word in block
-                              pointer = cast(void*) word
-                              mark(pointer)
+                           mark_range(block.begin, block.end)

 
 Aquí puede verse, con un poco de esfuerzo, la utilización de la
 :ref:`abstracción tricolor <gc_intro_tricolor>`: todas las celdas alcanzables
 
 Aquí puede verse, con un poco de esfuerzo, la utilización de la
 :ref:`abstracción tricolor <gc_intro_tricolor>`: todas las celdas alcanzables


@@ -1284,10 +1279,8 @@ Asignación de memoria
 
 Recolección
    *mark(pbot, ptop)*
 
 Recolección
    *mark(pbot, ptop)*

-      marca un rango de memoria. Este método es análogo al ``mark()``
-      presentado en la sección :ref:`dgc_algo_mark` pero marca un rango
-      completo de memoria, lo que permite que sea considerablemente más
-      eficiente.
+      marca un rango de memoria. Este método es análogo al ``mark_range()``
+      presentado en la sección :ref:`dgc_algo_mark`.

 
    *fullcollectshell()*
       guarda los registros en el *stack* y llama a ``fullcollect()``. El
 
    *fullcollectshell()*
       guarda los registros en el *stack* y llama a ``fullcollect()``. El


@@ -1423,6 +1416,72 @@ utiliza conjuntos de bits. Esto trae dos ventajas principales:
   considerablemente la fase de marcado.
 
 
   considerablemente la fase de marcado.
 
 

+.. _dgc_debug:
+
+Herramientas para depuración
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+El recolector provee algunas opciones para simplificar el diagnóstico
+y depuración de problemas, tanto del mismo recolector como del programa del
+usuario.
+
+Las opciones más importantes son:
+
+
+``MEMSTOMP``
+   Su función es escribir un patrón determinado de bits en todos los bytes de
+   un bloque de memoria según se haya:
+
+   * Pedido un bloque menor a una página (``0xF0``).
+   * Pedido un bloque mayor a una página (``0xF1``).
+   * Dejado de usar debido a un pedido de achicamiento de un bloque
+     (``0xF2``).
+   * Pedido más páginas debido a un pedido de agrandamiento de un bloque
+     (``0xF0``).
+   * Liberado intencionalmente por el usuario (``0xF2``).
+   * Barrido (``0xF3``).
+
+   Esto permite al diagnosticar un problema saber, por ejemplo, si un
+   determinado área de memoria fue recolectada recientemente, o liberada por
+   el usuario, o recién adquirida, etc. con tan solo ver si un patrón de bits
+   determinado está presente. Por supuesto puede existir *falsos positivos*
+   pero su probabilidad es lo suficientemente baja como para que sea útil en
+   la práctica.
+
+``SENTINEL``
+   Su función detectar errores producidos por escribir más allá (o antes) del
+   área de memoria solicitada y está implementado reservando un poco más de
+   memoria de la que pide el usuario, devolviendo un puntero a un bloque
+   ubicado dentro del bloque real reservado (en vez de al inicio) y finalmente
+   escribiendo un patrón de bits en los extremos del borde real (ver figura
+   :vref:`fig:sentinel`), de forma de poder verificar en distintas situación
+   (por ejemplo al barrer el bloque) que esas áreas de más con los patrones de
+   bits estén intactas. Esto permite detectar de forma temprana errores tanto
+   en el recolector como en el programa del usuario.
+
+   .. fig:: fig:sentinel
+
+      Esquema de un bloque cuando está activada la opción ``SENTINEL``.
+
+      .. aafig::
+
+         |              |              |                              |        |
+         +-- Palabra ---+-- Palabra ---+-- Tamaño bloque de usuario --+- Byte -+
+         |              |              |                              |        |
+
+         +--------------+--------------+------------------------------+--------+
+         |  Tamaño del  |     Pre      |                              |  Post  |
+         |  bloque  de  |              |      Bloque de usuario       |        |
+         |    usuario   |  0xF4F4F4F4  |                              |  0xF5  |
+         +--------------+--------------+------------------------------+--------+
+                                       A
+                                       |
+                   Puntero devuleto ---/
+
+Ambas opciones son seleccionables sólo en tiempo de compilación del
+recolector, por lo que su utilidad real, al menos para el usuario, se ve
+severamente reducida.
+

 
 .. _dgc_bad:
 
 
 .. _dgc_bad:
 


@@ -1584,8 +1643,8 @@ y en particular para mejorar la implementación de de arreglos asociativos.
 Referencias débiles
 ^^^^^^^^^^^^^^^^^^^
 El recolector actual no dispone de soporte de *referencias débiles*
 Referencias débiles
 ^^^^^^^^^^^^^^^^^^^
 El recolector actual no dispone de soporte de *referencias débiles*

-[#dgcweakref]_, sin embargo hay una demanda [NGD86840]_ [NGD13301]_ [NGL8264]_
-[NGD69761]_ [NGD74624]_ [NGD88065]_
+[#dgcweakref]_, sin embargo hay una demanda apreciable [NGD86840]_ [NGD13301]_
+[NGL8264]_ [NGD69761]_ [NGD74624]_ [NGD88065]_.

 
 .. [#dgcweakref] Una referencia débil (o *weak reference* en inglés) es
    aquella que que no protege al objeto referenciado de ser reciclado por el
 
 .. [#dgcweakref] Una referencia débil (o *weak reference* en inglés) es
    aquella que que no protege al objeto referenciado de ser reciclado por el


@@ -1594,7 +1653,7 @@ El recolector actual no dispone de soporte de *referencias débiles*
 Para cubrir esta demanda, se han implementado soluciones como biblioteca para
 suplir la inexistencia de una implementación oficial [NGA9103]_.
 
 Para cubrir esta demanda, se han implementado soluciones como biblioteca para
 suplir la inexistencia de una implementación oficial [NGA9103]_.
 

-Sin embargo éstas son en general poco robustas y extremadamente dependientes
+Sin embargo éstas son en general poco robustas, extremadamente dependientes

 de la implementación del recolector y, en general, presentan problemas muy
 sutiles [NGD88065]_. Por esta razón se ha discutido la posibilidad de incluir
 la implementación de *referencias débiles* como parte del lenguaje
 de la implementación del recolector y, en general, presentan problemas muy
 sutiles [NGD88065]_. Por esta razón se ha discutido la posibilidad de incluir
 la implementación de *referencias débiles* como parte del lenguaje


@@ -1662,6 +1721,37 @@ bits para la fase de marcado, el resto del algoritmo es casi la versión más
 básica de marcado y barrido. Hay mucho lugar para mejoras en este sentido.
 
 
 básica de marcado y barrido. Hay mucho lugar para mejoras en este sentido.
 
 

+Configurabilidad
+^^^^^^^^^^^^^^^^
+Si bien el recolector actual tiene algunas características configurables,
+todas son seleccionables sólo en tiempo de compilación del recolector (no del
+programa del usuario), como por ejemplo las opciones descriptas en
+:ref:`dgc_debug`. Por lo tanto, a nivel práctico, es como si no tuviera
+posibilidad alguna de ser configurado por el usuario, ya que no es parte del
+ciclo de desarrollo normal el recompilar el recolector o *runtime* de un
+lenguaje.
+
+Dado que es imposible que un recolector sea óptimo para todo tipo de
+programas, es muy deseable permitir una configuración de parámetros del
+recolector que permitan al usuario ajustarlo a las necesidades particulares de
+sus programas.
+
+
+.. _dgc_bad_ocup:
+
+Factor de ocupación del *heap*
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Otro problema potencialmente importante del recolector actual es que no se
+tiene ningún cuidado con respecto a que, luego de una recolección, se haya
+recuperado una buena parte del *heap*. Por lo tanto, en casos extremos, el
+recolector tiene que hacer una recolección por cada petición de memoria, lo
+que es extremadamente ineficiente.
+
+Para evitar esto, habría que usar algún esquema para evaluar cuando una
+recolección no fue lo suficientemente *exitosa* y en ese caso pedir más
+memoria al sistema operativo.
+
+

 Detalles
 ^^^^^^^^
 Finalmente hay varios detalles en la implementación actual que podrían
 Detalles
 ^^^^^^^^
 Finalmente hay varios detalles en la implementación actual que podrían