X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/b0956c037ae52da777b06705157486067755ec2c..ade63acf6c8d0abf0afa54e1eeb0f4fcc8f514e6:/source/dgc.rst?ds=sidebyside diff --git a/source/dgc.rst b/source/dgc.rst index bb0f3ba..e12b9df 100644 --- a/source/dgc.rst +++ b/source/dgc.rst @@ -7,7 +7,7 @@ ESTADO: SIN EMPEZAR, REVISAR LO HECHO -.. _ref_dgc: +.. _dgc: Recolección de basura en D ============================================================================ @@ -23,24 +23,730 @@ TODO +.. _dgc_actual: + 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 `, :ref:`no +incremental ` que realiza un :ref:`marcado y barrido ` +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 +`; 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 `. + +Si bien el recolector es bastante básico, posee una :ref:`organización de +memoria ` relativamente moderna (utiliza una :ref:`lista de libres +` 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 `) 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 ` (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| 16| 32| 64| 128| 256| 512| 1024| 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 `, indica que un nodo + ya fue visitado (serían las celdas *negras* en la :ref:`abstracción + tricolor `). + +*scan*: + utilizado también en la fase de :ref:`marcado `, indica que + una celda visitada todavía tiene *hijas* sin marcar (serían las celdas + *grises* en la :ref:`abstracción 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 ` y :ref:`barrido ` en el + :ref:`algoritmo actual ` (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 `:: + + 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 +` (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 `: 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 ` 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 +` 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á @@ -57,87 +763,82 @@ TODO -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]_. .. include:: links.rst -.. vim: set ts=2 sts=2 sw=2 et tw=75 : +.. vim: set ts=3 sts=3 sw=3 et tw=78 :