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
 30static 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 */
 38static 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 */
 53static 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 */
 89static 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
164static 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
183static 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
205static void sita_deinit(struct tcm *tcm)
206{
207	kfree(tcm);
208}
209
210static 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
230struct 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
258error:
259	kfree(tcm);
260	return NULL;
261}