1/* 2 * tcm-sita.c 3 * 4 * SImple Tiler Allocator (SiTA): 2D and 1D allocation(reservation) algorithm 5 * 6 * Authors: Ravi Ramachandra <r.ramachandra@ti.com>, 7 * Lajos Molnar <molnar@ti.com> 8 * 9 * Copyright (C) 2009-2010 Texas Instruments, Inc. 10 * 11 * This package is free software; you can redistribute it and/or modify 12 * it under the terms of the GNU General Public License version 2 as 13 * published by the Free Software Foundation. 14 * 15 * THIS PACKAGE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 16 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 17 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. 18 * 19 */ 20#include <linux/slab.h> 21#include <linux/spinlock.h> 22 23#include "tcm-sita.h" 24 25#define ALIGN_DOWN(value, align) ((value) & ~((align) - 1)) 26 27/* Individual selection criteria for different scan areas */ 28static s32 CR_L2R_T2B = CR_BIAS_HORIZONTAL; 29static s32 CR_R2L_T2B = CR_DIAGONAL_BALANCE; 30 31/********************************************* 32 * TCM API - Sita Implementation 33 *********************************************/ 34static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u8 align, 35 struct tcm_area *area); 36static s32 sita_reserve_1d(struct tcm *tcm, u32 slots, struct tcm_area *area); 37static s32 sita_free(struct tcm *tcm, struct tcm_area *area); 38static void sita_deinit(struct tcm *tcm); 39 40/********************************************* 41 * Main Scanner functions 42 *********************************************/ 43static s32 scan_areas_and_find_fit(struct tcm *tcm, u16 w, u16 h, u16 align, 44 struct tcm_area *area); 45 46static s32 scan_l2r_t2b(struct tcm *tcm, u16 w, u16 h, u16 align, 47 struct tcm_area *field, struct tcm_area *area); 48 49static s32 scan_r2l_t2b(struct tcm *tcm, u16 w, u16 h, u16 align, 50 struct tcm_area *field, struct tcm_area *area); 51 52static s32 scan_r2l_b2t_one_dim(struct tcm *tcm, u32 num_slots, 53 struct tcm_area *field, struct tcm_area *area); 54 55/********************************************* 56 * Support Infrastructure Methods 57 *********************************************/ 58static s32 is_area_free(struct tcm_area ***map, u16 x0, u16 y0, u16 w, u16 h); 59 60static s32 update_candidate(struct tcm *tcm, u16 x0, u16 y0, u16 w, u16 h, 61 struct tcm_area *field, s32 criteria, 62 struct score *best); 63 64static void get_nearness_factor(struct tcm_area *field, 65 struct tcm_area *candidate, 66 struct nearness_factor *nf); 67 68static void get_neighbor_stats(struct tcm *tcm, struct tcm_area *area, 69 struct neighbor_stats *stat); 70 71static void fill_area(struct tcm *tcm, 72 struct tcm_area *area, struct tcm_area *parent); 73 74 75/*********************************************/ 76 77/********************************************* 78 * Utility Methods 79 *********************************************/ 80struct tcm *sita_init(u16 width, u16 height, struct tcm_pt *attr) 81{ 82 struct tcm *tcm; 83 struct sita_pvt *pvt; 84 struct tcm_area area = {0}; 85 s32 i; 86 87 if (width == 0 || height == 0) 88 return NULL; 89 90 tcm = kmalloc(sizeof(*tcm), GFP_KERNEL); 91 pvt = kmalloc(sizeof(*pvt), GFP_KERNEL); 92 if (!tcm || !pvt) 93 goto error; 94 95 memset(tcm, 0, sizeof(*tcm)); 96 memset(pvt, 0, sizeof(*pvt)); 97 98 /* Updating the pointers to SiTA implementation APIs */ 99 tcm->height = height; 100 tcm->width = width; 101 tcm->reserve_2d = sita_reserve_2d; 102 tcm->reserve_1d = sita_reserve_1d; 103 tcm->free = sita_free; 104 tcm->deinit = sita_deinit; 105 tcm->pvt = (void *)pvt; 106 107 spin_lock_init(&(pvt->lock)); 108 109 /* Creating tam map */ 110 pvt->map = kmalloc(sizeof(*pvt->map) * tcm->width, GFP_KERNEL); 111 if (!pvt->map) 112 goto error; 113 114 for (i = 0; i < tcm->width; i++) { 115 pvt->map[i] = 116 kmalloc(sizeof(**pvt->map) * tcm->height, 117 GFP_KERNEL); 118 if (pvt->map[i] == NULL) { 119 while (i--) 120 kfree(pvt->map[i]); 121 kfree(pvt->map); 122 goto error; 123 } 124 } 125 126 if (attr && attr->x <= tcm->width && attr->y <= tcm->height) { 127 pvt->div_pt.x = attr->x; 128 pvt->div_pt.y = attr->y; 129 130 } else { 131 /* Defaulting to 3:1 ratio on width for 2D area split */ 132 /* Defaulting to 3:1 ratio on height for 2D and 1D split */ 133 pvt->div_pt.x = (tcm->width * 3) / 4; 134 pvt->div_pt.y = (tcm->height * 3) / 4; 135 } 136 137 spin_lock(&(pvt->lock)); 138 assign(&area, 0, 0, width - 1, height - 1); 139 fill_area(tcm, &area, NULL); 140 spin_unlock(&(pvt->lock)); 141 return tcm; 142 143error: 144 kfree(tcm); 145 kfree(pvt); 146 return NULL; 147} 148 149static void sita_deinit(struct tcm *tcm) 150{ 151 struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 152 struct tcm_area area = {0}; 153 s32 i; 154 155 area.p1.x = tcm->width - 1; 156 area.p1.y = tcm->height - 1; 157 158 spin_lock(&(pvt->lock)); 159 fill_area(tcm, &area, NULL); 160 spin_unlock(&(pvt->lock)); 161 162 for (i = 0; i < tcm->height; i++) 163 kfree(pvt->map[i]); 164 kfree(pvt->map); 165 kfree(pvt); 166} 167 168/** 169 * Reserve a 1D area in the container 170 * 171 * @param num_slots size of 1D area 172 * @param area pointer to the area that will be populated with the 173 * reserved area 174 * 175 * @return 0 on success, non-0 error value on failure. 176 */ 177static s32 sita_reserve_1d(struct tcm *tcm, u32 num_slots, 178 struct tcm_area *area) 179{ 180 s32 ret; 181 struct tcm_area field = {0}; 182 struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 183 184 spin_lock(&(pvt->lock)); 185 186 /* Scanning entire container */ 187 assign(&field, tcm->width - 1, tcm->height - 1, 0, 0); 188 189 ret = scan_r2l_b2t_one_dim(tcm, num_slots, &field, area); 190 if (!ret) 191 /* update map */ 192 fill_area(tcm, area, area); 193 194 spin_unlock(&(pvt->lock)); 195 return ret; 196} 197 198/** 199 * Reserve a 2D area in the container 200 * 201 * @param w width 202 * @param h height 203 * @param area pointer to the area that will be populated with the reserved 204 * area 205 * 206 * @return 0 on success, non-0 error value on failure. 207 */ 208static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u8 align, 209 struct tcm_area *area) 210{ 211 s32 ret; 212 struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 213 214 /* not supporting more than 64 as alignment */ 215 if (align > 64) 216 return -EINVAL; 217 218 /* we prefer 1, 32 and 64 as alignment */ 219 align = align <= 1 ? 1 : align <= 32 ? 32 : 64; 220 221 spin_lock(&(pvt->lock)); 222 ret = scan_areas_and_find_fit(tcm, w, h, align, area); 223 if (!ret) 224 /* update map */ 225 fill_area(tcm, area, area); 226 227 spin_unlock(&(pvt->lock)); 228 return ret; 229} 230 231/** 232 * Unreserve a previously allocated 2D or 1D area 233 * @param area area to be freed 234 * @return 0 - success 235 */ 236static s32 sita_free(struct tcm *tcm, struct tcm_area *area) 237{ 238 struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 239 240 spin_lock(&(pvt->lock)); 241 242 /* check that this is in fact an existing area */ 243 WARN_ON(pvt->map[area->p0.x][area->p0.y] != area || 244 pvt->map[area->p1.x][area->p1.y] != area); 245 246 /* Clear the contents of the associated tiles in the map */ 247 fill_area(tcm, area, NULL); 248 249 spin_unlock(&(pvt->lock)); 250 251 return 0; 252} 253 254/** 255 * Note: In general the cordinates in the scan field area relevant to the can 256 * sweep directions. The scan origin (e.g. top-left corner) will always be 257 * the p0 member of the field. Therfore, for a scan from top-left p0.x <= p1.x 258 * and p0.y <= p1.y; whereas, for a scan from bottom-right p1.x <= p0.x and p1.y 259 * <= p0.y 260 */ 261 262/** 263 * Raster scan horizontally right to left from top to bottom to find a place for 264 * a 2D area of given size inside a scan field. 265 * 266 * @param w width of desired area 267 * @param h height of desired area 268 * @param align desired area alignment 269 * @param area pointer to the area that will be set to the best position 270 * @param field area to scan (inclusive) 271 * 272 * @return 0 on success, non-0 error value on failure. 273 */ 274static s32 scan_r2l_t2b(struct tcm *tcm, u16 w, u16 h, u16 align, 275 struct tcm_area *field, struct tcm_area *area) 276{ 277 s32 x, y; 278 s16 start_x, end_x, start_y, end_y, found_x = -1; 279 struct tcm_area ***map = ((struct sita_pvt *)tcm->pvt)->map; 280 struct score best = {{0}, {0}, {0}, 0}; 281 282 start_x = field->p0.x; 283 end_x = field->p1.x; 284 start_y = field->p0.y; 285 end_y = field->p1.y; 286 287 /* check scan area co-ordinates */ 288 if (field->p0.x < field->p1.x || 289 field->p1.y < field->p0.y) 290 return -EINVAL; 291 292 /* check if allocation would fit in scan area */ 293 if (w > LEN(start_x, end_x) || h > LEN(end_y, start_y)) 294 return -ENOSPC; 295 296 /* adjust start_x and end_y, as allocation would not fit beyond */ 297 start_x = ALIGN_DOWN(start_x - w + 1, align); /* - 1 to be inclusive */ 298 end_y = end_y - h + 1; 299 300 /* check if allocation would still fit in scan area */ 301 if (start_x < end_x) 302 return -ENOSPC; 303 304 /* scan field top-to-bottom, right-to-left */ 305 for (y = start_y; y <= end_y; y++) { 306 for (x = start_x; x >= end_x; x -= align) { 307 if (is_area_free(map, x, y, w, h)) { 308 found_x = x; 309 310 /* update best candidate */ 311 if (update_candidate(tcm, x, y, w, h, field, 312 CR_R2L_T2B, &best)) 313 goto done; 314 315 /* change upper x bound */ 316 end_x = x + 1; 317 break; 318 } else if (map[x][y] && map[x][y]->is2d) { 319 /* step over 2D areas */ 320 x = ALIGN(map[x][y]->p0.x - w + 1, align); 321 } 322 } 323 324 /* break if you find a free area shouldering the scan field */ 325 if (found_x == start_x) 326 break; 327 } 328 329 if (!best.a.tcm) 330 return -ENOSPC; 331done: 332 assign(area, best.a.p0.x, best.a.p0.y, best.a.p1.x, best.a.p1.y); 333 return 0; 334} 335 336/** 337 * Raster scan horizontally left to right from top to bottom to find a place for 338 * a 2D area of given size inside a scan field. 339 * 340 * @param w width of desired area 341 * @param h height of desired area 342 * @param align desired area alignment 343 * @param area pointer to the area that will be set to the best position 344 * @param field area to scan (inclusive) 345 * 346 * @return 0 on success, non-0 error value on failure. 347 */ 348static s32 scan_l2r_t2b(struct tcm *tcm, u16 w, u16 h, u16 align, 349 struct tcm_area *field, struct tcm_area *area) 350{ 351 s32 x, y; 352 s16 start_x, end_x, start_y, end_y, found_x = -1; 353 struct tcm_area ***map = ((struct sita_pvt *)tcm->pvt)->map; 354 struct score best = {{0}, {0}, {0}, 0}; 355 356 start_x = field->p0.x; 357 end_x = field->p1.x; 358 start_y = field->p0.y; 359 end_y = field->p1.y; 360 361 /* check scan area co-ordinates */ 362 if (field->p1.x < field->p0.x || 363 field->p1.y < field->p0.y) 364 return -EINVAL; 365 366 /* check if allocation would fit in scan area */ 367 if (w > LEN(end_x, start_x) || h > LEN(end_y, start_y)) 368 return -ENOSPC; 369 370 start_x = ALIGN(start_x, align); 371 372 /* check if allocation would still fit in scan area */ 373 if (w > LEN(end_x, start_x)) 374 return -ENOSPC; 375 376 /* adjust end_x and end_y, as allocation would not fit beyond */ 377 end_x = end_x - w + 1; /* + 1 to be inclusive */ 378 end_y = end_y - h + 1; 379 380 /* scan field top-to-bottom, left-to-right */ 381 for (y = start_y; y <= end_y; y++) { 382 for (x = start_x; x <= end_x; x += align) { 383 if (is_area_free(map, x, y, w, h)) { 384 found_x = x; 385 386 /* update best candidate */ 387 if (update_candidate(tcm, x, y, w, h, field, 388 CR_L2R_T2B, &best)) 389 goto done; 390 /* change upper x bound */ 391 end_x = x - 1; 392 393 break; 394 } else if (map[x][y] && map[x][y]->is2d) { 395 /* step over 2D areas */ 396 x = ALIGN_DOWN(map[x][y]->p1.x, align); 397 } 398 } 399 400 /* break if you find a free area shouldering the scan field */ 401 if (found_x == start_x) 402 break; 403 } 404 405 if (!best.a.tcm) 406 return -ENOSPC; 407done: 408 assign(area, best.a.p0.x, best.a.p0.y, best.a.p1.x, best.a.p1.y); 409 return 0; 410} 411 412/** 413 * Raster scan horizontally right to left from bottom to top to find a place 414 * for a 1D area of given size inside a scan field. 415 * 416 * @param num_slots size of desired area 417 * @param align desired area alignment 418 * @param area pointer to the area that will be set to the best 419 * position 420 * @param field area to scan (inclusive) 421 * 422 * @return 0 on success, non-0 error value on failure. 423 */ 424static s32 scan_r2l_b2t_one_dim(struct tcm *tcm, u32 num_slots, 425 struct tcm_area *field, struct tcm_area *area) 426{ 427 s32 found = 0; 428 s16 x, y; 429 struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 430 struct tcm_area *p; 431 432 /* check scan area co-ordinates */ 433 if (field->p0.y < field->p1.y) 434 return -EINVAL; 435 436 /** 437 * Currently we only support full width 1D scan field, which makes sense 438 * since 1D slot-ordering spans the full container width. 439 */ 440 if (tcm->width != field->p0.x - field->p1.x + 1) 441 return -EINVAL; 442 443 /* check if allocation would fit in scan area */ 444 if (num_slots > tcm->width * LEN(field->p0.y, field->p1.y)) 445 return -ENOSPC; 446 447 x = field->p0.x; 448 y = field->p0.y; 449 450 /* find num_slots consecutive free slots to the left */ 451 while (found < num_slots) { 452 if (y < 0) 453 return -ENOSPC; 454 455 /* remember bottom-right corner */ 456 if (found == 0) { 457 area->p1.x = x; 458 area->p1.y = y; 459 } 460 461 /* skip busy regions */ 462 p = pvt->map[x][y]; 463 if (p) { 464 /* move to left of 2D areas, top left of 1D */ 465 x = p->p0.x; 466 if (!p->is2d) 467 y = p->p0.y; 468 469 /* start over */ 470 found = 0; 471 } else { 472 /* count consecutive free slots */ 473 found++; 474 if (found == num_slots) 475 break; 476 } 477 478 /* move to the left */ 479 if (x == 0) 480 y--; 481 x = (x ? : tcm->width) - 1; 482 483 } 484 485 /* set top-left corner */ 486 area->p0.x = x; 487 area->p0.y = y; 488 return 0; 489} 490 491/** 492 * Find a place for a 2D area of given size inside a scan field based on its 493 * alignment needs. 494 * 495 * @param w width of desired area 496 * @param h height of desired area 497 * @param align desired area alignment 498 * @param area pointer to the area that will be set to the best position 499 * 500 * @return 0 on success, non-0 error value on failure. 501 */ 502static s32 scan_areas_and_find_fit(struct tcm *tcm, u16 w, u16 h, u16 align, 503 struct tcm_area *area) 504{ 505 s32 ret = 0; 506 struct tcm_area field = {0}; 507 u16 boundary_x, boundary_y; 508 struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 509 510 if (align > 1) { 511 /* prefer top-left corner */ 512 boundary_x = pvt->div_pt.x - 1; 513 boundary_y = pvt->div_pt.y - 1; 514 515 /* expand width and height if needed */ 516 if (w > pvt->div_pt.x) 517 boundary_x = tcm->width - 1; 518 if (h > pvt->div_pt.y) 519 boundary_y = tcm->height - 1; 520 521 assign(&field, 0, 0, boundary_x, boundary_y); 522 ret = scan_l2r_t2b(tcm, w, h, align, &field, area); 523 524 /* scan whole container if failed, but do not scan 2x */ 525 if (ret != 0 && (boundary_x != tcm->width - 1 || 526 boundary_y != tcm->height - 1)) { 527 /* scan the entire container if nothing found */ 528 assign(&field, 0, 0, tcm->width - 1, tcm->height - 1); 529 ret = scan_l2r_t2b(tcm, w, h, align, &field, area); 530 } 531 } else if (align == 1) { 532 /* prefer top-right corner */ 533 boundary_x = pvt->div_pt.x; 534 boundary_y = pvt->div_pt.y - 1; 535 536 /* expand width and height if needed */ 537 if (w > (tcm->width - pvt->div_pt.x)) 538 boundary_x = 0; 539 if (h > pvt->div_pt.y) 540 boundary_y = tcm->height - 1; 541 542 assign(&field, tcm->width - 1, 0, boundary_x, boundary_y); 543 ret = scan_r2l_t2b(tcm, w, h, align, &field, area); 544 545 /* scan whole container if failed, but do not scan 2x */ 546 if (ret != 0 && (boundary_x != 0 || 547 boundary_y != tcm->height - 1)) { 548 /* scan the entire container if nothing found */ 549 assign(&field, tcm->width - 1, 0, 0, tcm->height - 1); 550 ret = scan_r2l_t2b(tcm, w, h, align, &field, 551 area); 552 } 553 } 554 555 return ret; 556} 557 558/* check if an entire area is free */ 559static s32 is_area_free(struct tcm_area ***map, u16 x0, u16 y0, u16 w, u16 h) 560{ 561 u16 x = 0, y = 0; 562 for (y = y0; y < y0 + h; y++) { 563 for (x = x0; x < x0 + w; x++) { 564 if (map[x][y]) 565 return false; 566 } 567 } 568 return true; 569} 570 571/* fills an area with a parent tcm_area */ 572static void fill_area(struct tcm *tcm, struct tcm_area *area, 573 struct tcm_area *parent) 574{ 575 s32 x, y; 576 struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 577 struct tcm_area a, a_; 578 579 /* set area's tcm; otherwise, enumerator considers it invalid */ 580 area->tcm = tcm; 581 582 tcm_for_each_slice(a, *area, a_) { 583 for (x = a.p0.x; x <= a.p1.x; ++x) 584 for (y = a.p0.y; y <= a.p1.y; ++y) 585 pvt->map[x][y] = parent; 586 587 } 588} 589 590/** 591 * Compares a candidate area to the current best area, and if it is a better 592 * fit, it updates the best to this one. 593 * 594 * @param x0, y0, w, h top, left, width, height of candidate area 595 * @param field scan field 596 * @param criteria scan criteria 597 * @param best best candidate and its scores 598 * 599 * @return 1 (true) if the candidate area is known to be the final best, so no 600 * more searching should be performed 601 */ 602static s32 update_candidate(struct tcm *tcm, u16 x0, u16 y0, u16 w, u16 h, 603 struct tcm_area *field, s32 criteria, 604 struct score *best) 605{ 606 struct score me; /* score for area */ 607 608 /* 609 * NOTE: For horizontal bias we always give the first found, because our 610 * scan is horizontal-raster-based and the first candidate will always 611 * have the horizontal bias. 612 */ 613 bool first = criteria & CR_BIAS_HORIZONTAL; 614 615 assign(&me.a, x0, y0, x0 + w - 1, y0 + h - 1); 616 617 /* calculate score for current candidate */ 618 if (!first) { 619 get_neighbor_stats(tcm, &me.a, &me.n); 620 me.neighs = me.n.edge + me.n.busy; 621 get_nearness_factor(field, &me.a, &me.f); 622 } 623 624 /* the 1st candidate is always the best */ 625 if (!best->a.tcm) 626 goto better; 627 628 BUG_ON(first); 629 630 /* diagonal balance check */ 631 if ((criteria & CR_DIAGONAL_BALANCE) && 632 best->neighs <= me.neighs && 633 (best->neighs < me.neighs || 634 /* this implies that neighs and occupied match */ 635 best->n.busy < me.n.busy || 636 (best->n.busy == me.n.busy && 637 /* check the nearness factor */ 638 best->f.x + best->f.y > me.f.x + me.f.y))) 639 goto better; 640 641 /* not better, keep going */ 642 return 0; 643 644better: 645 /* save current area as best */ 646 memcpy(best, &me, sizeof(me)); 647 best->a.tcm = tcm; 648 return first; 649} 650 651/** 652 * Calculate the nearness factor of an area in a search field. The nearness 653 * factor is smaller if the area is closer to the search origin. 654 */ 655static void get_nearness_factor(struct tcm_area *field, struct tcm_area *area, 656 struct nearness_factor *nf) 657{ 658 /** 659 * Using signed math as field coordinates may be reversed if 660 * search direction is right-to-left or bottom-to-top. 661 */ 662 nf->x = (s32)(area->p0.x - field->p0.x) * 1000 / 663 (field->p1.x - field->p0.x); 664 nf->y = (s32)(area->p0.y - field->p0.y) * 1000 / 665 (field->p1.y - field->p0.y); 666} 667 668/* get neighbor statistics */ 669static void get_neighbor_stats(struct tcm *tcm, struct tcm_area *area, 670 struct neighbor_stats *stat) 671{ 672 s16 x = 0, y = 0; 673 struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 674 675 /* Clearing any exisiting values */ 676 memset(stat, 0, sizeof(*stat)); 677 678 /* process top & bottom edges */ 679 for (x = area->p0.x; x <= area->p1.x; x++) { 680 if (area->p0.y == 0) 681 stat->edge++; 682 else if (pvt->map[x][area->p0.y - 1]) 683 stat->busy++; 684 685 if (area->p1.y == tcm->height - 1) 686 stat->edge++; 687 else if (pvt->map[x][area->p1.y + 1]) 688 stat->busy++; 689 } 690 691 /* process left & right edges */ 692 for (y = area->p0.y; y <= area->p1.y; ++y) { 693 if (area->p0.x == 0) 694 stat->edge++; 695 else if (pvt->map[area->p0.x - 1][y]) 696 stat->busy++; 697 698 if (area->p1.x == tcm->width - 1) 699 stat->edge++; 700 else if (pvt->map[area->p1.x + 1][y]) 701 stat->busy++; 702 } 703} 704