X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/f0fa88b43b9fae7a2011ffeb77e1311060d1bc12..a112b981181e8bd7bafc51d657dbf862e90612fd:/source/dgc.rst?ds=sidebyside diff --git a/source/dgc.rst b/source/dgc.rst index 9019246..804d554 100644 --- a/source/dgc.rst +++ b/source/dgc.rst @@ -461,25 +461,36 @@ algoritmo:: 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() 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()`` 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 @@ -517,9 +528,7 @@ Primero se marca el área de memoria estática de manera :ref:`conservativa ` (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:: @@ -528,14 +537,19 @@ en el *stack* a través de la función:: 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 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 @@ -546,20 +560,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 - 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 - 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 @@ -577,15 +594,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 - 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 `: todas las celdas alcanzables @@ -665,9 +678,9 @@ objetos grandes se marcan todas las páginas que utilizaban como ``FREE``:: 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 @@ -746,16 +759,15 @@ suficientemente grande como para poder almacenar el tamaño solicitado). Una 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 @@ -765,39 +777,41 @@ pidiendo memoria al *low level allocator* (el sistema operativo generalmente). 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 ` provisto por el *low level allocator* y en la @@ -813,22 +827,22 @@ Si el tamaño de bloque necesario para cumplir con la asignación de memoria es 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 @@ -854,34 +868,34 @@ completamente libres:: 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 @@ -1284,10 +1298,8 @@ Asignación de memoria 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 @@ -1319,6 +1331,8 @@ a ningún destructor), para el usuario puede ser una garantía muy débil y proveer finalización asegurada puede ser muy deseable. +.. _dgc_committed: + Memoria *encomendada* ^^^^^^^^^^^^^^^^^^^^^ El algoritmo actual divide un *pool* en dos áreas: memoria *encomendada* @@ -1423,6 +1437,73 @@ utiliza conjuntos de bits. Esto trae dos ventajas principales: 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: @@ -1436,6 +1517,8 @@ participación y observación del grupo de noticias, de donde se obtuvieron los 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 @@ -1584,8 +1667,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* -[#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 @@ -1594,7 +1677,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]_. -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 @@ -1662,6 +1745,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. +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