1 /* 2 * tcm-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 } 262