> -----Original Message-----
> From: Sin, David
> Sent: Saturday, July 24, 2010 4:52 AM
> To: linux-arm-kernel@xxxxxxxxxxxxxxxxxxxxxx; linux-omap@xxxxxxxxxxxxxxx;
> Tony Lindgren; Russell King
> Cc: Kanigeri, Hari; Ohad Ben-Cohen; Hiremath, Vaibhav; Shilimkar, Santosh;
> Ramachandra, Ravikiran; Molnar, Lajos; Sin, David
> Subject: [RFC 3/8] TILER-DMM: Sample TCM implementation: Simple TILER
> Allocator
>
> From: Ravi Ramachandra <r.ramachandra@xxxxxx>
>
> This patch implements a simple TILER Container Manager.
>
> Signed-off-by: Ravi Ramachandra <r.ramachandra@xxxxxx>
> Signed-off-by: Lajos Molnar <molnar@xxxxxx>
> Signed-off-by: David Sin <davidsin@xxxxxx>
> ---
> drivers/media/video/tiler/tcm/Makefile | 1 +
> drivers/media/video/tiler/tcm/_tcm-sita.h | 64 ++++
> drivers/media/video/tiler/tcm/tcm-sita.c | 459
> +++++++++++++++++++++++++++++
> drivers/media/video/tiler/tcm/tcm-sita.h | 37 +++
> 4 files changed, 561 insertions(+), 0 deletions(-)
> create mode 100644 drivers/media/video/tiler/tcm/Makefile
> create mode 100644 drivers/media/video/tiler/tcm/_tcm-sita.h
> create mode 100644 drivers/media/video/tiler/tcm/tcm-sita.c
> create mode 100644 drivers/media/video/tiler/tcm/tcm-sita.h
>
> diff --git a/drivers/media/video/tiler/tcm/Makefile
> b/drivers/media/video/tiler/tcm/Makefile
> new file mode 100644
> index 0000000..8434607
> --- /dev/null
> +++ b/drivers/media/video/tiler/tcm/Makefile
> @@ -0,0 +1 @@
> +obj-$(CONFIG_TI_TILER) += tcm-sita.o
> diff --git a/drivers/media/video/tiler/tcm/_tcm-sita.h
> b/drivers/media/video/tiler/tcm/_tcm-sita.h
> new file mode 100644
> index 0000000..4ede1ab
> --- /dev/null
> +++ b/drivers/media/video/tiler/tcm/_tcm-sita.h
> @@ -0,0 +1,64 @@
> +/*
> + * _tcm_sita.h
> + *
> + * SImple Tiler Allocator (SiTA) private structures.
> + *
> + * Author: Ravi Ramachandra <r.ramachandra@xxxxxx>
> + *
> + * Copyright (C) 2009-2010 Texas Instruments, Inc.
> + *
> + * This package is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License version 2 as
> + * published by the Free Software Foundation.
> + *
> + * THIS PACKAGE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
> + * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
> + * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
> + */
> +
> +#ifndef _TCM_SITA_H
> +#define _TCM_SITA_H
> +
> +#include "../tcm.h"
> +
> +/* length between two coordinates */
> +#define LEN(a, b) ((a) > (b) ? (a) - (b) + 1 : (b) - (a) + 1)
> +
> +enum criteria {
> + CR_MAX_NEIGHS = 0x01,
> + CR_FIRST_FOUND = 0x10,
> + CR_BIAS_HORIZONTAL = 0x20,
> + CR_BIAS_VERTICAL = 0x40,
> + CR_DIAGONAL_BALANCE = 0x80
> +};
> +
> +/* nearness to the beginning of the search field from 0 to 1000 */
> +struct nearness_factor {
> + s32 x;
> + s32 y;
> +};
> +
> +/*
> + * Statistics on immediately neighboring slots. Edge is the number of
> + * border segments that are also border segments of the scan field. Busy
> + * refers to the number of neighbors that are occupied.
> + */
> +struct neighbor_stats {
> + u16 edge;
> + u16 busy;
> +};
> +
> +/* structure to keep the score of a potential allocation */
> +struct score {
> + struct nearness_factor f;
> + struct neighbor_stats n;
> + struct tcm_area a;
> + u16 neighs; /* number of busy neighbors */
> +};
> +
> +struct sita_pvt {
> + struct mutex mtx;
> + struct tcm_area ***map; /* pointers to the parent area for each slot
> */
> +};
> +
> +#endif
> diff --git a/drivers/media/video/tiler/tcm/tcm-sita.c
> b/drivers/media/video/tiler/tcm/tcm-sita.c
> new file mode 100644
> index 0000000..93be3e6
> --- /dev/null
> +++ b/drivers/media/video/tiler/tcm/tcm-sita.c
> @@ -0,0 +1,459 @@
> +/*
> + * tcm-sita.c
> + *
> + * SImple Tiler Allocator (SiTA): 2D and 1D allocation(reservation)
> algorithm
> + *
> + * Authors: Ravi Ramachandra <r.ramachandra@xxxxxx>,
> + * Lajos Molnar <molnar@xxxxxx>
> + *
> + * Copyright (C) 2009-2010 Texas Instruments, Inc.
> + *
> + * This package is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License version 2 as
> + * published by the Free Software Foundation.
> + *
> + * THIS PACKAGE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
> + * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
> + * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
> + *
> + */
> +#include <linux/slab.h>
> +
> +#include "_tcm-sita.h"
> +#include "tcm-sita.h"
> +
> +#define TCM_ALG_NAME "tcm_sita"
[Hiremath, Vaibhav] Move this after include statement.
> +#include "tcm-utils.h"
> +
> +#define ALIGN_DOWN(value, align) ((value) & ~((align) - 1))
> +
> +/* Individual selection criteria for different scan areas */
> +static s32 CR_L2R_T2B = CR_BIAS_HORIZONTAL;
> +
[Hiremath, Vaibhav] Not good practice to define variable in caps.
Also why do we need this variable which is not getting modified and used as constant only?
> +/*********************************************
> + * 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_free(struct tcm *tcm, 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 align,
> + struct tcm_area *area);
> +
> +static s32 scan_l2r_t2b(struct tcm *tcm, u16 w, u16 h, u16 align,
> + struct tcm_area *field, struct tcm_area *area);
> +
> +/*********************************************
> + * Support Infrastructure Methods
> + *********************************************/
> +static s32 is_area_free(struct tcm_area ***map, u16 x0, u16 y0, u16 w, u16
> h);
> +
> +static s32 update_candidate(struct tcm *tcm, u16 x0, u16 y0, u16 w, u16 h,
> + struct tcm_area *field, s32 criteria,
> + struct score *best);
> +
> +static void get_nearness_factor(struct tcm_area *field,
> + struct tcm_area *candidate,
> + struct nearness_factor *nf);
> +
> +static void get_neighbor_stats(struct tcm *tcm, struct tcm_area *area,
> + struct neighbor_stats *stat);
> +
> +static void fill_area(struct tcm *tcm,
> + struct tcm_area *area, struct tcm_area *parent);
> +
> +/*********************************************/
> +
> +/*********************************************
> + * Utility Methods
> + *********************************************/
> +struct tcm *sita_init(u16 width, u16 height, void *attr)
> +{
> + struct tcm *tcm;
> + struct sita_pvt *pvt;
> + struct tcm_area area = {0};
> + s32 i;
> +
> + if (width == 0 || height == 0)
> + return NULL;
> +
> + tcm = kzalloc(sizeof(*tcm), GFP_KERNEL);
> + pvt = kzalloc(sizeof(*pvt), GFP_KERNEL);
> + if (!tcm || !pvt)
> + goto error;
> +
> + /* Updating the pointers to SiTA implementation APIs */
> + tcm->height = height;
> + tcm->width = width;
> + tcm->reserve_2d = sita_reserve_2d;
> + tcm->free = sita_free;
> + tcm->deinit = sita_deinit;
> + tcm->pvt = (void *)pvt;
> +
> + mutex_init(&(pvt->mtx));
> +
> + /* Creating tam map */
> + pvt->map = kzalloc(sizeof(*pvt->map) * tcm->width, GFP_KERNEL);
> + if (!pvt->map)
> + goto error;
> +
> + for (i = 0; i < tcm->width; i++) {
> + pvt->map[i] =
> + kzalloc(sizeof(**pvt->map) * tcm->height,
> + GFP_KERNEL);
> + if (pvt->map[i] == NULL) {
> + while (i--)
> + kfree(pvt->map[i]);
> + kfree(pvt->map);
> + goto error;
> + }
> + }
> +
> + mutex_lock(&(pvt->mtx));
> + assign(&area, 0, 0, width - 1, height - 1);
> + fill_area(tcm, &area, NULL);
> + mutex_unlock(&(pvt->mtx));
> + return tcm;
> +
> +error:
> + kfree(tcm);
> + kfree(pvt);
> + return NULL;
> +}
> +
> +static void sita_deinit(struct tcm *tcm)
> +{
> + struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
> + struct tcm_area area = {0};
> + s32 i;
> +
> + area.p1.x = tcm->width - 1;
> + area.p1.y = tcm->height - 1;
> +
> + mutex_lock(&(pvt->mtx));
> + fill_area(tcm, &area, NULL);
> + mutex_unlock(&(pvt->mtx));
> +
> + mutex_destroy(&(pvt->mtx));
> +
> + for (i = 0; i < tcm->height; i++)
> + kfree(pvt->map[i]);
> + kfree(pvt->map);
> + kfree(pvt);
[Hiremath, Vaibhav] Why are we not freeing tcm memory here?
Thanks,
Vaibhav
> +}
> +
> +/**
> + * Reserve a 2D area in the container
> + *
> + * @param w width
> + * @param h height
> + * @param area pointer to the area that will be populated with the
> reesrved
> + * area
> + *
> + * @return 0 on success, non-0 error value on failure.
> + */
> +static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u8 align,
> + struct tcm_area *area)
> +{
> + s32 ret;
> + struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
> +
> + /* not supporting more than 64 as alignment */
> + if (align > 64)
> + return -EINVAL;
> +
> + /* we prefer 1, 32 and 64 as alignment */
> + align = align <= 1 ? 1 : align <= 32 ? 32 : 64;
> +
> + mutex_lock(&(pvt->mtx));
> + ret = scan_areas_and_find_fit(tcm, w, h, align, area);
> + if (!ret)
> + /* update map */
> + fill_area(tcm, area, area);
> +
> + mutex_unlock(&(pvt->mtx));
> + return ret;
> +}
> +
> +/**
> + * Unreserve a previously allocated 2D or 1D area
> + * @param area area to be freed
> + * @return 0 - success
> + */
> +static s32 sita_free(struct tcm *tcm, struct tcm_area *area)
> +{
> + struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
> +
> + mutex_lock(&(pvt->mtx));
> +
> + /* Clear the contents of the associated tiles in the map */
> + fill_area(tcm, area, NULL);
> +
> + mutex_unlock(&(pvt->mtx));
> +
> + return 0;
> +}
> +
> +/**
> + * Note: In general the cordinates in the scan field area relevant to the
> can
> + * sweep directions. The scan origin (e.g. top-left corner) will always be
> + * the p0 member of the field. Therfore, for a scan from top-left p0.x <=
> p1.x
> + * and p0.y <= p1.y; whereas, for a scan from bottom-right p1.x <= p0.x and
> p1.y
> + * <= p0.y
> + */
> +
> +/**
> + * Raster scan horizontally left to right from top to bottom to find a
> place for
> + * a 2D area of given size inside a scan field.
> + *
> + * @param w width of desired area
> + * @param h height of desired area
> + * @param align desired area alignment
> + * @param area pointer to the area that will be set to the best position
> + * @param field area to scan (inclusive)
> + *
> + * @return 0 on success, non-0 error value on failure.
> + */
> +static s32 scan_l2r_t2b(struct tcm *tcm, u16 w, u16 h, u16 align,
> + struct tcm_area *field, struct tcm_area *area)
> +{
> + s32 x, y;
> + s16 start_x, end_x, start_y, end_y;
> + struct tcm_area ***map = ((struct sita_pvt *)tcm->pvt)->map;
> + struct score best = {{0}, {0}, {0}, 0};
> +
> + 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 > LEN(end_x, start_x) || h > LEN(end_y, start_y))
> + return -ENOSPC;
> +
> + start_x = ALIGN(start_x, align);
> +
> + /* check if allocation would still fit in scan area */
> + if (w > 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", align, start_x, end_x, start_y, end_y);
> +
> + /* scan field top-to-bottom, left-to-right */
> + for (y = start_y; y <= end_y; y++) {
> + for (x = start_x; x <= end_x; x += align) {
> + if (is_area_free(map, x, y, w, h)) {
> + P3("found shoulder: %d,%d", x, y);
> +
> + /* update best candidate */
> + if (update_candidate(tcm, x, y, w, h, field,
> + CR_L2R_T2B, &best))
> + goto done;
> + break;
> + } else if (map[x][y]) {
> + /* step over 2D areas */
> + x = ALIGN_DOWN(map[x][y]->p1.x, align);
> + P3("moving to: %d,%d", x, y);
> + }
> + }
> + }
> +
> + if (!best.a.tcm)
> + return -ENOSPC;
> +done:
> + assign(area, best.a.p0.x, best.a.p0.y, best.a.p1.x, best.a.p1.y);
> + return 0;
> +}
> +
> +/**
> + * Find a place for a 2D area of given size inside a scan field based on
> its
> + * alignment needs.
> + *
> + * @param w width of desired area
> + * @param h height of desired area
> + * @param align desired area alignment
> + * @param area pointer to the area that will be set to the best position
> + *
> + * @return 0 on success, non-0 error value on failure.
> + */
> +static s32 scan_areas_and_find_fit(struct tcm *tcm, u16 w, u16 h, u16 align,
> + struct tcm_area *area)
> +{
> + struct tcm_area field = {0};
> +
> + /* scan whole container left to right, top to bottom */
> + assign(&field, 0, 0, tcm->width - 1, tcm->height - 1);
> + return scan_l2r_t2b(tcm, w, h, align, &field, area);
> +}
> +
> +/* check if an entire area is free */
> +static s32 is_area_free(struct tcm_area ***map, u16 x0, u16 y0, u16 w, u16
> h)
> +{
> + u16 x = 0, y = 0;
> + for (y = y0; y < y0 + h; y++) {
> + for (x = x0; x < x0 + w; x++) {
> + if (map[x][y])
> + return false;
> + }
> + }
> + return true;
> +}
> +
> +/* fills an area with a parent tcm_area */
> +static void fill_area(struct tcm *tcm, struct tcm_area *area,
> + struct tcm_area *parent)
> +{
> + 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] = parent;
> +}
> +
> +/**
> + * Compares a candidate area to the current best area, and if it is a
> better
> + * fit, it updates the best to this one.
> + *
> + * @param x0, y0, w, h top, left, width, height of candidate area
> + * @param field scan field
> + * @param criteria scan criteria
> + * @param best best candidate and its scores
> + *
> + * @return 1 (true) if the candidate area is known to be the final best, so
> no
> + * more searching should be performed
> + */
> +static s32 update_candidate(struct tcm *tcm, u16 x0, u16 y0, u16 w, u16 h,
> + struct tcm_area *field, s32 criteria,
> + struct score *best)
> +{
> + struct score me; /* score for area */
> +
> + /*
> + * If first found is enabled then we stop looking
> + * NOTE: For horizontal bias we always give the first found, because
> our
> + * scan is horizontal-raster-based and the first candidate will always
> + * have the horizontal bias.
> + */
> + bool first = criteria & (CR_FIRST_FOUND | CR_BIAS_HORIZONTAL);
> +
> + assign(&me.a, x0, y0, x0 + w - 1, y0 + h - 1);
> +
> + /* calculate score for current candidate */
> + if (!first) {
> + get_neighbor_stats(tcm, &me.a, &me.n);
> + me.neighs = me.n.edge + me.n.busy;
> + get_nearness_factor(field, &me.a, &me.f);
> + }
> +
> + /* the 1st candidate is always the best */
> + if (!best->a.tcm)
> + goto better;
> +
> + /* see if this are is better than the best so far */
> +
> + /* neighbor check */
> + if ((criteria & CR_MAX_NEIGHS) &&
> + me.neighs > best->neighs)
> + goto better;
> +
> + /* 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
> + */
> + LEN(me.a.p0.y, field->p0.y) >
> + LEN(best->a.p0.y, field->p0.y))
> + goto better;
> +
> + /* diagonal balance check */
> + if ((criteria & CR_DIAGONAL_BALANCE) &&
> + best->neighs <= me.neighs &&
> + (best->neighs < me.neighs ||
> + /* this implies that neighs and occupied match */
> + best->n.busy < me.n.busy ||
> + (best->n.busy == me.n.busy &&
> + /* check the nearness factor */
> + best->f.x + best->f.y > me.f.x + me.f.y)))
> + goto better;
> +
> + /* not better, keep going */
> + return 0;
> +
> +better:
> + /* save current area as best */
> + memcpy(best, &me, sizeof(me));
> + best->a.tcm = tcm;
> + return first;
> +}
> +
> +/**
> + * Calculate the nearness factor of an area in a search field. The
> nearness
> + * factor is smaller if the area is closer to the search origin.
> + */
> +static void get_nearness_factor(struct tcm_area *field, struct tcm_area
> *area,
> + struct nearness_factor *nf)
> +{
> + /**
> + * Using signed math as field coordinates may be reversed if
> + * search direction is right-to-left or bottom-to-top.
> + */
> + 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);
> +}
> +
> +/* get neighbor statistics */
> +static void get_neighbor_stats(struct tcm *tcm, struct tcm_area *area,
> + struct neighbor_stats *stat)
> +{
> + s16 x = 0, y = 0;
> + struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
> +
> + /* Clearing any exisiting values */
> + memset(stat, 0, sizeof(*stat));
> +
> + /* process top & bottom edges */
> + for (x = area->p0.x; x <= area->p1.x; x++) {
> + if (area->p0.y == 0)
> + stat->edge++;
> + else if (pvt->map[x][area->p0.y - 1])
> + stat->busy++;
> +
> + if (area->p1.y == tcm->height - 1)
> + stat->edge++;
> + else if (pvt->map[x][area->p1.y + 1])
> + stat->busy++;
> + }
> +
> + /* process left & right edges */
> + for (y = area->p0.y; y <= area->p1.y; ++y) {
> + if (area->p0.x == 0)
> + stat->edge++;
> + else if (pvt->map[area->p0.x - 1][y])
> + stat->busy++;
> +
> + if (area->p1.x == tcm->width - 1)
> + stat->edge++;
> + else if (pvt->map[area->p1.x + 1][y])
> + stat->busy++;
> + }
> +}
> diff --git a/drivers/media/video/tiler/tcm/tcm-sita.h
> b/drivers/media/video/tiler/tcm/tcm-sita.h
> new file mode 100644
> index 0000000..ab2d05b
> --- /dev/null
> +++ b/drivers/media/video/tiler/tcm/tcm-sita.h
> @@ -0,0 +1,37 @@
> +/*
> + * tcm_sita.h
> + *
> + * SImple Tiler Allocator (SiTA) interface.
> + *
> + * Author: Ravi Ramachandra <r.ramachandra@xxxxxx>
> + *
> + * Copyright (C) 2009-2010 Texas Instruments, Inc.
> + *
> + * This package is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License version 2 as
> + * published by the Free Software Foundation.
> + *
> + * THIS PACKAGE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
> + * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
> + * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
> + */
> +
> +#ifndef TCM_SITA_H
> +#define TCM_SITA_H
> +
> +#include "../tcm.h"
> +
> +/**
> + * Create a SiTA tiler container manager.
> + *
> + * @param width Container width
> + * @param height Container height
> + * @param attr unused
> + *
> + * @return TCM instance
> + */
> +struct tcm *sita_init(u16 width, u16 height, void *attr);
> +
> +TCM_INIT(sita_init, void);
> +
> +#endif /* TCM_SITA_H_ */
> --
> 1.6.3.3
--
To unsubscribe from this list: send the line "unsubscribe linux-omap" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
