Embedded Studio带的malloc，使用的buddy算法

eric2013

伙伴算法（buddy算法），计算机算法的一种，是为了核心内存管理能够快速响应请求，尽可能地在提高内存利用率的同时减少内存碎片的一种算法。

1. // **********************************************************************
   
2. // *                    SEGGER Microcontroller GmbH                     *
   
3. // *                        The Embedded Experts                        *
   
4. // **********************************************************************
   
5. // *                                                                    *
   
6. // *            (c) 2014 - 2020 SEGGER Microcontroller GmbH             *
   
7. // *            (c) 2001 - 2020 Rowley Associates Limited               *
   
8. // *                                                                    *
   
9. // *           www.segger.com     Support: support@segger.com           *
   
10. // *                                                                    *
    
11. // **********************************************************************
    
12. // *                                                                    *
    
13. // * All rights reserved.                                               *
    
14. // *                                                                    *
    
15. // * Redistribution and use in source and binary forms, with or         *
    
16. // * without modification, are permitted provided that the following    *
    
17. // * condition is met:                                                  *
    
18. // *                                                                    *
    
19. // * - Redistributions of source code must retain the above copyright   *
    
20. // *   notice, this condition and the following disclaimer.             *
    
21. // *                                                                    *
    
22. // * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND             *
    
23. // * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,        *
    
24. // * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF           *
    
25. // * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE           *
    
26. // * DISCLAIMED. IN NO EVENT SHALL SEGGER Microcontroller BE LIABLE FOR *
    
27. // * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR           *
    
28. // * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT  *
    
29. // * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;    *
    
30. // * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF      *
    
31. // * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT          *
    
32. // * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE  *
    
33. // * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH   *
    
34. // * DAMAGE.                                                            *
    
35. // *                                                                    *
    
36. // **********************************************************************
    
37. 
    
38. #ifndef BUDDY_HEAP_H
    
39. #define BUDDY_HEAP_H
    
40. 
    
41. #include <stdlib.h>
    
42. 
    
43. typedef struct buddy_link_tag
    
44. {
    
45.   struct buddy_link_tag *next;
    
46.   struct buddy_link_tag *prev;
    
47. } __BUDDY_LINKS_t;
    
48. 
    
49. typedef struct {
    
50.   long total_capacity;     // total size of the heap
    
51.   long alloc_requests;     // number of times alloc called
    
52.   long alloc_failures;     // how many times alloc has failed
    
53.   long free_requests;      // number of times free called with non-zero argument
    
54.   long free_failures;      // how many times free has been called with a bad argument or corrupt heap
    
55.   long used_bytes;         // how many bytes are used in the heap (a multiple of the allocation unit)
    
56.   long free_bytes;         // how many bytes are free in the heap
    
57.   long min_free_bytes;     // lowest number of free bytes bytes in the heap
    
58.   long blocks_split;       // how many times blocks have needed to be split.
    
59.   long blocks_coalesed;    // how many times blocks have been coalesced.
    
60. } BUDDY_HEAP_STATS_t;
    
61. 
    
62. typedef struct
    
63. {
    
64.   char *mem;
    
65.   unsigned max_k;     // 'm' in Fundamental Algorithms
    
66.   unsigned min_k;     // minimum block size returned
    
67.   unsigned min_size;  // 1 << min_k
    
68.   unsigned size;
    
69.   BUDDY_HEAP_STATS_t stats;
    
70.   __BUDDY_LINKS_t free_head[sizeof(void *)*8];  // 4 entries unused, could do something here...
    
71. } BUDDY_HEAP_t;
    
72. 
    
73. 
    
74. void *buddy_alloc(BUDDY_HEAP_t *h, size_t size);
    
75. void buddy_free(BUDDY_HEAP_t *h, void *data);
    
76. int buddy_heap_init(BUDDY_HEAP_t *h, void *mem, size_t size);
    
77. 
    
78. // For the future...
    
79. //
    
80. //typedef struct
    
81. //{
    
82. //  BUDDY_HEAP_t heap;
    
83. //  CTL_MUTEX_t mutex;
    
84. //  CTL_EVENT_SET_t events;
    
85. //} CTL_BUDDY_HEAP_t;
    
86. //
    
87. //int ctl_buddy_heap_init(CTL_BUDDY_HEAP_t *h, void *mem, size_t size);
    
88. //void *ctl_buddy_alloc(CTL_BUDDY_HEAP_t *h, size_t size, CTL_TIMEOUT_t timeout, CTL_);
    
89. //void *ctl_buddy_alloc_with_timeout(CTL_BUDDY_HEAP_t *h, size_t size, CTL_TIMEOUT_t timeout, CTL_TIME_t t);
    
90. //void ctl_buddy_free(CTL_BUDDY_HEAP_t *h, void *data);
    
91. 
    
92. #endif
    

复制代码

庄永

在实时操作系统中，移植tlsf我个人觉得应该会更好一点。

hpdell

这个有没有完整的程序啊 ？

eric2013

hpdell 发表于 2020-9-3 08:57
这个有没有完整的程序啊 ？

这个没有完整程序，我就是简单浏览了下他们的底层。

阴世幽泉

eric2013 发表于 2020-9-3 13:44
这个没有完整程序，我就是简单浏览了下他们的底层。

我这边有一份参考程序，不过我在项目使用时有些问题（ARM7芯片上链表申请内存，会出现指针飞了情况），硬汉哥有空一起看看，我怀疑是有使用平台要求

阴世幽泉

这个别人写的，仅供参考

snakeemail

庄永 发表于 2020-8-18 17:51
在实时操作系统中，移植tlsf我个人觉得应该会更好一点。

请问是不是liteos里面带的？