Agregar ext/ftable para tablas flotantes

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

diff --git a/source/dgc.rst b/source/dgc.rst
index 90192467994cf1e5f9e25bb6142a9d52e5ab8a9c..14d78aad3e9148489f87a7c56cbd31611d5f513f 100644 (file)
--- a/source/dgc.rst
+++ b/source/dgc.rst
@@ -461,25 +461,36 @@ algoritmo::
       mark_free_lists()
       mark_static_data()
       push_registers_into_stack()
       mark_free_lists()
       mark_static_data()
       push_registers_into_stack()

+      thread_self.stack.end = get_stack_top()

       mark_stacks()
       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
       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
 
    function stop_the_world() is
       foreach thread in threads

+         if thread is thread_self
+            continue

          thread.pause()
          thread.pause()

+         push_registers_into_stack()
+         thread.stack.end = get_stack_top()

 
    function start_the_world() is
       foreach thread in threads
 
    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
          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
 <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::


@@ -528,14 +537,19 @@ en el *stack* a través de la función::
       foreach register in registers
          push(register)
 
       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
 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
 
 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
 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 +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
                      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


@@ -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
    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
          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
 
 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::
 
 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
          block = find_block_with_size(block_size)
          if block is null

-            collect()
+            new_pool()

             block = find_block_with_size(block_size)
             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
 
 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::
 
 
 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()
          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::
 
 
 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*::
 
 
 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
 
 Se recuerda que la función ``alloc()`` es un :ref:`servicio
 <gc_intro_services>` 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::
 
 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
          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
 
 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::
 
 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::
 
 
 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
             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
 
 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)*
 
 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 +1435,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:
 


@@ -1436,6 +1514,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.
 
 
 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
 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 +1664,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 +1674,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 +1742,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