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