1 /*
2 * Part of Scheme 48 1.9. See file COPYING for notices and license.
3 *
4 * Authors: David Frese
5 */
6
7 #include <stdlib.h>
8 #include <assert.h>
9 #include "utils.h"
10 #include "page_constants.h"
11 #include "page_alloc.h"
12 #include "memory.h"
13
14 /* A doubly linked list of free areas. (Not to be confused with Areas!) */
15
16 typedef struct FreeArea {
17 s48_address start; /* first page */
18 unsigned long size; /* number of pages */
19 struct FreeArea* next;
20 struct FreeArea* prev;
21 } FreeArea;
22
23 static FreeArea* freelist;
24
25 static unsigned long free_area_count = 0;
26 static unsigned long free_page_count = 0;
27
make_free_area(s48_address start,unsigned long size)28 static FreeArea* make_free_area(s48_address start, unsigned long size) {
29 FreeArea* new = (FreeArea*)malloc(sizeof(FreeArea));
30 if (new == NULL) s48_gc_error("make_free_area: out of memory");
31 new->start = start;
32 new->size = size;
33 new->next = NULL;
34 new->prev = NULL;
35 free_area_count = free_area_count + 1;
36 return new;
37 }
38
deallocate_free_area(FreeArea * area)39 inline static void deallocate_free_area(FreeArea* area) {
40 free(area);
41 free_area_count = free_area_count - 1;
42 }
43
connect(FreeArea * first,FreeArea * second)44 inline static void connect(FreeArea* first, FreeArea* second) {
45 second->prev = first;
46 first->next = second;
47 }
48
address_after_free_area(FreeArea * area)49 inline static s48_address address_after_free_area(FreeArea* area) {
50 /* Presumed safe because AREA->SIZE is the size in pages of an
51 allocated block of memory. */
52 return area->start + PAGES_TO_BYTES_I_KNOW_THIS_CAN_OVERFLOW(area->size);
53 }
54
adjust_free_area(FreeArea * area,unsigned long pages)55 inline static void adjust_free_area(FreeArea* area, unsigned long pages) {
56 area->size = area->size + pages;
57 }
58
s48_initialize_page_allocation()59 void s48_initialize_page_allocation() {
60 freelist = make_free_area(0, 0);
61 connect(freelist, freelist);
62 free_area_count = 0;
63 free_page_count = 0;
64 }
65
check_freelist()66 static void check_freelist() {
67 FreeArea* area = freelist->next;
68 unsigned int areas = 0, pages = 0;
69 while (1) {
70 s48_address end = address_after_free_area(area);
71 if (area == freelist) {
72 /* now we've seen the whole list */
73 if ((areas != free_area_count) || (pages != free_page_count))
74 s48_gc_error("bad page freelist (1)");
75 else return; /* the list is OK */
76 } else if ((end < area->start) ||
77 ((freelist != area->prev) &&
78 (area->start < address_after_free_area(area->prev)))) {
79 s48_gc_error("bad page freelist (2)");
80 } else {
81 char dummy; unsigned long addr;
82 /* check if area has correct addresses */
83 addr = (unsigned long)(area->start);
84 dummy = *(area->start);
85
86 if ((addr % 4) != 0) {
87 s48_gc_error("bad page start address");
88 }
89
90 areas = areas + 1;
91 pages = pages + area->size;
92 area = area->next;
93 /* LOOP */
94 }
95 }
96 /* Never reached */
97 }
98
99 /* Add SIZE pages starting from START to the set of free pages. We
100 walk down the list of free areas to find where START goes and then
101 either merge with an existing area or create a new one. */
102
s48_free_pagesB(s48_address start,unsigned long size)103 void s48_free_pagesB(s48_address start, unsigned long size) {
104 s48_address end = start + PAGES_TO_BYTES_I_KNOW_THIS_CAN_OVERFLOW(size);
105 FreeArea* before = freelist;
106 int done;
107
108 if (PAGES_TO_BYTES_LOSES_P(size)) {
109 s48_gc_error("s48_free_pagesB: integer overflow detected too late to avoid"
110 " crash (%li pages requested)", size);
111 };
112
113 free_page_count = free_page_count + size;
114
115 do {
116 FreeArea* after = before->next;
117 done = 1; /* true */
118 if (after == freelist) {
119 /* we're last */
120 if ( (start == address_after_free_area(before)) &&
121 (before != freelist))
122 adjust_free_area(before, size);
123 else {
124 FreeArea* new = make_free_area(start, size);
125 connect(before, new);
126 connect(new, after);
127 }
128 } else {
129 s48_address end_of_previous = address_after_free_area(before);
130 assert(end_of_previous <= start);
131 if (after->start < start) {
132 /* we're after AFTER */
133 before = after;
134 done = 0; /* LOOP */
135 } else {
136 assert(end <= after->start);
137 if ((start == end_of_previous) &&
138 (before != freelist)) {
139 /* merge us with BEFORE */
140 adjust_free_area(before, size);
141 if (end == after->start) {
142 /* and with AFTER, deleting AFTER */
143 adjust_free_area(before, after->size);
144 connect(before, after->next);
145 deallocate_free_area(after);
146 }
147 } else if (end == after->start) {
148 /* merge us with AFTER */
149 after->start = start;
150 adjust_free_area(after, size);
151 } else {
152 /* nothing doing, we're on our own */
153 FreeArea* new = make_free_area(start, size);
154 connect(before, new);
155 connect(new, after);
156 }
157 }
158 }
159 } while (!done);
160
161 check_freelist();
162 }
163
164 /* Getting more memory from the OS */
165
166 /* Grab at least a quarter-megabyte (2**18) at a time. */
167 /* minimum_allocation_quantum = 64 Pages (= 64 * 4KB = 256 KB) */
168
169 static unsigned long minimum_allocation_quantum = BYTES_TO_PAGES(2 << 18);
170
171
172 #define generic_max(a, b) ((a < b) ? b : a)
173
174 /* We grab the memory and then cut it down to even page boundaries. */
175 /* Returns 0 on failure, non-zero on success. */
176
get_more_memory(unsigned long minimum)177 static int get_more_memory(unsigned long minimum) {
178 unsigned long ask_for = generic_max(minimum, minimum_allocation_quantum) + 1;
179 /* may lose up to one full page on the ends */
180 unsigned long size = PAGES_TO_BYTES_I_KNOW_THIS_CAN_OVERFLOW(ask_for);
181 s48_address memory;
182 if (PAGES_TO_BYTES_LOSES_P(ask_for)) {
183 s48_gc_error("get_more_memory: integer overflow detected too late to avoid"
184 " crash (%li pages requested)", minimum);
185 };
186 memory = (s48_address)malloc(size);
187 if (memory == NULL)
188 return 0;
189 else {
190 s48_address start = PAGE_START_ADDRESS(memory);
191 if (start == memory)
192 s48_free_pagesB(start, ask_for);
193 else
194 s48_free_pagesB(ADD_PAGES_I_KNOW_THIS_CAN_OVERFLOW(start, 1),
195 ask_for - 1);
196 return 1;
197 }
198 }
199
200 /* Do a first-fit search of the free list to find a free section of
201 between MINIMUM and MAXIMUM pages, inclusive. */
202
203 /* Returns the number of pages allocated (between MINIMUM and MAXIMUM,
204 or 0 on failure). */
205
s48_allocate_pages(unsigned long minimum,unsigned long maximum,s48_address * start)206 unsigned long s48_allocate_pages(unsigned long minimum,
207 unsigned long maximum,
208 s48_address* start) {
209 FreeArea* area = freelist->next;
210
211 if (PAGES_TO_BYTES_LOSES_P(minimum) || PAGES_TO_BYTES_LOSES_P(maximum)) {
212 s48_gc_error("s48_allocate_pages: integer overflow detected too late to"
213 " avoid crash (%li..%li pages requested)", minimum, maximum);
214 };
215
216 while (1) {
217 if (area == freelist) {
218 if (!get_more_memory(minimum)) {
219 return 0;
220 };
221 area = freelist->next; /* LOOP */
222 } else if (area->size < minimum) {
223 area = area->next; /* LOOP */
224 } else if (maximum < area->size) {
225 *start = area->start;
226 area->start = ADD_PAGES_I_KNOW_THIS_CAN_OVERFLOW(area->start, minimum);
227
228 /* This integer overflow seems to be harmless. */
229 adjust_free_area(area, - ((long) minimum));
230
231 free_page_count = free_page_count - minimum;
232 check_freelist();
233 return minimum;
234 } else {
235 unsigned long size = area->size;
236 *start = area->start;
237 connect(area->prev, area->next);
238 deallocate_free_area(area);
239 free_page_count = free_page_count - size;
240 check_freelist();
241 #if (BIBOP_LOG)
242 s48_bibop_log("s48_allocate_pages: minimum %li < area->size %li < maximum %li",
243 minimum, size, maximum);
244 #endif
245 return size;
246 }
247 }
248 /* Never reached */
249 }
250
251