6 #include <zephyr/sys/sys_heap.h>
7 #include <zephyr/sys/util.h>
8 #include <zephyr/sys/heap_listener.h>
9 #include <zephyr/kernel.h>
10 #include <string.h>
11 #include "heap.h"
13 #include <sanitizer/msan_interface.h>
17 static inline void increase_allocated_bytes(struct z_heap *h, size_t num_bytes)  in increase_allocated_bytes()  argument
19 	h->allocated_bytes += num_bytes;  in increase_allocated_bytes()
20 	h->max_allocated_bytes = MAX(h->max_allocated_bytes, h->allocated_bytes);  in increase_allocated_bytes()
24 static void *chunk_mem(struct z_heap *h, chunkid_t c)  in chunk_mem()  argument
26 	chunk_unit_t *buf = chunk_buf(h);  in chunk_mem()
27 	uint8_t *ret = ((uint8_t *)&buf[c]) + chunk_header_bytes(h);  in chunk_mem()
29 	CHECK(!(((uintptr_t)ret) & (big_heap(h) ? 7 : 3)));  in chunk_mem()
34 static void free_list_remove_bidx(struct z_heap *h, chunkid_t c, int bidx)  in free_list_remove_bidx()  argument
36 	struct z_heap_bucket *b = &h->buckets[bidx];  in free_list_remove_bidx()
38 	CHECK(!chunk_used(h, c));  in free_list_remove_bidx()
40 	CHECK(h->avail_buckets & BIT(bidx));  in free_list_remove_bidx()
42 	if (next_free_chunk(h, c) == c) {  in free_list_remove_bidx()
44 		h->avail_buckets &= ~BIT(bidx);  in free_list_remove_bidx()
47 		chunkid_t first = prev_free_chunk(h, c),  in free_list_remove_bidx()
48 			  second = next_free_chunk(h, c);  in free_list_remove_bidx()
51 		set_next_free_chunk(h, first, second);  in free_list_remove_bidx()
52 		set_prev_free_chunk(h, second, first);  in free_list_remove_bidx()
56 	h->free_bytes -= chunksz_to_bytes(h, chunk_size(h, c));  in free_list_remove_bidx()
60 static void free_list_remove(struct z_heap *h, chunkid_t c)  in free_list_remove()  argument
62 	if (!solo_free_header(h, c)) {  in free_list_remove()
63 		int bidx = bucket_idx(h, chunk_size(h, c));  in free_list_remove()
64 		free_list_remove_bidx(h, c, bidx);  in free_list_remove()
68 static void free_list_add_bidx(struct z_heap *h, chunkid_t c, int bidx)  in free_list_add_bidx()  argument
70 	struct z_heap_bucket *b = &h->buckets[bidx];  in free_list_add_bidx()
73 		CHECK((h->avail_buckets & BIT(bidx)) == 0);  in free_list_add_bidx()
76 		h->avail_buckets |= BIT(bidx);  in free_list_add_bidx()
78 		set_prev_free_chunk(h, c, c);  in free_list_add_bidx()
79 		set_next_free_chunk(h, c, c);  in free_list_add_bidx()
81 		CHECK(h->avail_buckets & BIT(bidx));  in free_list_add_bidx()
85 		chunkid_t first = prev_free_chunk(h, second);  in free_list_add_bidx()
87 		set_prev_free_chunk(h, c, first);  in free_list_add_bidx()
88 		set_next_free_chunk(h, c, second);  in free_list_add_bidx()
89 		set_next_free_chunk(h, first, c);  in free_list_add_bidx()
90 		set_prev_free_chunk(h, second, c);  in free_list_add_bidx()
94 	h->free_bytes += chunksz_to_bytes(h, chunk_size(h, c));  in free_list_add_bidx()
98 static void free_list_add(struct z_heap *h, chunkid_t c)  in free_list_add()  argument
100 	if (!solo_free_header(h, c)) {  in free_list_add()
101 		int bidx = bucket_idx(h, chunk_size(h, c));  in free_list_add()
102 		free_list_add_bidx(h, c, bidx);  in free_list_add()
109 static void split_chunks(struct z_heap *h, chunkid_t lc, chunkid_t rc)  in split_chunks()  argument
112 	CHECK(rc - lc < chunk_size(h, lc));  in split_chunks()
114 	chunksz_t sz0 = chunk_size(h, lc);  in split_chunks()
118 	set_chunk_size(h, lc, lsz);  in split_chunks()
119 	set_chunk_size(h, rc, rsz);  in split_chunks()
120 	set_left_chunk_size(h, rc, lsz);  in split_chunks()
121 	set_left_chunk_size(h, right_chunk(h, rc), rsz);  in split_chunks()
125 static void merge_chunks(struct z_heap *h, chunkid_t lc, chunkid_t rc)  in merge_chunks()  argument
127 	chunksz_t newsz = chunk_size(h, lc) + chunk_size(h, rc);  in merge_chunks()
129 	set_chunk_size(h, lc, newsz);  in merge_chunks()
130 	set_left_chunk_size(h, right_chunk(h, rc), newsz);  in merge_chunks()
133 static void free_chunk(struct z_heap *h, chunkid_t c)  in free_chunk()  argument
136 	if (!chunk_used(h, right_chunk(h, c))) {  in free_chunk()
137 		free_list_remove(h, right_chunk(h, c));  in free_chunk()
138 		merge_chunks(h, c, right_chunk(h, c));  in free_chunk()
142 	if (!chunk_used(h, left_chunk(h, c))) {  in free_chunk()
143 		free_list_remove(h, left_chunk(h, c));  in free_chunk()
144 		merge_chunks(h, left_chunk(h, c), c);  in free_chunk()
145 		c = left_chunk(h, c);  in free_chunk()
148 	free_list_add(h, c);  in free_chunk()
157 static chunkid_t mem_to_chunkid(struct z_heap *h, void *p)  in mem_to_chunkid()  argument
159 	uint8_t *mem = p, *base = (uint8_t *)chunk_buf(h);  in mem_to_chunkid()
160 	return (mem - chunk_header_bytes(h) - base) / CHUNK_UNIT;  in mem_to_chunkid()
168 	struct z_heap *h = heap->heap;  in sys_heap_free()  local
169 	chunkid_t c = mem_to_chunkid(h, mem);  in sys_heap_free()
175 	__ASSERT(chunk_used(h, c),  in sys_heap_free()
183 	__ASSERT(left_chunk(h, right_chunk(h, c)) == c,  in sys_heap_free()
187 	set_chunk_used(h, c, false);  in sys_heap_free()
189 	h->allocated_bytes -= chunksz_to_bytes(h, chunk_size(h, c));  in sys_heap_free()
194 				  chunksz_to_bytes(h, chunk_size(h, c)));  in sys_heap_free()
197 	free_chunk(h, c);  in sys_heap_free()
202 	struct z_heap *h = heap->heap;  in sys_heap_usable_size()  local
203 	chunkid_t c = mem_to_chunkid(h, mem);  in sys_heap_usable_size()
205 	size_t chunk_base = (size_t)&chunk_buf(h)[c];  in sys_heap_usable_size()
206 	size_t chunk_sz = chunk_size(h, c) * CHUNK_UNIT;  in sys_heap_usable_size()
211 static chunkid_t alloc_chunk(struct z_heap *h, chunksz_t sz)  in alloc_chunk()  argument
213 	int bi = bucket_idx(h, sz);  in alloc_chunk()
214 	struct z_heap_bucket *b = &h->buckets[bi];  in alloc_chunk()
216 	CHECK(bi <= bucket_idx(h, h->end_chunk));  in alloc_chunk()
237 			if (chunk_size(h, c) >= sz) {  in alloc_chunk()
238 				free_list_remove_bidx(h, c, bi);  in alloc_chunk()
241 			b->next = next_free_chunk(h, c);  in alloc_chunk()
249 	uint32_t bmask = h->avail_buckets & ~BIT_MASK(bi + 1);  in alloc_chunk()
253 		chunkid_t c = h->buckets[minbucket].next;  in alloc_chunk()
255 		free_list_remove_bidx(h, c, minbucket);  in alloc_chunk()
256 		CHECK(chunk_size(h, c) >= sz);  in alloc_chunk()
265 	struct z_heap *h = heap->heap;  in sys_heap_alloc()  local
268 	if (bytes == 0U || size_too_big(h, bytes)) {  in sys_heap_alloc()
272 	chunksz_t chunk_sz = bytes_to_chunksz(h, bytes);  in sys_heap_alloc()
273 	chunkid_t c = alloc_chunk(h, chunk_sz);  in sys_heap_alloc()
279 	if (chunk_size(h, c) > chunk_sz) {  in sys_heap_alloc()
280 		split_chunks(h, c, c + chunk_sz);  in sys_heap_alloc()
281 		free_list_add(h, c + chunk_sz);  in sys_heap_alloc()
284 	set_chunk_used(h, c, true);  in sys_heap_alloc()
286 	mem = chunk_mem(h, c);  in sys_heap_alloc()
289 	increase_allocated_bytes(h, chunksz_to_bytes(h, chunk_size(h, c)));  in sys_heap_alloc()
294 				   chunksz_to_bytes(h, chunk_size(h, c)));  in sys_heap_alloc()
303 	struct z_heap *h = heap->heap;  in sys_heap_aligned_alloc()  local
316 		gap = MIN(rew, chunk_header_bytes(h));  in sys_heap_aligned_alloc()
318 		if (align <= chunk_header_bytes(h)) {  in sys_heap_aligned_alloc()
322 		gap = chunk_header_bytes(h);  in sys_heap_aligned_alloc()
326 	if (bytes == 0 || size_too_big(h, bytes)) {  in sys_heap_aligned_alloc()
335 	chunksz_t padded_sz = bytes_to_chunksz(h, bytes + align - gap);  in sys_heap_aligned_alloc()
336 	chunkid_t c0 = alloc_chunk(h, padded_sz);  in sys_heap_aligned_alloc()
341 	uint8_t *mem = chunk_mem(h, c0);  in sys_heap_aligned_alloc()
348 	chunkid_t c = mem_to_chunkid(h, mem);  in sys_heap_aligned_alloc()
349 	chunkid_t c_end = end - chunk_buf(h);  in sys_heap_aligned_alloc()
354 		split_chunks(h, c0, c);  in sys_heap_aligned_alloc()
355 		free_list_add(h, c0);  in sys_heap_aligned_alloc()
359 	if (right_chunk(h, c) > c_end) {  in sys_heap_aligned_alloc()
360 		split_chunks(h, c, c_end);  in sys_heap_aligned_alloc()
361 		free_list_add(h, c_end);  in sys_heap_aligned_alloc()
364 	set_chunk_used(h, c, true);  in sys_heap_aligned_alloc()
367 	increase_allocated_bytes(h, chunksz_to_bytes(h, chunk_size(h, c)));  in sys_heap_aligned_alloc()
372 				   chunksz_to_bytes(h, chunk_size(h, c)));  in sys_heap_aligned_alloc()
382 	struct z_heap *h = heap->heap;  in sys_heap_aligned_realloc()  local
395 	if (size_too_big(h, bytes)) {  in sys_heap_aligned_realloc()
399 	chunkid_t c = mem_to_chunkid(h, ptr);  in sys_heap_aligned_realloc()
400 	chunkid_t rc = right_chunk(h, c);  in sys_heap_aligned_realloc()
401 	size_t align_gap = (uint8_t *)ptr - (uint8_t *)chunk_mem(h, c);  in sys_heap_aligned_realloc()
402 	chunksz_t chunks_need = bytes_to_chunksz(h, bytes + align_gap);  in sys_heap_aligned_realloc()
406 	} else if (chunk_size(h, c) == chunks_need) {  in sys_heap_aligned_realloc()
409 	} else if (chunk_size(h, c) > chunks_need) {  in sys_heap_aligned_realloc()
412 		size_t bytes_freed = chunksz_to_bytes(h, chunk_size(h, c));  in sys_heap_aligned_realloc()
416 		h->allocated_bytes -=  in sys_heap_aligned_realloc()
417 			(chunk_size(h, c) - chunks_need) * CHUNK_UNIT;  in sys_heap_aligned_realloc()
420 		split_chunks(h, c, c + chunks_need);  in sys_heap_aligned_realloc()
421 		set_chunk_used(h, c, true);  in sys_heap_aligned_realloc()
422 		free_chunk(h, c + chunks_need);  in sys_heap_aligned_realloc()
426 					   chunksz_to_bytes(h, chunk_size(h, c)));  in sys_heap_aligned_realloc()
432 	} else if (!chunk_used(h, rc) &&  in sys_heap_aligned_realloc()
433 		   (chunk_size(h, c) + chunk_size(h, rc) >= chunks_need)) {  in sys_heap_aligned_realloc()
435 		chunksz_t split_size = chunks_need - chunk_size(h, c);  in sys_heap_aligned_realloc()
438 		size_t bytes_freed = chunksz_to_bytes(h, chunk_size(h, c));  in sys_heap_aligned_realloc()
442 		increase_allocated_bytes(h, split_size * CHUNK_UNIT);  in sys_heap_aligned_realloc()
445 		free_list_remove(h, rc);  in sys_heap_aligned_realloc()
447 		if (split_size < chunk_size(h, rc)) {  in sys_heap_aligned_realloc()
448 			split_chunks(h, rc, rc + split_size);  in sys_heap_aligned_realloc()
449 			free_list_add(h, rc + split_size);  in sys_heap_aligned_realloc()
452 		merge_chunks(h, c, rc);  in sys_heap_aligned_realloc()
453 		set_chunk_used(h, c, true);  in sys_heap_aligned_realloc()
457 					   chunksz_to_bytes(h, chunk_size(h, c)));  in sys_heap_aligned_realloc()
477 		size_t prev_size = chunksz_to_bytes(h, chunk_size(h, c)) - align_gap;  in sys_heap_aligned_realloc()
509 	struct z_heap *h = (struct z_heap *)addr;  in sys_heap_init()  local
510 	heap->heap = h;  in sys_heap_init()
511 	h->end_chunk = heap_sz;  in sys_heap_init()
512 	h->avail_buckets = 0;  in sys_heap_init()
515 	h->free_bytes = 0;  in sys_heap_init()
516 	h->allocated_bytes = 0;  in sys_heap_init()
517 	h->max_allocated_bytes = 0;  in sys_heap_init()
520 	int nb_buckets = bucket_idx(h, heap_sz) + 1;  in sys_heap_init()
524 	__ASSERT(chunk0_size + min_chunk_size(h) <= heap_sz, "heap size is too small");  in sys_heap_init()
527 		h->buckets[i].next = 0;  in sys_heap_init()
531 	set_chunk_size(h, 0, chunk0_size);  in sys_heap_init()
532 	set_left_chunk_size(h, 0, 0);  in sys_heap_init()
533 	set_chunk_used(h, 0, true);  in sys_heap_init()
536 	set_chunk_size(h, chunk0_size, heap_sz - chunk0_size);  in sys_heap_init()
537 	set_left_chunk_size(h, chunk0_size, chunk0_size);  in sys_heap_init()
540 	set_chunk_size(h, heap_sz, 0);  in sys_heap_init()
541 	set_left_chunk_size(h, heap_sz, heap_sz - chunk0_size);  in sys_heap_init()
542 	set_chunk_used(h, heap_sz, true);  in sys_heap_init()
544 	free_list_add(h, chunk0_size);  in sys_heap_init()