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 23typedef uint32_t vtd_baddr_t; 24 25void vtd_blog(vtd_space_t * bf) 26{ 27 uint32_t idx; 28 vtd_table_entry_t entry; 29 vtd_baddr_t next; 30 31 for (idx = 0; idx < bf->bheads_count; idx++) 32 { 33 next = bf->bheads[idx].free.next; 34 while (next) 35 { 36 VTLOG("[%d]: 0x%x\n", idx, next); 37 vtd_space_nfault(bf, next, 1); 38 entry = bf->tables[0][next]; 39 vtassert(entry.free.free); 40 next = entry.free.next; 41 } 42 } 43} 44 45static void 46vtd_bchunk_free(vtd_space_t * bf, vtd_baddr_t start, vtd_baddr_t size) 47{ 48 vtd_table_entry_t entry; 49 vtd_baddr_t next; 50 51 vtassert(start < (1U << bf->bheads_count)); 52// vtd_space_fault(bf, start, 1); 53 54 next = bf->bheads[size].free.next; 55 if (next) 56 { 57 vtassert(next < (1U << bf->bheads_count)); 58 bf->tables[0][next].free.prev = start; 59 } 60 entry.bits = 0; 61 entry.free.free = 1; 62 entry.free.size = size; 63 entry.free.prev = size; 64 entry.free.next = next; 65 bf->tables[0][start] = entry; 66 bf->bheads[size].free.next = start; 67 STAT_ADD(bf, bcounts[size], 1); 68} 69 70 71static void 72vtd_bfree(vtd_space_t * bf, vtd_baddr_t addr, vtd_baddr_t size) 73{ 74 vtd_table_entry_t entry; 75 vtd_baddr_t buddy; 76 uint32_t list; 77 78 list = vtd_log2up(size); 79 80 vtassert(!bf->tables[0][addr].free.free); 81 82 do 83 { 84 // merge less aggressively 85// if ((list <= 10) && (bf->stats.bcounts[list] < 3)) break; 86 87 buddy = (addr ^ (1 << list)); 88 if (!vtd_space_present(bf, buddy)) break; 89 entry = bf->tables[0][buddy]; 90 if (!entry.free.free) break; 91 if (entry.free.size != list) break; 92 // 93 vtassert(entry.free.prev < (1U << bf->bheads_count)); 94 bf->tables[0][entry.free.prev].free.next = entry.free.next; 95 vtassert(entry.free.next < (1U << bf->bheads_count)); 96 bf->tables[0][entry.free.next].free.prev = entry.free.prev; 97 STAT_ADD(bf, bcounts[list], -1); 98 // 99 addr &= ~(1 << list); 100 list++; 101 vtassert(buddy < (1U << bf->bheads_count)); 102 bf->tables[0][buddy].free.size = list; 103 STAT_ADD(bf, merges, 1); 104 } 105 while (list < bf->bheads_count); 106 107 vtd_bchunk_free(bf, addr, list); 108} 109 110static vtd_baddr_t 111vtd_balloc(vtd_space_t * bf, vtd_baddr_t size, 112 uint32_t mapOptions, upl_page_info_t * pageList) 113{ 114 uint32_t list, idx; 115 vtd_baddr_t addr; 116 vtd_baddr_t next; 117 vtd_baddr_t clear; 118 vtd_table_entry_t entry; 119 120 list = vtd_log2up(size); 121 122 addr = 0; 123 for (idx = list; idx < bf->bheads_count; idx++) 124 { 125 addr = bf->bheads[idx].free.next; 126 if (addr) break; 127 } 128 if (!addr) return (addr); 129 130 vtd_space_nfault(bf, addr, 1); 131 vtassert(bf->tables[0][addr].free.free); 132 // 133 vtassert(addr < (1U << bf->bheads_count)); 134 entry = bf->tables[0][addr]; 135 entry.free.free = 0; 136// bf->tables[0][addr].bits = 0; 137//f bf->tables[0][addr].free.free = 0; 138 139 next = entry.free.next; 140 bf->bheads[idx].free.next = next; 141 if (next) bf->tables[0][next].free.prev = idx; 142 STAT_ADD(bf, bcounts[idx], -1); 143 // 144 STAT_ADD(bf, breakups, idx - list); 145 while (idx != list) 146 { 147 idx--; 148 vtd_bchunk_free(bf, addr + (1 << idx), idx); 149 } 150 151// vtd_space_fault(bf, addr + 1, (1 << list) - 1); 152 153 // init or clear allocation 154 next = addr; 155 if (pageList) 156 { 157 vtd_space_set(bf, addr, size, mapOptions, pageList); 158 next += size; 159 } 160 // clear roundup size 161 clear = ((addr + (1 << list)) - next); 162 if (clear) bzero(&bf->tables[0][next], clear * sizeof(vtd_table_entry_t)); 163#if 0 164 for (; next < (addr + (1 << list)); next++) 165 { 166 vtassert(next < (1U << bf->bheads_count)); 167//f bf->tables[0][next].free.free = 0; 168 bf->tables[0][next].bits = 0; 169 } 170#endif 171 172 return (addr); 173} 174 175static void 176vtd_balloc_fixed(vtd_space_t * bf, vtd_baddr_t addr, vtd_baddr_t size) 177{ 178 int list; 179 vtd_table_entry_t entry; 180 vtd_baddr_t end; 181 vtd_baddr_t chunk; 182 vtd_baddr_t next; 183 vtd_baddr_t head; 184 vtd_baddr_t tail; 185 vtd_baddr_t start; 186 vtd_baddr_t finish; 187 vtd_baddr_t rem; 188 189 end = addr + size; 190 for (list = bf->bheads_count; (--list) >= 0;) 191 { 192 chunk = bf->bheads[list].free.next; 193 while (chunk) 194 { 195 entry = bf->tables[0][chunk]; 196 next = entry.free.next; 197 // intersect 198 start = (chunk < addr) ? addr : chunk; 199 finish = (chunk + (1 << list)); 200 if (end < finish) finish = end; 201 if (finish > start) 202 { 203 // 204 vtassert(entry.free.prev < (1U << bf->bheads_count)); 205 bf->tables[0][entry.free.prev].free.next = next; 206 vtassert(next < (1U << bf->bheads_count)); 207 bf->tables[0][next].free.prev = entry.free.prev; 208 STAT_ADD(bf, bcounts[list], -1); 209 // 210// vtd_space_fault(bf, start, finish - start); 211 for (head = start; head < finish; head++) 212 { 213 vtassert(head < (1U << bf->bheads_count)); 214//f bf->tables[0][head].free.free = 0; 215 bf->tables[0][head].bits = 0; 216 } 217 218 head = chunk; 219 if (1) while (head != start) 220 { 221 rem = vtd_log2down(start - head); 222//VTLOG("++ %x, %x\n", head, rem); 223 vtd_bchunk_free(bf, head, rem); 224 head += (1 << rem); 225 } 226 head = end; 227 tail = (chunk + (1 << list)); 228 if (1) while (head < tail) 229 { 230 rem = vtd_log2down(tail - head); 231//VTLOG("-- %x, %x\n", tail - (1 << rem), rem); 232 vtd_bchunk_free(bf, tail - (1 << rem), rem); 233 tail -= (1 << rem); 234 } 235 } 236 chunk = next; 237 } 238 } 239} 240 241 242static void 243vtd_bfree_fixed(vtd_space_t * bf, vtd_baddr_t addr, vtd_baddr_t size) 244{ 245 vtd_baddr_t end; 246 vtd_baddr_t head; 247 vtd_baddr_t tail; 248 249 end = addr + size; 250 251 while (addr != end) 252 { 253 head = __builtin_ctz((unsigned int) addr); 254 tail = __builtin_ctz((unsigned int) end); 255 if (head <= tail) 256 { 257//VTLOG("++ %x, %x\n", addr, head); 258 vtd_bfree(bf, addr, (1 << head)); 259 addr += (1 << head); 260 } 261 else 262 { 263 end -= (1 << tail); 264//VTLOG("-- %x, %x\n", end, tail); 265 vtd_bfree(bf, end, (1 << tail)); 266 } 267 } 268} 269 270static void 271vtd_ballocator_init(vtd_space_t * bf, uint32_t buddybits) 272{ 273 uint32_t idx; 274 275 bf->bheads_count = buddybits; 276 bf->bheads = bf->tables[0]; 277 vtd_space_fault(bf, 0, (1 << buddybits)); 278// bzero(bf->tables[0], (1 << buddybits)); 279// bzero(bf->bheads, sizeof(uint64_t) * bf->bheads_count); 280 281 idx = vtd_log2up(buddybits); 282 // reserve 2M of space 283 if (idx < 9) idx = 9; 284 VTLOG("ballocator count %d, bits 0x%lx, table %p, reserved 0x%x\n", 285 bf->bheads_count, bf->table_bitmap_size, bf->tables[0], (1 << idx)); 286 287 for (; idx < buddybits; idx++) 288 { 289 vtd_bchunk_free(bf, (1 << idx), idx); 290 } 291} 292 293/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 294 295#ifndef KERNEL 296 297/* 298cc balloc.c -o /tmp/balloc -Wall -framework IOKit -framework CoreFoundation -g 299*/ 300 301#include <assert.h> 302#include <CoreFoundation/CoreFoundation.h> 303#include <IOKit/IOKitLib.h> 304#include <IOKit/IOKitKeys.h> 305 306#define IONew(type,number) (type*)malloc(sizeof(type) * (number) ) 307#define IODelete(ptr,type,number) free( (ptr) ) 308 309#define atop(n) ((n) >> 12) 310#define page_size 4096 311 312#define L if (0) 313 314int main(int argc, char **argv) 315{ 316 vtd_space_t * bf; 317 int idx; 318 uint32_t bits = 20; 319 vtd_baddr_t allocs[256]; 320 vtd_baddr_t sizes [256] = { 1, atop(1024*1024), atop(4*1024*1024), 1, 3, 6, 1, 10, 99, 100, 50, 30, 0 }; 321 vtd_baddr_t aligns[256] = { 1, atop(1024*1024), atop(2*1024*1024), 1, 4, 8, 1, 0 }; 322 323 bf = vtd_ballocator_alloc(bits); 324 vtd_blog(bf); 325 326 for (idx = 0; idx < 1*999; idx++) 327 { 328 329VTLOG("fixed 0x%x, 0x%x\n", 0x40 + idx, (idx << 1) ^ (idx >> 3)); 330 vtd_balloc_fixed(bf, 0x40 + idx, (idx << 1) ^ (idx >> 3)); 331VTLOG("unfix 0x%x, 0x%x\n", 0x40 + idx, (idx << 1) ^ (idx >> 3)); 332 vtd_bfree_fixed(bf, 0x40 + idx, (idx << 1) ^ (idx >> 3)); 333 } 334 vtd_blog(bf); 335 336 337 vtd_balloc_fixed(bf, 0x43, 0x4); 338 vtd_blog(bf); 339 340 if (1) 341 { 342 srandomdev(); 343 long seed = random(); 344 long count = random(); 345 VTLOG("seed %ld, count %ld\n", seed, count); 346 347 srandom(seed); 348 bzero(&allocs[0], sizeof(allocs)); 349 while (count--) 350 { 351 long r = random(); 352 idx = (r & 255); 353 if (allocs[idx]) 354 { 355L VTLOG("free(0x%x, 0x%x)\n", allocs[idx], sizes[idx]); 356 vtd_bfree(bf, allocs[idx], sizes[idx]); 357L vtd_blog(bf); 358 allocs[idx] = sizes[idx] = 0; 359 } 360 sizes[idx] = (r >> 20); 361 if (!sizes[idx]) sizes[idx] = 1; 362 allocs[idx] = vtd_balloc(bf, sizes[idx], aligns[idx]); 363L VTLOG("alloc(0x%x) 0x%x\n", sizes[idx], allocs[idx]); 364L vtd_blog(bf); 365 } 366 367 for (idx = 0; idx < arrayCount(allocs); idx++) 368 { 369 if (allocs[idx]) 370 { 371L VTLOG("free(0x%x, 0x%x)\n", allocs[idx], sizes[idx]); 372 vtd_bfree(bf, allocs[idx], sizes[idx]); 373L vtd_blog(bf); 374 allocs[idx] = sizes[idx] = 0; 375 } 376 } 377 } 378 379 vtd_bfree_fixed(bf, 0x43, 0x4); 380 381 for (idx = 0; idx < bits; idx++) 382 { 383 vtd_baddr_t check; 384 check = (idx < vtd_log2up(bits)) ? 0 : (1 << idx); 385 vtassert(check == bf->bheads[idx].free.next); 386 } 387 388 vtd_blog(bf); 389 VTLOG("OK\n"); 390 391 exit(0); 392} 393 394#endif /* !KERNEL */ 395