Recolector de basura actual de D
----------------------------------------------------------------------------
-TODO
+Como paso básico fundamental para poder mejorar el recolector de basura de D_,
+primero hay que entender la implementación actual, de forma de conocer sus
+puntos fuertes, problemas y limitaciones, de manera tal de poder analizar
+formas de mejorarlo.
+
+Como se mencionó en la sección :ref:`d_lang`, en D_ hay dos bibliotecas base
+para soportar el lenguaje (*runtimes*): Phobos_ y Tango_. La primera es la
+biblioteca estándar de D_, la segunda un proyecto más abierto y dinámico que
+surgió como alternativa a Phobos_ debido a que Phobos_ es muy desprolija y que
+era muy difícil impulsar cambios en ella. Ahora Phobos_ tiene el agravante de
+estar *congelada* en su versión 1 (solo se realizan correcciones de errores).
+
+Dado que Tango_ está mejor organizada, su desarrollo es más abierto (aceptan
+cambios y mejoras) y que hay una mayor disponibilidad de programas
+y bibliotecas escritos para Tango_, en este trabajo se decide tomar esta
+biblioteca *runtime* como base para el análisis y mejoras propuestas, a pesar
+de ser Phobos_ la estándar. De todas formas el recolector de basura de Tango_
+es prácticamente el mismo que el de Phobos_, por lo tanto éste análisis en
+particular es válido para cualquiera de las dos.
+
+El recolector actual es un recolector :ref:`indirecto <gc_direct>`, :ref:`no
+incremental <gc_inc>` que realiza un :ref:`marcado y barrido <gc_mark_sweep>`
+relativamente básico. A diferencia del algoritmo clásico presentado éste
+realiza un marcado no recursivo. La fase de marcado es :ref:`stop-the-world
+<gc_concurrent` mientras que la fase de barrido corre en paralelo con el
+*mutator*, excepto el hilo que disparó la recolección que es quien efectúa el
+barrido (además los hilos que intenten asignar nueva memoria o interactuar con
+el recolector de cualquier otra forma se bloquean hasta que la fase de barrido
+concluya). El marcado es casi totalmente :ref:`conservativo <gc_conserv>`; si
+bien posee alguna información de tipos (distingue entre celdas que pueden
+tener punteros y celdas que definitivamente no los tienen, pero no dispone de
+información sobre qué campos de las celdas son punteros y cuales no). Además
+no tiene soporte alguno de :ref:`recolección particionada <gc_part>`.
+
+Si bien el recolector es bastante básico, posee una :ref:`organización de
+memoria <dgc_org>` relativamente moderna (utiliza una :ref:`lista de libres
+<gc_free_list>` con un *two level allocator*) y algunas optimizaciones
+particulares para amortiguar casos patológicos.
+
+
+.. _dgc_org:
+
+Organización del *heap*
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+La memoria del *heap* está organizada en *pools*. Un *pool* es una región de
+*páginas* contíguas. Una página es, en general, la unidad mínima de memoria que
+maneja un sistema operativo con soporte de memoria virtual. Cada página dentro
+de un *pool* sirve a su vez como contenedora de bloques (llamados *bin* en la
+:ref:`implementación <dgc_impl>`) de tamaño fijo. Todos los bloques
+pertenecientes a la misma página tienen el mismo tamaño de bloque (ver figura
+:vref:`fig:dgc-org`). Los tamaños de bloque posibles son potencias de 2 desde
+16 bytes hasta 4096 (el tamaño típico de una página), es decir: 16, 32, 64,
+128, 256, 512, 1024, 2048 y 4096 [#dgcpageplus]_. Todos los objetos, arreglos
+o celdas en general se ubican en estos bloques (en uno del tamaño más pequeño
+que haya que sea suficientemente grande como para almacenar dicho objeto). En
+caso de que un objeto sea mayor a una página, se utilizan la menor cantidad de
+páginas contíguas de un pool que tengan espacio suficiente para almacenar
+dicho objeto.
+
+.. [#dgcpageplus] Además existe otro tamaño de bloque especial que se utiliza
+ para indicar la continuación de un objeto grande (que ocupan más de una
+ página).
+
+.. fig:: fig:dgc-org
+
+ Organización del *heap* del recolector de basura actual de D.
+
+ Organización del *heap*. En este ejemplo todos los *pools* tienen 2 páginas
+ excepto el *pool* 2 que tiene una sola. El tamaño de bloque que almacena
+ cada página varía entre 64 bytes (página 0 del *pool* 2) hasta 4096 (ambas
+ páginas del *pool* N) que es una página completa.
+
+ .. aafig::
+ :scale: 1.4
+
+ +----------------------------------------------------------------------+
+ | Heap |
+ +======================================================================+
+ | "Pool 0" "Pool 1" "Pool 2" "Pool 3" ... "Pool N" |
+ | +----------+ +----------+ +----------+ +----------+ +----------+ |
+ | | Página 0 | | Página 0 | | Página 0 | | Página 0 | ... | Página 0 | |
+ | | (8x512) | | (4x1024) | | (64x64) | | (2x2048) | ... | (1x4096) | |
+ | |+--------+| |+--------+| |+--------+| |+--------+| |+--------+| |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| || Bloque || ||qqqqqqqq|| || || || || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| |+--------+| ||qqqqqqqq|| || Bloque || || || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| || Bloque || ||qqqqqqqq|| || || || || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| |+--------+| ||qqqqqqqq|| |+--------+| || Bloque || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| || Bloque || ||qqqqqqqq|| || || || || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| |+--------+| ||qqqqqqqq|| || Bloque || || || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| || Bloque || ||qqqqqqqq|| || || || || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| |+--------+| |+--------+| |+--------+| |+--------+| |
+ | | Página 1 | | Página 1 | +----------+ | Página 1 | ... | Página 1 | |
+ | | (16x256) | | (8x512) | | (32x128) | ... | (1x4096) | |
+ | |+--------+| |+--------+| |+--------+| |+--------+| |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || Bloque || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| |+--------+| ... |+--------+| |
+ | +----------+ +----------+ +----------+ +----------+ |
+ +----------------------------------------------------------------------+
+
+Cada página de un *pool* puede estar asignada a contener bloques de un tamaño
+específico o puede estar libre. A su vez, cada bloque puede estar ocupado por
+una celda o estar libre. Los bloques libres de un tamaño específico (a
+excepción de aquellos bloques que ocupen una página entera) además forman
+parte de una :ref:`lista de libres <gc_free_list>` (ver figura
+:vref:`fig:dgc-free-list`). Esto permite asignar objetos relativamente
+pequeños de forma bastante eficiente.
+
+.. fig:: fig:dgc-free-list
+
+ Ejemplo de listas de libres.
+
+ .. digraph:: dgc_free_list
+
+ margin = 0;
+ rankdir = LR;
+ ratio = fill;
+ size = "4.6,3.6";
+ node [ shape = record, width = 0, height = 0 ];
+
+ subgraph cluster_heap {
+ style = solid;
+ color = black;
+
+ free [ label = "Libres|<p16> 16|<p32> 32|<p64> 64|<p128> 128|<p256> 256|<p512> 512|<p1024> 1024|<p2048> 2048" ];
+
+ free:p16 -> b1 -> b2 -> b3;
+ free:p32 -> b4 -> b5 -> b6 -> b7 -> b8;
+ // free:p64 is empty
+ free:p128 -> b9;
+ free:p256 -> b10 -> b11;
+ free:p512 -> b12;
+ free:p1024 -> b13 -> b14;
+ free:p2048 -> b15 -> b16 -> b17;
+ }
+
+
+Atributos de *pool*
+^^^^^^^^^^^^^^^^^^^
+Cada *pool* tiene la siguiente información asociada:
+
+*number_of_pages*:
+ cantidad de páginas que tiene. Esta cantidad es fija en toda la vida de un
+ *pool*.
+
+*pages*:
+ bloque de memoria contíguo de tamaño ``PAGE_SIZE * number_of_pages``
+ (siendo ``PAGE_SIZE`` el tamaño de página, que normalmente son 4096 bytes).
+
+
+Atributos de página
+^^^^^^^^^^^^^^^^^^^
+Cada página dentro de un *pool* tiene un único atributo asociado: *block_size*.
+Se trata del tamaño de los bloques que almacena esta página.
+
+Una página siempre almacena bloques del mismo tamaño, que pueden ser 16, 32,
+64, 128, 256, 512, 1024, 2048 o 4096 (llamado con el nombre especial
+``PAGE``). Además hay dos tamaños de bloque símbólicos que tienen un
+significado especial:
+
+``FREE``:
+ indica que la página está completamente libre y que la página está
+ disponible para albergar cualquier tamaño de bloque que sea necesario (pero
+ una vez que se le asignó un nuevo tamaño de bloque ya no puede ser cambiado
+ hasta que la página vuelva a liberarse por completo).
+
+``CONTINUATION``:
+ indica que esta página es la continuación de un objeto grande (es decir,
+ que ocupa una o más páginas). Luego se presentan más detalles sobre objetos
+ grandes.
+
+Las páginas con esto tamaños de bloque especiales (conceptualmente) no
+contienen bloques.
+
+
+Atributos de bloque
+^^^^^^^^^^^^^^^^^^^
+Cada bloque tiene asociados varios atributos:
+
+*mark*:
+ utilizado en la fase de :ref:`marcado <dgc_algo_mark>`, indica que un nodo
+ ya fue visitado (serían las celdas *negras* en la :ref:`abstracción
+ tricolor <gc_intro_tricolor>`).
+
+*scan*:
+ utilizado también en la fase de :ref:`marcado <dgc_algo_mark>`, indica que
+ una celda visitada todavía tiene *hijas* sin marcar (serían las celdas
+ *grises* en la :ref:`abstracción tricolor <gc_intro_tricolor>`).
+
+*free*:
+ indica que el bloque está libre (no está siendo utilizado por ningún objeto
+ *vivo*). Esto es necesario solo por la forma en la que realiza el
+ :ref:`marcado <dgc_algo_mark>` y :ref:`barrido <dgc_algo_sweep>` en el
+ :ref:`algoritmo actual <dgc_algo>` (las celdas con el atributo este
+ atributo son tomadas como *basura* aunque estén marcadas con *mark*).
+*final*:
+ indica que el bloque contiene un objeto que tiene un destructor (que debe
+ ser llamado cuando la celda pasa de *viva* a *basura*).
-Diseño
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+*noscan*:
+ indica que el bloque contiene un objeto que no tiene punteros y por lo
+ tanto no debe ser marcado de forma conservativa (no tiene *hijas*).
-.. Acá iría básicamente lo que escribí en el blog sobre la implmentación
- actual
-TODO
+Objetos grandes
+^^^^^^^^^^^^^^^
+El recolector de basura actual de D_ trata de forma diferente a los objetos
+grandes. Todo objeto grande empieza en un bloque con tamaño ``PAGE``
+y (opcionalmente) continúa en los bloques contíguos subsiguientes que tengan
+el tamaño de bloque ``CONTINUATION`` (si el objeto ocupa más que una página).
+El fin de un objeto grande queda marcado por el fin del *pool* o una página
+con tamaño de bloque distinto a ``CONTINUATION`` (lo que suceda primero).
+
+Cuando un objeto grande se convierte en *basura*, todas sus páginas se liberan
+por completo, siendo marcadas con tamaño ``FREE`` para que puedan ser
+almacenado en ellas otros objetos grandes o incluso nuevos bloques de un
+tamaño determinado.
-Implementación
+.. _dgc_algo:
+
+Algoritmos del recolector
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+A continuación se explica como provee el recolector actual de D_ los servicios
+básicos que debe proveer cualquier recolector, como se presentó en la sección
+:ref:`gc_intro_services`.
+
+Cabe aclarar que se presenta una versión simplificada del algoritmo, o más
+precisamente, de la implementación del algoritmo, ya que no se exponen en esta
+sección muchas optimizaciones que harían muy compleja la tarea de explicar
+como funciona conceptualmente. En la siguiente sección, :ref:`dgc_impl`, se
+darán más detalles sobre las optimizaciones importantes y diferencias con el
+algoritmo aquí presentado, junto con detalles sobre como se implementa la
+organización del *heap* que se explicó en la sección anterior.
+
+
+.. _dgc_algo_collect:
+
+Recolección
+^^^^^^^^^^^
+A grandes razgos el algoritmo de recolección puede resumirse de las dos fases
+básicas de cualquier algoritmo de :ref:`marcado y barrido <gc_mark_sweep>`::
+
+ function collect() is
+ mark_phase()
+ sweep_phase()
+
+
+.. _dgc_algo_mark:
+
+Fase de marcado
+^^^^^^^^^^^^^^^
+Esta fase consiste de varios pasos, que pueden resumirse en el siguiente
+algoritmo::
+
+ function mark_phase() is
+ more_to_scan = false
+ stop_the_world()
+ clear_mark_scan_bits()
+ mark_free_lists()
+ mark_static_data()
+ push_registers_into_stack()
+ mark_stacks()
+ 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.
+
+Las funciones ``stop_the_world()`` y ``start_the_world()`` sencillamente
+pausan y reanudan todos los hilos respectivamente::
+
+ function stop_the_world() is
+ foreach thread in threads
+ thread.pause()
+
+ function start_the_world() is
+ foreach thread in threads
+ thread.resume()
+
+La función ``clear_mark_scan_bits()`` se encarga de resetear todos los
+atributos *mark* y *scan* de cada bloque del *heap*::
+
+ function clear_mark_scan_bits() is
+ foreach pool in heap
+ foreach page in pool
+ foreach block in page
+ block.mark = false
+ block.scan = false
+
+La función ``mark_free_lists()`` por su parte se encarga de activar el bit
+*mark* de todos los bloques de las listas de libres de manera de que la fase
+de marcado (que es iterativa y realiza varias pasadas sobre **todo** el
+*heap*, incluyendo las celdas libres) no visite las celdas libres perdiendo
+tiempo sin sentido y potencialmente manteniendo *vivas* celdas que en
+realdidad son *basura* (falsos positivos)::
+
+ function mark_free_lists() is
+ foreach free_list in heap
+ foreach block in free_list
+ block.mark = true
+ block.free = true
+
+Notar que los bloques libres quedan entonces marcados aunque sean *basura* por
+definición. Para evitar que en la etapa de barrido se tomen estos bloques como
+celdas vivas, a todos los bloques en la lista de libres también se los marca
+con el bit *free*, así el barrido puede tomar como *basura* estos bloques
+aunque estén marcados.
+
+El *root set* está compuesto por el área de memoria estática (variables
+globales), los *stacks* de todos los hilos y los registros del procesador.
+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
+ foreach word in static_data
+ pointer = cast(void*) word
+ mark(pointer)
+
+Para poder tomar los registros como parte del *root set* primero se apilan
+en el *stack* a través de la función::
+
+ function push_registers_into_stack() is
+ foreach register in registers
+ push(register)
+
+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)
+
+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
+set* convencional ni en el *heap* del recolector. Para evitar que se libere
+alguna celda que estaba siendo referenciada desde memoria administrada por el
+usuario, éste debe informarle al recolector sobre la existencia de estoas
+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)
+
+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
+
+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
+celda puede contener punteros. Por lo tanto solo resta marcar (nuevamente de
+forma conservativa) iterativamente todo el *heap* hasta que no hayan más
+celdas para visitar (con el bit *scan* activo)::
+
+ function mark_heap() is
+ while more_to_scan
+ more_to_scan = false
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size <= PAGE // saltea FREE y CONTINUATION
+ foreach block in page
+ if block.scan is true
+ block.scan = false
+ if page.block_size is PAGE // objeto grande
+ start = cast(byte*) page
+ end = find_big_object_end(pool, page)
+ foreach word in start..end
+ pointer = cast(void*) word
+ mark(pointer)
+ else // objeto pequeño
+ foreach word in block
+ pointer = cast(void*) word
+ mark(pointer)
+
+Aquí puede verse, con un poco de esfuerzo, la utilización de la
+:ref:`abtracción tricolor <gc_intro_tricolor>`: todas las celdas alcanzables
+desde el *root set* son pintadas de *gris* (tienen los bits *mark* y *scan*
+activados), excepto aquellas celdas atómicas (es decir, que se sabe que no
+tienen punteros) que son marcadas directamente de *negro*. Luego se van
+obteniendo celdas del conjunto de las *grises*, se las pinta de *negro* (es
+decir, se desactiva el big *scan*) y se pintan todas sus *hijas* de *gris* (o
+*negro* directamente si no tienen punteros). Este procedimiento se repite
+mientras el conjunto de celdas *grises* no sea vacío (es decir, que
+``more_to_scan`` sea ``true``).
+
+A continuación se presenta la implementación de las funciones suplementarias
+utilizadas en la fase de marcado::
+
+ function find_big_object_end(pool, page) is
+ pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages)
+ do
+ page = cast(byte*) page + PAGE_SIZE
+ while page.block_size is CONTINUATION and page < pool_end
+ return page
+
+ function find_block(pointer) is
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size is PAGE
+ big_object_start = cast(byte*) page
+ big_object_end = find_big_object_end(pool, page)
+ if big_object_start <= pointer < big_object_end
+ return [pool, page, big_object_start]
+ else if page.bloc_size < PAGE
+ foreach block in page
+ block_start = cast(byte*) block
+ block_end = block_start + page.block_size
+ if block_start <= pointer < block_end
+ return [pool, page, block_start]
+ return [null, null, null]
+
+Cabe destacar que la función ``find_block()`` devuelve el pool, la página y el
+comienzo del bloque al que apunta el puntero, es decir, soporta punteros
+*interiores*.
+
+
+.. _dgc_algo_sweep:
+
+Fase de barrido
+^^^^^^^^^^^^^^^
+Esta fase es considerablemente más sencilla que el marcado; el algoritmo puede
+dividirse en dos pasos básicos::
+
+ function sweep_phase() is
+ sweep()
+ rebuild_free_lists()
+
+El barrido se realiza con una pasada por sobre todo el *heap* de la siguiente
+manera::
+
+ function sweep() is
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size <= PAGE // saltea FREE y CONTINUATION
+ foreach block in page
+ if block.mark is false
+ if block.final is true
+ finalize(block)
+ block.free = true
+ block.final = false
+ block.noscan = false
+ if page.block_size is PAGE // objeto grande
+ free_big_object(pool, page)
+
+Como se observa, se recorre todo el *heap* en busca de bloques y páginas
+libres. Los bloques libres son marcados con el atributo ``free`` y las páginas
+libres son marcadas con el tamaño de bloque simbólico ``FREE``. Para los
+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
+
+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
+biblioteca *runtime* y en última instancia llama al destructor del objeto
+almacenado en el bloque a liberar.
+
+Una vez marcados todos los bloques y páginas como libre, se procede
+a reconstruir las listas de libres. En el proceso buscan las páginas que
+tengan todos los bloques libres para marcar la página completa como libre (de
+manera que pueda utilizarse para albergar otro tamaño de bloque u objetos
+grandes de ser necesario)::
+
+ function rebuild_free_lists() is
+ foreach free_list in heap
+ free_list.clear()
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size < PAGE // objetos pequeños
+ if is_page_free(page)
+ page.block_size = FREE
+ else
+ foreach block in page
+ if block.free is true
+ free_lists[page.block_size].link(block)
+
+Esta reorganización de listas libres además mejoran la localidad de
+referencia y previenen la fragmentación. La localidad de referencia se ve
+mojorada debido a que asignaciones de memoria proximas en el tiempo serán
+también próximas en espacio porque pertenecerán a la misma página (al menos si
+las asignaciones son todas del mismo tamaño). La fragmentación se minimiza por
+el mismo efecto, primero se asignarán todos los bloques de la misma página.
+
+A continuación se presenta la implementación de una de las funciones
+suplementarias de la fase de barrido::
+
+ function is_page_free(page) is
+ foreach block in page
+ if block.free is false
+ return false
+ return true
+
+Las demás funciones suplementarias pertenecen a la manipulación de listas
+libres que no son más que operaciones sobre una lista simplemente enlazada. En
+la sección :ref:`dgc_impl` se verá con más detalles como las implementa el
+recolector actual.
+
+
+.. _dgc_algo_alloc:
+
+Asignación de memoria
+^^^^^^^^^^^^^^^^^^^^^
+La asignación de memoria del recolector es relativamente compleja, excepto
+cuando se asgina un objeto pequeño y ya existe algún bloque con el tamaño
+preciso en la lista de libres. Para el resto de los casos la cantidad de
+trabajo que debe hacer el recolector para asignar la memoria es considerable.
+
+El algoritmo de asignación de memoria se puede resumir así::
+
+ function new(size, attrs) is
+ block_size = find_block_size(size)
+ if block_size < PAGE
+ block = new_small(block_size)
+ else
+ block = new_big(size)
+ if block is null
+ throw out_of_memory
+ if final in attrs
+ block.final = true
+ if noscan in attrs
+ block.noscan = true
+ return cast(void*) block
+
+La función ``find_block_size()`` sencillamente busca el tamaño de bloque se
+mejor se ajuste al tamaño solicitado (es decir, el bloque más pequeño lo
+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
+asginan de las siguiente manera::
+
+ 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
+ new_pool()
+ block = find_block_with_size(block_size)
+ return null
+ 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
+una :ref:`recolección <dgc_algo_collect>` y si no se puede encontrar
+suficiente espacio luego de ella se intenta crear un nuevo *pool* de memoria
+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
+ block = free_lists[block_size].pop_first()
+ if block is null
+ assign_page(block_size)
+ block = free_lists[block_size].pop_first()
+ 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)
+
+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
+
+Se recuerda que la función ``alloc()`` es un :ref:`servicio
+<gc_intro_services>` provisto por el *low level allocator* y en la
+implementación actual de D_ en general es el sistema operativo (aunque
+opcionalmente puede utilizarse la biblioteca estándar de C, que a su vez
+utiliza el sistema operativo).
+
+Cualquier error en estas funciones es propagado y en última instancia, cuando
+todo falla, la función ``new()`` termina lanzando una excepción indicando que
+se agotó la memoria.
+
+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)
+ 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]
+
+De forma similar a la asignación de objetos pequeños, se intenta encontrar una
+serie de páginas contíguas, dentro de un mismo *pool*, suficientes para
+almacenar el tamaño requerido y si esto falla, se realizan diferentes pasos
+y se vuelve a intentar. Puede observarse que, a diferencia de la asignación de
+objetos pequeños, si luego de la recolección no se pudo encontrar lugar
+suficiente, se trata de minimizar el uso de memoria física utilizando la
+siguiente función, que devuelve al *low level allocator* los *pools*
+completamente libres::
+
+ function minimize() is
+ for pool in heap
+ all_free = true
+ for page in pool
+ if page.block_size is not FREE
+ all_free = false
+ break
+ if all_free is true
+ free(pool.pages)
+ free(pool)
+ heap.remove(pool)
+
+Volviendo a la función ``new_big()``, para hallar una serie de páginas
+contíguas 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
+
+Como se dijo, las páginas deben estar contenidas en un mismo *pool* (para
+tener la garantía de que sean contíguas), 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]
+ 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
+suficientes como para almacenar el objeto grande y si esto falla el error se
+propaga hasta la función ``new()`` que lanza una excepción.
+
+
+
+.. _dgc_impl:
+
+Detalles de implementación
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.. Acá diría por qué hay que reescribirlo para usar lo que está
-Como se ha visto, D_ es un lenguaje de programación muy completo,
-pero aún tiene algunos aspectos inconclusos. Su recolector de basura
-está en un estado de evolución muy temprana. Se trata de un marcado y
-barrido (*mark and sweep*) conservativo que, en ciertas circunstancias,
-no se comporta como es debido, ya que revisa toda la memoria del programa
-en busca de referencias a objetos en el *heap* (en vez de revisar sólo
-las partes que almacenan punteros). Esto produce que, en ciertos casos,
-por ejemplo al almacenar arreglos de número o *strings* en la pila, el
-recolector de basura se encuentre con *falsos positivos*, pensando que
-un área del *heap* está siendo utilizada cuando en realidad el puntero
-que hacía referencia a ésta no era tal. Este efecto puede llevar a la
-pérdida de memoria masiva, llegando al límite de que eventualmente
+Como se ha visto, D_ es un lenguaje de programación muy completo, pero aún
+tiene algunos aspectos inconclusos. Su recolector de basura está en un estado
+de evolución muy temprana. Se trata de un marcado y barrido (*mark and sweep*)
+conservativo que, en ciertas circunstancias, no se comporta como es debido, ya
+que revisa toda la memoria del programa en busca de referencias a objetos en
+el *heap* (en vez de revisar sólo las partes que almacenan punteros). Esto
+produce que, en ciertos casos, por ejemplo al almacenar arreglos de número
+o *strings* en la pila, el recolector de basura se encuentre con *falsos
+positivos*, pensando que un área del *heap* está siendo utilizada cuando en
+realidad el puntero que hacía referencia a ésta no era tal. Este efecto puede
+llevar a la pérdida de memoria masiva, llegando al límite de que eventualmente
el sistema operativo tenga que matar al programa por falta de memoria
-[DNG46407]_. Aún cuando el programa no tenga estos problemas de por sí,
-por usar datos que no pueden ser confundidos con direcciones de memoria,
-este problema podría ser explotado por ataques de seguridad, inyectando
-valores que sí sean punteros válidos y provocando el efecto antes
-mencionado que deriva en la terminación abrupta del programa [DNG35364]_.
-Finalmente, a estos problemas se suman los problemas de *performance*
-[DNG43991]_.
-
-Es difícil que D_ pueda ser un lenguaje de programación exitoso si
-no provee un recolector de basura eficiente y que realmente evite la
-pérdida masiva de memoria. Por otro lado, D_ podría atraer a una base de
-usuarios mucho más amplia, si la gama de estrategias de recolección es
-más amplia, pudiendo lograr adaptarse a más casos de uso sin llegar al
-límite de tener que caer en el manejo explícito de memoria y perder por
-completo las ventajas de la recolección de basura (con la consecuencia
-ya mencionada de que el manejo de memoria tenga que pasar a ser parte
-de las interfaces y la complejidad que esto agrega al diseño -y uso-
-de una biblioteca).
+[DNG46407]_. Aún cuando el programa no tenga estos problemas de por sí, por
+usar datos que no pueden ser confundidos con direcciones de memoria, este
+problema podría ser explotado por ataques de seguridad, inyectando valores que
+sí sean punteros válidos y provocando el efecto antes mencionado que deriva en
+la terminación abrupta del programa [DNG35364]_. Finalmente, a estos problemas
+se suman los problemas de *performance* [DNG43991]_.
+
+Es difícil que D_ pueda ser un lenguaje de programación exitoso si no provee un
+recolector de basura eficiente y que realmente evite la pérdida masiva de
+memoria. Por otro lado, D_ podría atraer a una base de usuarios mucho más
+amplia, si la gama de estrategias de recolección es más amplia, pudiendo lograr
+adaptarse a más casos de uso sin llegar al límite de tener que caer en el
+manejo explícito de memoria y perder por completo las ventajas de la
+recolección de basura (con la consecuencia ya mencionada de que el manejo de
+memoria tenga que pasar a ser parte de las interfaces y la complejidad que esto
+agrega al diseño -y uso- de una biblioteca).
Soluciones Propuestas
-Para poder implementar un recolector de basura no conservativo es
-necesario disponer de un soporte de reflexión (en tiempo de compilación
-[DNG44607]_ y de ejecución [DNG29291]_) bastante completo . De otra forma
-es imposible distinguir si un área de memoria de la pila es utilizada
-como un puntero o como un simple conjunto de datos. D_ provee algún
-grado de reflexión, pero muy limitado como para poder obtener este
-tipo de información. Ya hay un plan para agregar mayores capacidades
-de reflexibilidad [DNG6842]_, y un pequeño avance en este sentido en la
-`versión 1.001`_, pero con algunos problemas [DNG6890]_ [DNG6893]_.
+Para poder implementar un recolector de basura no conservativo es necesario
+disponer de un soporte de reflexión (en tiempo de compilación [DNG44607]_ y de
+ejecución [DNG29291]_) bastante completo . De otra forma es imposible
+distinguir si un área de memoria de la pila es utilizada como un puntero o como
+un simple conjunto de datos. D_ provee algún grado de reflexión, pero muy
+limitado como para poder obtener este tipo de información. Ya hay un plan para
+agregar mayores capacidades de reflexibilidad [DNG6842]_, y un pequeño avance
+en este sentido en la `versión 1.001`_, pero con algunos problemas [DNG6890]_
+[DNG6893]_.
.. _`versión 1.001`: http://www.digitalmars.com/d/changelog.html#new1_001
-Se han propuesto otros métodos e implementaciones de recolector de basura,
-por ejemplo colectores con movimiento (*moving collectors*) [DNG42557]_
-y conteo de referencias [DNG38689]_. Pero D_ es un lenguaje muy particular
-en cuanto a la recolección de basura (al permitir :ref:d_low_level hay
-muchas consideraciones a las que otros lenguajes no deben enfrentarse) y no
-es sencillo pensar en otras implementaciones sin hacer modificaciones de
-base al lenguaje.
+Se han propuesto otros métodos e implementaciones de recolector de basura, por
+ejemplo colectores con movimiento (*moving collectors*) [DNG42557]_ y conteo de
+referencias [DNG38689]_. Pero D_ es un lenguaje muy particular en cuanto a la
+recolección de basura (al permitir :ref:d_low_level hay muchas consideraciones
+a las que otros lenguajes no deben enfrentarse) y no es sencillo pensar en
+otras implementaciones sin hacer modificaciones de base al lenguaje.
Problemas para Implementar Colectores con Movimiento
-El principal problema es la capacidad de D_ de manipular punteros y
-otras estructuras de bajo nivel, como uniones. O incluso la capacidad
-de interactuar con C. Al mover un objeto de un área de memoria a otro,
-es necesario actualizar todos los punteros que apuntan a éste. En D_
-esta tarea no es trivial [DNG42564]_
+El principal problema es la capacidad de D_ de manipular punteros y otras
+estructuras de bajo nivel, como uniones. O incluso la capacidad de interactuar
+con C. Al mover un objeto de un área de memoria a otro, es necesario actualizar
+todos los punteros que apuntan a éste. En D_ esta tarea no es trivial
+[DNG42564]_
Problemas para Implementar Conteo de Referencias
-Este tipo de recolectores reparten la carga de la recolección de forma
-uniforme a lo largo (y a la par) de la ejecución del programa. El
-problema principal para implementar este tipo de recolección es
-la necesidad de soporte en el compilador (cada asignación debe ser
-acompañada por el incremento/decremento de contadores de referencia), a
-menos que se implemente en una biblioteca. Por otro lado, características
-como el rebanado de arreglos (ver :ref:d_high_level) son
-difíciles de proveer con el conteo de referencias, entre otros problemas
+Este tipo de recolectores reparten la carga de la recolección de forma uniforme
+a lo largo (y a la par) de la ejecución del programa. El problema principal
+para implementar este tipo de recolección es la necesidad de soporte en el
+compilador (cada asignación debe ser acompañada por el incremento/decremento de
+contadores de referencia), a menos que se implemente en una biblioteca. Por
+otro lado, características como el rebanado de arreglos (ver :ref:d_high_level)
+son difíciles de proveer con el conteo de referencias, entre otros problemas
[DNG38704]_.
projects / z.facultad / 75.00 / informe.git / blobdiff