diff --git a/qnx/src/ipc3x_dev/tiler/resmgr/tiler/tcm/tcm_sita.c b/qnx/src/ipc3x_dev/tiler/resmgr/tiler/tcm/tcm_sita.c
+++ /dev/null
@@ -1,1378 +0,0 @@
-/*
- * Copyright (c) 2010, Texas Instruments Incorporated
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * * Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- *
- * * Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * * Neither the name of Texas Instruments Incorporated nor the names of
- * its contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
- * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
- * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
- * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
- * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
- * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
- * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- * */
-/*
- * tcm_sita.c
- *
- * Author: Ravi Ramachandra <r.ramachandra@ti.com>
- *
- * SImple Tiler Allocator (SiTA): 2D and 1D allocation(reservation) algorithm
- *
- */
-#include "../proto.h"
-#include "_tcm_sita.h"
-#include "tcm_sita.h"
-
-#define TCM_ALG_NAME "tcm_sita"
-#include "tcm_utils.h"
-
-#define X_SCAN_LIMITER 1
-#define Y_SCAN_LIMITER 1
-
-#define ALIGN_DOWN(value, align) ((value) & ~((align) - 1))
-
-/* Individual selection criteria for different scan areas */
-static s32 CR_L2R_T2B = CR_BIAS_HORIZONTAL;
-static s32 CR_R2L_T2B = CR_DIAGONAL_BALANCE;
-#ifdef SCAN_BOTTOM_UP
-static s32 CR_R2L_B2T = CR_FIRST_FOUND;
-static s32 CR_L2R_B2T = CR_DIAGONAL_BALANCE;
-#endif
-
-/*********************************************
- * TCM API - Sita Implementation
- *********************************************/
-static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u8 align,
- struct tcm_area *area);
-static s32 sita_reserve_1d(struct tcm *tcm, u32 slots, struct tcm_area
- *area);
-static s32 sita_free(struct tcm *tcm, struct tcm_area *to_be_removed_area);
-static s32 sita_get_parent(struct tcm *tcm, struct tcm_pt *pt,
- struct tcm_area *area);
-static void sita_deinit(struct tcm *tcm);
-
-/*********************************************
- * Main Scanner functions
- *********************************************/
-static s32 scan_areas_and_find_fit(struct tcm *tcm, u16 w, u16 h, u16 stride,
- struct tcm_area *area);
-
-static s32 scan_l2r_t2b(struct tcm *tcm, u16 w, u16 h, u16 stride,
- struct tcm_area *field, struct tcm_area *area);
-
-static s32 scan_r2l_t2b(struct tcm *tcm, u16 w, u16 h, u16 stride,
- struct tcm_area *field, struct tcm_area *area);
-
-#ifdef SCAN_BOTTOM_UP
-static s32 scan_l2r_b2t(struct tcm *tcm, u16 w, u16 h, u16 stride,
- struct tcm_area *field, struct tcm_area *area);
-
-static s32 scan_r2l_b2t(struct tcm *tcm, u16 w, u16 h, u16 stride,
- struct tcm_area *field, struct tcm_area *area);
-#endif
-static s32 scan_r2l_b2t_one_dim(struct tcm *tcm, u32 num_pages,
- struct tcm_area *field, struct tcm_area *area);
-
-/*********************************************
- * Support Infrastructure Methods
- *********************************************/
-static s32 check_fit_r_and_b(struct tcm *tcm, u16 w, u16 h, u16 left_x,
- u16 top_y);
-
-static s32 check_fit_r_one_dim(struct tcm *tcm, u16 x, u16 y, u32 num_pages,
- u16 *busy_x, u16 *busy_y);
-
-static void select_candidate(struct tcm *tcm, u16 w, u16 h,
- struct list_head *maybes, struct tcm_area *field,
- s32 criteria, struct tcm_area *area);
-
-static void get_nearness_factor(struct tcm_area *field,
- struct tcm_area *candidate, struct nearness_factor *nf);
-
-static s32 get_busy_neigh_stats(struct tcm *tcm, u16 width, u16 height,
- struct tcm_area *top_left_corner,
- struct neighbour_stats *neighbour_stat);
-
-static void fill_1d_area(struct tcm *tcm,
- struct tcm_area *area, struct slot slot);
-
-static void fill_2d_area(struct tcm *tcm,
- struct tcm_area *area, struct slot slot);
-
-static s32 move_left(struct tcm *tcm, u16 x, u16 y, u32 num_pages,
- u16 *xx, u16 *yy);
-static s32 move_right(struct tcm *tcm, u16 x, u16 y, u32 num_pages,
- u16 *xx, u16 *yy);
-/*********************************************/
-
-/*********************************************
- * Utility Methods
- *********************************************/
-
-/* TODO: check if element allocation succeeded */
-
-/* insert a given area at the end of a given list */
-static
-struct area_spec *insert_element(struct list_head *head, struct tcm_area *area)
-{
- struct area_spec *elem;
-
- elem = kmalloc(sizeof(*elem), GFP_KERNEL);
- if (elem) {
- elem->area = *area;
- list_add_tail(&elem->list, head);
- }
- return elem;
-}
-
-static
-s32 rem_element_with_match(struct list_head *head,
- struct tcm_area *area, u16 *is2d)
-{
- struct area_spec *elem = NULL, *tmp = NULL;
-
- /*If the area to be removed matchs the list head itself,
- we need to put the next one as list head */
- list_for_each_entry_safe(elem, tmp, head, list) {
- if (elem->area.p0.x == area->p0.x
- && elem->area.p0.y == area->p0.y
- && elem->area.p1.x == area->p1.x
- && elem->area.p1.y == area->p1.y) {
-
- *is2d = elem->area.is2d;
- list_del(&elem->list);
-
- kfree(elem);
- return 0;
- }
- }
- return -ENOENT;
-}
-
-static
-void clean_list(struct list_head *head)
-{
- struct area_spec *elem = NULL, *elem_ = NULL;
-
- list_for_each_entry_safe(elem, elem_, head, list) {
- list_del(&elem->list);
- kfree(elem);
- }
-}
-
-#if 0
-static
-void dump_list_entries(struct list_head *head)
-{
- struct area_spec *elem = NULL, *tmp = NULL;
-
- P1("Printing List Entries:\n");
-
- list_for_each_entry_safe(elem, tmp, head, list) {
- fprintf(stderr, "%dD:" AREA_FMT "\n", elem->area.type,
- AREA(elem->area));
- }
-
- P1("List Finished\n");
-}
-
-static
-s32 dump_neigh_stats(struct neighbour_stats *neighbour)
-{
- P1("Top Occ:Boundary %d:%d\n", neighbour->top_occupied,
- neighbour->top_boundary);
- P1("Bot Occ:Boundary %d:%d\n", neighbour->bottom_occupied,
- neighbour->bottom_boundary);
- P1("Left Occ:Boundary %d:%d\n", neighbour->left_occupied,
- neighbour->left_boundary);
- P1("Rigt Occ:Boundary %d:%d\n", neighbour->right_occupied,
- neighbour->right_boundary);
- return 0;
-}
-#endif
-
-struct tcm *sita_init(u16 width, u16 height, struct tcm_pt *attr)
-{
- struct tcm *tcm = NULL;
- struct sita_pvt *pvt = NULL;
- struct slot init_tile = {0};
- struct tcm_area area = {0};
- s32 i = 0;
-
- if (width == 0 || height == 0)
- goto error;
-
- tcm = kmalloc(sizeof(*tcm), GFP_KERNEL);
- pvt = kmalloc(sizeof(*pvt), GFP_KERNEL);
- if (!tcm || !pvt)
- goto error;
-
- memset(tcm, 0, sizeof(*tcm));
- memset(pvt, 0, sizeof(*pvt));
-
- /* Updating the pointers to SiTA implementation APIs */
- tcm->height = height;
- tcm->width = width;
- tcm->reserve_2d = sita_reserve_2d;
- tcm->reserve_1d = sita_reserve_1d;
- tcm->get_parent = sita_get_parent;
- tcm->free = sita_free;
- tcm->deinit = sita_deinit;
- tcm->pvt = (void *)pvt;
-
- INIT_LIST_HEAD(&pvt->res);
- pvt->height = height;
- pvt->width = width;
-
- mutex_init(&(pvt->mtx));
-
- /* Creating tam map */
- pvt->map = kmalloc(sizeof(*pvt->map) * pvt->width, GFP_KERNEL);
-
- if (!pvt->map)
- goto error;
-
- for (i = 0; i < pvt->width; i++) {
- pvt->map[i] =
- kmalloc(sizeof(**pvt->map) * pvt->height,
- GFP_KERNEL);
- if (pvt->map[i] == NULL) {
- while (i--)
- kfree(pvt->map[i]);
- kfree(pvt->map);
- goto error;
- }
- }
-
- if (attr && attr->x <= pvt->width && attr->y <= pvt->height) {
- pvt->div_pt.x = attr->x;
- pvt->div_pt.y = attr->y;
-
- } else {
- /* Defaulting to 3:1 ratio on width for 2D area split */
- /* Defaulting to 3:1 ratio on height for 2D and 1D split */
- pvt->div_pt.x = (pvt->width * 3) / 4;
- pvt->div_pt.y = (pvt->height * 3) / 4;
- }
-
- area.p1.x = width - 1;
- area.p1.y = height - 1;
-
- mutex_lock(&(pvt->mtx));
- fill_2d_area(tcm, &area, init_tile);
- mutex_unlock(&(pvt->mtx));
- return tcm;
-
-error:
- kfree(tcm);
- kfree(pvt);
- return NULL;
-}
-
-static void sita_deinit(struct tcm *tcm)
-{
- struct slot init_tile = {0};
- struct sita_pvt *pvt = NULL;
- struct tcm_area area = {0};
- s32 i = 0;
-
- pvt = (struct sita_pvt *)tcm->pvt;
- if (pvt) {
- area.p1.x = pvt->width - 1;
- area.p1.y = pvt->height - 1;
-
- mutex_lock(&(pvt->mtx));
- fill_2d_area(tcm, &area, init_tile);
- mutex_unlock(&(pvt->mtx));
-
- mutex_destroy(&(pvt->mtx));
-
- for (i = 0; i < pvt->height; i++) {
- kfree(pvt->map[i]);
- pvt->map[i] = NULL;
- }
- kfree(pvt->map);
- pvt->map = NULL;
- kfree(pvt);
- }
-}
-
-/**
- * @description: Allocate 1d pages if the required number of pages are
- * available in the container
- *
- * @input:num_pages to be allocated
- *
- * @return 0 on success, non-0 error value on failure. On success
- * area contain co-ordinates of start and end Tiles(inclusive)
- */
-static s32 sita_reserve_1d(struct tcm *tcm, u32 num_pages,
- struct tcm_area *area)
-{
- s32 ret = 0;
- struct tcm_area field = {0};
- struct slot slot = {0};
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
-
- area->is2d = false;
-
- mutex_lock(&(pvt->mtx));
-#ifdef RESTRICT_1D
- /* scan within predefined 1D boundary */
- assign(&field, pvt->width - 1, pvt->height - 1, 0, pvt->div_pt.y);
-#else
- /* Scanning entire container */
- assign(&field, pvt->width - 1, pvt->height - 1, 0, 0);
-#endif
- ret = scan_r2l_b2t_one_dim(tcm, num_pages,
- &field, area);
- /* There is not much to select, we pretty much give the first one
- which accomodates */
- if (!ret) {
- slot.busy = true;
- slot.parent = *area;
- /* inserting into tiler container */
- fill_1d_area(tcm, area, slot);
- /* updating the list of allocations */
- insert_element(&pvt->res, area);
- }
- mutex_unlock(&(pvt->mtx));
- return ret;
-}
-
-/**
- * @description: Allocate 2d area on availability in the container
- *
- * @input:'w'idth and 'h'eight of the 2d area, 'align'ment specification
- *
- * @return 0 on success, non-0 error value on failure. On success
- * area contain co-ordinates of TL corner Tile and BR corner Tile of
- * the rectangle (inclusive)
- */
-static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u8 align,
- struct tcm_area *area)
-{
- s32 ret = 0;
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
- /* we only support 1, 32 and 64 as alignment */
- u16 stride = align <= 1 ? 1 : align <= 32 ? 32 : 64;
- struct slot slot = {0};
-
- area->is2d = true;
-
- /* align must be 2 power */
- if (align & (align - 1) || align > 64)
- return -EINVAL;
-
- mutex_lock(&(pvt->mtx));
- ret = scan_areas_and_find_fit(tcm, w, h, stride, area);
- if (!ret) {
- slot.busy = true;
- slot.parent = *area;
-
- fill_2d_area(tcm, area, slot);
- insert_element(&(pvt->res), area);
- }
- mutex_unlock(&(pvt->mtx));
- return ret;
-}
-
-/**
- * @description: unreserve 2d or 1D allocations if previously allocated
- *
- * @input:'area' specification: for 2D this should contain
- * TL Corner and BR Corner of the 2D area, or for 1D allocation this should
- * contain the start and end Tiles
- *
- * @return 0 on success, non-0 error value on failure. On success
- * the to_be_removed_area is removed from g_allocation_list and the
- * corresponding tiles are marked 'NOT_OCCUPIED'
- *
- */
-static s32 sita_free(struct tcm *tcm, struct tcm_area *area)
-{
- s32 ret = 0;
- struct slot slot = {0};
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
- u16 is2d;
-
- slot.busy = false;
- mutex_lock(&(pvt->mtx));
- /*First we check if the given Area is aleast valid in our list*/
- ret = rem_element_with_match(&(pvt->res), area, &is2d);
-
- /* If we found a positive match & removed the area details from list
- * then we clear the contents of the associated tiles in the global
- * container*/
- if (!ret) {
- if (is2d)
- fill_2d_area(tcm, area, slot);
- else
- fill_1d_area(tcm, area, slot);
- }
- mutex_unlock(&(pvt->mtx));
- return ret;
-}
-
-/**
- * @description: raster scan right to left from top to bottom; find if there is
- * a free area to fit a given w x h inside the 'scan area'. If there is a free
- * area, then adds to maybes candidates, which later is sent for selection
- * as per pre-defined criteria.
- *
- * @input:'w x h' width and height of the allocation area.
- * 'stride' - 64/32/None for start address alignment
- * 'field' - area in which the scan operation should take place
- *
- * @return 0 on success, non-0 error value on failure. On success
- * the 'area' area contains TL and BR corners of the allocated area
- *
- */
-static s32 scan_r2l_t2b(struct tcm *tcm, u16 w, u16 h, u16 stride,
- struct tcm_area *field, struct tcm_area *area)
-{
- s32 xx = 0, yy = 0;
- s16 start_x = -1, end_x = -1, start_y = -1, end_y = -1;
- s16 found_x = -1, found_y = -1;
- LIST_HEAD(maybes);
- struct tcm_area candidate = {0};
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
-
- PA(2, "scan_r2l_t2b:", field);
-
- start_x = field->p0.x;
- end_x = field->p1.x;
- start_y = field->p0.y;
- end_y = field->p1.y;
-
- /* check scan area co-ordinates */
- if (field->p0.x < field->p1.x ||
- field->p1.y < field->p0.y)
- return -EINVAL;
-
- /* check if allocation would fit in scan area */
- if (w > INCL_LEN(start_x, end_x) || h > INCL_LEN(end_y, start_y))
- return -ENOSPC;
-
- /* adjust start_x and end_y, as allocation would not fit beyond */
- start_x = ALIGN_DOWN(start_x - w + 1, stride); /* - 1 to be inclusive */
- end_y = end_y - h + 1;
-
- /* check if allocation would still fit in scan area */
- if (start_x < end_x)
- return -ENOSPC;
-
- P2("ali=%d x=%d..%d y=%d..%d", stride, start_x, end_x, start_y, end_y);
-
- /*
- * Start scanning: These scans are always inclusive ones so if we are
- * given a start x = 0 is a valid value so if we have a end_x = 255,
- * 255th element is also checked
- */
- for (yy = start_y; yy <= end_y; yy++) {
- for (xx = start_x; xx >= end_x; xx -= stride) {
- if (!pvt->map[xx][yy].busy) {
- if (check_fit_r_and_b(tcm, w, h, xx, yy)) {
- P3("found shoulder: %d,%d", xx, yy);
- found_x = xx;
- found_y = yy;
- /* Insert this candidate, it is just a
- co-ordinate, reusing Area */
- assign(&candidate, xx, yy, 0, 0);
- insert_element(&maybes, &candidate);
-#ifdef X_SCAN_LIMITER
- /* change upper x bound */
- end_x = xx + 1;
-#endif
- break;
- }
- } else {
- /* Optimization required only for Non Aligned,
- Aligned anyways skip by 32/64 tiles at a time */
- if (stride == 1 &&
- pvt->map[xx][yy].parent.is2d) {
- xx = pvt->map[xx][yy].parent.p0.x;
- P3("moving to: %d,%d", xx, yy);
- }
- }
- }
-
- /* if you find a free area shouldering the given scan area on
- then we can break */
-#ifdef Y_SCAN_LIMITER
- if (found_x == start_x)
- break;
-#endif
- }
-
- if (list_empty(&maybes))
- return -ENOSPC;
-
- select_candidate(tcm, w, h, &maybes, field, CR_R2L_T2B, area);
- /* dump_list_entries(maybes); */
- clean_list(&maybes);
- return 0;
-}
-
-#ifdef SCAN_BOTTOM_UP
-/**
- * @description: raster scan right to left from bottom to top; find if there is
- * a free area to fit a given w x h inside the 'scan area'. If there is a free
- * area, then adds to maybes candidates, which later is sent for selection
- * as per pre-defined criteria.
- *
- * @input:'w x h' width and height of the allocation area.
- * 'stride' - 64/32/None for start address alignment
- * 'field' - area in which the scan operation should take place
- *
- * @return 0 on success, non-0 error value on failure. On success
- * the 'area' area contains TL and BR corners of the allocated area
- *
- */
-static s32 scan_r2l_b2t(struct tcm *tcm, u16 w, u16 h, u16 stride,
- struct tcm_area *field, struct tcm_area *area)
-{
- /* TODO: Should I check scan area?
- * Might have to take it as input during initialization
- */
- s32 xx = 0, yy = 0;
- s16 start_x = -1, end_x = -1, start_y = -1, end_y = -1;
- s16 found_x = -1, found_y = -1;
- LIST_HEAD(maybes);
- struct tcm_area candidate = {0};
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
-
- PA(2, "scan_r2l_b2t:", field);
-
- start_x = field->p0.x;
- end_x = field->p1.x;
- start_y = field->p0.y;
- end_y = field->p1.y;
-
- /* check scan area co-ordinates */
- if (field->p1.x < field->p0.x ||
- field->p1.y < field->p0.y)
- return -EINVAL;
-
- /* check if allocation would fit in scan area */
- if (w > INCL_LEN(start_x, end_x) || h > INCL_LEN(start_y, end_y))
- return -ENOSPC;
-
- /* adjust start_x and start_y, as allocation would not fit beyond */
- start_x = ALIGN_DOWN(start_x - w + 1, stride); /* + 1 to be inclusive */
- start_y = start_y - h + 1;
-
- /* check if allocation would still fit in scan area */
- if (start_x < end_x)
- return -ENOSPC;
-
- P2("ali=%d x=%d..%d y=%d..%d", stride, start_x, end_x, start_y, end_y);
-
- /*
- * Start scanning: These scans are always inclusive ones so if we are
- * given a start x = 0 is a valid value so if we have a end_x = 255,
- * 255th element is also checked
- */
- for (yy = start_y; yy >= end_y; yy--) {
- for (xx = start_x; xx >= end_x; xx -= stride) {
- if (!pvt->map[xx][yy].busy) {
- if (check_fit_r_and_b(tcm, w, h, xx, yy)) {
- P3("found shoulder: %d,%d", xx, yy);
- found_x = xx;
- found_y = yy;
- /* Insert this candidate, it is just a
- co-ordinate, reusing Area */
- assign(&candidate, xx, yy, 0, 0);
- insert_element(&maybes, &candidate);
-#ifdef X_SCAN_LIMITER
- /* change upper x bound */
- end_x = xx + 1;
-#endif
- break;
- }
- } else {
- /* Optimization required only for Non Aligned,
- Aligned anyways skip by 32/64 tiles at a time */
- if (stride == 1 &&
- pvt->map[xx][yy].parent.is2d) {
- xx = pvt->map[xx][yy].parent.p0.x;
- P3("moving to: %d,%d", xx, yy);
- }
- }
-
- }
-
- /* if you find a free area shouldering the given scan area on
- then we can break */
-#ifdef Y_SCAN_LIMITER
- if (found_x == start_x)
- break;
-#endif
- }
-
- if (list_empty(&maybes))
- return -ENOSPC;
-
- select_candidate(tcm, w, h, &maybes, field, CR_R2L_B2T, area);
- /* dump_list_entries(maybes); */
- clean_list(&maybes);
- return 0;
-}
-#endif
-
-/**
- * @description: raster scan left to right from top to bottom; find if there is
- * a free area to fit a given w x h inside the 'scan area'. If there is a free
- * area, then adds to maybes candidates, which later is sent for selection
- * as per pre-defined criteria.
- *
- * @input:'w x h' width and height of the allocation area.
- * 'stride' - 64/32/None for start address alignment
- * 'field' - area in which the scan operation should take place
- *
- * @return 0 on success, non-0 error value on failure. On success
- * the 'area' area contains TL and BR corners of the allocated area
- *
- */
-s32 scan_l2r_t2b(struct tcm *tcm, u16 w, u16 h, u16 stride,
- struct tcm_area *field, struct tcm_area *area)
-{
- s32 xx = 0, yy = 0;
- s16 start_x = -1, end_x = -1, start_y = -1, end_y = -1;
- s16 found_x = -1, found_y = -1;
- LIST_HEAD(maybes);
- struct tcm_area candidate = {0};
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
-
- PA(2, "scan_l2r_t2b:", field);
-
- start_x = field->p0.x;
- end_x = field->p1.x;
- start_y = field->p0.y;
- end_y = field->p1.y;
-
- /* check scan area co-ordinates */
- if (field->p1.x < field->p0.x ||
- field->p1.y < field->p0.y)
- return -EINVAL;
-
- /* check if allocation would fit in scan area */
- if (w > INCL_LEN(end_x, start_x) || h > INCL_LEN(end_y, start_y))
- return -ENOSPC;
-
- start_x = ALIGN(start_x, stride);
-
- /* check if allocation would still fit in scan area */
- if (w > INCL_LEN(end_x, start_x))
- return -ENOSPC;
-
- /* adjust end_x and end_y, as allocation would not fit beyond */
- end_x = end_x - w + 1; /* + 1 to be inclusive */
- end_y = end_y - h + 1;
-
- P2("ali=%d x=%d..%d y=%d..%d", stride, start_x, end_x, start_y, end_y);
-
- /*
- * Start scanning: These scans are always inclusive ones so if we are
- * given a start x = 0 is a valid value so if we have a end_x = 255,
- * 255th element is also checked
- */
- for (yy = start_y; yy <= end_y; yy++) {
- for (xx = start_x; xx <= end_x; xx += stride) {
- /* if NOT occupied */
- if (!pvt->map[xx][yy].busy) {
- if (check_fit_r_and_b(tcm, w, h, xx, yy)) {
- P3("found shoulder: %d,%d", xx, yy);
- found_x = xx;
- found_y = yy;
- /* Insert this candidate, it is just a
- co-ordinate, reusing Area */
- assign(&candidate, xx, yy, 0, 0);
- insert_element(&maybes, &candidate);
-#ifdef X_SCAN_LIMITER
- /* change upper x bound */
- end_x = xx - 1;
-#endif
- break;
- }
- } else {
- /* Optimization required only for Non Aligned,
- Aligned anyways skip by 32/64 tiles at a time */
- if (stride == 1 &&
- pvt->map[xx][yy].parent.is2d) {
- xx = pvt->map[xx][yy].parent.p1.x;
- P3("moving to: %d,%d", xx, yy);
- }
- }
- }
- /* if you find a free area shouldering the given scan area on
- then we can break */
-#ifdef Y_SCAN_LIMITER
- if (found_x == start_x)
- break;
-#endif
- }
-
- if (list_empty(&maybes))
- return -ENOSPC;
-
- select_candidate(tcm, w, h, &maybes, field, CR_L2R_T2B, area);
- /* dump_list_entries(maybes); */
- clean_list(&maybes);
- return 0;
-}
-
-#ifdef SCAN_BOTTOM_UP
-/**
- * @description: raster scan left to right from bottom to top; find if there is
- * a free area to fit a given w x h inside the 'scan area'. If there is a free
- * area, then adds to maybes candidates, which later is sent for selection
- * as per pre-defined criteria.
- *
- * @input:'w x h' width and height of the allocation area.
- * 'stride' - 64/32/None for start address alignment
- * 'field' - area in which the scan operation should take place
- *
- * @return 0 on success, non-0 error value on failure. On success
- * the 'area' area contains TL and BR corners of the allocated area
- *
- */
-static s32 scan_l2r_b2t(struct tcm *tcm, u16 w, u16 h, u16 stride,
- struct tcm_area *field, struct tcm_area *area)
-{
- s32 xx = 0, yy = 0;
- s16 start_x = -1, end_x = -1, start_y = -1, end_y = -1;
- s16 found_x = -1, found_y = -1;
- LIST_HEAD(maybes);
- struct tcm_area candidate = {0};
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
-
- PA(2, "scan_l2r_b2t:", field);
-
- start_x = field->p0.x;
- end_x = field->p1.x;
- start_y = field->p0.y;
- end_y = field->p1.y;
-
- /* check scan area co-ordinates */
- if (field->p1.x < field->p0.x ||
- field->p0.y < field->p1.y)
- return -EINVAL;
-
- /* check if allocation would fit in scan area */
- if (w > INCL_LEN(end_x, start_x) || h > INCL_LEN(start_y, end_y))
- return -ENOSPC;
-
- start_x = ALIGN(start_x, stride);
-
- /* check if allocation would still fit in scan area */
- if (w > INCL_LEN(end_x, start_x))
- return -ENOSPC;
-
- /* adjust end_x and start_y, as allocation would not fit beyond */
- end_x = end_x - w + 1; /* + 1 to be inclusive */
- start_y = start_y - h + 1;
-
- P2("ali=%d x=%d..%d y=%d..%d", stride, start_x, end_x, start_y, end_y);
-
- /*
- * Start scanning: These scans are always inclusive ones so if we are
- * given a start x = 0 is a valid value so if we have a end_x = 255,
- * 255th element is also checked
- */
- for (yy = start_y; yy >= end_y; yy--) {
- for (xx = start_x; xx <= end_x; xx += stride) {
- /* if NOT occupied */
- if (!pvt->map[xx][yy].busy) {
- if (check_fit_r_and_b(tcm, w, h, xx, yy)) {
- P3("found shoulder: %d,%d", xx, yy);
- found_x = xx;
- found_y = yy;
- /* Insert this candidate, it is just a
- co-ordinate, reusing Area */
- assign(&candidate, xx, yy, 0, 0);
- insert_element(&maybes, &candidate);
-#ifdef X_SCAN_LIMITER
- /* change upper x bound */
- end_x = xx - 1;
-#endif
- break;
- }
- } else {
- /* Optimization required only for Non Aligned,
- Aligned anyways skip by 32/64 tiles at a time */
- if (stride == 1 &&
- pvt->map[xx][yy].parent.is2d) {
- xx = pvt->map[xx][yy].parent.p1.x;
- P3("moving to: %d,%d", xx, yy);
- }
- }
- }
-
- /* if you find a free area shouldering the given scan area on
- then we can break */
-#ifdef Y_SCAN_LIMITER
- if (found_x == start_x)
- break;
-#endif
- }
-
- if (list_empty(&maybes))
- return -ENOSPC;
-
- select_candidate(tcm, w, h, &maybes, field, CR_L2R_B2T, area);
- /* dump_list_entries(maybes); */
- clean_list(&maybes);
- return 0;
-}
-#endif
-/*
-Note: In General the cordinates specified in the scan area area relevant to the
-scan sweep directions. i.e A scan Area from Top Left Corner will have
-p0.x <= p1.x and p0.y <= p1.y. Where as A scan Area from bottom Right Corner
-will have p1.x <= p0.x and p1.y <= p0.y
-*/
-
-/**
- * @description: raster scan right to left from bottom to top; find if there are
- * continuous free pages(one slot is one page, continuity always from left to
- * right) inside the 'scan area'. If there are enough continous free pages,
- * then it returns the start and end Tile/page co-ordinates inside 'area'
- *
- * @input:'num_pages' required,
- * 'field' - area in which the scan operation should take place
- *
- * @return 0 on success, non-0 error value on failure. On success
- * the 'area' area contains start and end slot (inclusive).
- *
- */
-static s32 scan_r2l_b2t_one_dim(struct tcm *tcm, u32 num_pages,
- struct tcm_area *field, struct tcm_area *area)
-{
- s32 fit = false;
- u16 x, y;
- u16 left_x, left_y, busy_x, busy_y;
- s32 ret = 0;
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
-
- /* check scan area co-ordinates */
- if (field->p0.y < field->p1.y)
- return -EINVAL;
-
- PA(2, "scan_r2l_b2t_one_dim:", field);
-
- /* Note: Checking sanctity of scan area
- * The reason for checking this that 1D allocations assume that the X
- ranges the entire TilerSpace X ie ALL Columns
- * The scan area can limit only the Y ie, Num of Rows for 1D allocation.
- We also expect we could have only 1 row for 1D allocation
- * i.e our field p0.y and p1.y may have a same value.
- */
-
- /* only support full width 1d scan area */
- if (pvt->width != field->p0.x - field->p1.x + 1)
- return -EINVAL;
-
- /* check if allocation would fit in scan area */
- if (num_pages > pvt->width * INCL_LEN(field->p0.y, field->p1.y))
- return -ENOSPC;
-
- left_x = field->p0.x;
- left_y = field->p0.y;
- while (!ret) {
- x = left_x;
- y = left_y;
-
- if (!pvt->map[x][y].busy) {
- ret = move_left(tcm, x, y, num_pages - 1,
- &left_x, &left_y);
- if (ret)
- break; /* out of space */
-
- P3("moved left %d slots: %d,%d", num_pages - 1,
- left_x, left_y);
- fit = check_fit_r_one_dim(tcm, left_x, left_y,
- num_pages, &busy_x, &busy_y);
- if (fit) {
- assign(area, left_x, left_y,
- busy_x, busy_y);
- break;
- } else {
- /* no fit, continue at the busy slot */
- x = busy_x;
- y = busy_y;
- }
- }
-
- /* now the tile is occupied, skip busy region */
- if (pvt->map[x][y].parent.is2d) {
- busy_x = pvt->map[x][y].parent.p0.x;
- busy_y = y;
- } else {
- busy_x = pvt->map[x][y].parent.p0.x;
- busy_y = pvt->map[x][y].parent.p0.y;
- }
- x = busy_x;
- y = busy_y;
-
- P3("moving left from: %d,%d", x, y);
- ret = move_left(tcm, x, y, 1, &left_x, &left_y);
- }
-
- return fit ? 0 : -ENOSPC;
-}
-
-/**
- * @description:
- *
- *
- *
- *
- * @input:
- *
- *
- * @return 0 on success, non-0 error value on failure. On success
- */
-static s32 scan_areas_and_find_fit(struct tcm *tcm, u16 w, u16 h, u16 stride,
- struct tcm_area *area)
-{
- s32 ret = 0;
- struct tcm_area field = {0};
- u16 boundary_x = 0, boundary_y = 0;
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
- s32 need_scan = 2;
-
- if (stride > 1) {
- boundary_x = pvt->div_pt.x - 1;
- boundary_y = pvt->div_pt.y - 1;
-
- /* more intelligence here */
- if (w > pvt->div_pt.x) {
- boundary_x = pvt->width - 1;
- need_scan--;
- }
- if (h > pvt->div_pt.y) {
- boundary_y = pvt->height - 1;
- need_scan--;
- }
-
- assign(&field, 0, 0, boundary_x, boundary_y);
- ret = scan_l2r_t2b(tcm, w, h, stride, &field, area);
- if (ret != 0 && need_scan) {
- /* scan the entire container if nothing found */
- assign(&field, 0, 0, pvt->width - 1, pvt->height - 1);
- ret = scan_l2r_t2b(tcm, w, h, stride, &field, area);
- }
- } else if (stride == 1) {
- boundary_x = pvt->div_pt.x;
- boundary_y = pvt->div_pt.y - 1;
-
- /* more intelligence here */
- if (w > (pvt->width - pvt->div_pt.x)) {
- boundary_x = 0;
- need_scan--;
- }
- if (h > pvt->div_pt.y) {
- boundary_y = pvt->height - 1;
- need_scan--;
- }
-
- assign(&field, pvt->width - 1, 0, boundary_x, boundary_y);
- ret = scan_r2l_t2b(tcm, w, h, stride, &field, area);
-
- if (ret != 0 && need_scan) {
- /* scan the entire container if nothing found */
- assign(&field, pvt->width - 1, 0, 0,
- pvt->height - 1);
- ret = scan_r2l_t2b(tcm, w, h, stride, &field,
- area);
- }
- }
-
- /* 3/30/2010: moved aligned to left, and unaligned to right side. */
-#if 0
- else if (stride == 1) {
- /* use 64-align area so we don't grow down and shrink 1D area */
- if (h > pvt->div_pt.y) {
- need_scan -= 2;
- assign(&field, 0, 0, pvt->width - 1, pvt->height - 1);
- ret = scan_l2r_t2b(tcm, w, h, stride, &field, area);
- } else {
- assign(&field, 0, pvt->div_pt.y - 1, pvt->width - 1, 0);
- /* scan up in 64 and 32 areas accross whole width */
- ret = scan_l2r_b2t(tcm, w, h, stride, &field, area);
- }
-
- if (ret != 0 && need_scan) {
- assign(&field, 0, 0, pvt->width - 1, pvt->height - 1);
- ret = scan_l2r_t2b(tcm, w, h, stride, &field, area);
- }
- }
-#endif
- return ret;
-}
-
-static s32 check_fit_r_and_b(struct tcm *tcm, u16 w, u16 h, u16 left_x,
- u16 top_y)
-{
- u16 xx = 0, yy = 0;
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
-
- for (yy = top_y; yy < top_y + h; yy++) {
- for (xx = left_x; xx < left_x + w; xx++) {
- if (pvt->map[xx][yy].busy)
- return false;
- }
- }
- return true;
-}
-
-static s32 check_fit_r_one_dim(struct tcm *tcm, u16 x, u16 y, u32 num_pages,
- u16 *busy_x, u16 *busy_y)
-{
- s32 ret = 0;
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
- s32 i = 0;
- *busy_x = x;
- *busy_y = y;
-
- P2("checking fit for %d pages from %d,%d", num_pages, x, y);
- while (i < num_pages) {
- if (pvt->map[x][y].busy) {
- /* go to the start of the blocking allocation
- to avoid unecessary checking */
- if (pvt->map[x][y].parent.is2d) {
- *busy_x = pvt->map[x][y].parent.p0.x;
- *busy_y = y;
- } else {
- *busy_x = pvt->map[x][y].parent.p0.x;
- *busy_y = pvt->map[x][y].parent.p0.y;
- }
- /* TODO: Could also move left in case of 2D */
- P2("after busy slot at: %d,%d", *busy_x, *busy_y);
- return false;
- }
-
- i++;
-
- /* break here so busy_x, busy_y will be correct */
- if (i == num_pages)
- break;
-
- ret = move_right(tcm, x, y, 1, busy_x, busy_y);
- if (ret)
- return false;
-
- x = *busy_x;
- y = *busy_y;
- }
-
- return true;
-}
-
-static void fill_2d_area(struct tcm *tcm, struct tcm_area *area,
- struct slot slot)
-{
- s32 x, y;
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
-
- PA(2, "fill 2d area", area);
- for (x = area->p0.x; x <= area->p1.x; ++x)
- for (y = area->p0.y; y <= area->p1.y; ++y)
- pvt->map[x][y] = slot;
-}
-
-/* area should be a valid area */
-static void fill_1d_area(struct tcm *tcm, struct tcm_area *area,
- struct slot slot)
-{
- u16 x = 0, y = 0;
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
-
- PA(2, "fill 1d area", area);
- x = area->p0.x;
- y = area->p0.y;
-
- while (!(x == area->p1.x && y == area->p1.y)) {
- pvt->map[x++][y] = slot;
- if (x == pvt->width) {
- x = 0;
- y++;
- }
- }
- /* set the last slot */
- pvt->map[x][y] = slot;
-}
-
-static void select_candidate(struct tcm *tcm, u16 w, u16 h,
- struct list_head *maybes,
- struct tcm_area *field, s32 criteria,
- struct tcm_area *area)
-{
- /* bookkeeping the best match and the one evaluated */
- struct area_spec *best = NULL;
- struct nearness_factor best_factor = {0};
- struct neighbour_stats best_stats = {0};
- u16 win_neighs = 0;
-
- /* bookkeeping the current one being evaluated */
- struct area_spec *elem = NULL, *tmp = NULL;
- struct nearness_factor factor = {0};
- struct neighbour_stats stats = {0};
- u16 neighs = 0;
-
- bool better; /* whether current is better */
-
- /* we default to the 1st candidate */
- best = list_first_entry(maybes, struct area_spec, list);
-
- /*i f there is only one candidate then that is the selection*/
-
- /* If first found is enabled then we just provide bluntly the first
- found candidate
- * NOTE: For Horizontal bias we just give the first found, because our
- * scan is Horizontal raster based and the first candidate will always
- * be the same as if selecting the Horizontal one.
- */
- if (list_is_singular(maybes) ||
- criteria & CR_FIRST_FOUND || criteria & CR_BIAS_HORIZONTAL)
- /* Note: Sure we could have done this in the previous function,
- but just wanted this to be cleaner so having
- * one place where the selection is made. Here I am returning
- the first one
- */
- goto done;
-
- /* lets calculate for the first candidate and assign him the best and
- replace with the one who has better credentials w/ to the criteria */
-
- get_busy_neigh_stats(tcm, w, h, &best->area, &best_stats);
- win_neighs = BOUNDARY(&best_stats) +
- OCCUPIED(&best_stats);
- get_nearness_factor(field, &best->area, &best_factor);
-
- list_for_each_entry_safe(elem, tmp, maybes->next, list) {
- better = false;
-
- /* calculate required statistics */
- get_busy_neigh_stats(tcm, w, h, &elem->area, &stats);
- get_nearness_factor(field, &elem->area, &factor);
- neighs = BOUNDARY(&stats) + OCCUPIED(&stats);
-
- /* see if this are is better than the best so far */
-
- /* neighbor check */
- if ((criteria & CR_MAX_NEIGHS) &&
- neighs > win_neighs)
- better = true;
-
- /* vertical bias check */
- if ((criteria & CR_BIAS_VERTICAL) &&
- /*
- * NOTE: not checking if lengths are same, because that does not
- * find new shoulders on the same row after a fit
- */
- INCL_LEN_MOD(elem->area.p0.y, field->p0.y) >
- INCL_LEN_MOD(best->area.p0.y, field->p0.y))
- better = true;
-
- /* diagonal balance check */
- if ((criteria & CR_DIAGONAL_BALANCE) &&
- win_neighs <= neighs &&
- (win_neighs < neighs ||
- /* this implies that neighs and occupied match */
- OCCUPIED(&best_stats) < OCCUPIED(&stats) ||
- (OCCUPIED(&best_stats) == OCCUPIED(&stats) &&
- /* check the nearness factor */
- best_factor.x + best_factor.y > factor.x + factor.y)))
- better = true;
-
- if (better) {
- best = elem;
- best_factor = factor;
- best_stats = stats;
- win_neighs = neighs;
- }
- }
-
-done:
- assign(area, best->area.p0.x, best->area.p0.y,
- best->area.p0.x + w - 1, best->area.p0.y + h - 1);
-}
-
-/* get the nearness factor of an area in a search field */
-static void get_nearness_factor(struct tcm_area *field,
- struct tcm_area *area, struct nearness_factor *nf)
-{
- /* For the following calculation we need worry of +/- sign, the
- relative distances take of this. Multiplied by 1000, there
- is no floating point arithmetic used in kernel */
-
- nf->x = (s32)(area->p0.x - field->p0.x) * 1000 /
- (field->p1.x - field->p0.x);
- nf->y = (s32)(area->p0.y - field->p0.y) * 1000 /
- (field->p1.y - field->p0.y);
-}
-
-/* Neighbours
- *
- * |<-----T------>|
- * _ _______________ _
- * L | Ar | R
- * _ |______________|_
- * |<-----B------>|
- */
-static s32 get_busy_neigh_stats(struct tcm *tcm, u16 width, u16 height,
- struct tcm_area *top_left_corner,
- struct neighbour_stats *neighbour_stat)
-{
- s16 xx = 0, yy = 0;
- struct tcm_area left_edge;
- struct tcm_area right_edge;
- struct tcm_area top_edge;
- struct tcm_area bottom_edge;
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
-
- if (neighbour_stat == NULL)
- return -EINVAL;
-
- if (width == 0 || height == 0)
- return -EINVAL;
-
- /* Clearing any exisiting values */
- memset(neighbour_stat, 0, sizeof(*neighbour_stat));
-
- /* Finding Top Edge */
- assign(&top_edge, top_left_corner->p0.x, top_left_corner->p0.y,
- top_left_corner->p0.x + width - 1, top_left_corner->p0.y);
-
- /* Finding Bottom Edge */
- assign(&bottom_edge, top_left_corner->p0.x,
- top_left_corner->p0.y+height - 1,
- top_left_corner->p0.x + width - 1,
- top_left_corner->p0.y + height - 1);
-
- /* Finding Left Edge */
- assign(&left_edge, top_left_corner->p0.x, top_left_corner->p0.y,
- top_left_corner->p0.x, top_left_corner->p0.y + height - 1);
-
- /* Finding Right Edge */
- assign(&right_edge, top_left_corner->p0.x + width - 1,
- top_left_corner->p0.y,
- top_left_corner->p0.x + width - 1,
- top_left_corner->p0.y + height - 1);
-
- /* dump_area(&top_edge);
- dump_area(&right_edge);
- dump_area(&bottom_edge);
- dump_area(&left_edge);
- */
-
- /* Parsing through top & bottom edge */
- for (xx = top_edge.p0.x; xx <= top_edge.p1.x; xx++) {
- if (top_edge.p0.y - 1 < 0)
- neighbour_stat->top_boundary++;
- else if (pvt->map[xx][top_edge.p0.y - 1].busy)
- neighbour_stat->top_occupied++;
-
- if (bottom_edge.p0.y + 1 > pvt->height - 1)
- neighbour_stat->bottom_boundary++;
- else if (pvt->map[xx][bottom_edge.p0.y+1].busy)
- neighbour_stat->bottom_occupied++;
- }
-
- /* Parsing throught left and right edge */
- for (yy = left_edge.p0.y; yy <= left_edge.p1.y; ++yy) {
- if (left_edge.p0.x - 1 < 0)
- neighbour_stat->left_boundary++;
- else if (pvt->map[left_edge.p0.x - 1][yy].busy)
- neighbour_stat->left_occupied++;
-
- if (right_edge.p0.x + 1 > pvt->width - 1)
- neighbour_stat->right_boundary++;
- else if (pvt->map[right_edge.p0.x + 1][yy].busy)
- neighbour_stat->right_occupied++;
-
- }
-
- return 0;
-}
-
-/**
- @description: Retrieves the parent area of the page at p0.x, p0.y if
- occupied
- @input:co-ordinates of the page (p0.x, p0.y) whoes parent area
- is required
- @return 0 on success, non-0 error value on failure. On success
-
- parent will contain co-ordinates (TL & BR corner) of the parent
- area
-*/
-static s32 sita_get_parent(struct tcm *tcm, struct tcm_pt *pt,
- struct tcm_area *parent)
-{
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
- s32 res = 0;
-
- mutex_lock(&(pvt->mtx));
-
- if (pvt->map[pt->x][pt->y].busy) {
- *parent = pvt->map[pt->x][pt->y].parent;
- } else {
- memset(parent, 0, sizeof(*parent));
- res = -ENOENT;
- }
-
- mutex_unlock(&(pvt->mtx));
-
- return res;
-}
-
-static s32 move_left(struct tcm *tcm, u16 x, u16 y, u32 num_pages,
- u16 *xx, u16 *yy)
-{
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
- u32 pos = x + pvt->width * y;
-
- if (pos < num_pages)
- return -ENOSPC;
-
- pos -= num_pages;
- *xx = pos % pvt->width;
- *yy = pos / pvt->width;
- return 0;
-}
-
-static s32 move_right(struct tcm *tcm, u16 x, u16 y, u32 num_pages,
- u16 *xx, u16 *yy)
-{
- struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
- u32 pos = x + pvt->width * y;
-
- if (num_pages > pvt->width * pvt->height - pos)
- return -ENOSPC;
-
- pos += num_pages;
- *xx = pos % pvt->width;
- *yy = pos / pvt->width;
- return 0;
-}
-