Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(683)

Side by Side Diff: platforms/stm/disco_dartino/src/cmpctmalloc.c

Issue 1659163007: Rename fletch -> dartino (Closed) Base URL: https://github.com/dartino/sdk.git@master
Patch Set: address comments Created 4 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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
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
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
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
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
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 }
OLDNEW
« no previous file with comments | « platforms/stm/disco_dartino/src/cmpctmalloc.h ('k') | platforms/stm/disco_dartino/src/cmpctmalloc_test.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698