171e8831f6407542afd1d8888d3cca13e677034efAndy Gross/* 271e8831f6407542afd1d8888d3cca13e677034efAndy Gross * tcm-sita.c 371e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 471e8831f6407542afd1d8888d3cca13e677034efAndy Gross * SImple Tiler Allocator (SiTA): 2D and 1D allocation(reservation) algorithm 571e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 671e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Authors: Ravi Ramachandra <r.ramachandra@ti.com>, 771e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Lajos Molnar <molnar@ti.com> 871e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 971e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Copyright (C) 2009-2010 Texas Instruments, Inc. 1071e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 1171e8831f6407542afd1d8888d3cca13e677034efAndy Gross * This package is free software; you can redistribute it and/or modify 1271e8831f6407542afd1d8888d3cca13e677034efAndy Gross * it under the terms of the GNU General Public License version 2 as 1371e8831f6407542afd1d8888d3cca13e677034efAndy Gross * published by the Free Software Foundation. 1471e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 1571e8831f6407542afd1d8888d3cca13e677034efAndy Gross * THIS PACKAGE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 1671e8831f6407542afd1d8888d3cca13e677034efAndy Gross * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 1771e8831f6407542afd1d8888d3cca13e677034efAndy Gross * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. 1871e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 1971e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 2071e8831f6407542afd1d8888d3cca13e677034efAndy Gross#include <linux/slab.h> 2171e8831f6407542afd1d8888d3cca13e677034efAndy Gross#include <linux/spinlock.h> 2271e8831f6407542afd1d8888d3cca13e677034efAndy Gross 2371e8831f6407542afd1d8888d3cca13e677034efAndy Gross#include "tcm-sita.h" 2471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 2571e8831f6407542afd1d8888d3cca13e677034efAndy Gross#define ALIGN_DOWN(value, align) ((value) & ~((align) - 1)) 2671e8831f6407542afd1d8888d3cca13e677034efAndy Gross 2771e8831f6407542afd1d8888d3cca13e677034efAndy Gross/* Individual selection criteria for different scan areas */ 2871e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 CR_L2R_T2B = CR_BIAS_HORIZONTAL; 2971e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 CR_R2L_T2B = CR_DIAGONAL_BALANCE; 3071e8831f6407542afd1d8888d3cca13e677034efAndy Gross 3171e8831f6407542afd1d8888d3cca13e677034efAndy Gross/********************************************* 3271e8831f6407542afd1d8888d3cca13e677034efAndy Gross * TCM API - Sita Implementation 3371e8831f6407542afd1d8888d3cca13e677034efAndy Gross *********************************************/ 3471e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u8 align, 3571e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *area); 3671e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 sita_reserve_1d(struct tcm *tcm, u32 slots, struct tcm_area *area); 3771e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 sita_free(struct tcm *tcm, struct tcm_area *area); 3871e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic void sita_deinit(struct tcm *tcm); 3971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 4071e8831f6407542afd1d8888d3cca13e677034efAndy Gross/********************************************* 4171e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Main Scanner functions 4271e8831f6407542afd1d8888d3cca13e677034efAndy Gross *********************************************/ 4371e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 scan_areas_and_find_fit(struct tcm *tcm, u16 w, u16 h, u16 align, 4471e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *area); 4571e8831f6407542afd1d8888d3cca13e677034efAndy Gross 4671e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 scan_l2r_t2b(struct tcm *tcm, u16 w, u16 h, u16 align, 4771e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *field, struct tcm_area *area); 4871e8831f6407542afd1d8888d3cca13e677034efAndy Gross 4971e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 scan_r2l_t2b(struct tcm *tcm, u16 w, u16 h, u16 align, 5071e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *field, struct tcm_area *area); 5171e8831f6407542afd1d8888d3cca13e677034efAndy Gross 5271e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 scan_r2l_b2t_one_dim(struct tcm *tcm, u32 num_slots, 5371e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *field, struct tcm_area *area); 5471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 5571e8831f6407542afd1d8888d3cca13e677034efAndy Gross/********************************************* 5671e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Support Infrastructure Methods 5771e8831f6407542afd1d8888d3cca13e677034efAndy Gross *********************************************/ 5871e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 is_area_free(struct tcm_area ***map, u16 x0, u16 y0, u16 w, u16 h); 5971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 6071e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 update_candidate(struct tcm *tcm, u16 x0, u16 y0, u16 w, u16 h, 6171e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *field, s32 criteria, 6271e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct score *best); 6371e8831f6407542afd1d8888d3cca13e677034efAndy Gross 6471e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic void get_nearness_factor(struct tcm_area *field, 6571e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *candidate, 6671e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct nearness_factor *nf); 6771e8831f6407542afd1d8888d3cca13e677034efAndy Gross 6871e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic void get_neighbor_stats(struct tcm *tcm, struct tcm_area *area, 6971e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct neighbor_stats *stat); 7071e8831f6407542afd1d8888d3cca13e677034efAndy Gross 7171e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic void fill_area(struct tcm *tcm, 7271e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *area, struct tcm_area *parent); 7371e8831f6407542afd1d8888d3cca13e677034efAndy Gross 7471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 7571e8831f6407542afd1d8888d3cca13e677034efAndy Gross/*********************************************/ 7671e8831f6407542afd1d8888d3cca13e677034efAndy Gross 7771e8831f6407542afd1d8888d3cca13e677034efAndy Gross/********************************************* 7871e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Utility Methods 7971e8831f6407542afd1d8888d3cca13e677034efAndy Gross *********************************************/ 8071e8831f6407542afd1d8888d3cca13e677034efAndy Grossstruct tcm *sita_init(u16 width, u16 height, struct tcm_pt *attr) 8171e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 8271e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm *tcm; 8371e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct sita_pvt *pvt; 8471e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area area = {0}; 8571e8831f6407542afd1d8888d3cca13e677034efAndy Gross s32 i; 8671e8831f6407542afd1d8888d3cca13e677034efAndy Gross 8771e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (width == 0 || height == 0) 8871e8831f6407542afd1d8888d3cca13e677034efAndy Gross return NULL; 8971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 9071e8831f6407542afd1d8888d3cca13e677034efAndy Gross tcm = kmalloc(sizeof(*tcm), GFP_KERNEL); 9171e8831f6407542afd1d8888d3cca13e677034efAndy Gross pvt = kmalloc(sizeof(*pvt), GFP_KERNEL); 9271e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (!tcm || !pvt) 9371e8831f6407542afd1d8888d3cca13e677034efAndy Gross goto error; 9471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 9571e8831f6407542afd1d8888d3cca13e677034efAndy Gross memset(tcm, 0, sizeof(*tcm)); 9671e8831f6407542afd1d8888d3cca13e677034efAndy Gross memset(pvt, 0, sizeof(*pvt)); 9771e8831f6407542afd1d8888d3cca13e677034efAndy Gross 9871e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* Updating the pointers to SiTA implementation APIs */ 9971e8831f6407542afd1d8888d3cca13e677034efAndy Gross tcm->height = height; 10071e8831f6407542afd1d8888d3cca13e677034efAndy Gross tcm->width = width; 10171e8831f6407542afd1d8888d3cca13e677034efAndy Gross tcm->reserve_2d = sita_reserve_2d; 10271e8831f6407542afd1d8888d3cca13e677034efAndy Gross tcm->reserve_1d = sita_reserve_1d; 10371e8831f6407542afd1d8888d3cca13e677034efAndy Gross tcm->free = sita_free; 10471e8831f6407542afd1d8888d3cca13e677034efAndy Gross tcm->deinit = sita_deinit; 10571e8831f6407542afd1d8888d3cca13e677034efAndy Gross tcm->pvt = (void *)pvt; 10671e8831f6407542afd1d8888d3cca13e677034efAndy Gross 10771e8831f6407542afd1d8888d3cca13e677034efAndy Gross spin_lock_init(&(pvt->lock)); 10871e8831f6407542afd1d8888d3cca13e677034efAndy Gross 10971e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* Creating tam map */ 11071e8831f6407542afd1d8888d3cca13e677034efAndy Gross pvt->map = kmalloc(sizeof(*pvt->map) * tcm->width, GFP_KERNEL); 11171e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (!pvt->map) 11271e8831f6407542afd1d8888d3cca13e677034efAndy Gross goto error; 11371e8831f6407542afd1d8888d3cca13e677034efAndy Gross 11471e8831f6407542afd1d8888d3cca13e677034efAndy Gross for (i = 0; i < tcm->width; i++) { 11571e8831f6407542afd1d8888d3cca13e677034efAndy Gross pvt->map[i] = 11671e8831f6407542afd1d8888d3cca13e677034efAndy Gross kmalloc(sizeof(**pvt->map) * tcm->height, 11771e8831f6407542afd1d8888d3cca13e677034efAndy Gross GFP_KERNEL); 11871e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (pvt->map[i] == NULL) { 11971e8831f6407542afd1d8888d3cca13e677034efAndy Gross while (i--) 12071e8831f6407542afd1d8888d3cca13e677034efAndy Gross kfree(pvt->map[i]); 12171e8831f6407542afd1d8888d3cca13e677034efAndy Gross kfree(pvt->map); 12271e8831f6407542afd1d8888d3cca13e677034efAndy Gross goto error; 12371e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 12471e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 12571e8831f6407542afd1d8888d3cca13e677034efAndy Gross 12671e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (attr && attr->x <= tcm->width && attr->y <= tcm->height) { 12771e8831f6407542afd1d8888d3cca13e677034efAndy Gross pvt->div_pt.x = attr->x; 12871e8831f6407542afd1d8888d3cca13e677034efAndy Gross pvt->div_pt.y = attr->y; 12971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 13071e8831f6407542afd1d8888d3cca13e677034efAndy Gross } else { 13171e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* Defaulting to 3:1 ratio on width for 2D area split */ 13271e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* Defaulting to 3:1 ratio on height for 2D and 1D split */ 13371e8831f6407542afd1d8888d3cca13e677034efAndy Gross pvt->div_pt.x = (tcm->width * 3) / 4; 13471e8831f6407542afd1d8888d3cca13e677034efAndy Gross pvt->div_pt.y = (tcm->height * 3) / 4; 13571e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 13671e8831f6407542afd1d8888d3cca13e677034efAndy Gross 13771e8831f6407542afd1d8888d3cca13e677034efAndy Gross spin_lock(&(pvt->lock)); 13871e8831f6407542afd1d8888d3cca13e677034efAndy Gross assign(&area, 0, 0, width - 1, height - 1); 13971e8831f6407542afd1d8888d3cca13e677034efAndy Gross fill_area(tcm, &area, NULL); 14071e8831f6407542afd1d8888d3cca13e677034efAndy Gross spin_unlock(&(pvt->lock)); 14171e8831f6407542afd1d8888d3cca13e677034efAndy Gross return tcm; 14271e8831f6407542afd1d8888d3cca13e677034efAndy Gross 14371e8831f6407542afd1d8888d3cca13e677034efAndy Grosserror: 14471e8831f6407542afd1d8888d3cca13e677034efAndy Gross kfree(tcm); 14571e8831f6407542afd1d8888d3cca13e677034efAndy Gross kfree(pvt); 14671e8831f6407542afd1d8888d3cca13e677034efAndy Gross return NULL; 14771e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 14871e8831f6407542afd1d8888d3cca13e677034efAndy Gross 14971e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic void sita_deinit(struct tcm *tcm) 15071e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 15171e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 15271e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area area = {0}; 15371e8831f6407542afd1d8888d3cca13e677034efAndy Gross s32 i; 15471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 15571e8831f6407542afd1d8888d3cca13e677034efAndy Gross area.p1.x = tcm->width - 1; 15671e8831f6407542afd1d8888d3cca13e677034efAndy Gross area.p1.y = tcm->height - 1; 15771e8831f6407542afd1d8888d3cca13e677034efAndy Gross 15871e8831f6407542afd1d8888d3cca13e677034efAndy Gross spin_lock(&(pvt->lock)); 15971e8831f6407542afd1d8888d3cca13e677034efAndy Gross fill_area(tcm, &area, NULL); 16071e8831f6407542afd1d8888d3cca13e677034efAndy Gross spin_unlock(&(pvt->lock)); 16171e8831f6407542afd1d8888d3cca13e677034efAndy Gross 16271e8831f6407542afd1d8888d3cca13e677034efAndy Gross for (i = 0; i < tcm->height; i++) 16371e8831f6407542afd1d8888d3cca13e677034efAndy Gross kfree(pvt->map[i]); 16471e8831f6407542afd1d8888d3cca13e677034efAndy Gross kfree(pvt->map); 16571e8831f6407542afd1d8888d3cca13e677034efAndy Gross kfree(pvt); 16671e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 16771e8831f6407542afd1d8888d3cca13e677034efAndy Gross 16871e8831f6407542afd1d8888d3cca13e677034efAndy Gross/** 16971e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Reserve a 1D area in the container 17071e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 17171e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param num_slots size of 1D area 17271e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param area pointer to the area that will be populated with the 17371e8831f6407542afd1d8888d3cca13e677034efAndy Gross * reserved area 17471e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 17571e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @return 0 on success, non-0 error value on failure. 17671e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 17771e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 sita_reserve_1d(struct tcm *tcm, u32 num_slots, 17871e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *area) 17971e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 18071e8831f6407542afd1d8888d3cca13e677034efAndy Gross s32 ret; 18171e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area field = {0}; 18271e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 18371e8831f6407542afd1d8888d3cca13e677034efAndy Gross 18471e8831f6407542afd1d8888d3cca13e677034efAndy Gross spin_lock(&(pvt->lock)); 18571e8831f6407542afd1d8888d3cca13e677034efAndy Gross 18671e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* Scanning entire container */ 18771e8831f6407542afd1d8888d3cca13e677034efAndy Gross assign(&field, tcm->width - 1, tcm->height - 1, 0, 0); 18871e8831f6407542afd1d8888d3cca13e677034efAndy Gross 18971e8831f6407542afd1d8888d3cca13e677034efAndy Gross ret = scan_r2l_b2t_one_dim(tcm, num_slots, &field, area); 19071e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (!ret) 19171e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* update map */ 19271e8831f6407542afd1d8888d3cca13e677034efAndy Gross fill_area(tcm, area, area); 19371e8831f6407542afd1d8888d3cca13e677034efAndy Gross 19471e8831f6407542afd1d8888d3cca13e677034efAndy Gross spin_unlock(&(pvt->lock)); 19571e8831f6407542afd1d8888d3cca13e677034efAndy Gross return ret; 19671e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 19771e8831f6407542afd1d8888d3cca13e677034efAndy Gross 19871e8831f6407542afd1d8888d3cca13e677034efAndy Gross/** 19971e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Reserve a 2D area in the container 20071e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 20171e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param w width 20271e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param h height 2036354eb81fe8cc32899959d2dac23aa1c9a12c9faJustin P. Mattock * @param area pointer to the area that will be populated with the reserved 20471e8831f6407542afd1d8888d3cca13e677034efAndy Gross * area 20571e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 20671e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @return 0 on success, non-0 error value on failure. 20771e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 20871e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u8 align, 20971e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *area) 21071e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 21171e8831f6407542afd1d8888d3cca13e677034efAndy Gross s32 ret; 21271e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 21371e8831f6407542afd1d8888d3cca13e677034efAndy Gross 21471e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* not supporting more than 64 as alignment */ 21571e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (align > 64) 21671e8831f6407542afd1d8888d3cca13e677034efAndy Gross return -EINVAL; 21771e8831f6407542afd1d8888d3cca13e677034efAndy Gross 21871e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* we prefer 1, 32 and 64 as alignment */ 21971e8831f6407542afd1d8888d3cca13e677034efAndy Gross align = align <= 1 ? 1 : align <= 32 ? 32 : 64; 22071e8831f6407542afd1d8888d3cca13e677034efAndy Gross 22171e8831f6407542afd1d8888d3cca13e677034efAndy Gross spin_lock(&(pvt->lock)); 22271e8831f6407542afd1d8888d3cca13e677034efAndy Gross ret = scan_areas_and_find_fit(tcm, w, h, align, area); 22371e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (!ret) 22471e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* update map */ 22571e8831f6407542afd1d8888d3cca13e677034efAndy Gross fill_area(tcm, area, area); 22671e8831f6407542afd1d8888d3cca13e677034efAndy Gross 22771e8831f6407542afd1d8888d3cca13e677034efAndy Gross spin_unlock(&(pvt->lock)); 22871e8831f6407542afd1d8888d3cca13e677034efAndy Gross return ret; 22971e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 23071e8831f6407542afd1d8888d3cca13e677034efAndy Gross 23171e8831f6407542afd1d8888d3cca13e677034efAndy Gross/** 23271e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Unreserve a previously allocated 2D or 1D area 23371e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param area area to be freed 23471e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @return 0 - success 23571e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 23671e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 sita_free(struct tcm *tcm, struct tcm_area *area) 23771e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 23871e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 23971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 24071e8831f6407542afd1d8888d3cca13e677034efAndy Gross spin_lock(&(pvt->lock)); 24171e8831f6407542afd1d8888d3cca13e677034efAndy Gross 24271e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* check that this is in fact an existing area */ 24371e8831f6407542afd1d8888d3cca13e677034efAndy Gross WARN_ON(pvt->map[area->p0.x][area->p0.y] != area || 24471e8831f6407542afd1d8888d3cca13e677034efAndy Gross pvt->map[area->p1.x][area->p1.y] != area); 24571e8831f6407542afd1d8888d3cca13e677034efAndy Gross 24671e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* Clear the contents of the associated tiles in the map */ 24771e8831f6407542afd1d8888d3cca13e677034efAndy Gross fill_area(tcm, area, NULL); 24871e8831f6407542afd1d8888d3cca13e677034efAndy Gross 24971e8831f6407542afd1d8888d3cca13e677034efAndy Gross spin_unlock(&(pvt->lock)); 25071e8831f6407542afd1d8888d3cca13e677034efAndy Gross 25171e8831f6407542afd1d8888d3cca13e677034efAndy Gross return 0; 25271e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 25371e8831f6407542afd1d8888d3cca13e677034efAndy Gross 25471e8831f6407542afd1d8888d3cca13e677034efAndy Gross/** 25571e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Note: In general the cordinates in the scan field area relevant to the can 25671e8831f6407542afd1d8888d3cca13e677034efAndy Gross * sweep directions. The scan origin (e.g. top-left corner) will always be 25771e8831f6407542afd1d8888d3cca13e677034efAndy Gross * the p0 member of the field. Therfore, for a scan from top-left p0.x <= p1.x 25871e8831f6407542afd1d8888d3cca13e677034efAndy Gross * and p0.y <= p1.y; whereas, for a scan from bottom-right p1.x <= p0.x and p1.y 25971e8831f6407542afd1d8888d3cca13e677034efAndy Gross * <= p0.y 26071e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 26171e8831f6407542afd1d8888d3cca13e677034efAndy Gross 26271e8831f6407542afd1d8888d3cca13e677034efAndy Gross/** 26371e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Raster scan horizontally right to left from top to bottom to find a place for 26471e8831f6407542afd1d8888d3cca13e677034efAndy Gross * a 2D area of given size inside a scan field. 26571e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 26671e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param w width of desired area 26771e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param h height of desired area 26871e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param align desired area alignment 26971e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param area pointer to the area that will be set to the best position 27071e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param field area to scan (inclusive) 27171e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 27271e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @return 0 on success, non-0 error value on failure. 27371e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 27471e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 scan_r2l_t2b(struct tcm *tcm, u16 w, u16 h, u16 align, 27571e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *field, struct tcm_area *area) 27671e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 27771e8831f6407542afd1d8888d3cca13e677034efAndy Gross s32 x, y; 27871e8831f6407542afd1d8888d3cca13e677034efAndy Gross s16 start_x, end_x, start_y, end_y, found_x = -1; 27971e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area ***map = ((struct sita_pvt *)tcm->pvt)->map; 28071e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct score best = {{0}, {0}, {0}, 0}; 28171e8831f6407542afd1d8888d3cca13e677034efAndy Gross 28271e8831f6407542afd1d8888d3cca13e677034efAndy Gross start_x = field->p0.x; 28371e8831f6407542afd1d8888d3cca13e677034efAndy Gross end_x = field->p1.x; 28471e8831f6407542afd1d8888d3cca13e677034efAndy Gross start_y = field->p0.y; 28571e8831f6407542afd1d8888d3cca13e677034efAndy Gross end_y = field->p1.y; 28671e8831f6407542afd1d8888d3cca13e677034efAndy Gross 28771e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* check scan area co-ordinates */ 28871e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (field->p0.x < field->p1.x || 28971e8831f6407542afd1d8888d3cca13e677034efAndy Gross field->p1.y < field->p0.y) 29071e8831f6407542afd1d8888d3cca13e677034efAndy Gross return -EINVAL; 29171e8831f6407542afd1d8888d3cca13e677034efAndy Gross 29271e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* check if allocation would fit in scan area */ 29371e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (w > LEN(start_x, end_x) || h > LEN(end_y, start_y)) 29471e8831f6407542afd1d8888d3cca13e677034efAndy Gross return -ENOSPC; 29571e8831f6407542afd1d8888d3cca13e677034efAndy Gross 29671e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* adjust start_x and end_y, as allocation would not fit beyond */ 29771e8831f6407542afd1d8888d3cca13e677034efAndy Gross start_x = ALIGN_DOWN(start_x - w + 1, align); /* - 1 to be inclusive */ 29871e8831f6407542afd1d8888d3cca13e677034efAndy Gross end_y = end_y - h + 1; 29971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 30071e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* check if allocation would still fit in scan area */ 30171e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (start_x < end_x) 30271e8831f6407542afd1d8888d3cca13e677034efAndy Gross return -ENOSPC; 30371e8831f6407542afd1d8888d3cca13e677034efAndy Gross 30471e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* scan field top-to-bottom, right-to-left */ 30571e8831f6407542afd1d8888d3cca13e677034efAndy Gross for (y = start_y; y <= end_y; y++) { 30671e8831f6407542afd1d8888d3cca13e677034efAndy Gross for (x = start_x; x >= end_x; x -= align) { 30771e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (is_area_free(map, x, y, w, h)) { 30871e8831f6407542afd1d8888d3cca13e677034efAndy Gross found_x = x; 30971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 31071e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* update best candidate */ 31171e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (update_candidate(tcm, x, y, w, h, field, 31271e8831f6407542afd1d8888d3cca13e677034efAndy Gross CR_R2L_T2B, &best)) 31371e8831f6407542afd1d8888d3cca13e677034efAndy Gross goto done; 31471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 31571e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* change upper x bound */ 31671e8831f6407542afd1d8888d3cca13e677034efAndy Gross end_x = x + 1; 31771e8831f6407542afd1d8888d3cca13e677034efAndy Gross break; 31871e8831f6407542afd1d8888d3cca13e677034efAndy Gross } else if (map[x][y] && map[x][y]->is2d) { 31971e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* step over 2D areas */ 32071e8831f6407542afd1d8888d3cca13e677034efAndy Gross x = ALIGN(map[x][y]->p0.x - w + 1, align); 32171e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 32271e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 32371e8831f6407542afd1d8888d3cca13e677034efAndy Gross 32471e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* break if you find a free area shouldering the scan field */ 32571e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (found_x == start_x) 32671e8831f6407542afd1d8888d3cca13e677034efAndy Gross break; 32771e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 32871e8831f6407542afd1d8888d3cca13e677034efAndy Gross 32971e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (!best.a.tcm) 33071e8831f6407542afd1d8888d3cca13e677034efAndy Gross return -ENOSPC; 33171e8831f6407542afd1d8888d3cca13e677034efAndy Grossdone: 33271e8831f6407542afd1d8888d3cca13e677034efAndy Gross assign(area, best.a.p0.x, best.a.p0.y, best.a.p1.x, best.a.p1.y); 33371e8831f6407542afd1d8888d3cca13e677034efAndy Gross return 0; 33471e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 33571e8831f6407542afd1d8888d3cca13e677034efAndy Gross 33671e8831f6407542afd1d8888d3cca13e677034efAndy Gross/** 33771e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Raster scan horizontally left to right from top to bottom to find a place for 33871e8831f6407542afd1d8888d3cca13e677034efAndy Gross * a 2D area of given size inside a scan field. 33971e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 34071e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param w width of desired area 34171e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param h height of desired area 34271e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param align desired area alignment 34371e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param area pointer to the area that will be set to the best position 34471e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param field area to scan (inclusive) 34571e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 34671e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @return 0 on success, non-0 error value on failure. 34771e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 34871e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 scan_l2r_t2b(struct tcm *tcm, u16 w, u16 h, u16 align, 34971e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *field, struct tcm_area *area) 35071e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 35171e8831f6407542afd1d8888d3cca13e677034efAndy Gross s32 x, y; 35271e8831f6407542afd1d8888d3cca13e677034efAndy Gross s16 start_x, end_x, start_y, end_y, found_x = -1; 35371e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area ***map = ((struct sita_pvt *)tcm->pvt)->map; 35471e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct score best = {{0}, {0}, {0}, 0}; 35571e8831f6407542afd1d8888d3cca13e677034efAndy Gross 35671e8831f6407542afd1d8888d3cca13e677034efAndy Gross start_x = field->p0.x; 35771e8831f6407542afd1d8888d3cca13e677034efAndy Gross end_x = field->p1.x; 35871e8831f6407542afd1d8888d3cca13e677034efAndy Gross start_y = field->p0.y; 35971e8831f6407542afd1d8888d3cca13e677034efAndy Gross end_y = field->p1.y; 36071e8831f6407542afd1d8888d3cca13e677034efAndy Gross 36171e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* check scan area co-ordinates */ 36271e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (field->p1.x < field->p0.x || 36371e8831f6407542afd1d8888d3cca13e677034efAndy Gross field->p1.y < field->p0.y) 36471e8831f6407542afd1d8888d3cca13e677034efAndy Gross return -EINVAL; 36571e8831f6407542afd1d8888d3cca13e677034efAndy Gross 36671e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* check if allocation would fit in scan area */ 36771e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (w > LEN(end_x, start_x) || h > LEN(end_y, start_y)) 36871e8831f6407542afd1d8888d3cca13e677034efAndy Gross return -ENOSPC; 36971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 37071e8831f6407542afd1d8888d3cca13e677034efAndy Gross start_x = ALIGN(start_x, align); 37171e8831f6407542afd1d8888d3cca13e677034efAndy Gross 37271e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* check if allocation would still fit in scan area */ 37371e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (w > LEN(end_x, start_x)) 37471e8831f6407542afd1d8888d3cca13e677034efAndy Gross return -ENOSPC; 37571e8831f6407542afd1d8888d3cca13e677034efAndy Gross 37671e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* adjust end_x and end_y, as allocation would not fit beyond */ 37771e8831f6407542afd1d8888d3cca13e677034efAndy Gross end_x = end_x - w + 1; /* + 1 to be inclusive */ 37871e8831f6407542afd1d8888d3cca13e677034efAndy Gross end_y = end_y - h + 1; 37971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 38071e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* scan field top-to-bottom, left-to-right */ 38171e8831f6407542afd1d8888d3cca13e677034efAndy Gross for (y = start_y; y <= end_y; y++) { 38271e8831f6407542afd1d8888d3cca13e677034efAndy Gross for (x = start_x; x <= end_x; x += align) { 38371e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (is_area_free(map, x, y, w, h)) { 38471e8831f6407542afd1d8888d3cca13e677034efAndy Gross found_x = x; 38571e8831f6407542afd1d8888d3cca13e677034efAndy Gross 38671e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* update best candidate */ 38771e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (update_candidate(tcm, x, y, w, h, field, 38871e8831f6407542afd1d8888d3cca13e677034efAndy Gross CR_L2R_T2B, &best)) 38971e8831f6407542afd1d8888d3cca13e677034efAndy Gross goto done; 39071e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* change upper x bound */ 39171e8831f6407542afd1d8888d3cca13e677034efAndy Gross end_x = x - 1; 39271e8831f6407542afd1d8888d3cca13e677034efAndy Gross 39371e8831f6407542afd1d8888d3cca13e677034efAndy Gross break; 39471e8831f6407542afd1d8888d3cca13e677034efAndy Gross } else if (map[x][y] && map[x][y]->is2d) { 39571e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* step over 2D areas */ 39671e8831f6407542afd1d8888d3cca13e677034efAndy Gross x = ALIGN_DOWN(map[x][y]->p1.x, align); 39771e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 39871e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 39971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 40071e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* break if you find a free area shouldering the scan field */ 40171e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (found_x == start_x) 40271e8831f6407542afd1d8888d3cca13e677034efAndy Gross break; 40371e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 40471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 40571e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (!best.a.tcm) 40671e8831f6407542afd1d8888d3cca13e677034efAndy Gross return -ENOSPC; 40771e8831f6407542afd1d8888d3cca13e677034efAndy Grossdone: 40871e8831f6407542afd1d8888d3cca13e677034efAndy Gross assign(area, best.a.p0.x, best.a.p0.y, best.a.p1.x, best.a.p1.y); 40971e8831f6407542afd1d8888d3cca13e677034efAndy Gross return 0; 41071e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 41171e8831f6407542afd1d8888d3cca13e677034efAndy Gross 41271e8831f6407542afd1d8888d3cca13e677034efAndy Gross/** 41371e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Raster scan horizontally right to left from bottom to top to find a place 41471e8831f6407542afd1d8888d3cca13e677034efAndy Gross * for a 1D area of given size inside a scan field. 41571e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 41671e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param num_slots size of desired area 41771e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param align desired area alignment 41871e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param area pointer to the area that will be set to the best 41971e8831f6407542afd1d8888d3cca13e677034efAndy Gross * position 42071e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param field area to scan (inclusive) 42171e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 42271e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @return 0 on success, non-0 error value on failure. 42371e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 42471e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 scan_r2l_b2t_one_dim(struct tcm *tcm, u32 num_slots, 42571e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *field, struct tcm_area *area) 42671e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 42771e8831f6407542afd1d8888d3cca13e677034efAndy Gross s32 found = 0; 42871e8831f6407542afd1d8888d3cca13e677034efAndy Gross s16 x, y; 42971e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 43071e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *p; 43171e8831f6407542afd1d8888d3cca13e677034efAndy Gross 43271e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* check scan area co-ordinates */ 43371e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (field->p0.y < field->p1.y) 43471e8831f6407542afd1d8888d3cca13e677034efAndy Gross return -EINVAL; 43571e8831f6407542afd1d8888d3cca13e677034efAndy Gross 43671e8831f6407542afd1d8888d3cca13e677034efAndy Gross /** 43771e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Currently we only support full width 1D scan field, which makes sense 43871e8831f6407542afd1d8888d3cca13e677034efAndy Gross * since 1D slot-ordering spans the full container width. 43971e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 44071e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (tcm->width != field->p0.x - field->p1.x + 1) 44171e8831f6407542afd1d8888d3cca13e677034efAndy Gross return -EINVAL; 44271e8831f6407542afd1d8888d3cca13e677034efAndy Gross 44371e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* check if allocation would fit in scan area */ 44471e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (num_slots > tcm->width * LEN(field->p0.y, field->p1.y)) 44571e8831f6407542afd1d8888d3cca13e677034efAndy Gross return -ENOSPC; 44671e8831f6407542afd1d8888d3cca13e677034efAndy Gross 44771e8831f6407542afd1d8888d3cca13e677034efAndy Gross x = field->p0.x; 44871e8831f6407542afd1d8888d3cca13e677034efAndy Gross y = field->p0.y; 44971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 45071e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* find num_slots consecutive free slots to the left */ 45171e8831f6407542afd1d8888d3cca13e677034efAndy Gross while (found < num_slots) { 45271e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (y < 0) 45371e8831f6407542afd1d8888d3cca13e677034efAndy Gross return -ENOSPC; 45471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 45571e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* remember bottom-right corner */ 45671e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (found == 0) { 45771e8831f6407542afd1d8888d3cca13e677034efAndy Gross area->p1.x = x; 45871e8831f6407542afd1d8888d3cca13e677034efAndy Gross area->p1.y = y; 45971e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 46071e8831f6407542afd1d8888d3cca13e677034efAndy Gross 46171e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* skip busy regions */ 46271e8831f6407542afd1d8888d3cca13e677034efAndy Gross p = pvt->map[x][y]; 46371e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (p) { 46471e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* move to left of 2D areas, top left of 1D */ 46571e8831f6407542afd1d8888d3cca13e677034efAndy Gross x = p->p0.x; 46671e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (!p->is2d) 46771e8831f6407542afd1d8888d3cca13e677034efAndy Gross y = p->p0.y; 46871e8831f6407542afd1d8888d3cca13e677034efAndy Gross 46971e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* start over */ 47071e8831f6407542afd1d8888d3cca13e677034efAndy Gross found = 0; 47171e8831f6407542afd1d8888d3cca13e677034efAndy Gross } else { 47271e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* count consecutive free slots */ 47371e8831f6407542afd1d8888d3cca13e677034efAndy Gross found++; 47471e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (found == num_slots) 47571e8831f6407542afd1d8888d3cca13e677034efAndy Gross break; 47671e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 47771e8831f6407542afd1d8888d3cca13e677034efAndy Gross 47871e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* move to the left */ 47971e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (x == 0) 48071e8831f6407542afd1d8888d3cca13e677034efAndy Gross y--; 48171e8831f6407542afd1d8888d3cca13e677034efAndy Gross x = (x ? : tcm->width) - 1; 48271e8831f6407542afd1d8888d3cca13e677034efAndy Gross 48371e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 48471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 48571e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* set top-left corner */ 48671e8831f6407542afd1d8888d3cca13e677034efAndy Gross area->p0.x = x; 48771e8831f6407542afd1d8888d3cca13e677034efAndy Gross area->p0.y = y; 48871e8831f6407542afd1d8888d3cca13e677034efAndy Gross return 0; 48971e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 49071e8831f6407542afd1d8888d3cca13e677034efAndy Gross 49171e8831f6407542afd1d8888d3cca13e677034efAndy Gross/** 49271e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Find a place for a 2D area of given size inside a scan field based on its 49371e8831f6407542afd1d8888d3cca13e677034efAndy Gross * alignment needs. 49471e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 49571e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param w width of desired area 49671e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param h height of desired area 49771e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param align desired area alignment 49871e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param area pointer to the area that will be set to the best position 49971e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 50071e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @return 0 on success, non-0 error value on failure. 50171e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 50271e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 scan_areas_and_find_fit(struct tcm *tcm, u16 w, u16 h, u16 align, 50371e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *area) 50471e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 50571e8831f6407542afd1d8888d3cca13e677034efAndy Gross s32 ret = 0; 50671e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area field = {0}; 50771e8831f6407542afd1d8888d3cca13e677034efAndy Gross u16 boundary_x, boundary_y; 50871e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 50971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 51071e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (align > 1) { 51171e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* prefer top-left corner */ 51271e8831f6407542afd1d8888d3cca13e677034efAndy Gross boundary_x = pvt->div_pt.x - 1; 51371e8831f6407542afd1d8888d3cca13e677034efAndy Gross boundary_y = pvt->div_pt.y - 1; 51471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 51571e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* expand width and height if needed */ 51671e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (w > pvt->div_pt.x) 51771e8831f6407542afd1d8888d3cca13e677034efAndy Gross boundary_x = tcm->width - 1; 51871e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (h > pvt->div_pt.y) 51971e8831f6407542afd1d8888d3cca13e677034efAndy Gross boundary_y = tcm->height - 1; 52071e8831f6407542afd1d8888d3cca13e677034efAndy Gross 52171e8831f6407542afd1d8888d3cca13e677034efAndy Gross assign(&field, 0, 0, boundary_x, boundary_y); 52271e8831f6407542afd1d8888d3cca13e677034efAndy Gross ret = scan_l2r_t2b(tcm, w, h, align, &field, area); 52371e8831f6407542afd1d8888d3cca13e677034efAndy Gross 52471e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* scan whole container if failed, but do not scan 2x */ 52571e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (ret != 0 && (boundary_x != tcm->width - 1 || 52671e8831f6407542afd1d8888d3cca13e677034efAndy Gross boundary_y != tcm->height - 1)) { 52771e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* scan the entire container if nothing found */ 52871e8831f6407542afd1d8888d3cca13e677034efAndy Gross assign(&field, 0, 0, tcm->width - 1, tcm->height - 1); 52971e8831f6407542afd1d8888d3cca13e677034efAndy Gross ret = scan_l2r_t2b(tcm, w, h, align, &field, area); 53071e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 53171e8831f6407542afd1d8888d3cca13e677034efAndy Gross } else if (align == 1) { 53271e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* prefer top-right corner */ 53371e8831f6407542afd1d8888d3cca13e677034efAndy Gross boundary_x = pvt->div_pt.x; 53471e8831f6407542afd1d8888d3cca13e677034efAndy Gross boundary_y = pvt->div_pt.y - 1; 53571e8831f6407542afd1d8888d3cca13e677034efAndy Gross 53671e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* expand width and height if needed */ 53771e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (w > (tcm->width - pvt->div_pt.x)) 53871e8831f6407542afd1d8888d3cca13e677034efAndy Gross boundary_x = 0; 53971e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (h > pvt->div_pt.y) 54071e8831f6407542afd1d8888d3cca13e677034efAndy Gross boundary_y = tcm->height - 1; 54171e8831f6407542afd1d8888d3cca13e677034efAndy Gross 54271e8831f6407542afd1d8888d3cca13e677034efAndy Gross assign(&field, tcm->width - 1, 0, boundary_x, boundary_y); 54371e8831f6407542afd1d8888d3cca13e677034efAndy Gross ret = scan_r2l_t2b(tcm, w, h, align, &field, area); 54471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 54571e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* scan whole container if failed, but do not scan 2x */ 54671e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (ret != 0 && (boundary_x != 0 || 54771e8831f6407542afd1d8888d3cca13e677034efAndy Gross boundary_y != tcm->height - 1)) { 54871e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* scan the entire container if nothing found */ 54971e8831f6407542afd1d8888d3cca13e677034efAndy Gross assign(&field, tcm->width - 1, 0, 0, tcm->height - 1); 55071e8831f6407542afd1d8888d3cca13e677034efAndy Gross ret = scan_r2l_t2b(tcm, w, h, align, &field, 55171e8831f6407542afd1d8888d3cca13e677034efAndy Gross area); 55271e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 55371e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 55471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 55571e8831f6407542afd1d8888d3cca13e677034efAndy Gross return ret; 55671e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 55771e8831f6407542afd1d8888d3cca13e677034efAndy Gross 55871e8831f6407542afd1d8888d3cca13e677034efAndy Gross/* check if an entire area is free */ 55971e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 is_area_free(struct tcm_area ***map, u16 x0, u16 y0, u16 w, u16 h) 56071e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 56171e8831f6407542afd1d8888d3cca13e677034efAndy Gross u16 x = 0, y = 0; 56271e8831f6407542afd1d8888d3cca13e677034efAndy Gross for (y = y0; y < y0 + h; y++) { 56371e8831f6407542afd1d8888d3cca13e677034efAndy Gross for (x = x0; x < x0 + w; x++) { 56471e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (map[x][y]) 56571e8831f6407542afd1d8888d3cca13e677034efAndy Gross return false; 56671e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 56771e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 56871e8831f6407542afd1d8888d3cca13e677034efAndy Gross return true; 56971e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 57071e8831f6407542afd1d8888d3cca13e677034efAndy Gross 57171e8831f6407542afd1d8888d3cca13e677034efAndy Gross/* fills an area with a parent tcm_area */ 57271e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic void fill_area(struct tcm *tcm, struct tcm_area *area, 57371e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *parent) 57471e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 57571e8831f6407542afd1d8888d3cca13e677034efAndy Gross s32 x, y; 57671e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 57771e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area a, a_; 57871e8831f6407542afd1d8888d3cca13e677034efAndy Gross 57971e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* set area's tcm; otherwise, enumerator considers it invalid */ 58071e8831f6407542afd1d8888d3cca13e677034efAndy Gross area->tcm = tcm; 58171e8831f6407542afd1d8888d3cca13e677034efAndy Gross 58271e8831f6407542afd1d8888d3cca13e677034efAndy Gross tcm_for_each_slice(a, *area, a_) { 58371e8831f6407542afd1d8888d3cca13e677034efAndy Gross for (x = a.p0.x; x <= a.p1.x; ++x) 58471e8831f6407542afd1d8888d3cca13e677034efAndy Gross for (y = a.p0.y; y <= a.p1.y; ++y) 58571e8831f6407542afd1d8888d3cca13e677034efAndy Gross pvt->map[x][y] = parent; 58671e8831f6407542afd1d8888d3cca13e677034efAndy Gross 58771e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 58871e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 58971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 59071e8831f6407542afd1d8888d3cca13e677034efAndy Gross/** 59171e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Compares a candidate area to the current best area, and if it is a better 59271e8831f6407542afd1d8888d3cca13e677034efAndy Gross * fit, it updates the best to this one. 59371e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 59471e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param x0, y0, w, h top, left, width, height of candidate area 59571e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param field scan field 59671e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param criteria scan criteria 59771e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @param best best candidate and its scores 59871e8831f6407542afd1d8888d3cca13e677034efAndy Gross * 59971e8831f6407542afd1d8888d3cca13e677034efAndy Gross * @return 1 (true) if the candidate area is known to be the final best, so no 60071e8831f6407542afd1d8888d3cca13e677034efAndy Gross * more searching should be performed 60171e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 60271e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic s32 update_candidate(struct tcm *tcm, u16 x0, u16 y0, u16 w, u16 h, 60371e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct tcm_area *field, s32 criteria, 60471e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct score *best) 60571e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 60671e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct score me; /* score for area */ 60771e8831f6407542afd1d8888d3cca13e677034efAndy Gross 60871e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* 60971e8831f6407542afd1d8888d3cca13e677034efAndy Gross * NOTE: For horizontal bias we always give the first found, because our 61071e8831f6407542afd1d8888d3cca13e677034efAndy Gross * scan is horizontal-raster-based and the first candidate will always 61171e8831f6407542afd1d8888d3cca13e677034efAndy Gross * have the horizontal bias. 61271e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 61371e8831f6407542afd1d8888d3cca13e677034efAndy Gross bool first = criteria & CR_BIAS_HORIZONTAL; 61471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 61571e8831f6407542afd1d8888d3cca13e677034efAndy Gross assign(&me.a, x0, y0, x0 + w - 1, y0 + h - 1); 61671e8831f6407542afd1d8888d3cca13e677034efAndy Gross 61771e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* calculate score for current candidate */ 61871e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (!first) { 61971e8831f6407542afd1d8888d3cca13e677034efAndy Gross get_neighbor_stats(tcm, &me.a, &me.n); 62071e8831f6407542afd1d8888d3cca13e677034efAndy Gross me.neighs = me.n.edge + me.n.busy; 62171e8831f6407542afd1d8888d3cca13e677034efAndy Gross get_nearness_factor(field, &me.a, &me.f); 62271e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 62371e8831f6407542afd1d8888d3cca13e677034efAndy Gross 62471e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* the 1st candidate is always the best */ 62571e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (!best->a.tcm) 62671e8831f6407542afd1d8888d3cca13e677034efAndy Gross goto better; 62771e8831f6407542afd1d8888d3cca13e677034efAndy Gross 62871e8831f6407542afd1d8888d3cca13e677034efAndy Gross BUG_ON(first); 62971e8831f6407542afd1d8888d3cca13e677034efAndy Gross 63071e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* diagonal balance check */ 63171e8831f6407542afd1d8888d3cca13e677034efAndy Gross if ((criteria & CR_DIAGONAL_BALANCE) && 63271e8831f6407542afd1d8888d3cca13e677034efAndy Gross best->neighs <= me.neighs && 63371e8831f6407542afd1d8888d3cca13e677034efAndy Gross (best->neighs < me.neighs || 63471e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* this implies that neighs and occupied match */ 63571e8831f6407542afd1d8888d3cca13e677034efAndy Gross best->n.busy < me.n.busy || 63671e8831f6407542afd1d8888d3cca13e677034efAndy Gross (best->n.busy == me.n.busy && 63771e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* check the nearness factor */ 63871e8831f6407542afd1d8888d3cca13e677034efAndy Gross best->f.x + best->f.y > me.f.x + me.f.y))) 63971e8831f6407542afd1d8888d3cca13e677034efAndy Gross goto better; 64071e8831f6407542afd1d8888d3cca13e677034efAndy Gross 64171e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* not better, keep going */ 64271e8831f6407542afd1d8888d3cca13e677034efAndy Gross return 0; 64371e8831f6407542afd1d8888d3cca13e677034efAndy Gross 64471e8831f6407542afd1d8888d3cca13e677034efAndy Grossbetter: 64571e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* save current area as best */ 64671e8831f6407542afd1d8888d3cca13e677034efAndy Gross memcpy(best, &me, sizeof(me)); 64771e8831f6407542afd1d8888d3cca13e677034efAndy Gross best->a.tcm = tcm; 64871e8831f6407542afd1d8888d3cca13e677034efAndy Gross return first; 64971e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 65071e8831f6407542afd1d8888d3cca13e677034efAndy Gross 65171e8831f6407542afd1d8888d3cca13e677034efAndy Gross/** 65271e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Calculate the nearness factor of an area in a search field. The nearness 65371e8831f6407542afd1d8888d3cca13e677034efAndy Gross * factor is smaller if the area is closer to the search origin. 65471e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 65571e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic void get_nearness_factor(struct tcm_area *field, struct tcm_area *area, 65671e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct nearness_factor *nf) 65771e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 65871e8831f6407542afd1d8888d3cca13e677034efAndy Gross /** 65971e8831f6407542afd1d8888d3cca13e677034efAndy Gross * Using signed math as field coordinates may be reversed if 66071e8831f6407542afd1d8888d3cca13e677034efAndy Gross * search direction is right-to-left or bottom-to-top. 66171e8831f6407542afd1d8888d3cca13e677034efAndy Gross */ 66271e8831f6407542afd1d8888d3cca13e677034efAndy Gross nf->x = (s32)(area->p0.x - field->p0.x) * 1000 / 66371e8831f6407542afd1d8888d3cca13e677034efAndy Gross (field->p1.x - field->p0.x); 66471e8831f6407542afd1d8888d3cca13e677034efAndy Gross nf->y = (s32)(area->p0.y - field->p0.y) * 1000 / 66571e8831f6407542afd1d8888d3cca13e677034efAndy Gross (field->p1.y - field->p0.y); 66671e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 66771e8831f6407542afd1d8888d3cca13e677034efAndy Gross 66871e8831f6407542afd1d8888d3cca13e677034efAndy Gross/* get neighbor statistics */ 66971e8831f6407542afd1d8888d3cca13e677034efAndy Grossstatic void get_neighbor_stats(struct tcm *tcm, struct tcm_area *area, 67071e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct neighbor_stats *stat) 67171e8831f6407542afd1d8888d3cca13e677034efAndy Gross{ 67271e8831f6407542afd1d8888d3cca13e677034efAndy Gross s16 x = 0, y = 0; 67371e8831f6407542afd1d8888d3cca13e677034efAndy Gross struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt; 67471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 67571e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* Clearing any exisiting values */ 67671e8831f6407542afd1d8888d3cca13e677034efAndy Gross memset(stat, 0, sizeof(*stat)); 67771e8831f6407542afd1d8888d3cca13e677034efAndy Gross 67871e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* process top & bottom edges */ 67971e8831f6407542afd1d8888d3cca13e677034efAndy Gross for (x = area->p0.x; x <= area->p1.x; x++) { 68071e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (area->p0.y == 0) 68171e8831f6407542afd1d8888d3cca13e677034efAndy Gross stat->edge++; 68271e8831f6407542afd1d8888d3cca13e677034efAndy Gross else if (pvt->map[x][area->p0.y - 1]) 68371e8831f6407542afd1d8888d3cca13e677034efAndy Gross stat->busy++; 68471e8831f6407542afd1d8888d3cca13e677034efAndy Gross 68571e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (area->p1.y == tcm->height - 1) 68671e8831f6407542afd1d8888d3cca13e677034efAndy Gross stat->edge++; 68771e8831f6407542afd1d8888d3cca13e677034efAndy Gross else if (pvt->map[x][area->p1.y + 1]) 68871e8831f6407542afd1d8888d3cca13e677034efAndy Gross stat->busy++; 68971e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 69071e8831f6407542afd1d8888d3cca13e677034efAndy Gross 69171e8831f6407542afd1d8888d3cca13e677034efAndy Gross /* process left & right edges */ 69271e8831f6407542afd1d8888d3cca13e677034efAndy Gross for (y = area->p0.y; y <= area->p1.y; ++y) { 69371e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (area->p0.x == 0) 69471e8831f6407542afd1d8888d3cca13e677034efAndy Gross stat->edge++; 69571e8831f6407542afd1d8888d3cca13e677034efAndy Gross else if (pvt->map[area->p0.x - 1][y]) 69671e8831f6407542afd1d8888d3cca13e677034efAndy Gross stat->busy++; 69771e8831f6407542afd1d8888d3cca13e677034efAndy Gross 69871e8831f6407542afd1d8888d3cca13e677034efAndy Gross if (area->p1.x == tcm->width - 1) 69971e8831f6407542afd1d8888d3cca13e677034efAndy Gross stat->edge++; 70071e8831f6407542afd1d8888d3cca13e677034efAndy Gross else if (pvt->map[area->p1.x + 1][y]) 70171e8831f6407542afd1d8888d3cca13e677034efAndy Gross stat->busy++; 70271e8831f6407542afd1d8888d3cca13e677034efAndy Gross } 70371e8831f6407542afd1d8888d3cca13e677034efAndy Gross} 704