Revert "gpu: drm: omap: Use bitmaps for placement"

This reverts commit 2857ec212485e407354d03be48cf00f03437c098.

diff --git a/drivers/staging/omapdrm/Makefile b/drivers/staging/omapdrm/Makefile
index a6bddd858eb8531914f600c3199eb8b693f41d23..d85e058f2845a014c0216cabeda52d70cc7bf0b6 100644 (file)
--- a/drivers/staging/omapdrm/Makefile
+++ b/drivers/staging/omapdrm/Makefile
@@ -16,7 +16,7 @@ omapdrm-y := omap_drv.o \
        omap_gem.o \
        omap_gem_dmabuf.o \
        omap_dmm_tiler.o \
-       sita.o
+       tcm-sita.o
 
 # temporary:
 omapdrm-y += omap_gem_helpers.o

diff --git a/drivers/staging/omapdrm/omap_dmm_tiler.c b/drivers/staging/omapdrm/omap_dmm_tiler.c
index fdf8e98fcf36d959b59051f9bb9c35fb51c183ad..b6c31c60fd51c73e37d96fd0bb88476c409b1773 100644 (file)
--- a/drivers/staging/omapdrm/omap_dmm_tiler.c
+++ b/drivers/staging/omapdrm/omap_dmm_tiler.c
@@ -353,7 +353,6 @@ struct tiler_block *tiler_reserve_2d(enum tiler_fmt fmt, uint16_t w,
        u32 min_align = 128;
        int ret;
        unsigned long flags;
-       size_t slot_bytes;
 
        BUG_ON(!validfmt(fmt));
 
@@ -362,15 +361,13 @@ struct tiler_block *tiler_reserve_2d(enum tiler_fmt fmt, uint16_t w,
        h = DIV_ROUND_UP(h, geom[fmt].slot_h);
 
        /* convert alignment to slots */
-       slot_bytes = geom[fmt].slot_w * geom[fmt].cpp;
-       min_align = max(min_align, slot_bytes);
-       align = (align > min_align) ? ALIGN(align, min_align) : min_align;
-       align /= slot_bytes;
+       min_align = max(min_align, (geom[fmt].slot_w * geom[fmt].cpp));
+       align = ALIGN(align, min_align);
+       align /= geom[fmt].slot_w * geom[fmt].cpp;
 
        block->fmt = fmt;
 
-       ret = tcm_reserve_2d(containers[fmt], w, h, align, -1, slot_bytes,
-                       &block->area);
+       ret = tcm_reserve_2d(containers[fmt], w, h, align, &block->area);
        if (ret) {
                kfree(block);
                return ERR_PTR(-ENOMEM);
@@ -719,7 +716,8 @@ static int omap_dmm_probe(struct platform_device *dev)
           programming during reill operations */
        for (i = 0; i < omap_dmm->num_lut; i++) {
                omap_dmm->tcm[i] = sita_init(omap_dmm->container_width,
-                                               omap_dmm->container_height);
+                                               omap_dmm->container_height,
+                                               NULL);
 
                if (!omap_dmm->tcm[i]) {
                        dev_err(&dev->dev, "failed to allocate container\n");

diff --git a/drivers/staging/omapdrm/sita.c b/drivers/staging/omapdrm/sita.c
deleted file mode 100644 (file)
index 07fc7ee..0000000
--- a/drivers/staging/omapdrm/sita.c
+++ /dev/null
@@ -1,261 +0,0 @@
-/*
- * sita.c
- *
- * SImple Tiler Allocator (SiTA): 2D and 1D allocation(reservation) algorithm
- *
- * Authors: Ravi Ramachandra <r.ramachandra@ti.com>,
- *          Lajos Molnar <molnar@ti.com>
- *          Andy Gross <andy.gross@ti.com>
- *
- * Copyright (C) 2012 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/init.h>
-#include <linux/module.h>
-#include <linux/errno.h>
-#include <linux/sched.h>
-#include <linux/wait.h>
-#include <linux/bitmap.h>
-#include <linux/slab.h>
-#include "tcm.h"
-
-static unsigned long mask[8];
-/*
- * pos         position in bitmap
- * w           width in slots
- * h           height in slots
- * map         ptr to bitmap
- * stride              slots in a row
- */
-static void free_slots(unsigned long pos, uint16_t w, uint16_t h,
-               unsigned long *map, uint16_t stride)
-{
-       int i;
-
-       for (i = 0; i < h; i++, pos += stride)
-               bitmap_clear(map, pos, w);
-}
-
-/*
- * w           width in slots
- * pos         ptr to position
- * map         ptr to bitmap
- * num_bits    number of bits in bitmap
- */
-static int r2l_b2t_1d(uint16_t w, unsigned long *pos, unsigned long *map,
-               size_t num_bits)
-{
-       unsigned long search_count = 0;
-       unsigned long bit;
-       bool area_found = false;
-
-       *pos = num_bits - w;
-
-       while (search_count < num_bits) {
-               bit = find_next_bit(map, num_bits, *pos);
-
-               if (bit - *pos >= w) {
-                       /* found a long enough free area */
-                       bitmap_set(map, *pos, w);
-                       area_found = true;
-                       break;
-               }
-
-               search_count = num_bits - bit + w;
-               *pos = bit - w;
-       }
-
-       return (area_found) ? 0 : -ENOMEM;
-}
-
-/*
- * w = width in slots
- * h = height in slots
- * a = align in slots  (mask, 2^n-1, 0 is unaligned)
- * offset = offset in bytes from 4KiB
- * pos = position in bitmap for buffer
- * map = bitmap ptr
- * num_bits = size of bitmap
- * stride = bits in one row of container
- */
-static int l2r_t2b(uint16_t w, uint16_t h, uint16_t a, int16_t offset,
-               unsigned long *pos, unsigned long slot_bytes,
-               unsigned long *map, size_t num_bits, size_t slot_stride)
-{
-       int i;
-       unsigned long index;
-       bool area_free;
-       unsigned long slots_per_band = PAGE_SIZE / slot_bytes;
-       unsigned long bit_offset = (offset > 0) ? offset / slot_bytes : 0;
-       unsigned long curr_bit = bit_offset;
-
-       /* reset alignment to 1 if we are matching a specific offset */
-       /* adjust alignment - 1 to get to the format expected in bitmaps */
-       a = (offset > 0) ? 0 : a - 1;
-
-       /* FIXME Return error if slots_per_band > stride */
-
-       while (curr_bit < num_bits) {
-               *pos = bitmap_find_next_zero_area(map, num_bits, curr_bit, w,
-                               a);
-
-               /* skip forward if we are not at right offset */
-               if (bit_offset > 0 && (*pos % slots_per_band != bit_offset)) {
-                       curr_bit = ALIGN(*pos, slots_per_band) + bit_offset;
-                       continue;
-               }
-
-               /* skip forward to next row if we overlap end of row */
-               if ((*pos % slot_stride) + w > slot_stride) {
-                       curr_bit = ALIGN(*pos, slot_stride) + bit_offset;
-                       continue;
-               }
-
-               /* TODO: Handle overlapping 4K boundaries */
-
-               /* break out of look if we will go past end of container */
-               if ((*pos + slot_stride * h) > num_bits)
-                       break;
-
-               /* generate mask that represents out matching pattern */
-               bitmap_clear(mask, 0, slot_stride);
-               bitmap_set(mask, (*pos % BITS_PER_LONG), w);
-
-               /* assume the area is free until we find an overlap */
-               area_free = true;
-
-               /* check subsequent rows to see if complete area is free */
-               for (i = 1; i < h; i++) {
-                       index = *pos / BITS_PER_LONG + i * 8;
-                       if (bitmap_intersects(&map[index], mask,
-                               (*pos % BITS_PER_LONG) + w)) {
-                               area_free = false;
-                               break;
-                       }
-               }
-
-               if (area_free)
-                       break;
-
-               /* go forward past this match */
-               if (bit_offset > 0)
-                       curr_bit = ALIGN(*pos, slots_per_band) + bit_offset;
-               else
-                       curr_bit = *pos + a + 1;
-       }
-
-       if (area_free) {
-               /* set area as in-use. iterate over rows */
-               for (i = 0, index = *pos; i < h; i++, index += slot_stride)
-                       bitmap_set(map, index, w);
-       }
-
-       return (area_free) ? 0 : -ENOMEM;
-}
-
-static s32 sita_reserve_1d(struct tcm *tcm, u32 num_slots,
-                          struct tcm_area *area)
-{
-       unsigned long pos;
-       int ret;
-
-       spin_lock(&(tcm->lock));
-       ret = r2l_b2t_1d(num_slots, &pos, tcm->bitmap, tcm->map_size);
-       if (!ret) {
-               area->p0.x = pos % tcm->width;
-               area->p0.y = pos / tcm->width;
-               area->p1.x = (pos + num_slots - 1) % tcm->width;
-               area->p1.y = (pos + num_slots - 1) / tcm->width;
-       }
-       spin_unlock(&(tcm->lock));
-
-       return ret;
-}
-
-static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u16 align,
-                               int16_t offset, uint16_t slot_bytes,
-                               struct tcm_area *area)
-{
-       unsigned long pos;
-       int ret;
-
-       spin_lock(&(tcm->lock));
-       ret = l2r_t2b(w, h, align, offset, &pos, slot_bytes, tcm->bitmap,
-                       tcm->map_size, tcm->width);
-
-       if (!ret) {
-               area->p0.x = pos % tcm->width;
-               area->p0.y = pos / tcm->width;
-               area->p1.x = area->p0.x + w - 1;
-               area->p1.y = area->p0.y + h - 1;
-       }
-       spin_unlock(&(tcm->lock));
-
-       return ret;
-}
-
-static void sita_deinit(struct tcm *tcm)
-{
-       kfree(tcm);
-}
-
-static s32 sita_free(struct tcm *tcm, struct tcm_area *area)
-{
-       unsigned long pos;
-       uint16_t w, h;
-
-       pos = area->p0.x + area->p0.y * tcm->width;
-       if (area->is2d) {
-               w = area->p1.x - area->p0.x + 1;
-               h = area->p1.y - area->p0.y + 1;
-       } else {
-               w = area->p1.x + area->p1.y * tcm->width - pos + 1;
-               h = 1;
-       }
-
-       spin_lock(&(tcm->lock));
-       free_slots(pos, w, h, tcm->bitmap, tcm->width);
-       spin_unlock(&(tcm->lock));
-       return 0;
-}
-
-struct tcm *sita_init(u16 width, u16 height)
-{
-       struct tcm *tcm;
-       size_t map_size = BITS_TO_LONGS(width*height) * sizeof(unsigned long);
-
-       if (width == 0 || height == 0)
-               return NULL;
-
-       tcm = kzalloc(sizeof(*tcm) + map_size, GFP_KERNEL);
-       if (!tcm)
-               goto error;
-
-       /* 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->free = sita_free;
-       tcm->deinit = sita_deinit;
-
-       spin_lock_init(&tcm->lock);
-       tcm->bitmap = (unsigned long *)(tcm + 1);
-       bitmap_clear(tcm->bitmap, 0, width*height);
-
-       tcm->map_size = width*height;
-
-       return tcm;
-
-error:
-       kfree(tcm);
-       return NULL;
-}

diff --git a/drivers/staging/omapdrm/tcm-sita.c b/drivers/staging/omapdrm/tcm-sita.c
new file mode 100644 (file)
index 0000000..efb6095
--- /dev/null
+++ b/drivers/staging/omapdrm/tcm-sita.c
@@ -0,0 +1,703 @@
+/*
+ * tcm-sita.c
+ *
+ * SImple Tiler Allocator (SiTA): 2D and 1D allocation(reservation) algorithm
+ *
+ * Authors: Ravi Ramachandra <r.ramachandra@ti.com>,
+ *          Lajos Molnar <molnar@ti.com>
+ *
+ * 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 <linux/spinlock.h>
+
+#include "tcm-sita.h"
+
+#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;
+
+/*********************************************
+ *     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 *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);
+
+static s32 scan_r2l_t2b(struct tcm *tcm, u16 w, u16 h, u16 align,
+                       struct tcm_area *field, struct tcm_area *area);
+
+static s32 scan_r2l_b2t_one_dim(struct tcm *tcm, u32 num_slots,
+                       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, struct tcm_pt *attr)
+{
+       struct tcm *tcm;
+       struct sita_pvt *pvt;
+       struct tcm_area area = {0};
+       s32 i;
+
+       if (width == 0 || height == 0)
+               return NULL;
+
+       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->free = sita_free;
+       tcm->deinit = sita_deinit;
+       tcm->pvt = (void *)pvt;
+
+       spin_lock_init(&(pvt->lock));
+
+       /* Creating tam map */
+       pvt->map = kmalloc(sizeof(*pvt->map) * tcm->width, GFP_KERNEL);
+       if (!pvt->map)
+               goto error;
+
+       for (i = 0; i < tcm->width; i++) {
+               pvt->map[i] =
+                       kmalloc(sizeof(**pvt->map) * tcm->height,
+                                                               GFP_KERNEL);
+               if (pvt->map[i] == NULL) {
+                       while (i--)
+                               kfree(pvt->map[i]);
+                       kfree(pvt->map);
+                       goto error;
+               }
+       }
+
+       if (attr && attr->x <= tcm->width && attr->y <= tcm->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 = (tcm->width * 3) / 4;
+               pvt->div_pt.y = (tcm->height * 3) / 4;
+       }
+
+       spin_lock(&(pvt->lock));
+       assign(&area, 0, 0, width - 1, height - 1);
+       fill_area(tcm, &area, NULL);
+       spin_unlock(&(pvt->lock));
+       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;
+
+       spin_lock(&(pvt->lock));
+       fill_area(tcm, &area, NULL);
+       spin_unlock(&(pvt->lock));
+
+       for (i = 0; i < tcm->height; i++)
+               kfree(pvt->map[i]);
+       kfree(pvt->map);
+       kfree(pvt);
+}
+
+/**
+ * Reserve a 1D area in the container
+ *
+ * @param num_slots    size of 1D area
+ * @param area         pointer to the area that will be populated with the
+ *                     reserved area
+ *
+ * @return 0 on success, non-0 error value on failure.
+ */
+static s32 sita_reserve_1d(struct tcm *tcm, u32 num_slots,
+                          struct tcm_area *area)
+{
+       s32 ret;
+       struct tcm_area field = {0};
+       struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
+
+       spin_lock(&(pvt->lock));
+
+       /* Scanning entire container */
+       assign(&field, tcm->width - 1, tcm->height - 1, 0, 0);
+
+       ret = scan_r2l_b2t_one_dim(tcm, num_slots, &field, area);
+       if (!ret)
+               /* update map */
+               fill_area(tcm, area, area);
+
+       spin_unlock(&(pvt->lock));
+       return ret;
+}
+
+/**
+ * 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 reserved
+ *             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;
+
+       spin_lock(&(pvt->lock));
+       ret = scan_areas_and_find_fit(tcm, w, h, align, area);
+       if (!ret)
+               /* update map */
+               fill_area(tcm, area, area);
+
+       spin_unlock(&(pvt->lock));
+       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;
+
+       spin_lock(&(pvt->lock));
+
+       /* check that this is in fact an existing area */
+       WARN_ON(pvt->map[area->p0.x][area->p0.y] != area ||
+               pvt->map[area->p1.x][area->p1.y] != area);
+
+       /* Clear the contents of the associated tiles in the map */
+       fill_area(tcm, area, NULL);
+
+       spin_unlock(&(pvt->lock));
+
+       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 right to left 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_r2l_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, found_x = -1;
+       struct tcm_area ***map = ((struct sita_pvt *)tcm->pvt)->map;
+       struct score best = {{0}, {0}, {0}, 0};
+
+       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 > LEN(start_x, end_x) || h > 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, align); /* - 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;
+
+       /* scan field top-to-bottom, right-to-left */
+       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)) {
+                               found_x = x;
+
+                               /* update best candidate */
+                               if (update_candidate(tcm, x, y, w, h, field,
+                                                       CR_R2L_T2B, &best))
+                                       goto done;
+
+                               /* change upper x bound */
+                               end_x = x + 1;
+                               break;
+                       } else if (map[x][y] && map[x][y]->is2d) {
+                               /* step over 2D areas */
+                               x = ALIGN(map[x][y]->p0.x - w + 1, align);
+                       }
+               }
+
+               /* break if you find a free area shouldering the scan field */
+               if (found_x == start_x)
+                       break;
+       }
+
+       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;
+}
+
+/**
+ * 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, found_x = -1;
+       struct tcm_area ***map = ((struct sita_pvt *)tcm->pvt)->map;
+       struct score best = {{0}, {0}, {0}, 0};
+
+       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;
+
+       /* 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)) {
+                               found_x = x;
+
+                               /* update best candidate */
+                               if (update_candidate(tcm, x, y, w, h, field,
+                                                       CR_L2R_T2B, &best))
+                                       goto done;
+                               /* change upper x bound */
+                               end_x = x - 1;
+
+                               break;
+                       } else if (map[x][y] && map[x][y]->is2d) {
+                               /* step over 2D areas */
+                               x = ALIGN_DOWN(map[x][y]->p1.x, align);
+                       }
+               }
+
+               /* break if you find a free area shouldering the scan field */
+               if (found_x == start_x)
+                       break;
+       }
+
+       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;
+}
+
+/**
+ * Raster scan horizontally right to left from bottom to top to find a place
+ * for a 1D area of given size inside a scan field.
+ *
+ * @param num_slots    size 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_r2l_b2t_one_dim(struct tcm *tcm, u32 num_slots,
+                               struct tcm_area *field, struct tcm_area *area)
+{
+       s32 found = 0;
+       s16 x, y;
+       struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
+       struct tcm_area *p;
+
+       /* check scan area co-ordinates */
+       if (field->p0.y < field->p1.y)
+               return -EINVAL;
+
+       /**
+        * Currently we only support full width 1D scan field, which makes sense
+        * since 1D slot-ordering spans the full container width.
+        */
+       if (tcm->width != field->p0.x - field->p1.x + 1)
+               return -EINVAL;
+
+       /* check if allocation would fit in scan area */
+       if (num_slots > tcm->width * LEN(field->p0.y, field->p1.y))
+               return -ENOSPC;
+
+       x = field->p0.x;
+       y = field->p0.y;
+
+       /* find num_slots consecutive free slots to the left */
+       while (found < num_slots) {
+               if (y < 0)
+                       return -ENOSPC;
+
+               /* remember bottom-right corner */
+               if (found == 0) {
+                       area->p1.x = x;
+                       area->p1.y = y;
+               }
+
+               /* skip busy regions */
+               p = pvt->map[x][y];
+               if (p) {
+                       /* move to left of 2D areas, top left of 1D */
+                       x = p->p0.x;
+                       if (!p->is2d)
+                               y = p->p0.y;
+
+                       /* start over */
+                       found = 0;
+               } else {
+                       /* count consecutive free slots */
+                       found++;
+                       if (found == num_slots)
+                               break;
+               }
+
+               /* move to the left */
+               if (x == 0)
+                       y--;
+               x = (x ? : tcm->width) - 1;
+
+       }
+
+       /* set top-left corner */
+       area->p0.x = x;
+       area->p0.y = 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)
+{
+       s32 ret = 0;
+       struct tcm_area field = {0};
+       u16 boundary_x, boundary_y;
+       struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
+
+       if (align > 1) {
+               /* prefer top-left corner */
+               boundary_x = pvt->div_pt.x - 1;
+               boundary_y = pvt->div_pt.y - 1;
+
+               /* expand width and height if needed */
+               if (w > pvt->div_pt.x)
+                       boundary_x = tcm->width - 1;
+               if (h > pvt->div_pt.y)
+                       boundary_y = tcm->height - 1;
+
+               assign(&field, 0, 0, boundary_x, boundary_y);
+               ret = scan_l2r_t2b(tcm, w, h, align, &field, area);
+
+               /* scan whole container if failed, but do not scan 2x */
+               if (ret != 0 && (boundary_x != tcm->width - 1 ||
+                                boundary_y != tcm->height - 1)) {
+                       /* scan the entire container if nothing found */
+                       assign(&field, 0, 0, tcm->width - 1, tcm->height - 1);
+                       ret = scan_l2r_t2b(tcm, w, h, align, &field, area);
+               }
+       } else if (align == 1) {
+               /* prefer top-right corner */
+               boundary_x = pvt->div_pt.x;
+               boundary_y = pvt->div_pt.y - 1;
+
+               /* expand width and height if needed */
+               if (w > (tcm->width - pvt->div_pt.x))
+                       boundary_x = 0;
+               if (h > pvt->div_pt.y)
+                       boundary_y = tcm->height - 1;
+
+               assign(&field, tcm->width - 1, 0, boundary_x, boundary_y);
+               ret = scan_r2l_t2b(tcm, w, h, align, &field, area);
+
+               /* scan whole container if failed, but do not scan 2x */
+               if (ret != 0 && (boundary_x != 0 ||
+                                boundary_y != tcm->height - 1)) {
+                       /* scan the entire container if nothing found */
+                       assign(&field, tcm->width - 1, 0, 0, tcm->height - 1);
+                       ret = scan_r2l_t2b(tcm, w, h, align, &field,
+                                          area);
+               }
+       }
+
+       return ret;
+}
+
+/* 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;
+       struct tcm_area a, a_;
+
+       /* set area's tcm; otherwise, enumerator considers it invalid */
+       area->tcm = tcm;
+
+       tcm_for_each_slice(a, *area, a_) {
+               for (x = a.p0.x; x <= a.p1.x; ++x)
+                       for (y = a.p0.y; y <= a.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 */
+
+       /*
+        * 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_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;
+
+       BUG_ON(first);
+
+       /* 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/staging/omapdrm/tcm.h b/drivers/staging/omapdrm/tcm.h
index ef7df7d6fc84c7faa2b92b94e93be1853a8c4c55..a8d5ce47686f791981b96b401d701ae83abab585 100644 (file)
--- a/drivers/staging/omapdrm/tcm.h
+++ b/drivers/staging/omapdrm/tcm.h
@@ -61,17 +61,18 @@ struct tcm {
 
        unsigned int y_offset;  /* offset to use for y coordinates */
 
-       spinlock_t lock;
-       unsigned long *bitmap;
-       size_t map_size;
+       /* 'pvt' structure shall contain any tcm details (attr) along with
+       linked list of allocated areas and mutex for mutually exclusive access
+       to the list.  It may also contain copies of width and height to notice
+       any changes to the publicly available width and height fields. */
+       void *pvt;
 
        /* function table */
-       s32 (*reserve_2d)(struct tcm *tcm, u16 height, u16 width, u16 align,
-                         int16_t offset, uint16_t slot_bytes,
+       s32 (*reserve_2d)(struct tcm *tcm, u16 height, u16 width, u8 align,
                          struct tcm_area *area);
        s32 (*reserve_1d)(struct tcm *tcm, u32 slots, struct tcm_area *area);
-       s32 (*free)(struct tcm *tcm, struct tcm_area *area);
-       void (*deinit)(struct tcm *tcm);
+       s32 (*free)      (struct tcm *tcm, struct tcm_area *area);
+       void (*deinit)   (struct tcm *tcm);
 };
 
 /*=============================================================================
@@ -90,7 +91,7 @@ struct tcm {
  *
  */
 
-struct tcm *sita_init(u16 width, u16 height);
+struct tcm *sita_init(u16 width, u16 height, struct tcm_pt *attr);
 
 
 /**
@@ -119,9 +120,6 @@ static inline void tcm_deinit(struct tcm *tcm)
  *                     all values may be supported by the container manager,
  *                     but it must support 0 (1), 32 and 64.
  *                     0 value is equivalent to 1.
- * @param offset       Offset requirement, in bytes.  This is the offset
- *                     from a 4KiB aligned virtual address.
- * @param slot_bytes   Width of slot in bytes
  * @param area         Pointer to where the reserved area should be stored.
  *
  * @return 0 on success.  Non-0 error code on failure.  Also,
@@ -131,8 +129,7 @@ static inline void tcm_deinit(struct tcm *tcm)
  *         allocation.
  */
 static inline s32 tcm_reserve_2d(struct tcm *tcm, u16 width, u16 height,
-                               u16 align, int16_t offset, uint16_t slot_bytes,
-                               struct tcm_area *area)
+                                u16 align, struct tcm_area *area)
 {
        /* perform rudimentary error checking */
        s32 res = tcm  == NULL ? -ENODEV :
@@ -143,8 +140,7 @@ static inline s32 tcm_reserve_2d(struct tcm *tcm, u16 width, u16 height,
 
        if (!res) {
                area->is2d = true;
-               res = tcm->reserve_2d(tcm, height, width, align, offset,
-                                       slot_bytes, area);
+               res = tcm->reserve_2d(tcm, height, width, align, area);
                area->tcm = res ? NULL : tcm;
        }