[Concept,00/37] malloc: Import dlmalloc 2.8.6

  From: Simon Glass <simon.glass@canonical.com>

This series imports dlmalloc 2.8.6 from Doug Lea, replacing the old
version 2.6.6 that U-Boot has been using since 2002.

The new version provides:
- Better memory efficiency with improved binning algorithms
- More robust overflow checking via MAX_REQUEST
- Somewhat cleaner codebase

All U-Boot-specific modifications from the historical commits have been
ported to the new implementation, including:
- Pre-relocation malloc via malloc_simple
- Valgrind annotations
- Malloc testing infrastructure
- mcheck heap protection support
- Sandbox USE_DL_PREFIX support

The approach here is to leave the upstream code unchanged, so much as
possible, clearly marking U-Boot-specific changes with an #ifdef

Unfortunately the code size is not great out-of-the-box, so the final
part of the series includes some options to remove in-place realloc(),
provide a simplified init, remove the tree stucture for large blocks
and a few other things.

With these adjustments the new version is about 1K less code on Thumb2
(firefly-rk3288).

The new free() algorithm is more sophisticated but also larger. If
needed we might be able to shrink by a few hundred bytes. Of course SPL
doesn't normally use free() so the benefit might be minimal.

Another point worth mentioning is that the pre-inited av_[] array has
been replaced replaced with a BSS _sm_ struct which reduces the image
size by about 1.5K. One patch adjusts some imx8mp boards to deal with
the larger BSS.

Some code-size stats:

  $ buildman -b mala imx8mp_venice firefly-rk3288 firefly-rk3399 -sS --step 0
  Summary of 2 commits for 3 boards (3 threads, 11 jobs per thread)
  01: backtrace: Strip the source tree prefix from filenames
     aarch64:  w+   imx8mp_venice firefly-rk3399
  40: doc: Add malloc documentation
     aarch64: (for 2/2 boards) all -3904.0 bss +864.0 data -2076.0
       spl/u-boot-spl:all -654.0 spl/u-boot-spl:bss +316.0
       spl/u-boot-spl:data -1034.0 spl/u-boot-spl:text +64.0 text -2692.0
     arm: (for 1/1 boards) all -1436.0 data -1040.0 text -396.0

For the new malloc.h I have avoided including string.h so have added
that to various places that need it.

The existing common/dlmalloc.src file is left alone.

In order to bring this in without losing functionality, I went through
the patches applied to the original implementation over time. Where
these commits were added, they are added as a cherry-pick, with the
original commit hash.

Here is a list of what was done with each U-Boot commit on top of the
new common/dlmalloc.c and include/malloc.h:

 1. 217c9dad827 2002-10-25 Initial revision
    - Ignored

 2. 5b1d713721c 2002-11-03 Initial revision
    - Ignored

 3. 8bde7f776c7 2003-06-27 * Code cleanup:
    - Ignored as we don't really want to change the style

 4. d87080b721e 2006-03-31 GCC-4.x fixes: clean up global data pointer initialization for all boards.
    - Global data is not needed at this point

 5. 81673e9ae14 2008-05-13 Make sure common.h is the first include.
    - common.h has been removed

 6. f2302d4430e 2008-08-06 Fix merge problems
    - no merge problems to fix with the new code

 7. 60a3f404acb 2009-06-13 malloc.h: protect it against multiple include
    - Already covered: new malloc.h has MALLOC_280_H include guards

 8. 5e93bd1c9aa 2009-08-21 Consolidate arch-specific sbrk() implementations
    - Already covered: sbrk() and mem_malloc_init() in separate commit

 9. d4e8ada0f6d 2009-08-21 Consolidate arch-specific mem_malloc_init() implementations
    - Already covered: mem_malloc_init() in separate commit

10. 521af04d853 2009-09-21 Conditionally perform common relocation fixups
    - Not needed: Manual relocation removed in 4babaa0c28b

11. b4feeb4e8a1 2009-11-24 i386: Fix malloc initialization
    - Already covered: mem_malloc_init() is common, no arch-specific guards

12. 2740544881f 2010-01-15 malloc: return NULL if not initialized yet
    - Done: Add check in dlmalloc() to return NULL if not initialized

13. ae30b8c200d 2010-04-06 malloc: sbrk() should return MORECORE_FAILURE instead of NULL on failure
    - Already covered: sbrk() returns MFAIL on failure

14. ea882baf9c1 2010-06-20 New implementation for internal handling of environment variables.
    - Not needed: Just changes #if 0 to #ifdef DEBUG for old stats code

15. 1ba91ba2339 2010-10-14 dlmalloc.c: Fix gcc alias warning
    - Not needed: New dlmalloc has no strict-aliasing warnings

16. 2e5167ccad9 2010-10-28 Replace CONFIG_RELOC_FIXUP_WORKS by CONFIG_NEEDS_MANUAL_RELOC
    - Not needed: Manual relocation removed in 4babaa0c28b

17. 6163f5b4c88 2010-11-15 malloc: Fix issue with calloc memory possibly being non-zero
    - Already covered: sbrk() clears memory on negative increment

18. 21726a7afce 2011-06-29 Add assert() for debug assertions
    - Not needed: New dlmalloc uses U-Boot's global assert()

19. ea95cb73310 2011-09-10 utx8245: fix build breakage due to assert()
    - Not needed: New dlmalloc has different debug check functions

20. 213adf6dffe 2012-03-29 Malloc: Fix -Wundef warnings
    - Not needed: New malloc.h doesn't have these #if issues

21. 93691842e8d 2012-09-04 Fix strict-aliasing warning in dlmalloc
    - Not needed: New dlmalloc has no malloc_bin_reloc()

22. 00d0d2ad4e8 2012-06-03 malloc: remove extern declarations of malloc_bin_reloc() in board.c files
    - Not needed: New dlmalloc has no malloc_bin_reloc()

23. 199adb601ff 2012-10-29 common/misc: sparse fixes
    - Not needed: New dlmalloc uses proper NULL

24. 7b395232da8 2013-01-21 malloc: make malloc_bin_reloc static
    - Not needed: New dlmalloc has no malloc_bin_reloc()

25. 472d546054d 2013-04-01 Consolidate bool type
    - Not needed: Just a comment change (True -> true)

26. d93041a4ca0 2014-07-10 Remove form-feeds from dlmalloc.c
    - Not needed: New dlmalloc doesn't have form-feeds

27. d59476b6446 2014-07-10 Add a simple malloc() implementation for pre-relocation
    - Done (updated): Redirect to malloc_simple before GD_FLG_FULL_MALLOC_INIT

28. 6d7601e7443 2014-07-10 sandbox: Always enable malloc debug
    - Done (updated): Combined with #64, use 'DEBUG 1' for new dlmalloc

29. 854d2b9753e 2014-10-29 dlmalloc: ensure gd is set for early alloc
    - Not needed: Reverted by #38

30. 868de51ddee 2014-08-26 malloc: Output region when debugging
    - Already covered: debug() message in mem_malloc_init()

31. c9356be3074 2014-11-10 dm: Split the simple malloc() implementation into its own file
    - Already covered: Redirect to malloc_simple.c via GD_FLG_FULL_MALLOC_INIT

32. 0aa8a4ad999 2015-03-04 dlmalloc: do memset in malloc init as new default config
    - Already covered: SYS_MALLOC_CLEAR_ON_INIT at line 6396

33. fb5cf7f16be 2015-02-27 Move initf_malloc() to a common place
    - Already covered: initf_malloc() at line 6357

34. 1eb0c03c219 2015-09-13 malloc_simple: Add Kconfig option for using only malloc_simple in the SPL
    - Not needed: Changes to Kconfig/malloc_simple.c, not dlmalloc.c

35. 4f144a41646 2016-01-25 malloc: work around some memalign fragmentation issues
    - Done (updated): Ported to internal_memalign() at line 4955

36. ee05fedc6c8 2016-02-04 malloc: solve dead code issue in memalign()
    - Not needed: New dlmalloc 2.8.6 has rewritten internal_memalign()

37. 2f0bcd4de1a 2016-03-05 malloc: use hidden visibility
    - Done (updated): Use DLMALLOC_EXPORT at line 546

38. deff6fb3a77 2016-03-05 malloc: remove !gd handling
    - Not needed: Reverts #29, we don't add gd check

39. 4eece2602b6 2016-04-21 common/dlmalloc.c: Delete content that was moved to malloc.h
    - Not needed: New dlmalloc doesn't have #if 0 code

40. 034eda867f4 2016-04-25 malloc: improve memalign fragmentation fix
    - Done (updated): Combined with #35 in memalign workaround port

41. 4e33316f656 2017-05-25 malloc: Turn on DEBUG when enabling unit tests
    - Already covered: Combined with #28, #63 at line 555

42. f1896c45cb2 2017-07-24 spl: make SPL and normal u-boot stage use independent SYS_MALLOC_F_LEN
    - Already covered: Use CONFIG_IS_ENABLED and CONFIG_VAL at line 6410

43. a874cac3b45 2017-11-10 malloc: don't compare pointers to 0
    - Not needed: New dlmalloc uses proper NULL comparisons

44. ee038c58d51 2018-05-18 malloc: Use malloc simple before malloc is fully initialized in memalign()
    - Already covered: memalign_simple redirect at line 5367

45. 7cbd2d2e327 2018-11-18 malloc_simple: Add logging of allocations
    - Not needed: Changes to malloc_simple.c, not dlmalloc.c

46. 4c6be01c271 2019-03-27 malloc: Fix memalign not honoring alignment prior to full malloc init
    - Already covered: Uses memalign_simple at line 5367

47. bb71a2d9dcd 2019-10-25 dlmalloc: calloc: fix zeroing early allocations
    - Done (updated): Port to dlcalloc() at line 4857

48. cfda60f99ae 2020-02-03 sandbox: Use a prefix for all allocation functions
    - Done: USE_DL_PREFIX and reverse mappings in malloc.h

49. be621c11b9f 2020-04-15 dlmalloc: remove unit test support in SPL
    - Already covered: CONFIG_IS_ENABLED(UNIT_TEST) at line 554

50. 9297e366d6a 2020-04-29 malloc: dlmalloc: add an ability for the malloc to be re-init/init multiple times
    - Not needed: No boards use CONFIG_SYS_MALLOC_DEFAULT_TO_INIT

51. f7ae49fc4f3 2020-05-10 common: Drop log.h from common header
    - Already covered: Includes log.h at line 559

52. 401d1c4f5d2 2020-10-30 common: Drop asm/global_data.h from common header
    - Already covered: Includes asm/global_data.h at line 557

53. c6bf4f38988 2021-02-10 malloc: adjust memcpy() and memset() definitions.
    - Not needed: New malloc.h doesn't declare memset/memcpy

54. c197f6e2792 2021-03-15 malloc: Export malloc_simple_info()
    - Not needed: Only changes malloc.h, not dlmalloc.c

55. 5ad9220bf7b 2021-05-29 malloc: add SPDX license identifiers
    - Not needed: New dlmalloc has MIT-0 license from upstream

56. bdaeea1b686 2022-03-23 malloc: Annotate allocator for valgrind
    - Done (updated): Valgrind annotations in dlmalloc(), dlfree(), dlrealloc()

57. 62d638386c1 2022-09-06 test: Support testing malloc() failures
    - Done: malloc_testing/malloc_max_allocs in dlmalloc()

58. f88d48cc74f 2023-02-27 dlmalloc: Fix a warning with clang-15
    - Done: Add (void) to dlmalloc_stats() function definition

59. c9db9a2ef55 2023-08-25 dlmalloc: Add support for SPL_SYS_MALLOC_CLEAR_ON_INIT
    - Already covered: Uses CONFIG_IS_ENABLED() in mem_malloc_init() from #32

60. 6a595c2f67e 2023-09-06 common: malloc: Remove unused NEEDS_MANUAL_RELOC code bits
    - Not needed: NEEDS_MANUAL_RELOC has been removed

61. ac897385bbf 2023-10-02 Merge branch 'next'
    - Not needed: Merge commit, no dlmalloc changes

62. 3d6d5075146 2023-09-26 spl: Use SYS_MALLOC_F instead of SYS_MALLOC_F_LEN
    - Already covered: Uses CONFIG_IS_ENABLED(SYS_MALLOC_F) throughout

63. 1786861415f 2023-10-07 malloc: Enable assertions if UNIT_TEST is enabled
    - Done (updated): Combined with #28, use 'DEBUG 1' for new dlmalloc

64. c82ff481159 2024-03-31 mcheck: prepare +1 tier for mcheck-wrappers, in dl-*alloc commands
    - Done (updated): Added STATIC_IF_MCHECK and *_impl macros for dlmalloc 2.8.6

65. dfba071ddc3 2024-03-31 mcheck: Use memset/memcpy instead of MALLOC_ZERO/MALLOC_COPY for mcheck.
    - Done: Undef and redefine MALLOC_ZERO/MALLOC_COPY when mcheck enabled

66. 151493a8750 2024-03-31 mcheck: integrate mcheck into dlmalloc.c
    - Done: Added mcheck wrapper functions for dlmalloc, dlfree, dlrealloc, dlmemalign, dlcalloc

67. ae838768d79 2024-03-31 mcheck: support memalign
    - Done: Implemented dlmemalign wrapper with mcheck hooks

68. 18c1bfafe0c 2024-03-31 mcheck: add pedantic mode support
    - Done: Added mcheck_pedantic_prehook() calls and mcheck_pedantic()/mcheck_check_all() API

69. a79fc7a79cc 2024-04-27 common: Remove <common.h> and add needed includes
    - Not needed: common.h has been removed

70. d678a59d2d7 2024-05-18 Revert "Merge patch series "arm: dts: am62-beagleplay: Fix Beagleplay Ethernet""
    - Not needed: common.h has been removed

71. 03de305ec48 2024-05-20 Restore patch series "arm: dts: am62-beagleplay: Fix Beagleplay Ethernet"
    - Not needed: common.h has been removed

72. 910cef3d2fb 2024-07-13 common: Remove duplicate newlines
    - Not needed: New dlmalloc has its own formatting from upstream

73. 6627fbba203 2024-07-23 include: Remove duplicate newlines
    - Not needed: New malloc.h has its own formatting from upstream

74. 04894f5ad53 2024-07-30 malloc: Support testing with realloc()
    - Done: Combined with #57, malloc_testing check in dlrealloc()

75. 8642b2178d2 2024-08-02 dlmalloc: Fix integer overflow in request2size()
    - Not needed: New dlmalloc 2.8.6 uses MAX_REQUEST for robust overflow checks

76. 0a10b49206a 2024-08-02 dlmalloc: Fix integer overflow in sbrk()
    - Already covered: sbrk() checks bounds before memset in U-Boot section

77. 9b9368b5c4d 2024-08-02 dlmalloc: Make sure allocation size is within malloc area
    - Not needed: New dlmalloc 2.8.6 uses MAX_REQUEST for robust overflow checks

78. 41fecdc94e3 2024-10-21 common: Tidy up how malloc() is inited
    - Already covered: mem_malloc_init() uses map_sysmem in U-Boot section

79. 22f87ef5304 2025-08-17 malloc: Avoid defining calloc()
    - Done: Added SYS_MALLOC_SIMPLE section to malloc.h with calloc redirect


Simon Glass (37):
  test: hooks: Add a symlink for tasman
  treewide: Add missing string.h includes
  imx8mp: Increase the BSS limit for a few boards
  test: Use TOTAL_MALLOC_LEN for abuf and alist tests
  malloc: Rename dlmalloc.c to dlmalloc_old.c
  malloc: Rename malloc.h to malloc_old.h
  malloc: Import dlmalloc 2.8.6
  malloc: Add mem_malloc_init() and sbrk()
  malloc: Add U-Boot configuration for dlmalloc 2.8.6
  malloc: Fix assert warning
  malloc: return NULL if not initialized yet
  Add a simple malloc() implementation for pre-relocation
  malloc: Enable assertions if UNIT_TEST is enabled
  malloc: Reduce code size with INSECURE and NO_MALLINFO
  malloc: work around some memalign fragmentation issues
  malloc: use hidden visibility
  dlmalloc: calloc: fix zeroing early allocations
  sandbox: Use a prefix for all allocation functions
  malloc: Annotate allocator for valgrind
  test: Support testing malloc() failures
  dlmalloc: Fix a warning with clang-15
  mcheck: prepare +1 tier for mcheck-wrappers, in dl-*alloc commands
  mcheck: Use memset/memcpy instead of MALLOC_ZERO/MALLOC_COPY for
    mcheck.
  mcheck: integrate mcheck into dlmalloc.c
  mcheck: support memalign
  mcheck: add pedantic mode support
  malloc: Avoid defining calloc()
  malloc: Set up the malloc() state in mem_malloc_init()
  malloc: Allow building dlmalloc with SPL_SYS_MALLOC_SIMPLE
  malloc: Add a way to control the size of dlmalloc
  malloc: Add NO_REALLOC_IN_PLACE option to reduce code size
  malloc: Add NO_TREE_BINS option to reduce code size
  malloc: Add SIMPLE_MEMALIGN to simplify memalign for code size
  malloc: Add SMALLCHUNKS_AS_FUNCS to convert macros to funcs
  test: Add some tests for dlmalloc
  malloc: Switch to the new malloc() implementation
  doc: Add malloc documentation

 Kconfig                                     |   63 +
 arch/arm/mach-zynq/slcr.c                   |    1 +
 board/ti/common/cape_detect.c               |    1 +
 boot/expo_build_cb.c                        |    1 +
 cmd/printf.c                                |    1 +
 common/Makefile                             |    4 +
 common/bouncebuf.c                          |    5 +-
 common/dlmalloc.c                           | 8277 ++++++++++++++-----
 common/dlmalloc_old.c                       | 2611 ++++++
 common/iomux.c                              |    1 +
 common/menu.c                               |    1 +
 configs/imx8mp_data_modul_edm_sbc_defconfig |    2 +-
 configs/imx8mp_dhsom.config                 |    2 +-
 configs/imx8mp_venice_defconfig             |    2 +-
 configs/venice2_defconfig                   |    1 +
 doc/arch/sandbox/sandbox.rst                |    2 +
 doc/develop/index.rst                       |    1 +
 doc/develop/malloc.rst                      |  333 +
 drivers/crypto/fsl/desc_constr.h            |    1 +
 drivers/crypto/fsl/error.c                  |    1 +
 drivers/crypto/fsl/fsl_blob.c               |    1 +
 drivers/crypto/fsl/fsl_hash.c               |    1 +
 drivers/dma/apbh_dma.c                      |    1 +
 drivers/fpga/versalpl.c                     |    1 +
 drivers/net/fsl-mc/dpio/qbman_portal.c      |    1 +
 drivers/net/qe/uccf.c                       |    1 +
 drivers/spi/spi-mem-nodm.c                  |    1 +
 drivers/video/imx/ipu_common.c              |    1 +
 include/malloc.h                            | 1515 ++--
 include/malloc_old.h                        |  999 +++
 lib/circbuf.c                               |    1 +
 lib/crypto/x509_helper.c                    |    2 +
 lib/dhry/dhry_1.c                           |    1 +
 lib/libavb/avb_sysdeps_posix.c              |    1 +
 lib/linux_compat.c                          |    1 +
 lib/list_sort.c                             |    1 +
 lib/mbedtls/mscode_parser.c                 |    1 +
 lib/membuf.c                                |    1 +
 lib/strto.c                                 |    1 +
 test/common/Makefile                        |    1 +
 test/common/malloc.c                        |  629 ++
 test/hooks/bin/tasman                       |    1 +
 test/lib/abuf.c                             |    5 +-
 test/lib/alist.c                            |    3 +-
 44 files changed, 11624 insertions(+), 2858 deletions(-)
 create mode 100644 common/dlmalloc_old.c
 create mode 100644 doc/develop/malloc.rst
 create mode 100644 include/malloc_old.h
 create mode 100644 test/common/malloc.c
 create mode 120000 test/hooks/bin/tasman