drivers/gpu/drm/omapdrm/sita.c

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