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 } 260