104 atomic_subtract_int(&ctx->entries_cnt, 1); 105 uma_zfree(dmar_map_entry_zone, entry); 106} 107 108static int 109dmar_gas_cmp_entries(struct dmar_map_entry *a, struct dmar_map_entry *b) 110{ 111 112 /* Last entry have zero size, so <= */ 113 KASSERT(a->start <= a->end, ("inverted entry %p (%jx, %jx)", 114 a, (uintmax_t)a->start, (uintmax_t)a->end)); 115 KASSERT(b->start <= b->end, ("inverted entry %p (%jx, %jx)", 116 b, (uintmax_t)b->start, (uintmax_t)b->end)); 117 KASSERT(a->end <= b->start || b->end <= a->start || 118 a->end == a->start || b->end == b->start, 119 ("overlapping entries %p (%jx, %jx) %p (%jx, %jx)", 120 a, (uintmax_t)a->start, (uintmax_t)a->end, 121 b, (uintmax_t)b->start, (uintmax_t)b->end)); 122 123 if (a->end < b->end) 124 return (-1); 125 else if (b->end < a->end) 126 return (1); 127 return (0); 128} 129 130static void 131dmar_gas_augment_entry(struct dmar_map_entry *entry) 132{ 133 struct dmar_map_entry *l, *r; 134 135 for (; entry != NULL; entry = RB_PARENT(entry, rb_entry)) { 136 l = RB_LEFT(entry, rb_entry); 137 r = RB_RIGHT(entry, rb_entry); 138 if (l == NULL && r == NULL) { 139 entry->free_down = entry->free_after; 140 } else if (l == NULL && r != NULL) { 141 entry->free_down = MAX(entry->free_after, r->free_down); 142 } else if (/*l != NULL && */ r == NULL) { 143 entry->free_down = MAX(entry->free_after, l->free_down); 144 } else /* if (l != NULL && r != NULL) */ { 145 entry->free_down = MAX(entry->free_after, l->free_down); 146 entry->free_down = MAX(entry->free_down, r->free_down); 147 } 148 } 149} 150 151RB_GENERATE(dmar_gas_entries_tree, dmar_map_entry, rb_entry, 152 dmar_gas_cmp_entries); 153 154static void 155dmar_gas_fix_free(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 156{ 157 struct dmar_map_entry *next; 158 159 next = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry); 160 entry->free_after = (next != NULL ? next->start : ctx->end) - 161 entry->end; 162 dmar_gas_augment_entry(entry); 163} 164 165#ifdef INVARIANTS 166static void 167dmar_gas_check_free(struct dmar_ctx *ctx) 168{ 169 struct dmar_map_entry *entry, *next, *l, *r; 170 dmar_gaddr_t v; 171 172 RB_FOREACH(entry, dmar_gas_entries_tree, &ctx->rb_root) {
| 109 atomic_subtract_int(&ctx->entries_cnt, 1); 110 uma_zfree(dmar_map_entry_zone, entry); 111} 112 113static int 114dmar_gas_cmp_entries(struct dmar_map_entry *a, struct dmar_map_entry *b) 115{ 116 117 /* Last entry have zero size, so <= */ 118 KASSERT(a->start <= a->end, ("inverted entry %p (%jx, %jx)", 119 a, (uintmax_t)a->start, (uintmax_t)a->end)); 120 KASSERT(b->start <= b->end, ("inverted entry %p (%jx, %jx)", 121 b, (uintmax_t)b->start, (uintmax_t)b->end)); 122 KASSERT(a->end <= b->start || b->end <= a->start || 123 a->end == a->start || b->end == b->start, 124 ("overlapping entries %p (%jx, %jx) %p (%jx, %jx)", 125 a, (uintmax_t)a->start, (uintmax_t)a->end, 126 b, (uintmax_t)b->start, (uintmax_t)b->end)); 127 128 if (a->end < b->end) 129 return (-1); 130 else if (b->end < a->end) 131 return (1); 132 return (0); 133} 134 135static void 136dmar_gas_augment_entry(struct dmar_map_entry *entry) 137{ 138 struct dmar_map_entry *l, *r; 139 140 for (; entry != NULL; entry = RB_PARENT(entry, rb_entry)) { 141 l = RB_LEFT(entry, rb_entry); 142 r = RB_RIGHT(entry, rb_entry); 143 if (l == NULL && r == NULL) { 144 entry->free_down = entry->free_after; 145 } else if (l == NULL && r != NULL) { 146 entry->free_down = MAX(entry->free_after, r->free_down); 147 } else if (/*l != NULL && */ r == NULL) { 148 entry->free_down = MAX(entry->free_after, l->free_down); 149 } else /* if (l != NULL && r != NULL) */ { 150 entry->free_down = MAX(entry->free_after, l->free_down); 151 entry->free_down = MAX(entry->free_down, r->free_down); 152 } 153 } 154} 155 156RB_GENERATE(dmar_gas_entries_tree, dmar_map_entry, rb_entry, 157 dmar_gas_cmp_entries); 158 159static void 160dmar_gas_fix_free(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 161{ 162 struct dmar_map_entry *next; 163 164 next = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry); 165 entry->free_after = (next != NULL ? next->start : ctx->end) - 166 entry->end; 167 dmar_gas_augment_entry(entry); 168} 169 170#ifdef INVARIANTS 171static void 172dmar_gas_check_free(struct dmar_ctx *ctx) 173{ 174 struct dmar_map_entry *entry, *next, *l, *r; 175 dmar_gaddr_t v; 176 177 RB_FOREACH(entry, dmar_gas_entries_tree, &ctx->rb_root) {
|
173 next = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry); 174 if (next == NULL) { 175 MPASS(entry->free_after == ctx->end - entry->end); 176 } else { 177 MPASS(entry->free_after = next->start - entry->end); 178 MPASS(entry->end <= next->start); 179 } 180 l = RB_LEFT(entry, rb_entry); 181 r = RB_RIGHT(entry, rb_entry); 182 if (l == NULL && r == NULL) { 183 MPASS(entry->free_down == entry->free_after); 184 } else if (l == NULL && r != NULL) { 185 MPASS(entry->free_down = MAX(entry->free_after, 186 r->free_down)); 187 } else if (r == NULL) { 188 MPASS(entry->free_down = MAX(entry->free_after, 189 l->free_down)); 190 } else { 191 v = MAX(entry->free_after, l->free_down); 192 v = MAX(entry->free_down, r->free_down); 193 MPASS(entry->free_down == v); 194 } 195 } 196} 197#endif 198 199static bool 200dmar_gas_rb_insert(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 201{ 202 struct dmar_map_entry *prev, *found; 203 204 found = RB_INSERT(dmar_gas_entries_tree, &ctx->rb_root, entry); 205 dmar_gas_fix_free(ctx, entry); 206 prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry); 207 if (prev != NULL) 208 dmar_gas_fix_free(ctx, prev); 209 return (found == NULL); 210} 211 212static void 213dmar_gas_rb_remove(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 214{ 215 struct dmar_map_entry *prev; 216 217 prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry); 218 RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry); 219 if (prev != NULL) 220 dmar_gas_fix_free(ctx, prev); 221} 222 223void 224dmar_gas_init_ctx(struct dmar_ctx *ctx) 225{ 226 struct dmar_map_entry *begin, *end; 227 228 begin = dmar_gas_alloc_entry(ctx, DMAR_PGF_WAITOK); 229 end = dmar_gas_alloc_entry(ctx, DMAR_PGF_WAITOK); 230 231 DMAR_CTX_LOCK(ctx); 232 KASSERT(ctx->entries_cnt == 2, ("dirty ctx %p", ctx)); 233 KASSERT(RB_EMPTY(&ctx->rb_root), ("non-empty entries %p", ctx)); 234 235 begin->start = 0; 236 begin->end = DMAR_PAGE_SIZE; 237 begin->free_after = ctx->end - begin->end; 238 begin->flags = DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_UNMAPPED; 239 dmar_gas_rb_insert(ctx, begin); 240 241 end->start = ctx->end; 242 end->end = ctx->end; 243 end->free_after = 0; 244 end->flags = DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_UNMAPPED; 245 dmar_gas_rb_insert(ctx, end); 246 247 ctx->first_place = begin; 248 ctx->last_place = end; 249 DMAR_CTX_UNLOCK(ctx); 250} 251 252void 253dmar_gas_fini_ctx(struct dmar_ctx *ctx) 254{ 255 struct dmar_map_entry *entry, *entry1; 256 257 DMAR_CTX_ASSERT_LOCKED(ctx); 258 KASSERT(ctx->entries_cnt == 2, ("ctx still in use %p", ctx)); 259 260 entry = RB_MIN(dmar_gas_entries_tree, &ctx->rb_root); 261 KASSERT(entry->start == 0, ("start entry start %p", ctx)); 262 KASSERT(entry->end == DMAR_PAGE_SIZE, ("start entry end %p", ctx)); 263 KASSERT(entry->flags == DMAR_MAP_ENTRY_PLACE, 264 ("start entry flags %p", ctx)); 265 RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry); 266 dmar_gas_free_entry(ctx, entry); 267 268 entry = RB_MAX(dmar_gas_entries_tree, &ctx->rb_root); 269 KASSERT(entry->start == ctx->end, ("end entry start %p", ctx)); 270 KASSERT(entry->end == ctx->end, ("end entry end %p", ctx)); 271 KASSERT(entry->free_after == 0, ("end entry free_after%p", ctx)); 272 KASSERT(entry->flags == DMAR_MAP_ENTRY_PLACE, 273 ("end entry flags %p", ctx)); 274 RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry); 275 dmar_gas_free_entry(ctx, entry); 276 277 RB_FOREACH_SAFE(entry, dmar_gas_entries_tree, &ctx->rb_root, entry1) { 278 KASSERT((entry->flags & DMAR_MAP_ENTRY_RMRR) != 0, 279 ("non-RMRR entry left %p", ctx)); 280 RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry); 281 dmar_gas_free_entry(ctx, entry); 282 } 283} 284 285struct dmar_gas_match_args { 286 struct dmar_ctx *ctx; 287 dmar_gaddr_t size; 288 const struct bus_dma_tag_common *common; 289 u_int gas_flags; 290 struct dmar_map_entry *entry; 291}; 292 293static bool 294dmar_gas_match_one(struct dmar_gas_match_args *a, struct dmar_map_entry *prev, 295 dmar_gaddr_t end) 296{ 297 dmar_gaddr_t bs, start; 298 299 if (a->entry->start + a->size > end) 300 return (false); 301 302 /* DMAR_PAGE_SIZE to create gap after new entry. */ 303 if (a->entry->start < prev->end + DMAR_PAGE_SIZE || 304 a->entry->start + a->size + DMAR_PAGE_SIZE > prev->end + 305 prev->free_after) 306 return (false); 307 308 /* No boundary crossing. */ 309 if (dmar_test_boundary(a->entry->start, a->size, a->common->boundary)) 310 return (true); 311 312 /* 313 * The start to start + size region crosses the boundary. 314 * Check if there is enough space after the next boundary 315 * after the prev->end. 316 */ 317 bs = (a->entry->start + a->common->boundary) & ~(a->common->boundary 318 - 1); 319 start = roundup2(bs, a->common->alignment); 320 /* DMAR_PAGE_SIZE to create gap after new entry. */ 321 if (start + a->size + DMAR_PAGE_SIZE <= prev->end + prev->free_after && 322 start + a->size <= end) { 323 a->entry->start = start; 324 return (true); 325 } 326 327 /* 328 * Not enough space to align at boundary, but allowed to split. 329 * We already checked that start + size does not overlap end. 330 * 331 * XXXKIB. It is possible that bs is exactly at the start of 332 * the next entry, then we do not have gap. Ignore for now. 333 */ 334 if ((a->gas_flags & DMAR_GM_CANSPLIT) != 0) { 335 a->size = bs - a->entry->start; 336 return (true); 337 } 338 339 return (false); 340} 341 342static void 343dmar_gas_match_insert(struct dmar_gas_match_args *a, 344 struct dmar_map_entry *prev) 345{ 346 struct dmar_map_entry *next; 347 bool found; 348 349 /* 350 * The prev->end is always aligned on the page size, which 351 * causes page alignment for the entry->start too. The size 352 * is checked to be multiple of the page size. 353 * 354 * The page sized gap is created between consequent 355 * allocations to ensure that out-of-bounds accesses fault. 356 */ 357 a->entry->end = a->entry->start + a->size; 358 359 next = RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, prev); 360 KASSERT(next->start >= a->entry->end && 361 next->start - a->entry->start >= a->size, 362 ("dmar_gas_match_insert hole failed %p prev (%jx, %jx) " 363 "free_after %jx next (%jx, %jx) entry (%jx, %jx)", a->ctx, 364 (uintmax_t)prev->start, (uintmax_t)prev->end, 365 (uintmax_t)prev->free_after, 366 (uintmax_t)next->start, (uintmax_t)next->end, 367 (uintmax_t)a->entry->start, (uintmax_t)a->entry->end)); 368 369 prev->free_after = a->entry->start - prev->end; 370 a->entry->free_after = next->start - a->entry->end; 371 372 found = dmar_gas_rb_insert(a->ctx, a->entry); 373 KASSERT(found, ("found dup %p start %jx size %jx", 374 a->ctx, (uintmax_t)a->entry->start, (uintmax_t)a->size)); 375 a->entry->flags = DMAR_MAP_ENTRY_MAP; 376 377 KASSERT(RB_PREV(dmar_gas_entries_tree, &a->ctx->rb_root, 378 a->entry) == prev, 379 ("entry %p prev %p inserted prev %p", a->entry, prev, 380 RB_PREV(dmar_gas_entries_tree, &a->ctx->rb_root, a->entry))); 381 KASSERT(RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, 382 a->entry) == next, 383 ("entry %p next %p inserted next %p", a->entry, next, 384 RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, a->entry))); 385} 386 387static int 388dmar_gas_lowermatch(struct dmar_gas_match_args *a, struct dmar_map_entry *prev) 389{ 390 struct dmar_map_entry *l; 391 int ret; 392 393 if (prev->end < a->common->lowaddr) { 394 a->entry->start = roundup2(prev->end + DMAR_PAGE_SIZE, 395 a->common->alignment); 396 if (dmar_gas_match_one(a, prev, a->common->lowaddr)) { 397 dmar_gas_match_insert(a, prev); 398 return (0); 399 } 400 } 401 if (prev->free_down < a->size + DMAR_PAGE_SIZE) 402 return (ENOMEM); 403 l = RB_LEFT(prev, rb_entry); 404 if (l != NULL) { 405 ret = dmar_gas_lowermatch(a, l); 406 if (ret == 0) 407 return (0); 408 } 409 l = RB_RIGHT(prev, rb_entry); 410 if (l != NULL) 411 return (dmar_gas_lowermatch(a, l)); 412 return (ENOMEM); 413} 414 415static int 416dmar_gas_uppermatch(struct dmar_gas_match_args *a) 417{ 418 struct dmar_map_entry *next, *prev, find_entry; 419 420 find_entry.start = a->common->highaddr; 421 next = RB_NFIND(dmar_gas_entries_tree, &a->ctx->rb_root, &find_entry); 422 if (next == NULL) 423 return (ENOMEM); 424 prev = RB_PREV(dmar_gas_entries_tree, &a->ctx->rb_root, next); 425 KASSERT(prev != NULL, ("no prev %p %jx", a->ctx, 426 (uintmax_t)find_entry.start)); 427 for (;;) { 428 a->entry->start = prev->start + DMAR_PAGE_SIZE; 429 if (a->entry->start < a->common->highaddr) 430 a->entry->start = a->common->highaddr; 431 a->entry->start = roundup2(a->entry->start, 432 a->common->alignment); 433 if (dmar_gas_match_one(a, prev, a->ctx->end)) { 434 dmar_gas_match_insert(a, prev); 435 return (0); 436 } 437 438 /* 439 * XXXKIB. This falls back to linear iteration over 440 * the free space in the high region. But high 441 * regions are almost unused, the code should be 442 * enough to cover the case, although in the 443 * non-optimal way. 444 */ 445 prev = next; 446 next = RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, prev); 447 KASSERT(next != NULL, ("no next %p %jx", a->ctx, 448 (uintmax_t)find_entry.start)); 449 if (next->end >= a->ctx->end) 450 return (ENOMEM); 451 } 452} 453 454static int 455dmar_gas_find_space(struct dmar_ctx *ctx, 456 const struct bus_dma_tag_common *common, dmar_gaddr_t size, 457 u_int flags, struct dmar_map_entry *entry) 458{ 459 struct dmar_gas_match_args a; 460 int error; 461 462 DMAR_CTX_ASSERT_LOCKED(ctx); 463 KASSERT(entry->flags == 0, ("dirty entry %p %p", ctx, entry)); 464 KASSERT((size & DMAR_PAGE_MASK) == 0, ("size %jx", (uintmax_t)size)); 465 466 a.ctx = ctx; 467 a.size = size; 468 a.common = common; 469 a.gas_flags = flags; 470 a.entry = entry; 471 472 /* Handle lower region. */ 473 if (common->lowaddr > 0) { 474 error = dmar_gas_lowermatch(&a, RB_ROOT(&ctx->rb_root)); 475 if (error == 0) 476 return (0); 477 KASSERT(error == ENOMEM, 478 ("error %d from dmar_gas_lowermatch", error)); 479 } 480 /* Handle upper region. */ 481 if (common->highaddr >= ctx->end) 482 return (ENOMEM); 483 error = dmar_gas_uppermatch(&a); 484 KASSERT(error == ENOMEM, 485 ("error %d from dmar_gas_uppermatch", error)); 486 return (error); 487} 488 489static int 490dmar_gas_alloc_region(struct dmar_ctx *ctx, struct dmar_map_entry *entry, 491 u_int flags) 492{ 493 struct dmar_map_entry *next, *prev; 494 bool found; 495 496 DMAR_CTX_ASSERT_LOCKED(ctx); 497 498 if ((entry->start & DMAR_PAGE_MASK) != 0 || 499 (entry->end & DMAR_PAGE_MASK) != 0) 500 return (EINVAL); 501 if (entry->start >= entry->end) 502 return (EINVAL); 503 if (entry->end >= ctx->end) 504 return (EINVAL); 505 506 next = RB_NFIND(dmar_gas_entries_tree, &ctx->rb_root, entry); 507 KASSERT(next != NULL, ("next must be non-null %p %jx", ctx, 508 (uintmax_t)entry->start)); 509 prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, next); 510 /* prev could be NULL */ 511 512 /* 513 * Adapt to broken BIOSes which specify overlapping RMRR 514 * entries. 515 * 516 * XXXKIB: this does not handle a case when prev or next 517 * entries are completely covered by the current one, which 518 * extends both ways. 519 */ 520 if (prev != NULL && prev->end > entry->start && 521 (prev->flags & DMAR_MAP_ENTRY_PLACE) == 0) { 522 if ((prev->flags & DMAR_MAP_ENTRY_RMRR) == 0) 523 return (EBUSY); 524 entry->start = prev->end; 525 } 526 if (next != NULL && next->start < entry->end && 527 (next->flags & DMAR_MAP_ENTRY_PLACE) == 0) { 528 if ((next->flags & DMAR_MAP_ENTRY_RMRR) == 0) 529 return (EBUSY); 530 entry->end = next->start; 531 } 532 if (entry->end == entry->start) 533 return (0); 534 535 if (prev != NULL && prev->end > entry->start) { 536 /* This assumes that prev is the placeholder entry. */ 537 dmar_gas_rb_remove(ctx, prev); 538 prev = NULL; 539 } 540 if (next != NULL && next->start < entry->end) { 541 dmar_gas_rb_remove(ctx, next); 542 next = NULL; 543 } 544 545 found = dmar_gas_rb_insert(ctx, entry); 546 KASSERT(found, ("found RMRR dup %p start %jx end %jx", 547 ctx, (uintmax_t)entry->start, (uintmax_t)entry->end)); 548 entry->flags = DMAR_MAP_ENTRY_RMRR; 549 550#ifdef INVARIANTS 551 struct dmar_map_entry *ip, *in; 552 ip = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry); 553 in = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry); 554 KASSERT(prev == NULL || ip == prev, 555 ("RMRR %p (%jx %jx) prev %p (%jx %jx) ins prev %p (%jx %jx)", 556 entry, entry->start, entry->end, prev, 557 prev == NULL ? 0 : prev->start, prev == NULL ? 0 : prev->end, 558 ip, ip == NULL ? 0 : ip->start, ip == NULL ? 0 : ip->end)); 559 KASSERT(next == NULL || in == next, 560 ("RMRR %p (%jx %jx) next %p (%jx %jx) ins next %p (%jx %jx)", 561 entry, entry->start, entry->end, next, 562 next == NULL ? 0 : next->start, next == NULL ? 0 : next->end, 563 in, in == NULL ? 0 : in->start, in == NULL ? 0 : in->end)); 564#endif 565 566 return (0); 567} 568 569void 570dmar_gas_free_space(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 571{ 572 573 DMAR_CTX_ASSERT_LOCKED(ctx); 574 KASSERT((entry->flags & (DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_RMRR | 575 DMAR_MAP_ENTRY_MAP)) == DMAR_MAP_ENTRY_MAP, 576 ("permanent entry %p %p", ctx, entry)); 577 578 dmar_gas_rb_remove(ctx, entry); 579 entry->flags &= ~DMAR_MAP_ENTRY_MAP; 580#ifdef INVARIANTS 581 if (dmar_check_free) 582 dmar_gas_check_free(ctx); 583#endif 584} 585
| 181 next = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry); 182 if (next == NULL) { 183 MPASS(entry->free_after == ctx->end - entry->end); 184 } else { 185 MPASS(entry->free_after = next->start - entry->end); 186 MPASS(entry->end <= next->start); 187 } 188 l = RB_LEFT(entry, rb_entry); 189 r = RB_RIGHT(entry, rb_entry); 190 if (l == NULL && r == NULL) { 191 MPASS(entry->free_down == entry->free_after); 192 } else if (l == NULL && r != NULL) { 193 MPASS(entry->free_down = MAX(entry->free_after, 194 r->free_down)); 195 } else if (r == NULL) { 196 MPASS(entry->free_down = MAX(entry->free_after, 197 l->free_down)); 198 } else { 199 v = MAX(entry->free_after, l->free_down); 200 v = MAX(entry->free_down, r->free_down); 201 MPASS(entry->free_down == v); 202 } 203 } 204} 205#endif 206 207static bool 208dmar_gas_rb_insert(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 209{ 210 struct dmar_map_entry *prev, *found; 211 212 found = RB_INSERT(dmar_gas_entries_tree, &ctx->rb_root, entry); 213 dmar_gas_fix_free(ctx, entry); 214 prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry); 215 if (prev != NULL) 216 dmar_gas_fix_free(ctx, prev); 217 return (found == NULL); 218} 219 220static void 221dmar_gas_rb_remove(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 222{ 223 struct dmar_map_entry *prev; 224 225 prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry); 226 RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry); 227 if (prev != NULL) 228 dmar_gas_fix_free(ctx, prev); 229} 230 231void 232dmar_gas_init_ctx(struct dmar_ctx *ctx) 233{ 234 struct dmar_map_entry *begin, *end; 235 236 begin = dmar_gas_alloc_entry(ctx, DMAR_PGF_WAITOK); 237 end = dmar_gas_alloc_entry(ctx, DMAR_PGF_WAITOK); 238 239 DMAR_CTX_LOCK(ctx); 240 KASSERT(ctx->entries_cnt == 2, ("dirty ctx %p", ctx)); 241 KASSERT(RB_EMPTY(&ctx->rb_root), ("non-empty entries %p", ctx)); 242 243 begin->start = 0; 244 begin->end = DMAR_PAGE_SIZE; 245 begin->free_after = ctx->end - begin->end; 246 begin->flags = DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_UNMAPPED; 247 dmar_gas_rb_insert(ctx, begin); 248 249 end->start = ctx->end; 250 end->end = ctx->end; 251 end->free_after = 0; 252 end->flags = DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_UNMAPPED; 253 dmar_gas_rb_insert(ctx, end); 254 255 ctx->first_place = begin; 256 ctx->last_place = end; 257 DMAR_CTX_UNLOCK(ctx); 258} 259 260void 261dmar_gas_fini_ctx(struct dmar_ctx *ctx) 262{ 263 struct dmar_map_entry *entry, *entry1; 264 265 DMAR_CTX_ASSERT_LOCKED(ctx); 266 KASSERT(ctx->entries_cnt == 2, ("ctx still in use %p", ctx)); 267 268 entry = RB_MIN(dmar_gas_entries_tree, &ctx->rb_root); 269 KASSERT(entry->start == 0, ("start entry start %p", ctx)); 270 KASSERT(entry->end == DMAR_PAGE_SIZE, ("start entry end %p", ctx)); 271 KASSERT(entry->flags == DMAR_MAP_ENTRY_PLACE, 272 ("start entry flags %p", ctx)); 273 RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry); 274 dmar_gas_free_entry(ctx, entry); 275 276 entry = RB_MAX(dmar_gas_entries_tree, &ctx->rb_root); 277 KASSERT(entry->start == ctx->end, ("end entry start %p", ctx)); 278 KASSERT(entry->end == ctx->end, ("end entry end %p", ctx)); 279 KASSERT(entry->free_after == 0, ("end entry free_after%p", ctx)); 280 KASSERT(entry->flags == DMAR_MAP_ENTRY_PLACE, 281 ("end entry flags %p", ctx)); 282 RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry); 283 dmar_gas_free_entry(ctx, entry); 284 285 RB_FOREACH_SAFE(entry, dmar_gas_entries_tree, &ctx->rb_root, entry1) { 286 KASSERT((entry->flags & DMAR_MAP_ENTRY_RMRR) != 0, 287 ("non-RMRR entry left %p", ctx)); 288 RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry); 289 dmar_gas_free_entry(ctx, entry); 290 } 291} 292 293struct dmar_gas_match_args { 294 struct dmar_ctx *ctx; 295 dmar_gaddr_t size; 296 const struct bus_dma_tag_common *common; 297 u_int gas_flags; 298 struct dmar_map_entry *entry; 299}; 300 301static bool 302dmar_gas_match_one(struct dmar_gas_match_args *a, struct dmar_map_entry *prev, 303 dmar_gaddr_t end) 304{ 305 dmar_gaddr_t bs, start; 306 307 if (a->entry->start + a->size > end) 308 return (false); 309 310 /* DMAR_PAGE_SIZE to create gap after new entry. */ 311 if (a->entry->start < prev->end + DMAR_PAGE_SIZE || 312 a->entry->start + a->size + DMAR_PAGE_SIZE > prev->end + 313 prev->free_after) 314 return (false); 315 316 /* No boundary crossing. */ 317 if (dmar_test_boundary(a->entry->start, a->size, a->common->boundary)) 318 return (true); 319 320 /* 321 * The start to start + size region crosses the boundary. 322 * Check if there is enough space after the next boundary 323 * after the prev->end. 324 */ 325 bs = (a->entry->start + a->common->boundary) & ~(a->common->boundary 326 - 1); 327 start = roundup2(bs, a->common->alignment); 328 /* DMAR_PAGE_SIZE to create gap after new entry. */ 329 if (start + a->size + DMAR_PAGE_SIZE <= prev->end + prev->free_after && 330 start + a->size <= end) { 331 a->entry->start = start; 332 return (true); 333 } 334 335 /* 336 * Not enough space to align at boundary, but allowed to split. 337 * We already checked that start + size does not overlap end. 338 * 339 * XXXKIB. It is possible that bs is exactly at the start of 340 * the next entry, then we do not have gap. Ignore for now. 341 */ 342 if ((a->gas_flags & DMAR_GM_CANSPLIT) != 0) { 343 a->size = bs - a->entry->start; 344 return (true); 345 } 346 347 return (false); 348} 349 350static void 351dmar_gas_match_insert(struct dmar_gas_match_args *a, 352 struct dmar_map_entry *prev) 353{ 354 struct dmar_map_entry *next; 355 bool found; 356 357 /* 358 * The prev->end is always aligned on the page size, which 359 * causes page alignment for the entry->start too. The size 360 * is checked to be multiple of the page size. 361 * 362 * The page sized gap is created between consequent 363 * allocations to ensure that out-of-bounds accesses fault. 364 */ 365 a->entry->end = a->entry->start + a->size; 366 367 next = RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, prev); 368 KASSERT(next->start >= a->entry->end && 369 next->start - a->entry->start >= a->size, 370 ("dmar_gas_match_insert hole failed %p prev (%jx, %jx) " 371 "free_after %jx next (%jx, %jx) entry (%jx, %jx)", a->ctx, 372 (uintmax_t)prev->start, (uintmax_t)prev->end, 373 (uintmax_t)prev->free_after, 374 (uintmax_t)next->start, (uintmax_t)next->end, 375 (uintmax_t)a->entry->start, (uintmax_t)a->entry->end)); 376 377 prev->free_after = a->entry->start - prev->end; 378 a->entry->free_after = next->start - a->entry->end; 379 380 found = dmar_gas_rb_insert(a->ctx, a->entry); 381 KASSERT(found, ("found dup %p start %jx size %jx", 382 a->ctx, (uintmax_t)a->entry->start, (uintmax_t)a->size)); 383 a->entry->flags = DMAR_MAP_ENTRY_MAP; 384 385 KASSERT(RB_PREV(dmar_gas_entries_tree, &a->ctx->rb_root, 386 a->entry) == prev, 387 ("entry %p prev %p inserted prev %p", a->entry, prev, 388 RB_PREV(dmar_gas_entries_tree, &a->ctx->rb_root, a->entry))); 389 KASSERT(RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, 390 a->entry) == next, 391 ("entry %p next %p inserted next %p", a->entry, next, 392 RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, a->entry))); 393} 394 395static int 396dmar_gas_lowermatch(struct dmar_gas_match_args *a, struct dmar_map_entry *prev) 397{ 398 struct dmar_map_entry *l; 399 int ret; 400 401 if (prev->end < a->common->lowaddr) { 402 a->entry->start = roundup2(prev->end + DMAR_PAGE_SIZE, 403 a->common->alignment); 404 if (dmar_gas_match_one(a, prev, a->common->lowaddr)) { 405 dmar_gas_match_insert(a, prev); 406 return (0); 407 } 408 } 409 if (prev->free_down < a->size + DMAR_PAGE_SIZE) 410 return (ENOMEM); 411 l = RB_LEFT(prev, rb_entry); 412 if (l != NULL) { 413 ret = dmar_gas_lowermatch(a, l); 414 if (ret == 0) 415 return (0); 416 } 417 l = RB_RIGHT(prev, rb_entry); 418 if (l != NULL) 419 return (dmar_gas_lowermatch(a, l)); 420 return (ENOMEM); 421} 422 423static int 424dmar_gas_uppermatch(struct dmar_gas_match_args *a) 425{ 426 struct dmar_map_entry *next, *prev, find_entry; 427 428 find_entry.start = a->common->highaddr; 429 next = RB_NFIND(dmar_gas_entries_tree, &a->ctx->rb_root, &find_entry); 430 if (next == NULL) 431 return (ENOMEM); 432 prev = RB_PREV(dmar_gas_entries_tree, &a->ctx->rb_root, next); 433 KASSERT(prev != NULL, ("no prev %p %jx", a->ctx, 434 (uintmax_t)find_entry.start)); 435 for (;;) { 436 a->entry->start = prev->start + DMAR_PAGE_SIZE; 437 if (a->entry->start < a->common->highaddr) 438 a->entry->start = a->common->highaddr; 439 a->entry->start = roundup2(a->entry->start, 440 a->common->alignment); 441 if (dmar_gas_match_one(a, prev, a->ctx->end)) { 442 dmar_gas_match_insert(a, prev); 443 return (0); 444 } 445 446 /* 447 * XXXKIB. This falls back to linear iteration over 448 * the free space in the high region. But high 449 * regions are almost unused, the code should be 450 * enough to cover the case, although in the 451 * non-optimal way. 452 */ 453 prev = next; 454 next = RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, prev); 455 KASSERT(next != NULL, ("no next %p %jx", a->ctx, 456 (uintmax_t)find_entry.start)); 457 if (next->end >= a->ctx->end) 458 return (ENOMEM); 459 } 460} 461 462static int 463dmar_gas_find_space(struct dmar_ctx *ctx, 464 const struct bus_dma_tag_common *common, dmar_gaddr_t size, 465 u_int flags, struct dmar_map_entry *entry) 466{ 467 struct dmar_gas_match_args a; 468 int error; 469 470 DMAR_CTX_ASSERT_LOCKED(ctx); 471 KASSERT(entry->flags == 0, ("dirty entry %p %p", ctx, entry)); 472 KASSERT((size & DMAR_PAGE_MASK) == 0, ("size %jx", (uintmax_t)size)); 473 474 a.ctx = ctx; 475 a.size = size; 476 a.common = common; 477 a.gas_flags = flags; 478 a.entry = entry; 479 480 /* Handle lower region. */ 481 if (common->lowaddr > 0) { 482 error = dmar_gas_lowermatch(&a, RB_ROOT(&ctx->rb_root)); 483 if (error == 0) 484 return (0); 485 KASSERT(error == ENOMEM, 486 ("error %d from dmar_gas_lowermatch", error)); 487 } 488 /* Handle upper region. */ 489 if (common->highaddr >= ctx->end) 490 return (ENOMEM); 491 error = dmar_gas_uppermatch(&a); 492 KASSERT(error == ENOMEM, 493 ("error %d from dmar_gas_uppermatch", error)); 494 return (error); 495} 496 497static int 498dmar_gas_alloc_region(struct dmar_ctx *ctx, struct dmar_map_entry *entry, 499 u_int flags) 500{ 501 struct dmar_map_entry *next, *prev; 502 bool found; 503 504 DMAR_CTX_ASSERT_LOCKED(ctx); 505 506 if ((entry->start & DMAR_PAGE_MASK) != 0 || 507 (entry->end & DMAR_PAGE_MASK) != 0) 508 return (EINVAL); 509 if (entry->start >= entry->end) 510 return (EINVAL); 511 if (entry->end >= ctx->end) 512 return (EINVAL); 513 514 next = RB_NFIND(dmar_gas_entries_tree, &ctx->rb_root, entry); 515 KASSERT(next != NULL, ("next must be non-null %p %jx", ctx, 516 (uintmax_t)entry->start)); 517 prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, next); 518 /* prev could be NULL */ 519 520 /* 521 * Adapt to broken BIOSes which specify overlapping RMRR 522 * entries. 523 * 524 * XXXKIB: this does not handle a case when prev or next 525 * entries are completely covered by the current one, which 526 * extends both ways. 527 */ 528 if (prev != NULL && prev->end > entry->start && 529 (prev->flags & DMAR_MAP_ENTRY_PLACE) == 0) { 530 if ((prev->flags & DMAR_MAP_ENTRY_RMRR) == 0) 531 return (EBUSY); 532 entry->start = prev->end; 533 } 534 if (next != NULL && next->start < entry->end && 535 (next->flags & DMAR_MAP_ENTRY_PLACE) == 0) { 536 if ((next->flags & DMAR_MAP_ENTRY_RMRR) == 0) 537 return (EBUSY); 538 entry->end = next->start; 539 } 540 if (entry->end == entry->start) 541 return (0); 542 543 if (prev != NULL && prev->end > entry->start) { 544 /* This assumes that prev is the placeholder entry. */ 545 dmar_gas_rb_remove(ctx, prev); 546 prev = NULL; 547 } 548 if (next != NULL && next->start < entry->end) { 549 dmar_gas_rb_remove(ctx, next); 550 next = NULL; 551 } 552 553 found = dmar_gas_rb_insert(ctx, entry); 554 KASSERT(found, ("found RMRR dup %p start %jx end %jx", 555 ctx, (uintmax_t)entry->start, (uintmax_t)entry->end)); 556 entry->flags = DMAR_MAP_ENTRY_RMRR; 557 558#ifdef INVARIANTS 559 struct dmar_map_entry *ip, *in; 560 ip = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry); 561 in = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry); 562 KASSERT(prev == NULL || ip == prev, 563 ("RMRR %p (%jx %jx) prev %p (%jx %jx) ins prev %p (%jx %jx)", 564 entry, entry->start, entry->end, prev, 565 prev == NULL ? 0 : prev->start, prev == NULL ? 0 : prev->end, 566 ip, ip == NULL ? 0 : ip->start, ip == NULL ? 0 : ip->end)); 567 KASSERT(next == NULL || in == next, 568 ("RMRR %p (%jx %jx) next %p (%jx %jx) ins next %p (%jx %jx)", 569 entry, entry->start, entry->end, next, 570 next == NULL ? 0 : next->start, next == NULL ? 0 : next->end, 571 in, in == NULL ? 0 : in->start, in == NULL ? 0 : in->end)); 572#endif 573 574 return (0); 575} 576 577void 578dmar_gas_free_space(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 579{ 580 581 DMAR_CTX_ASSERT_LOCKED(ctx); 582 KASSERT((entry->flags & (DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_RMRR | 583 DMAR_MAP_ENTRY_MAP)) == DMAR_MAP_ENTRY_MAP, 584 ("permanent entry %p %p", ctx, entry)); 585 586 dmar_gas_rb_remove(ctx, entry); 587 entry->flags &= ~DMAR_MAP_ENTRY_MAP; 588#ifdef INVARIANTS 589 if (dmar_check_free) 590 dmar_gas_check_free(ctx); 591#endif 592} 593
|
587dmar_gas_free_region(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 588{ 589 struct dmar_map_entry *next, *prev; 590 591 DMAR_CTX_ASSERT_LOCKED(ctx); 592 KASSERT((entry->flags & (DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_RMRR | 593 DMAR_MAP_ENTRY_MAP)) == DMAR_MAP_ENTRY_RMRR, 594 ("non-RMRR entry %p %p", ctx, entry)); 595 596 prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry); 597 next = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry); 598 dmar_gas_rb_remove(ctx, entry); 599 entry->flags &= ~DMAR_MAP_ENTRY_RMRR; 600 601 if (prev == NULL) 602 dmar_gas_rb_insert(ctx, ctx->first_place); 603 if (next == NULL) 604 dmar_gas_rb_insert(ctx, ctx->last_place); 605} 606 607int 608dmar_gas_map(struct dmar_ctx *ctx, const struct bus_dma_tag_common *common, 609 dmar_gaddr_t size, u_int eflags, u_int flags, vm_page_t *ma, 610 struct dmar_map_entry **res) 611{ 612 struct dmar_map_entry *entry; 613 int error; 614 615 KASSERT((flags & ~(DMAR_GM_CANWAIT | DMAR_GM_CANSPLIT)) == 0, 616 ("invalid flags 0x%x", flags)); 617 618 entry = dmar_gas_alloc_entry(ctx, (flags & DMAR_GM_CANWAIT) != 0 ? 619 DMAR_PGF_WAITOK : 0); 620 if (entry == NULL) 621 return (ENOMEM); 622 DMAR_CTX_LOCK(ctx); 623 error = dmar_gas_find_space(ctx, common, size, flags, entry); 624 if (error == ENOMEM) { 625 DMAR_CTX_UNLOCK(ctx); 626 dmar_gas_free_entry(ctx, entry); 627 return (error); 628 } 629#ifdef INVARIANTS 630 if (dmar_check_free) 631 dmar_gas_check_free(ctx); 632#endif 633 KASSERT(error == 0, 634 ("unexpected error %d from dmar_gas_find_entry", error)); 635 KASSERT(entry->end < ctx->end, ("allocated GPA %jx, max GPA %jx", 636 (uintmax_t)entry->end, (uintmax_t)ctx->end)); 637 entry->flags |= eflags; 638 DMAR_CTX_UNLOCK(ctx); 639 640 error = ctx_map_buf(ctx, entry->start, size, ma, 641 ((eflags & DMAR_MAP_ENTRY_READ) != 0 ? DMAR_PTE_R : 0) | 642 ((eflags & DMAR_MAP_ENTRY_WRITE) != 0 ? DMAR_PTE_W : 0) | 643 ((eflags & DMAR_MAP_ENTRY_SNOOP) != 0 ? DMAR_PTE_SNP : 0) | 644 ((eflags & DMAR_MAP_ENTRY_TM) != 0 ? DMAR_PTE_TM : 0), 645 (flags & DMAR_GM_CANWAIT) != 0 ? DMAR_PGF_WAITOK : 0); 646 if (error == ENOMEM) {
| 595dmar_gas_free_region(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 596{ 597 struct dmar_map_entry *next, *prev; 598 599 DMAR_CTX_ASSERT_LOCKED(ctx); 600 KASSERT((entry->flags & (DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_RMRR | 601 DMAR_MAP_ENTRY_MAP)) == DMAR_MAP_ENTRY_RMRR, 602 ("non-RMRR entry %p %p", ctx, entry)); 603 604 prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry); 605 next = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry); 606 dmar_gas_rb_remove(ctx, entry); 607 entry->flags &= ~DMAR_MAP_ENTRY_RMRR; 608 609 if (prev == NULL) 610 dmar_gas_rb_insert(ctx, ctx->first_place); 611 if (next == NULL) 612 dmar_gas_rb_insert(ctx, ctx->last_place); 613} 614 615int 616dmar_gas_map(struct dmar_ctx *ctx, const struct bus_dma_tag_common *common, 617 dmar_gaddr_t size, u_int eflags, u_int flags, vm_page_t *ma, 618 struct dmar_map_entry **res) 619{ 620 struct dmar_map_entry *entry; 621 int error; 622 623 KASSERT((flags & ~(DMAR_GM_CANWAIT | DMAR_GM_CANSPLIT)) == 0, 624 ("invalid flags 0x%x", flags)); 625 626 entry = dmar_gas_alloc_entry(ctx, (flags & DMAR_GM_CANWAIT) != 0 ? 627 DMAR_PGF_WAITOK : 0); 628 if (entry == NULL) 629 return (ENOMEM); 630 DMAR_CTX_LOCK(ctx); 631 error = dmar_gas_find_space(ctx, common, size, flags, entry); 632 if (error == ENOMEM) { 633 DMAR_CTX_UNLOCK(ctx); 634 dmar_gas_free_entry(ctx, entry); 635 return (error); 636 } 637#ifdef INVARIANTS 638 if (dmar_check_free) 639 dmar_gas_check_free(ctx); 640#endif 641 KASSERT(error == 0, 642 ("unexpected error %d from dmar_gas_find_entry", error)); 643 KASSERT(entry->end < ctx->end, ("allocated GPA %jx, max GPA %jx", 644 (uintmax_t)entry->end, (uintmax_t)ctx->end)); 645 entry->flags |= eflags; 646 DMAR_CTX_UNLOCK(ctx); 647 648 error = ctx_map_buf(ctx, entry->start, size, ma, 649 ((eflags & DMAR_MAP_ENTRY_READ) != 0 ? DMAR_PTE_R : 0) | 650 ((eflags & DMAR_MAP_ENTRY_WRITE) != 0 ? DMAR_PTE_W : 0) | 651 ((eflags & DMAR_MAP_ENTRY_SNOOP) != 0 ? DMAR_PTE_SNP : 0) | 652 ((eflags & DMAR_MAP_ENTRY_TM) != 0 ? DMAR_PTE_TM : 0), 653 (flags & DMAR_GM_CANWAIT) != 0 ? DMAR_PGF_WAITOK : 0); 654 if (error == ENOMEM) {
|