1/* 2 * Copyright (c) 2012 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * The contents of this file constitute Original Code as defined in and 7 * are subject to the Apple Public Source License Version 1.1 (the 8 * "License"). You may not use this file except in compliance with the 9 * License. Please obtain a copy of the License at 10 * http://www.apple.com/publicsource and read it before using this file. 11 * 12 * This Original Code and all software distributed under the License are 13 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER 14 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 15 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 16 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the 17 * License for the specific language governing rights and limitations 18 * under the License. 19 * 20 * @APPLE_LICENSE_HEADER_END@ 21 */ 22 23#ifndef KERNEL 24 25/* 26cc rballoc.c -o /tmp/rballoc -Wall -framework IOKit -framework CoreFoundation -g 27*/ 28 29#include <assert.h> 30#include <CoreFoundation/CoreFoundation.h> 31#include <IOKit/IOKitLib.h> 32#include <IOKit/IOKitKeys.h> 33#include <Kernel/libkern/tree.h> 34 35#define IONew(type,number) (type*)malloc(sizeof(type) * (number) ) 36#define IODelete(ptr,type,number) free( (ptr) ) 37 38#define atop(n) ((n) >> 12) 39 40typedef uint32_t vtd_rbaddr_t; 41 42struct vtd_rblock 43{ 44 RB_ENTRY(vtd_rblock) address_link; 45 RB_ENTRY(vtd_rblock) size_link; 46 47 vtd_rbaddr_t start; 48 vtd_rbaddr_t end; 49}; 50 51RB_HEAD(vtd_rbaddr_list, vtd_rblock); 52RB_HEAD(vtd_rbsize_list, vtd_rblock); 53 54struct vtd_space 55{ 56 struct vtd_rbaddr_list rbaddr_list; 57 struct vtd_rbsize_list rbsize_list; 58}; 59typedef struct vtd_space vtd_space_t; 60 61#define vtd_space_fault(x,y,z) 62 63#define VTLOG(fmt, args...) printf(fmt, ## args); 64 65#define vtassert(x) assert(x) 66 67int main(int argc, char **argv) 68{ 69 vtd_space_t _list; 70 vtd_space_t * bf = &_list; 71 72 RB_INIT(&bf->rbaddr_list); 73 RB_INIT(&bf->rbsize_list); 74 75 int idx; 76 vtd_rbaddr_t allocs[20]; 77 vtd_rbaddr_t sizes [20] = { 0x100, 0x100, 0x300, 0x100, 0x300, 0x100, 0 }; 78 vtd_rbaddr_t aligns[20] = { atop(2*1024*1024), atop(2*1024*1024), atop(2*1024*1024), atop(2*1024*1024), atop(2*1024*1024), atop(2*1024*1024), 0 }; 79 80 81 vtd_rbfree(bf, 0, 0); 82 vtd_rbfree(bf, (1<<20), (1 << 21)); 83 84 vtd_rblog(bf); 85 86#if 0 87 88 vtd_rballoc_fixed(bf, 0x100, 0x80); 89 vtd_rblog(bf); 90 vtd_rballoc_fixed(bf, 0x180, 0x80); 91 vtd_rblog(bf); 92 vtd_rballoc_fixed(bf, 0x1, 0x1); 93 vtd_rblog(bf); 94 vtd_rballoc_fixed(bf, 0x2, 0xfe); 95 vtd_rblog(bf); 96 97 vtd_rbfree(bf, 50, 50); 98 vtd_rblog(bf); 99 vtd_rbfree(bf, 1, 49); 100 vtd_rblog(bf); 101 vtd_rbfree(bf, 100, 100); 102 vtd_rblog(bf); 103 vtd_rbfree(bf, 400, 100); 104 vtd_rblog(bf); 105 vtd_rbfree(bf, 250, 50); 106 vtd_rblog(bf); 107#endif 108 109 for (idx = 0; sizes[idx]; idx++) 110 { 111 allocs[idx] = vtd_rballoc(bf, sizes[idx], aligns[idx]); 112 VTLOG("alloc(0x%x) 0x%x\n", sizes[idx], allocs[idx]); 113 vtd_rblog(bf); 114 vtassert(allocs[idx]); 115 } 116 117 for (idx = 0; sizes[idx]; idx++) 118 { 119 vtd_rbfree(bf, allocs[idx], sizes[idx]); 120 VTLOG("free(0x%x, 0x%x)\n", allocs[idx], sizes[idx]); 121 vtd_rblog(bf); 122 } 123 124 125#if 0 126 vtd_rbfree(bf, 300, 100); 127 vtd_rblog(bf); 128 vtd_rbfree(bf, 200, 50); 129 vtd_rblog(bf); 130#endif 131 132 exit(0); 133} 134 135#endif /* KERNEL */ 136 137 138 139static int 140vtd_rbaddr_compare(struct vtd_rblock *node, struct vtd_rblock *parent) 141{ 142 if (node->start < parent->start) return (-1); 143 if (node->start >= parent->end) return (1); 144 return (0); 145} 146 147static int 148vtd_rbsize_compare(struct vtd_rblock *node, struct vtd_rblock *parent) 149{ 150 vtd_rbaddr_t sizen = node->end - node->start; 151 vtd_rbaddr_t sizep = parent->end - parent->start; 152 153 if (sizen < sizep) return (1); 154 // never a dup 155 return (-1); 156} 157 158RB_PROTOTYPE_SC(static, vtd_rbaddr_list, vtd_rblock, address_link, vtd_rbaddr_compare); 159RB_PROTOTYPE_SC(static, vtd_rbsize_list, vtd_rblock, size_link, vtd_rbsize_compare); 160 161RB_GENERATE(vtd_rbaddr_list, vtd_rblock, address_link, vtd_rbaddr_compare); 162RB_GENERATE(vtd_rbsize_list, vtd_rblock, size_link, vtd_rbsize_compare); 163 164static void 165vtd_rblog(vtd_space_t * bf) 166{ 167 struct vtd_rblock * elem; 168 169 RB_FOREACH(elem, vtd_rbaddr_list, &bf->rbaddr_list) 170 { 171 VTLOG("[0x%x, 0x%x)\n", elem->start, elem->end); 172 } 173 RB_FOREACH(elem, vtd_rbsize_list, &bf->rbsize_list) 174 { 175 VTLOG("S[0x%x, 0x%x)\n", elem->start, elem->end); 176 } 177 VTLOG("\n"); 178} 179 180static void 181vtd_rbfree(vtd_space_t * bf, vtd_rbaddr_t addr, vtd_rbaddr_t size, vtd_rbaddr_t maxround) 182{ 183 struct vtd_rblock * next = RB_ROOT(&bf->rbaddr_list); 184 struct vtd_rblock * prior = NULL; 185 vtd_rbaddr_t hwalign; 186 vtd_rbaddr_t end = addr + size; 187 188 hwalign = vtd_log2up(size); 189 if (hwalign > maxround) hwalign = maxround; 190 hwalign = (1 << hwalign); 191 hwalign--; 192 193 size = (size + hwalign) & ~hwalign; 194 end = addr + size; 195 196 while (next) 197 { 198 vtassert(addr != next->start); 199 if (addr > next->start) 200 { 201 prior = next; 202 next = RB_RIGHT(next, address_link); 203 } 204 else 205 { 206 next = RB_LEFT(next, address_link); 207 } 208 } 209 210 if (prior) 211 { 212 next = RB_NEXT(vtd_rbaddr_list, &bf->rbaddr_list, prior); 213 if (addr != prior->end) 214 { 215 prior = NULL; 216 } 217 else 218 { 219 // coalesce to end of prior 220 addr = prior->start; 221 } 222 223 if (next && (end == next->start)) 224 { 225 if (!prior) 226 { 227 // coalesce to start of next 228 prior = next; 229 end = next->end; 230 } 231 else 232 { 233 end = next->end; 234 RB_REMOVE(vtd_rbaddr_list, &bf->rbaddr_list, next); 235 RB_REMOVE(vtd_rbsize_list, &bf->rbsize_list, next); 236 } 237 } 238 } 239 240 if (prior) 241 { 242 // recolor? 243 RB_REMOVE(vtd_rbaddr_list, &bf->rbaddr_list, prior); 244 RB_REMOVE(vtd_rbsize_list, &bf->rbsize_list, prior); 245 prior->start = addr; 246 prior->end = end; 247 next = RB_INSERT(vtd_rbaddr_list, &bf->rbaddr_list, prior); 248 vtassert(NULL == next); 249 next = RB_INSERT(vtd_rbsize_list, &bf->rbsize_list, prior); 250 vtassert(NULL == next); 251 } 252 else 253 { 254 next = IONew(typeof(*next), 1); 255#if VTASRT 256 memset(next, 0xef, sizeof(*next)); 257#endif 258 next->start = addr; 259 next->end = end; 260 prior = RB_INSERT(vtd_rbaddr_list, &bf->rbaddr_list, next); 261 vtassert(NULL == prior); 262 prior = RB_INSERT(vtd_rbsize_list, &bf->rbsize_list, next); 263 vtassert(NULL == prior); 264 } 265} 266 267static vtd_rbaddr_t 268vtd_rballoc(vtd_space_t * bf, vtd_rbaddr_t pages, vtd_rbaddr_t align, vtd_rbaddr_t maxround, 269 uint32_t mapOptions, upl_page_info_t * pageList) 270{ 271 vtd_rbaddr_t addr = 0; 272 vtd_rbaddr_t end, head, tail; 273 vtd_rbaddr_t size, hwalign; 274 struct vtd_rblock * next = RB_ROOT(&bf->rbsize_list); 275 struct vtd_rblock * prior = NULL; 276 277 vtassert(align); 278 279 hwalign = vtd_log2up(pages); 280 if (hwalign > maxround) hwalign = maxround; 281 hwalign = (1 << hwalign); 282 hwalign--; 283 size = (pages + hwalign) & ~hwalign; 284 285 align--; 286 if (align < hwalign) align = hwalign; 287 288 while (next) 289 { 290 head = (next->start + align) & ~align; 291 if ((head + size) <= next->end) 292 { 293 prior = next; 294 next = RB_RIGHT(next, size_link); 295 } 296 else 297 { 298 next = RB_LEFT(next, size_link); 299 } 300 } 301 302 if (prior) 303 { 304 addr = (prior->start + align) & ~align; 305 306 vtassert((addr + size) <= prior->end); 307 308 // recolor? 309 RB_REMOVE(vtd_rbaddr_list, &bf->rbaddr_list, prior); 310 RB_REMOVE(vtd_rbsize_list, &bf->rbsize_list, prior); 311 312 end = addr + size; 313 tail = prior->end - end; 314 head = addr - prior->start; 315 316 if (!head && !tail) IODelete(prior, typeof(*prior), 1); 317 else 318 { 319 if (tail) 320 { 321 prior->start = end; 322 next = RB_INSERT(vtd_rbaddr_list, &bf->rbaddr_list, prior); 323 vtassert(NULL == next); 324 next = RB_INSERT(vtd_rbsize_list, &bf->rbsize_list, prior); 325 vtassert(NULL == next); 326 } 327 if (head) 328 { 329 if (tail) 330 { 331 prior = IONew(typeof(*prior), 1); 332#if VASRT 333 memset(prior, 0xef, sizeof(*prior)); 334#endif 335 prior->start = addr - head; 336 prior->end = addr; 337 } 338 else 339 { 340 prior->end = addr; 341 } 342 next = RB_INSERT(vtd_rbaddr_list, &bf->rbaddr_list, prior); 343 vtassert(NULL == next); 344 next = RB_INSERT(vtd_rbsize_list, &bf->rbsize_list, prior); 345 vtassert(NULL == next); 346 } 347 } 348 } 349 350 return (addr); 351} 352 353static void 354vtd_rballoc_fixed(vtd_space_t * bf, vtd_rbaddr_t addr, vtd_rbaddr_t size) 355{ 356 vtd_rbaddr_t end, head, tail; 357 struct vtd_rblock * prior = RB_ROOT(&bf->rbaddr_list); 358 struct vtd_rblock * next = NULL; 359 360 end = addr + size; 361 while (prior) 362 { 363 if (addr >= prior->start) 364 { 365 if (end <= prior->end) break; 366 prior = RB_RIGHT(prior, address_link); 367 } 368 else 369 { 370 prior = RB_LEFT(prior, address_link); 371 } 372 } 373 374 if (prior) 375 { 376 // recolor? 377 RB_REMOVE(vtd_rbaddr_list, &bf->rbaddr_list, prior); 378 RB_REMOVE(vtd_rbsize_list, &bf->rbsize_list, prior); 379 380 tail = prior->end - end; 381 head = addr - prior->start; 382 383 if (tail) 384 { 385 prior->start = end; 386 next = RB_INSERT(vtd_rbaddr_list, &bf->rbaddr_list, prior); 387 vtassert(NULL == next); 388 next = RB_INSERT(vtd_rbsize_list, &bf->rbsize_list, prior); 389 vtassert(NULL == next); 390 } 391 if (head) 392 { 393 if (tail) 394 { 395 prior = IONew(typeof(*prior), 1); 396#if VASRT 397 memset(prior, 0xef, sizeof(*prior)); 398#endif 399 prior->start = addr - head; 400 prior->end = addr; 401 } 402 else 403 { 404 prior->end = addr; 405 } 406 next = RB_INSERT(vtd_rbaddr_list, &bf->rbaddr_list, prior); 407 vtassert(NULL == next); 408 next = RB_INSERT(vtd_rbsize_list, &bf->rbsize_list, prior); 409 vtassert(NULL == next); 410 } 411 } 412} 413 414 415static void 416vtd_rballocator_init(vtd_space_t * bf, ppnum_t start, ppnum_t size) 417{ 418 RB_INIT(&bf->rbaddr_list); 419 RB_INIT(&bf->rbsize_list); 420 421 vtd_rbfree(bf, 0, 0, 0); 422 vtd_rbfree(bf, start, size, 0); 423} 424 425 426