OLD | NEW |
1 // Copyright (c) 2016, the Dartino project authors. Please see the AUTHORS file | 1 // Copyright (c) 2016, the Dartino project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE.md file. | 3 // BSD-style license that can be found in the LICENSE.md file. |
4 | 4 |
5 // This code is ported from the LK repository. To keep the code in | 5 // This code is ported from the LK repository. To keep the code in |
6 // sync the define FLETCH_TARGET_OS_LK provides the code from the LK | 6 // sync the define DARTINO_TARGET_OS_LK provides the code from the LK |
7 // repository. Without the define FLETCH_TARGET_OS_LK this code will | 7 // repository. Without the define DARTINO_TARGET_OS_LK this code will |
8 // build and link for the disco_fletch project. | 8 // build and link for the disco_dartino project. |
9 #ifdef FLETCH_TARGET_OS_LK | 9 #ifdef DARTINO_TARGET_OS_LK |
10 | 10 |
11 #include <debug.h> | 11 #include <debug.h> |
12 #include <trace.h> | 12 #include <trace.h> |
13 #include <assert.h> | 13 #include <assert.h> |
14 #include <stdio.h> | 14 #include <stdio.h> |
15 #include <stdlib.h> | 15 #include <stdlib.h> |
16 #include <string.h> | 16 #include <string.h> |
17 #include <kernel/thread.h> | 17 #include <kernel/thread.h> |
18 #include <kernel/mutex.h> | 18 #include <kernel/mutex.h> |
19 #include <kernel/spinlock.h> | 19 #include <kernel/spinlock.h> |
20 #include <lib/cmpctmalloc.h> | 20 #include <lib/cmpctmalloc.h> |
21 #include <lib/heap.h> | 21 #include <lib/heap.h> |
22 #include <lib/page_alloc.h> | 22 #include <lib/page_alloc.h> |
23 | 23 |
24 #else // FLETCH_TARGET_OS_LK | 24 #else // DARTINO_TARGET_OS_LK |
25 | 25 |
26 #include "platforms/stm/disco_fletch/src/cmpctmalloc.h" | 26 #include "platforms/stm/disco_dartino/src/cmpctmalloc.h" |
27 | 27 |
28 #include <inttypes.h> | 28 #include <inttypes.h> |
29 #include <stdbool.h> | 29 #include <stdbool.h> |
30 #include <stddef.h> | 30 #include <stddef.h> |
31 #include <stdio.h> | 31 #include <stdio.h> |
32 #include <stdlib.h> | 32 #include <stdlib.h> |
33 #include <string.h> | 33 #include <string.h> |
34 #include <unistd.h> | 34 #include <unistd.h> |
35 | 35 |
36 #include "platforms/stm/disco_fletch/src/globals.h" | 36 #include "platforms/stm/disco_dartino/src/globals.h" |
37 | 37 |
38 void* page_alloc(size_t pages); | 38 void* page_alloc(size_t pages); |
39 void page_free(void* start, size_t pages); | 39 void page_free(void* start, size_t pages); |
40 | 40 |
41 typedef uintptr_t addr_t; | 41 typedef uintptr_t addr_t; |
42 typedef uintptr_t vaddr_t; | 42 typedef uintptr_t vaddr_t; |
43 | 43 |
44 #define LTRACEF(...) | 44 #define LTRACEF(...) |
45 #define LTRACE_ENTRY | 45 #define LTRACE_ENTRY |
46 #define DEBUG_ASSERT ASSERT | 46 #define DEBUG_ASSERT ASSERT |
47 #define ASSERT(condition) \ | 47 #define ASSERT(condition) \ |
48 while (false && (condition)) { \ | 48 while (false && (condition)) { \ |
49 } | 49 } |
50 #define STATIC_ASSERT(condition) | 50 #define STATIC_ASSERT(condition) |
51 #define dprintf(...) fprintf(__VA_ARGS__) | 51 #define dprintf(...) fprintf(__VA_ARGS__) |
52 #define INFO stdout | 52 #define INFO stdout |
53 | 53 |
54 #endif // FLETCH_TARGET_OS_LK | 54 #endif // DARTINO_TARGET_OS_LK |
55 | 55 |
56 // Malloc implementation tuned for space. | 56 // Malloc implementation tuned for space. |
57 // | 57 // |
58 // Allocation strategy takes place with a global mutex. Freelist entries are | 58 // Allocation strategy takes place with a global mutex. Freelist entries are |
59 // kept in linked lists with 8 different sizes per binary order of magnitude | 59 // kept in linked lists with 8 different sizes per binary order of magnitude |
60 // and the header size is two words with eager coalescing on free. | 60 // and the header size is two words with eager coalescing on free. |
61 | 61 |
62 #ifdef DEBUG | 62 #ifdef DEBUG |
63 #define CMPCT_DEBUG | 63 #define CMPCT_DEBUG |
64 #endif | 64 #endif |
65 | 65 |
66 #ifdef FLETCH_TARGET_OS_LK | 66 #ifdef DARTINO_TARGET_OS_LK |
67 #define LOCAL_TRACE 0 | 67 #define LOCAL_TRACE 0 |
68 #endif | 68 #endif |
69 | 69 |
70 #define ALLOC_FILL 0x99 | 70 #define ALLOC_FILL 0x99 |
71 #define FREE_FILL 0x77 | 71 #define FREE_FILL 0x77 |
72 #define PADDING_FILL 0x55 | 72 #define PADDING_FILL 0x55 |
73 | 73 |
74 #ifdef FLETCH_TARGET_OS_LK | 74 #ifdef DARTINO_TARGET_OS_LK |
75 #if WITH_KERNEL_VM && !defined(HEAP_GROW_SIZE) | 75 #if WITH_KERNEL_VM && !defined(HEAP_GROW_SIZE) |
76 #define HEAP_GROW_SIZE (1 * 1024 * 1024) /* Grow aggressively */ | 76 #define HEAP_GROW_SIZE (1 * 1024 * 1024) /* Grow aggressively */ |
77 #elif !defined(HEAP_GROW_SIZE) | 77 #elif !defined(HEAP_GROW_SIZE) |
78 #define HEAP_GROW_SIZE (4 * 1024) /* Grow less aggressively */ | 78 #define HEAP_GROW_SIZE (4 * 1024) /* Grow less aggressively */ |
79 #endif | 79 #endif |
80 #else | 80 #else |
81 #define HEAP_GROW_SIZE (4 * 1024) /* Grow less aggressively */ | 81 #define HEAP_GROW_SIZE (4 * 1024) /* Grow less aggressively */ |
82 #endif | 82 #endif |
83 | 83 |
84 STATIC_ASSERT(IS_PAGE_ALIGNED(HEAP_GROW_SIZE)); | 84 STATIC_ASSERT(IS_PAGE_ALIGNED(HEAP_GROW_SIZE)); |
(...skipping 23 matching lines...) Expand all Loading... |
108 | 108 |
109 typedef struct free_struct { | 109 typedef struct free_struct { |
110 header_t header; | 110 header_t header; |
111 struct free_struct *next; | 111 struct free_struct *next; |
112 struct free_struct *prev; | 112 struct free_struct *prev; |
113 } free_t; | 113 } free_t; |
114 | 114 |
115 struct heap { | 115 struct heap { |
116 size_t size; | 116 size_t size; |
117 size_t remaining; | 117 size_t remaining; |
118 #ifdef FLETCH_TARGET_OS_LK | 118 #ifdef DARTINO_TARGET_OS_LK |
119 mutex_t lock; | 119 mutex_t lock; |
120 #endif | 120 #endif |
121 free_t *free_lists[NUMBER_OF_BUCKETS]; | 121 free_t *free_lists[NUMBER_OF_BUCKETS]; |
122 // We have some 32 bit words that tell us whether there is an entry in the | 122 // We have some 32 bit words that tell us whether there is an entry in the |
123 // freelist. | 123 // freelist. |
124 #define BUCKET_WORDS (((NUMBER_OF_BUCKETS) + 31) >> 5) | 124 #define BUCKET_WORDS (((NUMBER_OF_BUCKETS) + 31) >> 5) |
125 uint32_t free_list_bits[BUCKET_WORDS]; | 125 uint32_t free_list_bits[BUCKET_WORDS]; |
126 }; | 126 }; |
127 | 127 |
128 // Heap static vars. | 128 // Heap static vars. |
129 static struct heap theheap; | 129 static struct heap theheap; |
130 | 130 |
131 static ssize_t heap_grow(size_t len, free_t **bucket); | 131 static ssize_t heap_grow(size_t len, free_t **bucket); |
132 | 132 |
133 static void lock(void) | 133 static void lock(void) |
134 { | 134 { |
135 #ifdef FLETCH_TARGET_OS_LK | 135 #ifdef DARTINO_TARGET_OS_LK |
136 mutex_acquire(&theheap.lock); | 136 mutex_acquire(&theheap.lock); |
137 #endif | 137 #endif |
138 } | 138 } |
139 | 139 |
140 static void unlock(void) | 140 static void unlock(void) |
141 { | 141 { |
142 #ifdef FLETCH_TARGET_OS_LK | 142 #ifdef DARTINO_TARGET_OS_LK |
143 mutex_release(&theheap.lock); | 143 mutex_release(&theheap.lock); |
144 #endif | 144 #endif |
145 } | 145 } |
146 | 146 |
147 static void dump_free(header_t *header) | 147 static void dump_free(header_t *header) |
148 { | 148 { |
149 dprintf(INFO, "\t\tbase %p, end 0x%lx, len 0x%zx\n", header, (vaddr_t)header
+ header->size, header->size); | 149 dprintf(INFO, "\t\tbase %p, end 0x%lx, len 0x%zx\n", header, (vaddr_t)header
+ header->size, header->size); |
150 } | 150 } |
151 | 151 |
152 void cmpct_dump(void) | 152 void cmpct_dump(void) |
(...skipping 230 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
383 | 383 |
384 static void TestTrimFreeHelper(char *block) | 384 static void TestTrimFreeHelper(char *block) |
385 { | 385 { |
386 while (block) { | 386 while (block) { |
387 char *next_block = *(char **)block; | 387 char *next_block = *(char **)block; |
388 cmpct_free(block); | 388 cmpct_free(block); |
389 block = next_block; | 389 block = next_block; |
390 } | 390 } |
391 } | 391 } |
392 | 392 |
393 #ifdef FLETCH_TARGET_OS_LK | 393 #ifdef DARTINO_TARGET_OS_LK |
394 static void cmpct_test_trim(void) | 394 static void cmpct_test_trim(void) |
395 #else | 395 #else |
396 void cmpct_test_trim(void) | 396 void cmpct_test_trim(void) |
397 #endif | 397 #endif |
398 { | 398 { |
399 WasteFreeMemory(); | 399 WasteFreeMemory(); |
400 | 400 |
401 size_t test_sizes[200]; | 401 size_t test_sizes[200]; |
402 int sizes = 0; | 402 int sizes = 0; |
403 | 403 |
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
486 | 486 |
487 // We should have < 1 page on either side of the big allocation. | 487 // We should have < 1 page on either side of the big allocation. |
488 ASSERT(remaining < PAGE_SIZE * 2); | 488 ASSERT(remaining < PAGE_SIZE * 2); |
489 | 489 |
490 TestTrimFreeHelper(big_bit_in_the_middle); | 490 TestTrimFreeHelper(big_bit_in_the_middle); |
491 } | 491 } |
492 } | 492 } |
493 } | 493 } |
494 | 494 |
495 | 495 |
496 #ifdef FLETCH_TARGET_OS_LK | 496 #ifdef DARTINO_TARGET_OS_LK |
497 static void cmpct_test_buckets(void) | 497 static void cmpct_test_buckets(void) |
498 #else | 498 #else |
499 void cmpct_test_buckets(void) | 499 void cmpct_test_buckets(void) |
500 #endif | 500 #endif |
501 { | 501 { |
502 size_t rounded; | 502 size_t rounded; |
503 unsigned bucket; | 503 unsigned bucket; |
504 // Check for the 8-spaced buckets up to 128. | 504 // Check for the 8-spaced buckets up to 128. |
505 for (unsigned i = 1; i <= 128; i++) { | 505 for (unsigned i = 1; i <= 128; i++) { |
506 // Round up when allocating. | 506 // Round up when allocating. |
(...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
568 | 568 |
569 cmpct_free(allocated); | 569 cmpct_free(allocated); |
570 void *allocated3 = cmpct_alloc(size); | 570 void *allocated3 = cmpct_alloc(size); |
571 // To avoid churn and fragmentation we would want to get the newly freed | 571 // To avoid churn and fragmentation we would want to get the newly freed |
572 // memory back again when we allocate the same size shortly after. | 572 // memory back again when we allocate the same size shortly after. |
573 ASSERT(allocated3 == allocated); | 573 ASSERT(allocated3 == allocated); |
574 cmpct_free(allocated2); | 574 cmpct_free(allocated2); |
575 cmpct_free(allocated3); | 575 cmpct_free(allocated3); |
576 } | 576 } |
577 | 577 |
578 #ifdef FLETCH_TARGET_OS_LK | 578 #ifdef DARTINO_TARGET_OS_LK |
579 static void cmpct_test_get_back_newly_freed(void) | 579 static void cmpct_test_get_back_newly_freed(void) |
580 #else | 580 #else |
581 void cmpct_test_get_back_newly_freed(void) | 581 void cmpct_test_get_back_newly_freed(void) |
582 #endif | 582 #endif |
583 { | 583 { |
584 size_t increment = 16; | 584 size_t increment = 16; |
585 for (size_t i = 128; i <= 0x8000000; i *= 2, increment *= 2) { | 585 for (size_t i = 128; i <= 0x8000000; i *= 2, increment *= 2) { |
586 for (size_t j = i; j < i * 2; j += increment) { | 586 for (size_t j = i; j < i * 2; j += increment) { |
587 cmpct_test_get_back_newly_freed_helper(i - 8); | 587 cmpct_test_get_back_newly_freed_helper(i - 8); |
588 cmpct_test_get_back_newly_freed_helper(i); | 588 cmpct_test_get_back_newly_freed_helper(i); |
589 cmpct_test_get_back_newly_freed_helper(i + 1); | 589 cmpct_test_get_back_newly_freed_helper(i + 1); |
590 } | 590 } |
591 } | 591 } |
592 for (size_t i = 1024; i <= 2048; i++) { | 592 for (size_t i = 1024; i <= 2048; i++) { |
593 cmpct_test_get_back_newly_freed_helper(i); | 593 cmpct_test_get_back_newly_freed_helper(i); |
594 } | 594 } |
595 } | 595 } |
596 | 596 |
597 #ifdef FLETCH_TARGET_OS_LK | 597 #ifdef DARTINO_TARGET_OS_LK |
598 static void cmpct_test_return_to_os(void) | 598 static void cmpct_test_return_to_os(void) |
599 #else | 599 #else |
600 void cmpct_test_return_to_os(void) | 600 void cmpct_test_return_to_os(void) |
601 #endif | 601 #endif |
602 { | 602 { |
603 cmpct_trim(); | 603 cmpct_trim(); |
604 size_t remaining = theheap.remaining; | 604 size_t remaining = theheap.remaining; |
605 // This goes in a new OS allocation since the trim above removed any free | 605 // This goes in a new OS allocation since the trim above removed any free |
606 // area big enough to contain it. | 606 // area big enough to contain it. |
607 void *a = cmpct_alloc(5000); | 607 void *a = cmpct_alloc(5000); |
(...skipping 267 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
875 LTRACEF("growing heap by 0x%zx bytes, new ptr %p\n", size, ptr); | 875 LTRACEF("growing heap by 0x%zx bytes, new ptr %p\n", size, ptr); |
876 add_to_heap(ptr, size, bucket); | 876 add_to_heap(ptr, size, bucket); |
877 return size; | 877 return size; |
878 } | 878 } |
879 | 879 |
880 void cmpct_init(void) | 880 void cmpct_init(void) |
881 { | 881 { |
882 LTRACE_ENTRY; | 882 LTRACE_ENTRY; |
883 | 883 |
884 // Create a mutex. | 884 // Create a mutex. |
885 #ifdef FLETCH_TARGET_OS_LK | 885 #ifdef DARTINO_TARGET_OS_LK |
886 mutex_init(&theheap.lock); | 886 mutex_init(&theheap.lock); |
887 #endif | 887 #endif |
888 | 888 |
889 // Initialize the free list. | 889 // Initialize the free list. |
890 for (int i = 0; i < NUMBER_OF_BUCKETS; i++) { | 890 for (int i = 0; i < NUMBER_OF_BUCKETS; i++) { |
891 theheap.free_lists[i] = NULL; | 891 theheap.free_lists[i] = NULL; |
892 } | 892 } |
893 for (int i = 0; i < BUCKET_WORDS; i++) { | 893 for (int i = 0; i < BUCKET_WORDS; i++) { |
894 theheap.free_list_bits[i] = 0; | 894 theheap.free_list_bits[i] = 0; |
895 } | 895 } |
896 | 896 |
897 size_t initial_alloc = HEAP_GROW_SIZE - 2 * sizeof(header_t); | 897 size_t initial_alloc = HEAP_GROW_SIZE - 2 * sizeof(header_t); |
898 | 898 |
899 theheap.remaining = 0; | 899 theheap.remaining = 0; |
900 | 900 |
901 heap_grow(initial_alloc, NULL); | 901 heap_grow(initial_alloc, NULL); |
902 } | 902 } |
OLD | NEW |