mark_free_lists()
mark_static_data()
push_registers_into_stack()
+ thread_self.stack.end = get_stack_top()
mark_stacks()
+ pop_registers_from_stack()
mark_user_roots()
mark_heap()
start_the_world()
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()`` pausan y reanudan
+todos los hilos respectivamente (salvo el actual). Al pausar los hilos además
+se guardan los registros del procesador en el *stack* y se guarda la posición
+actual del *stack* para que la fase de marcado pueda recorrerlos::
function stop_the_world() is
foreach thread in threads
+ if thread is thread_self
+ continue
thread.pause()
+ push_registers_into_stack()
+ thread.stack.end = get_stack_top()
function start_the_world() is
foreach thread in threads
+ if thread is thread_self
+ continue
+ pop_registers_from_stack()
thread.resume()
La función ``clear_mark_scan_bits()`` se encarga de restablecer todos los
foreach register in registers
push(register)
+Y luego se descartan (no es necesario ni correcto restablecer los valores ya
+que podrían tener nuevos valores) al sacarlos de la pila::
+
+ function pop_registers_from_stack() is
+ foreach register in reverse(registers)
+ pop()
+
Una vez hecho esto, basta marcar (de forma conservativa) los *stacks* de todos
los threads para terminar de marcar el *root set*::
function free_big_object(pool, page) is
pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages)
do
- page = cast(byte*) page + PAGE_SIZE
page.block_size = FREE
- while page.block_size is CONTINUATION and page < pool_end
+ page = cast(byte*) page + PAGE_SIZE
+ while page < pool_end and page.block_size is CONTINUATION
Además, los bloques que tienen en atributo ``final`` son finalizados llamando
a la función ``finalize()``. Esta función es un servicio que provee la
vez más el algoritmo distingue objetos grandes de pequeños. Los pequeños se
asignan de las siguiente manera::
- function new_small(block_size) is
+ function new_small(block_size) is
+ block = find_block_with_size(block_size)
+ if block is null
+ collect()
block = find_block_with_size(block_size)
if block is null
- collect()
+ new_pool()
block = find_block_with_size(block_size)
- if block is null
- new_pool()
- block = find_block_with_size(block_size)
- return null
- return block
+ return block
Se intenta reiteradas veces conseguir un bloque del tamaño correcto libre,
realizando diferentes acciones si no se tiene éxito. Primero se intenta hacer
Para intentar buscar un bloque de memoria libre se realiza lo siguiente::
- function find_block_with_size(block_size) is
+ function find_block_with_size(block_size) is
+ block = free_lists[block_size].pop_first()
+ if block is null
+ assign_page(block_size)
block = free_lists[block_size].pop_first()
- if block is null
- assign_page(block_size)
- block = free_lists[block_size].pop_first()
- return block
+ return block
Si no se puede obtener un bloque de la lista de libres correspondiente, se
busca asignar una página libre al tamaño de bloque deseado de forma de
*alimentar* la lista de libres con dicho tamaño::
- function assign_page(block_size) is
- foreach pool in heap
- foreach page in pool
- if page.block_size is FREE
- page.block_size = block_size
- foreach block in page
- free_lists[page.block_size].link(block)
+ function assign_page(block_size) is
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size is FREE
+ page.block_size = block_size
+ foreach block in page
+ free_lists[page.block_size].link(block)
Cuando todo ello falla, el último recurso consiste en pedir memoria al sistema
operativo, creando un nuevo *pool*::
- funciones new_pool(number_of_pages = 1) is
- pool = alloc(pool.sizeof)
- if pool is null
- return null
- pool.number_of_pages = number_of_pages
- pool.pages = alloc(number_of_pages * PAGE_SIZE)
- if pool.pages is null
- free(pool)
- return null
- heap.add(pool)
- return pool
+ function new_pool(number_of_pages = 1) is
+ pool = alloc(pool.sizeof)
+ if pool is null
+ return null
+ pool.number_of_pages = number_of_pages
+ pool.pages = alloc(number_of_pages * PAGE_SIZE)
+ if pool.pages is null
+ free(pool)
+ return null
+ heap.add(pool)
+ foreach page in pool
+ page.block_size = FREE
+ return pool
Se recuerda que la función ``alloc()`` es un :ref:`servicio
<gc_intro_services>` provisto por el *low level allocator* y en la
de una página, entonces se utiliza otro algoritmo para alocar un objeto
grande::
- function new_big(size) is
- number_of_pages = ceil(size / PAGE_SIZE)
+ function new_big(size) is
+ number_of_pages = ceil(size / PAGE_SIZE)
+ pages = find_pages(number_of_pages)
+ if pages is null
+ collect()
pages = find_pages(number_of_pages)
if pages is null
- collect()
- pages = find_pages(number_of_pages)
- if pages is null
- minimize()
- pool = new_pool(number_of_pages)
- if pool is null
- return null
- pages = assign_pages(pool, number_of_pages)
- pages[0].block_size = PAGE
- foreach page in pages[1..end]
- page.block_size = CONTINUATION
- return pages[0]
+ minimize()
+ pool = new_pool(number_of_pages)
+ if pool is null
+ return null
+ pages = assign_pages(pool, number_of_pages)
+ pages[0].block_size = PAGE
+ foreach page in pages[1..end]
+ page.block_size = CONTINUATION
+ return pages[0]
De forma similar a la asignación de objetos pequeños, se intenta encontrar una
serie de páginas contiguas, dentro de un mismo *pool*, suficientes para
Volviendo a la función ``new_big()``, para hallar una serie de páginas
contiguas se utiliza el siguiente algoritmo::
- function find_pages(number_of_pages) is
- foreach pool in heap
- pages = assign_pages(pool, number_of_pages)
- if pages
- return pages
- return null
+ function find_pages(number_of_pages) is
+ foreach pool in heap
+ pages = assign_pages(pool, number_of_pages)
+ if pages
+ return pages
+ return null
Como se dijo, las páginas deben estar contenidas en un mismo *pool* (para
tener la garantía de que sean contiguas), por lo tanto se busca *pool* por
*pool* dicha cantidad de páginas libres consecutivas a través del siguiente
algoritmo::
- function assign_pages(pool, number_of_pages) is
- pages_found = 0
- first_page = null
- foreach page in pool
- if page.block_size is FREE
- if pages_found is 0
- pages_found = 1
- first_page = page
- else
- pages_found = pages_found + 1
- if pages_found is number_of_pages
- return [first_page .. page]
+ function assign_pages(pool, number_of_pages) is
+ pages_found = 0
+ first_page = null
+ foreach page in pool
+ if page.block_size is FREE
+ if pages_found is 0
+ pages_found = 1
+ first_page = page
else
- pages_found = 0
- first_page = null
- return null
+ pages_found = pages_found + 1
+ if pages_found is number_of_pages
+ return [first_page .. page]
+ else
+ pages_found = 0
+ first_page = null
+ return null
Una vez más, cuando todo ello falla (incluso luego de una recolección), se
intenta alocar un nuevo *pool*, esta vez con una cantidad de páginas
y proveer finalización asegurada puede ser muy deseable.
+.. _dgc_committed:
+
Memoria *encomendada*
^^^^^^^^^^^^^^^^^^^^^
El algoritmo actual divide un *pool* en dos áreas: memoria *encomendada*
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::
+ :textual:
+
+ | | | | |
+ +-- 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:
principales problemas percibidos por la comunidad que utiliza el lenguaje.
+.. _dgc_bad_code:
+
Complejidad del código y documentación
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
El análisis del código fue muy complicado debido a la falta de documentación
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