algoritmo::
function mark_phase() is
- more_to_scan = false
+ global more_to_scan = false
stop_the_world()
clear_mark_scan_bits()
mark_free_lists()
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::
<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::
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
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*)::
- 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
- 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
celdas para visitar (con el bit *scan* activo)::
function mark_heap() is
- while more_to_scan
- more_to_scan = false
+ while global more_to_scan
+ global more_to_scan = false
foreach pool in heap
foreach page in pool
if page.block_size <= PAGE // saltea FREE y CONTINUATION
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)
- foreach word in start..end
- pointer = cast(void*) word
- mark(pointer)
+ mark_range(begin, end)
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
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
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:
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
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
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
projects / z.facultad / 75.00 / informe.git / blobdiff