llvm-project.git/libc/src/stdlib/freelist_malloc.cpp, branch users/nico/python-1 Unnamed repository; edit this file 'description' to name the repository. [libc] Breakup freelist_malloc into separate files (#119806) 2024-12-16T18:30:27+00:00 Petr Hosek phosek@google.com 2024-12-16T18:30:27+00:00 7bf3137c39a61283ebcb58793e830f8b768b74e7 This better matches the structure we use for the rest of libc. 
This better matches the structure we use for the rest of libc.
 Revert "[libc] Breakup freelist_malloc into separate files" (#119749) 2024-12-12T21:28:30+00:00 Petr Hosek phosek@google.com 2024-12-12T21:28:30+00:00 379cc44f56e6f220422ce85d2295833f849086e0 Reverts llvm/llvm-project#98784 which broke libc builders. 
Reverts llvm/llvm-project#98784 which broke libc builders.
 [libc] Breakup freelist_malloc into separate files (#98784) 2024-12-12T19:24:36+00:00 Petr Hosek phosek@google.com 2024-12-12T19:24:36+00:00 4e2a9e50f6dd6760b12838517c7f85a0c9032921 This better matches the structure we use for the rest of libc. 
This better matches the structure we use for the rest of libc.
 Reapply "[libc] Use best-fit binary trie to make malloc logarithmic (#117065)" 2024-11-21T23:26:24+00:00 Daniel Thornburgh dthorn@google.com 2024-11-21T21:43:27+00:00 385961d7b23d5500d20954ad8137b27ecced2692 This reverts commit 93b83642ee34d0092b94776728dad0117c2b72a1. - Correct riscv32 assumption about alignment (bit of a hack). - Fix test case where the largest_small and smallest sizes are the same. 
This reverts commit 93b83642ee34d0092b94776728dad0117c2b72a1.

 - Correct riscv32 assumption about alignment (bit of a hack).
 - Fix test case where the largest_small and smallest sizes are the
   same.
Revert "[libc] Use best-fit binary trie to make malloc logarithmic (#117065)" 2024-11-21T19:56:05+00:00 Daniel Thornburgh dthorn@google.com 2024-11-21T19:55:44+00:00 93b83642ee34d0092b94776728dad0117c2b72a1 This reverts commit b05600d96f46697e21f6b1b7ad901391326243a8. riscv32 unit test still broken 
This reverts commit b05600d96f46697e21f6b1b7ad901391326243a8.
riscv32 unit test still broken
Reapply "[libc] Use best-fit binary trie to make malloc logarithmic" (#117065) 2024-11-21T19:30:51+00:00 Daniel Thornburgh dthorn@google.com 2024-11-20T22:05:44+00:00 b05600d96f46697e21f6b1b7ad901391326243a8 - Fix assertion expressions. - Fix incorrect small size in freestore_test. - There may only be one small size for high alignment and small pointers (riscv32). - Don't rely on stack alignment in FreeList test. 
 - Fix assertion expressions.
 - Fix incorrect small size in freestore_test.
 - There may only be one small size for high alignment and small
   pointers (riscv32).
 - Don't rely on stack alignment in FreeList test.
Revert "[libc] Use best-fit binary trie to make malloc logarithmic" (#117065) 2024-11-20T22:00:07+00:00 Daniel Thornburgh dthorn@google.com 2024-11-20T22:00:07+00:00 9be475af81ee36f1d360ad1d70b695c4b26c98fa Reverts llvm/llvm-project#106259 Unit tests break on AArch64. 
Reverts llvm/llvm-project#106259

Unit tests break on AArch64.
 [libc] Use best-fit binary trie to make malloc logarithmic (#106259) 2024-11-20T21:54:00+00:00 Daniel Thornburgh dthorn@google.com 2024-11-20T21:54:00+00:00 c3207c31fce8afa4e5ae728804f18b4e863197e7 This reworks the free store implementation in libc's malloc to use a dlmalloc-style binary trie of circularly linked FIFO free lists. This data structure can be maintained in logarithmic time, but it still permits a relatively small implementation compared to other logarithmic-time ordered maps. The implementation doesn't do the various bitwise tricks or optimizations used in actual dlmalloc; it instead optimizes for (relative) readability and minimum code size. Specific optimization can be added as necessary given future profiling. 
This reworks the free store implementation in libc's malloc to use a
dlmalloc-style binary trie of circularly linked FIFO free lists. This
data structure can be maintained in logarithmic time, but it still
permits a relatively small implementation compared to other
logarithmic-time ordered maps.

The implementation doesn't do the various bitwise tricks or
optimizations used in actual dlmalloc; it instead optimizes for
(relative) readability and minimum code size. Specific optimization can
be added as necessary given future profiling.
 [libc] Lazily initialize freelist malloc using symbols (#99254) 2024-07-25T20:38:06+00:00 Daniel Thornburgh dthorn@google.com 2024-07-25T20:38:06+00:00 0c10bdc05f0f90ae173f29854f03796e92ed76e4 This requires the user to set the upper bounds of the heap by defining the symbol `__libc_heap_limit`. The heap begins at `_end` and ends `__libc_heap_limit` bytes afterwards. This prevents a completely unused heap from requiring any space, and it prevents the heap from being zeroed at initialization time as part of BSS. It also allows users to customize the available heap location without recompiling libc. I'd think this should eventually be replaced with an implemenation based on a morecore() library. This would allow the same implementation to use sbrk() on POSIX, `_end` and `__libc_heap_limit` on embedded, and a buffer in tests. It would also provide better "wilderness" behavior that tends to decrease heap fragementation (see Wilson et al.) See #98096 
This requires the user to set the upper bounds of the heap by defining
the symbol `__libc_heap_limit`. The heap begins at `_end` and ends
`__libc_heap_limit` bytes afterwards. This prevents a completely unused
heap from requiring any space, and it prevents the heap from being
zeroed at initialization time as part of BSS. It also allows users to
customize the available heap location without recompiling libc.
    
I'd think this should eventually be replaced with an implemenation based
on a morecore() library. This would allow the same implementation to use
sbrk() on POSIX, `_end` and `__libc_heap_limit` on embedded, and a
buffer in tests. It would also provide better "wilderness" behavior that
tends to decrease heap fragementation (see Wilson et al.)

See #98096
 [libc] Migrate to using LIBC_NAMESPACE_DECL for namespace declaration (#98597) 2024-07-12T16:28:41+00:00 Petr Hosek phosek@google.com 2024-07-12T16:28:41+00:00 5ff3ff33ff930e4ec49da7910612d8a41eb068cb This is a part of #97655. 
This is a part of #97655.