arena allocator
1.0.0
Alocador de arena de um único cabeçalho. C89 Compatível.
arena.h Os alocadores de arena são uma maneira simples de alcançar o gerenciamento de memória dinâmica mais fácil, mais rápido e mais seguro, permitindo que várias alocações sejam libertadas como um grupo. Isso é feito alocando a memória em grandes regiões e depois distribuindo partes dessa memória, conforme necessário, reduzindo a quantidade de chamadas malloc (que são lentas em comparação com a aritmética do ponteiro simples).
Quando você destrói a arena, você também a libera e todo o seu conteúdo, reduzindo a quantidade de chamadas free que também são lentas. Indo além, você pode limpar as arenas simplesmente redefinindo seus ponteiros de memória para 0 , permitindo que você os reutilize e eliminando a necessidade de ainda mais de malloc e free .
Você pode aprender mais sobre alocadores de arena/zona/região lendo este artigo fantástico.
Vou manter isso curto. Estou mantendo a conformidade do C89 por diversão, não porque eu o uso. Pessoalmente, sou um desfrute C11. Se você acha que C89 é o único caminho, bem, bom para você! Mas você está errado.
Sempre que compartilho este projeto com outros programadores, uma das respostas mais comuns que recebo é algo como: você nunca deve colocar o código de implementação/lógica em um arquivo de cabeçalho! Eu discordo desta declaração por três razões ...
Isso mostra que uma construção prejudicial desatualizada e, por conseqüência, ainda está sendo aplicada no sistema educacional, que é onde a construção referida é geralmente introduzida.
Muito raramente a pessoa que faz essa afirmação tem uma razão real para acreditar. Essa pessoa pensa sobre por que "nunca deve colocar o código de implementação/lógica em um arquivo de cabeçalho"? Simplesmente regurgitando o que eles ouviram sem nenhuma base para o motivo pelo qual escolheram concordar com isso não me ajuda de forma alguma, e essa pessoa não deve esperar que eu aceite apenas como fizeram.
A maior e mais válida crítica às bibliotecas apenas para cabeçalho/de um único cabeçalho é que uma alteração no cabeçalho requer recompilação de todos os arquivos que o incluem. No caso do meu projeto, fazendo alterações no arena.h , mesmo que a implementação real esteja contida apenas na unidade de tradução que a ARENA_IMPLEMENTATION #define na reconstrução de todos os arquivos que o incluem. A solução? Depois que arena.h está no estado desejado, pare de fazer mudanças!
Vincular é lento e complicado. Muitos iniciantes muitas vezes lutam para aprender o processo de vinculação e também são o maior culpado quando se trata de escrever código inseguro. Isso por si só é um motivo suficiente para eu tornar essa arena alocadora uma biblioteca somente para cabeçalho. Meu código (em seu estado atual) é muito pequeno, aproximadamente 300 linhas. Por que eu faria você construir e vincular uma implementação tão pequena quando você poderia simplesmente #include uma vez e começar a usá -lo para fora da caixa? Se você realmente tiver um problema com isso, esse alocador no formato de um único cabeçalho não o impede de seguir o construto de origem+cabeçalho, se desejar. Caramba, sinta -se à vontade para bifurcar e torná -lo fonte+cabeçalho, é de código aberto por um motivo!
Isso não implementa um alocador no nível do kernel, mas envolve malloc e free (Biblioteca Padrão ou Custom, sua escolha).
Embora eu acredite que o software deva ser de código aberto, não acredito que seja ético exigir software que use essa biblioteca para também ser de código aberto. Na era moderna da tecnologia e no estado atual do mundo, escrever código seguro para a memória é mais importante do que nunca. Por esse motivo, este software está licenciado sob a versão 2.0 da Licença Apache. Você é fortemente incentivado a ler a LICENSE (incluída abaixo, no arena.h , e seu próprio arquivo neste repositório) se estiver pensando em usar o software, a menos que acredite que esteja 100% familiarizado com os termos e condições.
Apache License
Version 2.0, January 2004
http://www.apache.org/licenses/
TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
1. Definitions.
"License" shall mean the terms and conditions for use, reproduction,
and distribution as defined by Sections 1 through 9 of this document.
"Licensor" shall mean the copyright owner or entity authorized by
the copyright owner that is granting the License.
"Legal Entity" shall mean the union of the acting entity and all
other entities that control, are controlled by, or are under common
control with that entity. For the purposes of this definition,
"control" means (i) the power, direct or indirect, to cause the
direction or management of such entity, whether by contract or
otherwise, or (ii) ownership of fifty percent (50%) or more of the
outstanding shares, or (iii) beneficial ownership of such entity.
"You" (or "Your") shall mean an individual or Legal Entity
exercising permissions granted by this License.
"Source" form shall mean the preferred form for making modifications,
including but not limited to software source code, documentation
source, and configuration files.
"Object" form shall mean any form resulting from mechanical
transformation or translation of a Source form, including but
not limited to compiled object code, generated documentation,
and conversions to other media types.
"Work" shall mean the work of authorship, whether in Source or
Object form, made available under the License, as indicated by a
copyright notice that is included in or attached to the work
(an example is provided in the Appendix below).
"Derivative Works" shall mean any work, whether in Source or Object
form, that is based on (or derived from) the Work and for which the
editorial revisions, annotations, elaborations, or other modifications
represent, as a whole, an original work of authorship. For the purposes
of this License, Derivative Works shall not include works that remain
separable from, or merely link (or bind by name) to the interfaces of,
the Work and Derivative Works thereof.
"Contribution" shall mean any work of authorship, including
the original version of the Work and any modifications or additions
to that Work or Derivative Works thereof, that is intentionally
submitted to Licensor for inclusion in the Work by the copyright owner
or by an individual or Legal Entity authorized to submit on behalf of
the copyright owner. For the purposes of this definition, "submitted"
means any form of electronic, verbal, or written communication sent
to the Licensor or its representatives, including but not limited to
communication on electronic mailing lists, source code control systems,
and issue tracking systems that are managed by, or on behalf of, the
Licensor for the purpose of discussing and improving the Work, but
excluding communication that is conspicuously marked or otherwise
designated in writing by the copyright owner as "Not a Contribution."
"Contributor" shall mean Licensor and any individual or Legal Entity
on behalf of whom a Contribution has been received by Licensor and
subsequently incorporated within the Work.
2. Grant of Copyright License. Subject to the terms and conditions of
this License, each Contributor hereby grants to You a perpetual,
worldwide, non-exclusive, no-charge, royalty-free, irrevocable
copyright license to reproduce, prepare Derivative Works of,
publicly display, publicly perform, sublicense, and distribute the
Work and such Derivative Works in Source or Object form.
3. Grant of Patent License. Subject to the terms and conditions of
this License, each Contributor hereby grants to You a perpetual,
worldwide, non-exclusive, no-charge, royalty-free, irrevocable
(except as stated in this section) patent license to make, have made,
use, offer to sell, sell, import, and otherwise transfer the Work,
where such license applies only to those patent claims licensable
by such Contributor that are necessarily infringed by their
Contribution(s) alone or by combination of their Contribution(s)
with the Work to which such Contribution(s) was submitted. If You
institute patent litigation against any entity (including a
cross-claim or counterclaim in a lawsuit) alleging that the Work
or a Contribution incorporated within the Work constitutes direct
or contributory patent infringement, then any patent licenses
granted to You under this License for that Work shall terminate
as of the date such litigation is filed.
4. Redistribution. You may reproduce and distribute copies of the
Work or Derivative Works thereof in any medium, with or without
modifications, and in Source or Object form, provided that You
meet the following conditions:
(a) You must give any other recipients of the Work or
Derivative Works a copy of this License; and
(b) You must cause any modified files to carry prominent notices
stating that You changed the files; and
(c) You must retain, in the Source form of any Derivative Works
that You distribute, all copyright, patent, trademark, and
attribution notices from the Source form of the Work,
excluding those notices that do not pertain to any part of
the Derivative Works; and
(d) If the Work includes a "NOTICE" text file as part of its
distribution, then any Derivative Works that You distribute must
include a readable copy of the attribution notices contained
within such NOTICE file, excluding those notices that do not
pertain to any part of the Derivative Works, in at least one
of the following places: within a NOTICE text file distributed
as part of the Derivative Works; within the Source form or
documentation, if provided along with the Derivative Works; or,
within a display generated by the Derivative Works, if and
wherever such third-party notices normally appear. The contents
of the NOTICE file are for informational purposes only and
do not modify the License. You may add Your own attribution
notices within Derivative Works that You distribute, alongside
or as an addendum to the NOTICE text from the Work, provided
that such additional attribution notices cannot be construed
as modifying the License.
You may add Your own copyright statement to Your modifications and
may provide additional or different license terms and conditions
for use, reproduction, or distribution of Your modifications, or
for any such Derivative Works as a whole, provided Your use,
reproduction, and distribution of the Work otherwise complies with
the conditions stated in this License.
5. Submission of Contributions. Unless You explicitly state otherwise,
any Contribution intentionally submitted for inclusion in the Work
by You to the Licensor shall be under the terms and conditions of
this License, without any additional terms or conditions.
Notwithstanding the above, nothing herein shall supersede or modify
the terms of any separate license agreement you may have executed
with Licensor regarding such Contributions.
6. Trademarks. This License does not grant permission to use the trade
names, trademarks, service marks, or product names of the Licensor,
except as required for reasonable and customary use in describing the
origin of the Work and reproducing the content of the NOTICE file.
7. Disclaimer of Warranty. Unless required by applicable law or
agreed to in writing, Licensor provides the Work (and each
Contributor provides its Contributions) on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied, including, without limitation, any warranties or conditions
of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
PARTICULAR PURPOSE. You are solely responsible for determining the
appropriateness of using or redistributing the Work and assume any
risks associated with Your exercise of permissions under this License.
8. Limitation of Liability. In no event and under no legal theory,
whether in tort (including negligence), contract, or otherwise,
unless required by applicable law (such as deliberate and grossly
negligent acts) or agreed to in writing, shall any Contributor be
liable to You for damages, including any direct, indirect, special,
incidental, or consequential damages of any character arising as a
result of this License or out of the use or inability to use the
Work (including but not limited to damages for loss of goodwill,
work stoppage, computer failure or malfunction, or any and all
other commercial damages or losses), even if such Contributor
has been advised of the possibility of such damages.
9. Accepting Warranty or Additional Liability. While redistributing
the Work or Derivative Works thereof, You may choose to offer,
and charge a fee for, acceptance of support, warranty, indemnity,
or other liability obligations and/or rights consistent with this
License. However, in accepting such obligations, You may act only
on Your own behalf and on Your sole responsibility, not on behalf
of any other Contributor, and only if You agree to indemnify,
defend, and hold each Contributor harmless for any liability
incurred by, or claims asserted against, such Contributor by reason
of your accepting any such warranty or additional liability.
END OF TERMS AND CONDITIONS
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
Copyright 2024 Carter Dugan
A documentação para o alocador da arena pode ser encontrada no arena.h . Há um comentário na parte superior do arquivo de cabeçalho com instruções rápidas para uso para sua conveniência.
Para um arquivo em uma unidade de tradução , você precisa do seguinte:
#define ARENA_IMPLEMENTATION
#include "arena.h" A partir desse ponto, outros arquivos em outras unidades de tradução podem simplesmente #include "arena.h" normalmente. Existem macros adicionais que você pode definir/usar. Veja a seção sobre funções e macros.
Existem duas estruturas definidas na arena.h . Isso lista cada um junto com seus membros.
Arena_Allocation A estrutura de dados para uma alocação de arena. Disponível apenas quando ARENA_DEBUG é definido.
size_t index O índice na arena em que o início da alocação está localizado.size_t size do tamanho da memória alocada a essa alocação em bytes.char *pointer O ponteiro associado à alocação.struct Arena_Allocation_s *next a próxima alocação na lista vinculada. Arena a estrutura de dados para uma arena.
char *region A região da memória alocada.size_t index O índice da região para que o próximo ponteiro seja distribuído.size_t size do tamanho da memória alocada para a arena em bytes.unsigned long allocations O número de alocações de arena que foram feitas. Disponível apenas quando ARENA_DEBUG é definido.Arena_Allocation *head_allocation A primeira alocação feita na arena (usada para uma lista vinculada). Disponível apenas quando ARENA_DEBUG é definido. /*
Allocate and return a pointer to memory to the arena
with a region with the specified size. Providing a
size of zero results in a failure.
Parameters:
size_t size | The size (in bytes) of the arena
memory region.
Return:
Pointer to arena on success, NULL on failure
*/
Arena * arena_create ( size_t size );
/*
Return a pointer to a portion of specified size of the
specified arena's region. Nothing will restrict you
from allocating more memory than you specified, so be
mindful of your memory (as you should anyways) or you
will get some hard-to-track bugs. By default, memory is
aligned by alignof(size_t), but you can change this by
#defining ARENA_DEFAULT_ALIGNMENT before #include'ing
arena.h. Providing a size of zero results in a failure.
Parameters:
Arena *arena | The arena of which the pointer
from the region will be
distributed
size_t size | The size (in bytes) of
allocated memory planned to be
used.
Return:
Pointer to arena region segment on success, NULL on
failure.
*/
ARENA_INLINE void * arena_alloc ( Arena * arena , size_t size );
/*
Same as arena_alloc, except you can specify a memory
alignment for allocations.
Return a pointer to a portion of specified size of the
specified arena's region. Nothing will restrict you
from allocating more memory than you specified, so be
mindful of your memory (as you should anyways) or you
will get some hard-to-track bugs. Providing a size of
zero results in a failure.
Parameters:
Arena *arena | The arena of which the pointer
from the region will be
distributed
size_t size | The size (in bytes) of
allocated memory planned to be
used.
unsigned int alignment | Alignment (in bytes) for each
memory allocation.
Return:
Pointer to arena region segment on success, NULL on
failure.
*/
void * arena_alloc_aligned ( Arena * arena , size_t size , unsigned int alignment );
/*
Copy the memory contents of one arena to another.
Parameters:
Arena *src | The arena being copied, the source.
Arena *dest | The arena being copied to. Must be created/allocated
already.
Return:
Number of bytes copied.
*/
ARENA_INLINE size_t arena_copy ( Arena * dest , Arena * src );
/*
Reset the pointer to the arena region to the beginning
of the allocation. Allows reuse of the memory without
realloc or frees.
Parameters:
Arena *arena | The arena to be cleared.
*/
ARENA_INLINE void arena_clear ( Arena * arena );
/*
Free the memory allocated for the entire arena region.
Parameters:
Arena *arena | The arena to be destroyed.
*/
ARENA_INLINE void arena_destroy ( Arena * arena );
/*
Returns a pointer to the allocation struct associated
with a pointer to a segment in the specified arena's
region.
Parameters:
Arena *arena | The arena whose region should
have a portion pointed to by
ptr.
void *ptr | The ptr being searched for
within the arena in order to
find an allocation struct
associated with it.
*/
Arena_Allocation * arena_get_allocation_struct ( Arena * arena , void * ptr );
/*
Adds an arena allocation to the arena's linked list of
allocations under debug.
Parameters:
Arena *arena | The arena whose allocation list
should be added to
size_t size | The size of the allocation being
added.
*/
void arena_add_allocation ( Arena * arena , size_t size );
/*
Deletes the arena's linked list of allocations under
debug.
Parameters:
Arena *arena | The arena whose allocation list
is being deleted.
*/
void arena_delete_allocation_list ( Arena * arena ); No seu código, você pode definir algumas macros opcionais. ARENA_MALLOC , ARENA_FREE e ARENA_MEMCPY podem ser atribuídos a funções alternativas malloc , free e semelhantes memcpy , respectivamente, e arena.h os usará no lugar das funções padrão da biblioteca. Você pode acessar a funcionalidade de depuração adicional para acompanhar as alocações definindo ARENA_DEBUG . Por fim, você também pode especificar um valor padrão para o alinhamento de alocação, definindo um valor para ARENA_DEFAULT_ALIGNMENT . Veja abaixo para exemplos.
// All of these are optional
// Replace standard library functions
#define ARENA_MALLOC <stdlib_malloc_like_allocator>
#define ARENA_FREE <stdlib_free_like_deallocator>
#define ARENA_MEMCPY <stdlib_memcpy_like_copier>
// for debug functionality:
#define ARENA_DEBUG
// If you would like to change the default alignment for
// allocations:
#define ARENA_DEFAULT_ALIGNMENT <alignment_value> Há também uma macro para determinar o alinhamento dos tipos. Como todo o resto, também é amigável ao C89, embora ao compilar no C11 ele usará alignof do stdalign.h .
ARENA_ALIGNOF ( type ) // Gives alignment of `type` O código foi gravado para construir com qualquer compilador que suporta o padrão C89 e seja executado em qualquer plataforma. No entanto, existem alguns problemas na construção de janelas com o Makefile . Leia todas as informações abaixo.
Os testes e exemplos foram compilados e executados com sucesso nos seguintes compiladores e versões:
Os testes e exemplos foram compilados e executados com sucesso nos seguintes sistemas operacionais:
NOTA Atualmente, o Makefile não foi configurado para funcionar no Windows ao executar $ make test devido ao uso de Valgrind e à ausência de extensões .exe . Essa deve ser uma correção simples e está na minha lista de tarefas (fique à vontade para abrir um problema e consertar você mesmo!).
Este projeto tem diretrizes muito simples para contribuir.
Para quaisquer contribuições para o Código de arena.h , abra uma solicitação de tração apenas se você estiver abordando um problema para atender a uma solicitação de recurso ou corrigir um bug . Siga o estilo de código e execute os testes automatizados antes de abrir uma solicitação de tração. Todos os testes devem ser passados.
Para solicitações de recursos ou bugs , abra um problema . Você pode abordar esse problema.
Para qualquer outra coisa , abra um problema e discutiremos isso.
arena.hNo momento, não há documentação para o estilo de código, mas deve ser relativamente simples o suficiente para entender a leitura do código existente para a maioria das coisas. Se você está tendo problemas, fique à vontade para abrir um problema para um FR. Se já existir, comente descrevendo o que você está confuso.
Se você modificar arena.h , deve executar os testes. Veja a próxima seção.
Se você adicionar um recurso no arena.h , deverá criar um teste ou teste adequado no test.c .
Se você adicionar um recurso no arena.h , deve um exemplo adequado em code_examples/ e adicioná -lo ao makefile , mas não é necessário.
Se você mudar de arena.h , execute os testes antes de abrir um PR . Se você abrir um PR com modificações no código e os testes não passarem, faça um comentário sobre o seu PR, informando em qual teste você acredita estar errado e está impedindo que você passe todos os testes. Se algum teste falhar e seu PR não tiver um comentário que afirma corrigir um teste com falha, seu PR será ignorado.
Fora de abordar bugs e solicitações de recursos, atendendo a uma solicitação de recurso ou correção de bugs para funcionalidade no arena.h permite modificar ou adicionar código de teste relevante no test.c , e você deve fazê -lo se desejar que seu PR seja reconhecido. Há documentação para testar o código no test.c na parte superior do arquivo na forma de comentários.
Os testes também devem passar por Valgrind sem vazamentos, e arena.h deve ser compatível com C89. Você deve verificar isso usando o Makefile , mas se por algum motivo você não puder ou não quiser, compilar test.c com
-Werror -Wall -Wextra -Wstrict-prototypes -Wold-style-definition -Wmissing-prototypes -Wmissing-declarations -Wdeclaration-after-statement
E para conformidade, compile test_compliance.c com
-pedantic -std=c89 -Werror -Wall -Wextra -Wstrict-prototypes -Wold-style-definition -Wmissing-prototypes -Wmissing-declarations -Wdeclaration-after-statement
Como eu disse, você pode fazer tudo isso com o Makefile
$ make test
Identificadores
variable_name . Para os ponteiros , o asterisco ( * ) deve ser anexado ao nome da variável, não ao tipo, por exemplo, type *variable_name .type function_name(p1, p2, ...) . No caso dos ponteiros, o asterisco ( * ) deve ser anexado ao tipo de densidade, por exemplo, type* function_name(p1, p2, ...) . As funções devem ter uma declaração avançada com um comentário para documentação acima dele em torno da parte superior do arquivo, verifique se o pedido em relação a outras funções é consistente.struct StructName . Eles devem ser digitados e localizados ao redor da parte superior do arquivo de cabeçalho.ARENA_ , por exemplo, ARENA_MACRO_NAME . Evite adicionar macros sem me consultar primeiro . Sinta -se à vontade para fazer alterações nas macros existentes, no entanto.O espaço em branco é baseado na relevância de uma linha de código para as pessoas ao seu redor. Se você não entender o que esses pontos significam, observe o código. Deve ser formatado da seguinte maneira:
A verificação de erros deve ser feita sempre que possível e imitar o comportamento das implementações padrão da biblioteca, como retornar NULL em erros em funções que retornam ponteiros ou retornando valores de erro inteiro das funções inteiras. Você deve usar a verificação antecipada de erros , o que significa verificar erros assim que eles puderam ser produzidos, por exemplo. Verificando um NULL retornou após uma ligação falhada malloc .
Os comentários devem descrever por que você fez algo, não o que você fez. Em outras palavras, seu código deve ser auto-explicativo. A documentação para funções na forma de comentários deve estar localizada acima da função no seguinte formato:
/*
Description of function, description of function description of function.
Description of function description of function, description of function
description of function.
Parameters:
paramter1_type paramter1_name | Description of parameter 1, description
of parameter one description of paramter
1.
paramter2_type paramter2_name | Description of parameter 2, description
of parameter one description of paramter
2.
Return:
Description of return value, description of return value description of return value.
*/
