1  // Copyright 2015-2016 Espressif Systems (Shanghai) PTE LTD
  2  //
  3  // Licensed under the Apache License, Version 2.0 (the "License");
  4  // you may not use this file except in compliance with the License.
  5  // You may obtain a copy of the License at
  6  
  7  //     http://www.apache.org/licenses/LICENSE-2.0
  8  //
  9  // Unless required by applicable law or agreed to in writing, software
 10  // distributed under the License is distributed on an "AS IS" BASIS,
 11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 12  // See the License for the specific language governing permissions and
 13  // limitations under the License.
 14  #include <stdint.h>
 15  #include <stdlib.h>
 16  #include <stdbool.h>
 17  #include <assert.h>
 18  #include <string.h>
 19  #include <stddef.h>
 20  #include <stdio.h>
 21  #include <sys/cdefs.h>
 22  #include "heap_tlsf.h"
 23  #include <multi_heap.h>
 24  #include "multi_heap_internal.h"
 25  
 26  /* Note: Keep platform-specific parts in this header, this source
 27     file should depend on libc only */
 28  #include "multi_heap_platform.h"
 29  
 30  /* Defines compile-time configuration macros */
 31  #include "multi_heap_config.h"
 32  
 33  #ifndef MULTI_HEAP_POISONING
 34  /* if no heap poisoning, public API aliases directly to these implementations */
 35  void *multi_heap_malloc(multi_heap_handle_t heap, size_t size)
 36      __attribute__((alias("multi_heap_malloc_impl")));
 37  
 38  void *multi_heap_aligned_alloc(multi_heap_handle_t heap, size_t size, size_t alignment)
 39      __attribute__((alias("multi_heap_aligned_alloc_impl")));
 40  
 41  void multi_heap_aligned_free(multi_heap_handle_t heap, void *p)
 42      __attribute__((alias("multi_heap_free_impl")));
 43  
 44  void multi_heap_free(multi_heap_handle_t heap, void *p)
 45      __attribute__((alias("multi_heap_free_impl")));
 46  
 47  void *multi_heap_realloc(multi_heap_handle_t heap, void *p, size_t size)
 48      __attribute__((alias("multi_heap_realloc_impl")));
 49  
 50  size_t multi_heap_get_allocated_size(multi_heap_handle_t heap, void *p)
 51      __attribute__((alias("multi_heap_get_allocated_size_impl")));
 52  
 53  multi_heap_handle_t multi_heap_register(void *start, size_t size)
 54      __attribute__((alias("multi_heap_register_impl")));
 55  
 56  void multi_heap_get_info(multi_heap_handle_t heap, multi_heap_info_t *info)
 57      __attribute__((alias("multi_heap_get_info_impl")));
 58  
 59  size_t multi_heap_free_size(multi_heap_handle_t heap)
 60      __attribute__((alias("multi_heap_free_size_impl")));
 61  
 62  size_t multi_heap_minimum_free_size(multi_heap_handle_t heap)
 63      __attribute__((alias("multi_heap_minimum_free_size_impl")));
 64  
 65  void *multi_heap_get_block_address(multi_heap_block_handle_t block)
 66      __attribute__((alias("multi_heap_get_block_address_impl")));
 67  
 68  void *multi_heap_get_block_owner(multi_heap_block_handle_t block)
 69  {
 70      return NULL;
 71  }
 72  
 73  #endif
 74  
 75  #define ALIGN(X) ((X) & ~(sizeof(void *)-1))
 76  #define ALIGN_UP(X) ALIGN((X)+sizeof(void *)-1)
 77  #define ALIGN_UP_BY(num, align) (((num) + ((align) - 1)) & ~((align) - 1))
 78  
 79  
 80  typedef struct multi_heap_info {
 81      void *lock;
 82      size_t free_bytes;
 83      size_t minimum_free_bytes;
 84      size_t pool_size;
 85      tlsf_t heap_data;
 86  } heap_t;
 87  
 88  /* Return true if this block is free. */
 89  static inline bool is_free(const block_header_t *block)
 90  {
 91      return ((block->size & 0x01) != 0);
 92  }
 93  
 94  /* Data size of the block (excludes this block's header) */
 95  static inline size_t block_data_size(const block_header_t *block)
 96  {
 97      return (block->size & ~0x03);
 98  }
 99  
100  /* Check a block is valid for this heap. Used to verify parameters. */
101  static void assert_valid_block(const heap_t *heap, const block_header_t *block)
102  {
103      pool_t pool = tlsf_get_pool(heap->heap_data);
104      void *ptr = block_to_ptr(block);
105  
106      MULTI_HEAP_ASSERT((ptr >= pool) && 
107                      (ptr < pool + heap->pool_size), 
108                      (uintptr_t)ptr);
109  }
110  
111  void *multi_heap_get_block_address_impl(multi_heap_block_handle_t block)
112  {
113      void *ptr = block_to_ptr(block);
114      return (ptr);
115  }
116  
117  size_t multi_heap_get_allocated_size_impl(multi_heap_handle_t heap, void *p)
118  {
119      return tlsf_block_size(p);
120  }
121  
122  multi_heap_handle_t multi_heap_register_impl(void *start_ptr, size_t size)
123  {
124      assert(start_ptr);
125      if(size < (tlsf_size() + tlsf_block_size_min() + sizeof(heap_t))) {
126          //Region too small to be a heap.
127          return NULL;
128      }
129  
130      heap_t *result = (heap_t *)start_ptr;
131      size -= sizeof(heap_t);
132  
133      result->heap_data = tlsf_create_with_pool(start_ptr + sizeof(heap_t), size);
134      if(!result->heap_data) {
135          return NULL;
136      }
137  
138      result->lock = NULL;
139      result->free_bytes = size - tlsf_size();
140      result->pool_size = size;
141      result->minimum_free_bytes = result->free_bytes;
142      return result;
143  }
144  
145  void multi_heap_set_lock(multi_heap_handle_t heap, void *lock)
146  {
147      heap->lock = lock;
148  }
149  
150  void inline multi_heap_internal_lock(multi_heap_handle_t heap)
151  {
152      MULTI_HEAP_LOCK(heap->lock);
153  }
154  
155  void inline multi_heap_internal_unlock(multi_heap_handle_t heap)
156  {
157      MULTI_HEAP_UNLOCK(heap->lock);
158  }
159  
160  multi_heap_block_handle_t multi_heap_get_first_block(multi_heap_handle_t heap)
161  {
162      assert(heap != NULL);
163      pool_t pool = tlsf_get_pool(heap->heap_data);
164      block_header_t* block = offset_to_block(pool, -(int)block_header_overhead);
165  
166      return (multi_heap_block_handle_t)block;
167  }
168  
169  multi_heap_block_handle_t multi_heap_get_next_block(multi_heap_handle_t heap, multi_heap_block_handle_t block)
170  {
171      assert(heap != NULL);
172      assert_valid_block(heap, block);
173      block_header_t* next = block_next(block);
174   
175      if(block_data_size(next) == 0) {
176          //Last block:
177          return NULL;
178      } else {
179          return (multi_heap_block_handle_t)next;
180      }
181  
182  }
183  
184  bool multi_heap_is_free(multi_heap_block_handle_t block)
185  {
186      return is_free(block);
187  }
188  
189  void *multi_heap_malloc_impl(multi_heap_handle_t heap, size_t size)
190  {
191      if (size == 0 || heap == NULL) {
192          return NULL;
193      }
194  
195  
196      multi_heap_internal_lock(heap);
197      void *result = tlsf_malloc(heap->heap_data, size);
198      if(result) {
199          heap->free_bytes -= tlsf_block_size(result);
200          if (heap->free_bytes < heap->minimum_free_bytes) {
201              heap->minimum_free_bytes = heap->free_bytes;
202          }
203      }    
204      multi_heap_internal_unlock(heap);
205  
206      return result;
207  }
208  
209  void multi_heap_free_impl(multi_heap_handle_t heap, void *p)
210  {
211  
212      if (heap == NULL || p == NULL) {
213          return;
214      }
215  
216      assert_valid_block(heap, p);
217  
218      multi_heap_internal_lock(heap);
219      heap->free_bytes += tlsf_block_size(p);
220      tlsf_free(heap->heap_data, p);
221      multi_heap_internal_unlock(heap);
222  }
223  
224  void *multi_heap_realloc_impl(multi_heap_handle_t heap, void *p, size_t size)
225  {
226      assert(heap != NULL);
227  
228      if (p == NULL) {
229          return multi_heap_malloc_impl(heap, size);
230      }
231  
232      assert_valid_block(heap, p);
233  
234      if (heap == NULL) {
235          return NULL;
236      }
237  
238      multi_heap_internal_lock(heap);
239      size_t previous_block_size =  tlsf_block_size(p);
240      void *result = tlsf_realloc(heap->heap_data, p, size);
241      if(result) {
242          heap->free_bytes += previous_block_size;
243          heap->free_bytes -= tlsf_block_size(result);
244          if (heap->free_bytes < heap->minimum_free_bytes) {
245              heap->minimum_free_bytes = heap->free_bytes;
246          }
247      }
248      
249      multi_heap_internal_unlock(heap);
250  
251      return result;
252  }
253  
254  void *multi_heap_aligned_alloc_impl(multi_heap_handle_t heap, size_t size, size_t alignment)
255  {
256      if(heap == NULL) {
257          return NULL;
258      }
259  
260      if(!size) {
261          return NULL;
262      }
263  
264      //Alignment must be a power of two:
265      if(((alignment & (alignment - 1)) != 0) ||(!alignment)) {
266          return NULL;
267      }
268  
269      multi_heap_internal_lock(heap);
270      void *result = tlsf_memalign(heap->heap_data, alignment, size);
271      if(result) {
272          heap->free_bytes -= tlsf_block_size(result);
273          if(heap->free_bytes < heap->minimum_free_bytes) {
274              heap->minimum_free_bytes = heap->free_bytes;
275          }
276      }
277      multi_heap_internal_unlock(heap);
278  
279      return result;
280  }
281  
282  bool multi_heap_check(multi_heap_handle_t heap, bool print_errors)
283  {
284      (void)print_errors;
285      bool valid = true;
286      assert(heap != NULL);
287  
288      multi_heap_internal_lock(heap);
289      if(tlsf_check(heap->heap_data)) {
290          valid = false;
291      }
292  
293      if(tlsf_check_pool(tlsf_get_pool(heap->heap_data))) {
294          valid = false;
295      }
296  
297      multi_heap_internal_unlock(heap);
298      return valid;
299  }
300  
301  static void multi_heap_dump_tlsf(void* ptr, size_t size, int used, void* user)
302  {
303      (void)user;
304      MULTI_HEAP_STDERR_PRINTF("Block %p data, size: %d bytes, Free: %s \n", 
305                              (void *)ptr,
306                              size,
307                              used ? "No" : "Yes");
308  }
309  
310  void multi_heap_dump(multi_heap_handle_t heap)
311  {
312      assert(heap != NULL);
313  
314      multi_heap_internal_lock(heap);
315      MULTI_HEAP_STDERR_PRINTF("Showing data for heap: %p \n", (void *)heap);
316      tlsf_walk_pool(tlsf_get_pool(heap->heap_data), multi_heap_dump_tlsf, NULL);
317      multi_heap_internal_unlock(heap);
318  }
319  
320  size_t multi_heap_free_size_impl(multi_heap_handle_t heap)
321  {
322      if (heap == NULL) {
323          return 0;
324      }
325  
326      return heap->free_bytes;
327  }
328  
329  size_t multi_heap_minimum_free_size_impl(multi_heap_handle_t heap)
330  {
331      if (heap == NULL) {
332          return 0;
333      }
334  
335      return heap->minimum_free_bytes;
336  }
337  
338  static void multi_heap_get_info_tlsf(void* ptr, size_t size, int used, void* user)
339  {
340      multi_heap_info_t *info = user;
341      
342      if(used) {
343          info->allocated_blocks++;
344      } else {
345          info->free_blocks++;
346          
347          if(size > info->largest_free_block ) {
348              info->largest_free_block = size;
349          }   
350      }
351      
352      info->total_blocks++; 
353  }
354  
355  void multi_heap_get_info_impl(multi_heap_handle_t heap, multi_heap_info_t *info)
356  {
357      memset(info, 0, sizeof(multi_heap_info_t));
358  
359      if (heap == NULL) {
360          return;
361      }
362  
363      multi_heap_internal_lock(heap);
364      tlsf_walk_pool(tlsf_get_pool(heap->heap_data), multi_heap_get_info_tlsf, info);
365      info->total_allocated_bytes = (heap->pool_size - tlsf_size()) - heap->free_bytes;
366      info->minimum_free_bytes = heap->minimum_free_bytes;
367      info->total_free_bytes = heap->free_bytes;
368      info->largest_free_block = info->largest_free_block ? 1 << (31 - __builtin_clz(info->largest_free_block)) : 0;
369      multi_heap_internal_unlock(heap);
370  }