+/rtos

git clone https://git.julia.blue/+/rtos

Vivek MalneediMerge branch 'master' of github.com:EE445M-Sp20/lab-6-vm22967_jbr2558021d2d4

master
6.1 KiB220 linesraw
1#include "heap.h"
2#include "OS.h"
3#include "interpreter.h"
4#include "io.h"
5#include "printf.h"
6#include "std.h"
7#include <stdint.h>
8
9const uint32_t MIN_ALLOCATION = 4;
10
11extern uint32_t _heap;
12extern uint32_t _eheap;
13
14static HeapNode* head;
15static Sema4 heap_mutex;
16
17static uint16_t total_heap_size;
18static uint16_t free_space;
19static uint16_t used_space;
20
21void heap_init(void) {
22    total_heap_size = (uint32_t)&_eheap - (uint32_t)&_heap;
23    free_space = total_heap_size - sizeof(HeapNode);
24    used_space = 0;
25    head = (HeapNode*)&_heap;
26    *head = (HeapNode){0, free_space};
27    OS_InitSemaphore(&heap_mutex, 0);
28}
29
30HeapNode* heap_node_from_alloc(void* alloc) {
31    return (HeapNode*)((uint8_t*)alloc - sizeof(HeapNode));
32}
33
34static HeapNode* heap_next_node(HeapNode* current) {
35    return (HeapNode*)((uint8_t*)current + current->size + sizeof(HeapNode));
36}
37
38static bool try_splitting_block(HeapNode* node, uint32_t size) {
39    if (node->size < size + sizeof(HeapNode) + MIN_ALLOCATION) {
40        return false;
41    }
42    HeapNode* new = (HeapNode*)(((uint8_t*)node) + sizeof(HeapNode) +
43                                max(size, MIN_ALLOCATION));
44    new->next = node->next;
45    new->size = node->size - sizeof(HeapNode) - size;
46    node->size = max(size, MIN_ALLOCATION);
47    node->next = new;
48    free_space -= sizeof(HeapNode);
49    return true;
50}
51
52// attempt to merge two heap nodes to reduce fragmentation
53// 'a' should be the node at a lower memory address
54static bool try_combining(HeapNode* a, HeapNode* b) {
55    if (heap_next_node(a) == b) {
56        a->size += b->size + sizeof(HeapNode);
57        free_space += sizeof(HeapNode);
58        return true;
59    }
60    return false;
61}
62
63static uint32_t align4(uint32_t n) {
64    return n += n % 4 ? 4 - n % 4 : 0;
65}
66
67void* _malloc(uint32_t size) {
68    size = align4(size);
69    HeapNode* prev;
70    HeapNode* current = head;
71    while (current) {
72        if (current->size >= size) {
73            try_splitting_block(current, size);
74            if (current == head) {
75                head = current->next;
76            } else {
77                prev->next = current->next;
78            }
79            used_space += current->size;
80            free_space -= current->size;
81            return ((uint8_t*)current) + sizeof(HeapNode);
82        }
83        prev = current;
84        current = current->next;
85    }
86    return 0;
87}
88
89void _free(void* allocation) {
90    if (!allocation) {
91        __asm("BKPT"); // you've fucked up
92    }
93    HeapNode* this = heap_node_from_alloc(allocation);
94    // move along the linked list until prev/current bracket 'this' in terms
95    // of their location
96    HeapNode* current = head;
97    HeapNode* prev;
98    while (current && this > current) {
99        prev = current, current = current->next;
100    }
101    used_space -= this->size;
102    free_space += this->size;
103    // attempt to merge this block with the adjacent ones before and after it
104    if (current == head) {
105        head = this;
106    } else {
107        if (try_combining(prev, this)) {
108            this = prev;
109        } else {
110            prev->next = this;
111        }
112    }
113    this->next = try_combining(this, current) ? current->next : current;
114}
115
116void* _realloc(void* allocation, uint32_t size) {
117    if (!allocation) {
118        return malloc(size);
119    }
120    size = align4(size);
121    HeapNode* this = heap_node_from_alloc(allocation);
122    uint16_t original_size = this->size;
123    // if shrinking, try splitting the block to return unused space
124    if (this->size > size) {
125        bool temp = try_splitting_block(this, size);
126        if (temp) {
127            free_space += sizeof(HeapNode);
128            used_space -= sizeof(HeapNode);
129            _free((uint8_t*)heap_next_node(this) + sizeof(HeapNode));
130        }
131        return allocation;
132    }
133    // otherwise, grow into adjacent block if possible to avoid copying
134    HeapNode* current = head;
135    while (current && this > current) { current = current->next; }
136    if (try_combining(this, current)) {
137        this->next = current->next;
138        try_splitting_block(this, size);
139        uint16_t additional_space = this->size - original_size;
140        used_space += additional_space;
141        free_space -= additional_space;
142        if (current == head) {
143            head = this->next;
144        }
145        return allocation;
146    }
147    // if neither works, grab a new allocation, copy, and free the old
148    void* new = _malloc(size);
149    if (new) {
150        memcpy(new, allocation, this->size);
151        _free(allocation);
152    }
153    return new;
154}
155
156// TODO: check whether critical sections are required or if the mutex is fine
157void* malloc(uint32_t size) {
158    OS_Wait(&heap_mutex);
159    void* temp = _malloc(size);
160    OS_Signal(&heap_mutex);
161    return temp;
162}
163
164void free(void* allocation) {
165    OS_Wait(&heap_mutex);
166    _free(allocation);
167    OS_Signal(&heap_mutex);
168}
169
170void* realloc(void* allocation, uint32_t size) {
171    OS_Wait(&heap_mutex);
172    void* temp = _realloc(allocation, size);
173    OS_Signal(&heap_mutex);
174    return temp;
175}
176
177void* calloc(uint32_t size) {
178    uint8_t* temp = (uint8_t*)malloc(size);
179    if (temp) {
180        memset(temp, 0, size);
181    }
182    return temp;
183}
184
185uint32_t heap_get_space(void) {
186    return free_space;
187}
188
189uint32_t heap_get_max(void) {
190    uint16_t largest = 0;
191    OS_Wait(&heap_mutex);
192    HeapNode* current = head;
193    while (current) {
194        largest = max(largest, current->size);
195        current = current->next;
196    }
197    OS_Signal(&heap_mutex);
198    return largest;
199}
200
201const int graph_width = 80;
202void heap_stats(void) {
203    printf("Total bytes available: %d\n\r", total_heap_size);
204    printf("Bytes in use: " RED "%d" NORMAL "\n\r", used_space);
205    printf("Bytes still available: " CYAN "%d" NORMAL "\n\r", free_space);
206    uint16_t wasted = total_heap_size - used_space - free_space;
207    printf("Bytes wasted: " YELLOW "%d" NORMAL "\n\r", wasted);
208    printf("[" RED);
209    for (int i = 0; i < graph_width; ++i) {
210        if (used_space * graph_width / total_heap_size == i) {
211            printf(YELLOW);
212        }
213        if ((used_space + wasted) * graph_width / total_heap_size == i) {
214            printf(CYAN);
215        }
216        putchar('#');
217    }
218    printf(NORMAL "]\n\rLargest possible allocation: %d bytes.\n\r",
219           heap_get_max());
220}