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
 28static 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 */
 36static 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 */
 51static 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 */
 87static 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
162static 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
181static 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
203static void sita_deinit(struct tcm *tcm)
204{
205	kfree(tcm);
206}
207
208static 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
228struct 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
256error:
257	kfree(tcm);
258	return NULL;
259}