drivers/gpu/drm/omapdrm/tcm-sita.c

   1 /*
   2  * SImple Tiler Allocator (SiTA): 2D and 1D allocation(reservation) algorithm
   3  *
   4  * Authors: Ravi Ramachandra <r.ramachandra@ti.com>,
   5  *          Lajos Molnar <molnar@ti.com>
   6  *          Andy Gross <andy.gross@ti.com>
   7  *
   8  * Copyright (C) 2012 Texas Instruments Incorporated - http://www.ti.com/
   9  *
  10  * This package is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License version 2 as
  12  * published by the Free Software Foundation.
  13  *
  14  * THIS PACKAGE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  15  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  16  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  17  *
  18  */
  19 #include <linux/init.h>
  20 #include <linux/module.h>
  21 #include <linux/errno.h>
  22 #include <linux/sched.h>
  23 #include <linux/wait.h>
  24 #include <linux/bitmap.h>
  25 #include <linux/slab.h>
  26 #include "tcm.h"
  27
  28 static unsigned long mask[8];
  29 /*
  30  * pos          position in bitmap
  31  * w            width in slots
  32  * h            height in slots
  33  * map          ptr to bitmap
  34  * stride               slots in a row
  35  */
  36 static void free_slots(unsigned long pos, u16 w, u16 h,
  37                 unsigned long *map, u16 stride)
  38 {
  39         int i;
  40
  41         for (i = 0; i < h; i++, pos += stride)
  42                 bitmap_clear(map, pos, w);
  43 }
  44
  45 /*
  46  * w            width in slots
  47  * pos          ptr to position
  48  * map          ptr to bitmap
  49  * num_bits     number of bits in bitmap
  50  */
  51 static int r2l_b2t_1d(u16 w, unsigned long *pos, unsigned long *map,
  52                 size_t num_bits)
  53 {
  54         unsigned long search_count = 0;
  55         unsigned long bit;
  56         bool area_found = false;
  57
  58         *pos = num_bits - w;
  59
  60         while (search_count < num_bits) {
  61                 bit = find_next_bit(map, num_bits, *pos);
  62
  63                 if (bit - *pos >= w) {
  64                         /* found a long enough free area */
  65                         bitmap_set(map, *pos, w);
  66                         area_found = true;
  67                         break;
  68                 }
  69
  70                 search_count = num_bits - bit + w;
  71                 *pos = bit - w;
  72         }
  73
  74         return (area_found) ? 0 : -ENOMEM;
  75 }
  76
  77 /*
  78  * w = width in slots
  79  * h = height in slots
  80  * a = align in slots   (mask, 2^n-1, 0 is unaligned)
  81  * offset = offset in bytes from 4KiB
  82  * pos = position in bitmap for buffer
  83  * map = bitmap ptr
  84  * num_bits = size of bitmap
  85  * stride = bits in one row of container
  86  */
  87 static int l2r_t2b(u16 w, u16 h, u16 a, s16 offset,
  88                 unsigned long *pos, unsigned long slot_bytes,
  89                 unsigned long *map, size_t num_bits, size_t slot_stride)
  90 {
  91         int i;
  92         unsigned long index;
  93         bool area_free = false;
  94         unsigned long slots_per_band = PAGE_SIZE / slot_bytes;
  95         unsigned long bit_offset = (offset > 0) ? offset / slot_bytes : 0;
  96         unsigned long curr_bit = bit_offset;
  97
  98         /* reset alignment to 1 if we are matching a specific offset */
  99         /* adjust alignment - 1 to get to the format expected in bitmaps */
 100         a = (offset > 0) ? 0 : a - 1;
 101
 102         /* FIXME Return error if slots_per_band > stride */
 103
 104         while (curr_bit < num_bits) {
 105                 *pos = bitmap_find_next_zero_area(map, num_bits, curr_bit, w,
 106                                 a);
 107
 108                 /* skip forward if we are not at right offset */
 109                 if (bit_offset > 0 && (*pos % slots_per_band != bit_offset)) {
 110                         curr_bit = ALIGN(*pos, slots_per_band) + bit_offset;
 111                         continue;
 112                 }
 113
 114                 /* skip forward to next row if we overlap end of row */
 115                 if ((*pos % slot_stride) + w > slot_stride) {
 116                         curr_bit = ALIGN(*pos, slot_stride) + bit_offset;
 117                         continue;
 118                 }
 119
 120                 /* TODO: Handle overlapping 4K boundaries */
 121
 122                 /* break out of look if we will go past end of container */
 123                 if ((*pos + slot_stride * h) > num_bits)
 124                         break;
 125
 126                 /* generate mask that represents out matching pattern */
 127                 bitmap_clear(mask, 0, slot_stride);
 128                 bitmap_set(mask, (*pos % BITS_PER_LONG), w);
 129
 130                 /* assume the area is free until we find an overlap */
 131                 area_free = true;
 132
 133                 /* check subsequent rows to see if complete area is free */
 134                 for (i = 1; i < h; i++) {
 135                         index = *pos / BITS_PER_LONG + i * 8;
 136                         if (bitmap_intersects(&map[index], mask,
 137                                 (*pos % BITS_PER_LONG) + w)) {
 138                                 area_free = false;
 139                                 break;
 140                         }
 141                 }
 142
 143                 if (area_free)
 144                         break;
 145
 146                 /* go forward past this match */
 147                 if (bit_offset > 0)
 148                         curr_bit = ALIGN(*pos, slots_per_band) + bit_offset;
 149                 else
 150                         curr_bit = *pos + a + 1;
 151         }
 152
 153         if (area_free) {
 154                 /* set area as in-use. iterate over rows */
 155                 for (i = 0, index = *pos; i < h; i++, index += slot_stride)
 156                         bitmap_set(map, index, w);
 157         }
 158
 159         return (area_free) ? 0 : -ENOMEM;
 160 }
 161
 162 static s32 sita_reserve_1d(struct tcm *tcm, u32 num_slots,
 163                            struct tcm_area *area)
 164 {
 165         unsigned long pos;
 166         int ret;
 167
 168         spin_lock(&(tcm->lock));
 169         ret = r2l_b2t_1d(num_slots, &pos, tcm->bitmap, tcm->map_size);
 170         if (!ret) {
 171                 area->p0.x = pos % tcm->width;
 172                 area->p0.y = pos / tcm->width;
 173                 area->p1.x = (pos + num_slots - 1) % tcm->width;
 174                 area->p1.y = (pos + num_slots - 1) / tcm->width;
 175         }
 176         spin_unlock(&(tcm->lock));
 177
 178         return ret;
 179 }
 180
 181 static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u16 align,
 182                                 s16 offset, u16 slot_bytes,
 183                                 struct tcm_area *area)
 184 {
 185         unsigned long pos;
 186         int ret;
 187
 188         spin_lock(&(tcm->lock));
 189         ret = l2r_t2b(w, h, align, offset, &pos, slot_bytes, tcm->bitmap,
 190                         tcm->map_size, tcm->width);
 191
 192         if (!ret) {
 193                 area->p0.x = pos % tcm->width;
 194                 area->p0.y = pos / tcm->width;
 195                 area->p1.x = area->p0.x + w - 1;
 196                 area->p1.y = area->p0.y + h - 1;
 197         }
 198         spin_unlock(&(tcm->lock));
 199
 200         return ret;
 201 }
 202
 203 static void sita_deinit(struct tcm *tcm)
 204 {
 205         kfree(tcm);
 206 }
 207
 208 static s32 sita_free(struct tcm *tcm, struct tcm_area *area)
 209 {
 210         unsigned long pos;
 211         u16 w, h;
 212
 213         pos = area->p0.x + area->p0.y * tcm->width;
 214         if (area->is2d) {
 215                 w = area->p1.x - area->p0.x + 1;
 216                 h = area->p1.y - area->p0.y + 1;
 217         } else {
 218                 w = area->p1.x + area->p1.y * tcm->width - pos + 1;
 219                 h = 1;
 220         }
 221
 222         spin_lock(&(tcm->lock));
 223         free_slots(pos, w, h, tcm->bitmap, tcm->width);
 224         spin_unlock(&(tcm->lock));
 225         return 0;
 226 }
 227
 228 struct tcm *sita_init(u16 width, u16 height)
 229 {
 230         struct tcm *tcm;
 231         size_t map_size = BITS_TO_LONGS(width*height) * sizeof(unsigned long);
 232
 233         if (width == 0 || height == 0)
 234                 return NULL;
 235
 236         tcm = kzalloc(sizeof(*tcm) + map_size, GFP_KERNEL);
 237         if (!tcm)
 238                 goto error;
 239
 240         /* Updating the pointers to SiTA implementation APIs */
 241         tcm->height = height;
 242         tcm->width = width;
 243         tcm->reserve_2d = sita_reserve_2d;
 244         tcm->reserve_1d = sita_reserve_1d;
 245         tcm->free = sita_free;
 246         tcm->deinit = sita_deinit;
 247
 248         spin_lock_init(&tcm->lock);
 249         tcm->bitmap = (unsigned long *)(tcm + 1);
 250         bitmap_clear(tcm->bitmap, 0, width*height);
 251
 252         tcm->map_size = width*height;
 253
 254         return tcm;
 255
 256 error:
 257         kfree(tcm);
 258         return NULL;
 259 }