1 /* 2 * Copyright 2004-2008, Axel Dörfler, axeld@pinc-software.de. 3 * Distributed under the terms of the MIT License. 4 */ 5 6 7 #include <OS.h> 8 9 #include <kernel.h> 10 #include <boot/stage2.h> 11 #include <boot/platform.h> 12 13 #include <string.h> 14 15 16 static const size_t kChunkSize = 8 * B_PAGE_SIZE; 17 18 kernel_args gKernelArgs; 19 20 static void* sFirstFree; 21 static void* sLast; 22 static size_t sFree = kChunkSize; 23 24 25 static void 26 remove_range_index(addr_range* ranges, uint32& numRanges, uint32 index) 27 { 28 if (index + 1 == numRanges) { 29 // remove last range 30 numRanges--; 31 return; 32 } 33 34 memmove(&ranges[index], &ranges[index + 1], 35 sizeof(addr_range) * (numRanges - 1 - index)); 36 numRanges--; 37 } 38 39 40 static status_t 41 add_kernel_args_range(void* start, uint32 size) 42 { 43 return insert_address_range(gKernelArgs.kernel_args_range, 44 &gKernelArgs.num_kernel_args_ranges, MAX_KERNEL_ARGS_RANGE, 45 (addr_t)start, size); 46 } 47 48 49 // #pragma mark - addr_range utility 50 51 52 /*! Inserts the specified (start, size) pair (aka range) in the 53 addr_range array. 54 It will extend existing ranges in order to have as little 55 ranges in the array as possible. 56 Returns B_OK on success, or B_ENTRY_NOT_FOUND if there was 57 no free array entry available anymore. 58 */ 59 extern "C" status_t 60 insert_address_range(addr_range* ranges, uint32* _numRanges, uint32 maxRanges, 61 addr_t start, uint32 size) 62 { 63 uint32 numRanges = *_numRanges; 64 65 start = ROUNDOWN(start, B_PAGE_SIZE); 66 size = ROUNDUP(size, B_PAGE_SIZE); 67 addr_t end = start + size; 68 69 for (uint32 i = 0; i < numRanges; i++) { 70 addr_t rangeStart = ranges[i].start; 71 addr_t rangeEnd = rangeStart + ranges[i].size; 72 73 if (end < rangeStart || start > rangeEnd) { 74 // ranges don't intersect or touch each other 75 continue; 76 } 77 if (start >= rangeStart && end <= rangeEnd) { 78 // range is already completely covered 79 return B_OK; 80 } 81 82 if (start < rangeStart) { 83 // prepend to the existing range 84 ranges[i].start = start; 85 ranges[i].size += rangeStart - start; 86 } 87 if (end > ranges[i].start + ranges[i].size) { 88 // append to the existing range 89 ranges[i].size = end - ranges[i].start; 90 } 91 92 // join ranges if possible 93 94 for (uint32 j = 0; j < numRanges; j++) { 95 if (i == j) 96 continue; 97 98 rangeStart = ranges[i].start; 99 rangeEnd = rangeStart + ranges[i].size; 100 addr_t joinStart = ranges[j].start; 101 addr_t joinEnd = joinStart + ranges[j].size; 102 103 if (rangeStart <= joinEnd && joinEnd <= rangeEnd) { 104 // join range that used to be before the current one, or 105 // the one that's now entirely included by the current one 106 if (joinStart < rangeStart) { 107 ranges[i].size += rangeStart - joinStart; 108 ranges[i].start = joinStart; 109 } 110 111 remove_range_index(ranges, numRanges, j--); 112 } else if (joinStart <= rangeEnd && joinEnd > rangeEnd) { 113 // join range that used to be after the current one 114 ranges[i].size += joinEnd - rangeEnd; 115 116 remove_range_index(ranges, numRanges, j--); 117 } 118 } 119 120 *_numRanges = numRanges; 121 return B_OK; 122 } 123 124 // no range matched, we need to create a new one 125 126 if (numRanges >= maxRanges) 127 return B_ENTRY_NOT_FOUND; 128 129 ranges[numRanges].start = (addr_t)start; 130 ranges[numRanges].size = size; 131 (*_numRanges)++; 132 133 return B_OK; 134 } 135 136 137 extern "C" status_t 138 remove_address_range(addr_range* ranges, uint32* _numRanges, uint32 maxRanges, 139 addr_t start, uint32 size) 140 { 141 uint32 numRanges = *_numRanges; 142 143 addr_t end = ROUNDUP(start + size, B_PAGE_SIZE); 144 start = ROUNDOWN(start, B_PAGE_SIZE); 145 146 for (uint32 i = 0; i < numRanges; i++) { 147 addr_t rangeStart = ranges[i].start; 148 addr_t rangeEnd = rangeStart + ranges[i].size; 149 150 if (start <= rangeStart) { 151 if (end <= rangeStart) { 152 // no intersection 153 } else if (end >= rangeEnd) { 154 // remove the complete range 155 remove_range_index(ranges, numRanges, i); 156 i--; 157 } else { 158 // remove the head of the range 159 ranges[i].start = end; 160 ranges[i].size = rangeEnd - end; 161 } 162 } else if (end >= rangeEnd) { 163 if (start < rangeEnd) { 164 // remove the tail 165 ranges[i].size = start - rangeStart; 166 } // else: no intersection 167 } else { 168 // rangeStart < start < end < rangeEnd 169 // The ugly case: We have to remove something from the middle of 170 // the range. We keep the head of the range and insert its tail 171 // as a new range. 172 ranges[i].size = start - rangeStart; 173 return insert_address_range(ranges, _numRanges, maxRanges, 174 end, rangeEnd - end); 175 } 176 } 177 178 *_numRanges = numRanges; 179 return B_OK; 180 } 181 182 183 status_t 184 insert_physical_memory_range(addr_t start, uint32 size) 185 { 186 return insert_address_range(gKernelArgs.physical_memory_range, 187 &gKernelArgs.num_physical_memory_ranges, MAX_PHYSICAL_MEMORY_RANGE, 188 start, size); 189 } 190 191 192 status_t 193 insert_physical_allocated_range(addr_t start, uint32 size) 194 { 195 return insert_address_range(gKernelArgs.physical_allocated_range, 196 &gKernelArgs.num_physical_allocated_ranges, 197 MAX_PHYSICAL_ALLOCATED_RANGE, start, size); 198 } 199 200 201 status_t 202 insert_virtual_allocated_range(addr_t start, uint32 size) 203 { 204 return insert_address_range(gKernelArgs.virtual_allocated_range, 205 &gKernelArgs.num_virtual_allocated_ranges, MAX_VIRTUAL_ALLOCATED_RANGE, 206 start, size); 207 } 208 209 210 // #pragma mark - kernel_args allocations 211 212 213 /*! This function can be used to allocate memory that is going 214 to be passed over to the kernel. For example, the preloaded_image 215 structures are allocated this way. 216 The boot loader heap doesn't make it into the kernel! 217 */ 218 extern "C" void* 219 kernel_args_malloc(size_t size) 220 { 221 //dprintf("kernel_args_malloc(): %ld bytes (%ld bytes left)\n", size, sFree); 222 223 if (sFirstFree != NULL && size <= sFree) { 224 // there is enough space in the current buffer 225 void* address = sFirstFree; 226 sFirstFree = (void*)((addr_t)sFirstFree + size); 227 sLast = address; 228 sFree -= size; 229 230 return address; 231 } 232 233 if (size > kChunkSize / 2 && sFree < size) { 234 // the block is so large, we'll allocate a new block for it 235 void* block = NULL; 236 if (platform_allocate_region(&block, size, B_READ_AREA | B_WRITE_AREA, 237 false) != B_OK) { 238 return NULL; 239 } 240 241 if (add_kernel_args_range(block, size) != B_OK) 242 panic("kernel_args max range to low!\n"); 243 return block; 244 } 245 246 // just allocate a new block and "close" the old one 247 void* block = NULL; 248 if (platform_allocate_region(&block, kChunkSize, B_READ_AREA | B_WRITE_AREA, 249 false) != B_OK) { 250 return NULL; 251 } 252 253 sFirstFree = (void*)((addr_t)block + size); 254 sLast = block; 255 sFree = kChunkSize - size; 256 if (add_kernel_args_range(block, kChunkSize) != B_OK) 257 panic("kernel_args max range to low!\n"); 258 259 return block; 260 } 261 262 263 /*! Convenience function that copies strdup() functions for the 264 kernel args heap. 265 */ 266 extern "C" char * 267 kernel_args_strdup(const char *string) 268 { 269 if (string == NULL || string[0] == '\0') 270 return NULL; 271 272 size_t length = strlen(string) + 1; 273 274 char *target = (char *)kernel_args_malloc(length); 275 if (target == NULL) 276 return NULL; 277 278 memcpy(target, string, length); 279 return target; 280 } 281 282 283 /*! This function frees a block allocated via kernel_args_malloc(). 284 It's very simple; it can only free the last allocation. It's 285 enough for its current usage in the boot loader, though. 286 */ 287 extern "C" void 288 kernel_args_free(void *block) 289 { 290 if (sLast != block) { 291 // sorry, we're dumb 292 return; 293 } 294 295 sFree = (addr_t)sFirstFree - (addr_t)sLast; 296 sFirstFree = block; 297 sLast = NULL; 298 } 299 300