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 *
9 * Copyright (C) 2009-2010 Texas Instruments, Inc.
10 *
11 * This package is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU General Public License version 2 as
13 * published by the Free Software Foundation.
14 *
15 * THIS PACKAGE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
17 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
18 *
19 */
20#include <linux/slab.h>
21#include <linux/spinlock.h>
22
23#include "tcm-sita.h"
24
25#define ALIGN_DOWN(value, align) ((value) & ~((align) - 1))
26
27/* Individual selection criteria for different scan areas */
28static s32 CR_L2R_T2B = CR_BIAS_HORIZONTAL;
29static s32 CR_R2L_T2B = CR_DIAGONAL_BALANCE;
30
31/*********************************************
32 *	TCM API - Sita Implementation
33 *********************************************/
34static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u8 align,
35			   struct tcm_area *area);
36static s32 sita_reserve_1d(struct tcm *tcm, u32 slots, struct tcm_area *area);
37static s32 sita_free(struct tcm *tcm, struct tcm_area *area);
38static void sita_deinit(struct tcm *tcm);
39
40/*********************************************
41 *	Main Scanner functions
42 *********************************************/
43static s32 scan_areas_and_find_fit(struct tcm *tcm, u16 w, u16 h, u16 align,
44				   struct tcm_area *area);
45
46static s32 scan_l2r_t2b(struct tcm *tcm, u16 w, u16 h, u16 align,
47			struct tcm_area *field, struct tcm_area *area);
48
49static s32 scan_r2l_t2b(struct tcm *tcm, u16 w, u16 h, u16 align,
50			struct tcm_area *field, struct tcm_area *area);
51
52static s32 scan_r2l_b2t_one_dim(struct tcm *tcm, u32 num_slots,
53			struct tcm_area *field, struct tcm_area *area);
54
55/*********************************************
56 *	Support Infrastructure Methods
57 *********************************************/
58static s32 is_area_free(struct tcm_area ***map, u16 x0, u16 y0, u16 w, u16 h);
59
60static s32 update_candidate(struct tcm *tcm, u16 x0, u16 y0, u16 w, u16 h,
61			    struct tcm_area *field, s32 criteria,
62			    struct score *best);
63
64static void get_nearness_factor(struct tcm_area *field,
65				struct tcm_area *candidate,
66				struct nearness_factor *nf);
67
68static void get_neighbor_stats(struct tcm *tcm, struct tcm_area *area,
69			       struct neighbor_stats *stat);
70
71static void fill_area(struct tcm *tcm,
72				struct tcm_area *area, struct tcm_area *parent);
73
74
75/*********************************************/
76
77/*********************************************
78 *	Utility Methods
79 *********************************************/
80struct tcm *sita_init(u16 width, u16 height, struct tcm_pt *attr)
81{
82	struct tcm *tcm;
83	struct sita_pvt *pvt;
84	struct tcm_area area = {0};
85	s32 i;
86
87	if (width == 0 || height == 0)
88		return NULL;
89
90	tcm = kmalloc(sizeof(*tcm), GFP_KERNEL);
91	pvt = kmalloc(sizeof(*pvt), GFP_KERNEL);
92	if (!tcm || !pvt)
93		goto error;
94
95	memset(tcm, 0, sizeof(*tcm));
96	memset(pvt, 0, sizeof(*pvt));
97
98	/* Updating the pointers to SiTA implementation APIs */
99	tcm->height = height;
100	tcm->width = width;
101	tcm->reserve_2d = sita_reserve_2d;
102	tcm->reserve_1d = sita_reserve_1d;
103	tcm->free = sita_free;
104	tcm->deinit = sita_deinit;
105	tcm->pvt = (void *)pvt;
106
107	spin_lock_init(&(pvt->lock));
108
109	/* Creating tam map */
110	pvt->map = kmalloc(sizeof(*pvt->map) * tcm->width, GFP_KERNEL);
111	if (!pvt->map)
112		goto error;
113
114	for (i = 0; i < tcm->width; i++) {
115		pvt->map[i] =
116			kmalloc(sizeof(**pvt->map) * tcm->height,
117								GFP_KERNEL);
118		if (pvt->map[i] == NULL) {
119			while (i--)
120				kfree(pvt->map[i]);
121			kfree(pvt->map);
122			goto error;
123		}
124	}
125
126	if (attr && attr->x <= tcm->width && attr->y <= tcm->height) {
127		pvt->div_pt.x = attr->x;
128		pvt->div_pt.y = attr->y;
129
130	} else {
131		/* Defaulting to 3:1 ratio on width for 2D area split */
132		/* Defaulting to 3:1 ratio on height for 2D and 1D split */
133		pvt->div_pt.x = (tcm->width * 3) / 4;
134		pvt->div_pt.y = (tcm->height * 3) / 4;
135	}
136
137	spin_lock(&(pvt->lock));
138	assign(&area, 0, 0, width - 1, height - 1);
139	fill_area(tcm, &area, NULL);
140	spin_unlock(&(pvt->lock));
141	return tcm;
142
143error:
144	kfree(tcm);
145	kfree(pvt);
146	return NULL;
147}
148
149static void sita_deinit(struct tcm *tcm)
150{
151	struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
152	struct tcm_area area = {0};
153	s32 i;
154
155	area.p1.x = tcm->width - 1;
156	area.p1.y = tcm->height - 1;
157
158	spin_lock(&(pvt->lock));
159	fill_area(tcm, &area, NULL);
160	spin_unlock(&(pvt->lock));
161
162	for (i = 0; i < tcm->height; i++)
163		kfree(pvt->map[i]);
164	kfree(pvt->map);
165	kfree(pvt);
166}
167
168/**
169 * Reserve a 1D area in the container
170 *
171 * @param num_slots	size of 1D area
172 * @param area		pointer to the area that will be populated with the
173 *			reserved area
174 *
175 * @return 0 on success, non-0 error value on failure.
176 */
177static s32 sita_reserve_1d(struct tcm *tcm, u32 num_slots,
178			   struct tcm_area *area)
179{
180	s32 ret;
181	struct tcm_area field = {0};
182	struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
183
184	spin_lock(&(pvt->lock));
185
186	/* Scanning entire container */
187	assign(&field, tcm->width - 1, tcm->height - 1, 0, 0);
188
189	ret = scan_r2l_b2t_one_dim(tcm, num_slots, &field, area);
190	if (!ret)
191		/* update map */
192		fill_area(tcm, area, area);
193
194	spin_unlock(&(pvt->lock));
195	return ret;
196}
197
198/**
199 * Reserve a 2D area in the container
200 *
201 * @param w	width
202 * @param h	height
203 * @param area	pointer to the area that will be populated with the reesrved
204 *		area
205 *
206 * @return 0 on success, non-0 error value on failure.
207 */
208static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u8 align,
209			   struct tcm_area *area)
210{
211	s32 ret;
212	struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
213
214	/* not supporting more than 64 as alignment */
215	if (align > 64)
216		return -EINVAL;
217
218	/* we prefer 1, 32 and 64 as alignment */
219	align = align <= 1 ? 1 : align <= 32 ? 32 : 64;
220
221	spin_lock(&(pvt->lock));
222	ret = scan_areas_and_find_fit(tcm, w, h, align, area);
223	if (!ret)
224		/* update map */
225		fill_area(tcm, area, area);
226
227	spin_unlock(&(pvt->lock));
228	return ret;
229}
230
231/**
232 * Unreserve a previously allocated 2D or 1D area
233 * @param area	area to be freed
234 * @return 0 - success
235 */
236static s32 sita_free(struct tcm *tcm, struct tcm_area *area)
237{
238	struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
239
240	spin_lock(&(pvt->lock));
241
242	/* check that this is in fact an existing area */
243	WARN_ON(pvt->map[area->p0.x][area->p0.y] != area ||
244		pvt->map[area->p1.x][area->p1.y] != area);
245
246	/* Clear the contents of the associated tiles in the map */
247	fill_area(tcm, area, NULL);
248
249	spin_unlock(&(pvt->lock));
250
251	return 0;
252}
253
254/**
255 * Note: In general the cordinates in the scan field area relevant to the can
256 * sweep directions. The scan origin (e.g. top-left corner) will always be
257 * the p0 member of the field.  Therfore, for a scan from top-left p0.x <= p1.x
258 * and p0.y <= p1.y; whereas, for a scan from bottom-right p1.x <= p0.x and p1.y
259 * <= p0.y
260 */
261
262/**
263 * Raster scan horizontally right to left from top to bottom to find a place for
264 * a 2D area of given size inside a scan field.
265 *
266 * @param w	width of desired area
267 * @param h	height of desired area
268 * @param align	desired area alignment
269 * @param area	pointer to the area that will be set to the best position
270 * @param field	area to scan (inclusive)
271 *
272 * @return 0 on success, non-0 error value on failure.
273 */
274static s32 scan_r2l_t2b(struct tcm *tcm, u16 w, u16 h, u16 align,
275			struct tcm_area *field, struct tcm_area *area)
276{
277	s32 x, y;
278	s16 start_x, end_x, start_y, end_y, found_x = -1;
279	struct tcm_area ***map = ((struct sita_pvt *)tcm->pvt)->map;
280	struct score best = {{0}, {0}, {0}, 0};
281
282	start_x = field->p0.x;
283	end_x = field->p1.x;
284	start_y = field->p0.y;
285	end_y = field->p1.y;
286
287	/* check scan area co-ordinates */
288	if (field->p0.x < field->p1.x ||
289	    field->p1.y < field->p0.y)
290		return -EINVAL;
291
292	/* check if allocation would fit in scan area */
293	if (w > LEN(start_x, end_x) || h > LEN(end_y, start_y))
294		return -ENOSPC;
295
296	/* adjust start_x and end_y, as allocation would not fit beyond */
297	start_x = ALIGN_DOWN(start_x - w + 1, align); /* - 1 to be inclusive */
298	end_y = end_y - h + 1;
299
300	/* check if allocation would still fit in scan area */
301	if (start_x < end_x)
302		return -ENOSPC;
303
304	/* scan field top-to-bottom, right-to-left */
305	for (y = start_y; y <= end_y; y++) {
306		for (x = start_x; x >= end_x; x -= align) {
307			if (is_area_free(map, x, y, w, h)) {
308				found_x = x;
309
310				/* update best candidate */
311				if (update_candidate(tcm, x, y, w, h, field,
312							CR_R2L_T2B, &best))
313					goto done;
314
315				/* change upper x bound */
316				end_x = x + 1;
317				break;
318			} else if (map[x][y] && map[x][y]->is2d) {
319				/* step over 2D areas */
320				x = ALIGN(map[x][y]->p0.x - w + 1, align);
321			}
322		}
323
324		/* break if you find a free area shouldering the scan field */
325		if (found_x == start_x)
326			break;
327	}
328
329	if (!best.a.tcm)
330		return -ENOSPC;
331done:
332	assign(area, best.a.p0.x, best.a.p0.y, best.a.p1.x, best.a.p1.y);
333	return 0;
334}
335
336/**
337 * Raster scan horizontally left to right from top to bottom to find a place for
338 * a 2D area of given size inside a scan field.
339 *
340 * @param w	width of desired area
341 * @param h	height of desired area
342 * @param align	desired area alignment
343 * @param area	pointer to the area that will be set to the best position
344 * @param field	area to scan (inclusive)
345 *
346 * @return 0 on success, non-0 error value on failure.
347 */
348static s32 scan_l2r_t2b(struct tcm *tcm, u16 w, u16 h, u16 align,
349			struct tcm_area *field, struct tcm_area *area)
350{
351	s32 x, y;
352	s16 start_x, end_x, start_y, end_y, found_x = -1;
353	struct tcm_area ***map = ((struct sita_pvt *)tcm->pvt)->map;
354	struct score best = {{0}, {0}, {0}, 0};
355
356	start_x = field->p0.x;
357	end_x = field->p1.x;
358	start_y = field->p0.y;
359	end_y = field->p1.y;
360
361	/* check scan area co-ordinates */
362	if (field->p1.x < field->p0.x ||
363	    field->p1.y < field->p0.y)
364		return -EINVAL;
365
366	/* check if allocation would fit in scan area */
367	if (w > LEN(end_x, start_x) || h > LEN(end_y, start_y))
368		return -ENOSPC;
369
370	start_x = ALIGN(start_x, align);
371
372	/* check if allocation would still fit in scan area */
373	if (w > LEN(end_x, start_x))
374		return -ENOSPC;
375
376	/* adjust end_x and end_y, as allocation would not fit beyond */
377	end_x = end_x - w + 1; /* + 1 to be inclusive */
378	end_y = end_y - h + 1;
379
380	/* scan field top-to-bottom, left-to-right */
381	for (y = start_y; y <= end_y; y++) {
382		for (x = start_x; x <= end_x; x += align) {
383			if (is_area_free(map, x, y, w, h)) {
384				found_x = x;
385
386				/* update best candidate */
387				if (update_candidate(tcm, x, y, w, h, field,
388							CR_L2R_T2B, &best))
389					goto done;
390				/* change upper x bound */
391				end_x = x - 1;
392
393				break;
394			} else if (map[x][y] && map[x][y]->is2d) {
395				/* step over 2D areas */
396				x = ALIGN_DOWN(map[x][y]->p1.x, align);
397			}
398		}
399
400		/* break if you find a free area shouldering the scan field */
401		if (found_x == start_x)
402			break;
403	}
404
405	if (!best.a.tcm)
406		return -ENOSPC;
407done:
408	assign(area, best.a.p0.x, best.a.p0.y, best.a.p1.x, best.a.p1.y);
409	return 0;
410}
411
412/**
413 * Raster scan horizontally right to left from bottom to top to find a place
414 * for a 1D area of given size inside a scan field.
415 *
416 * @param num_slots	size of desired area
417 * @param align		desired area alignment
418 * @param area		pointer to the area that will be set to the best
419 *			position
420 * @param field		area to scan (inclusive)
421 *
422 * @return 0 on success, non-0 error value on failure.
423 */
424static s32 scan_r2l_b2t_one_dim(struct tcm *tcm, u32 num_slots,
425				struct tcm_area *field, struct tcm_area *area)
426{
427	s32 found = 0;
428	s16 x, y;
429	struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
430	struct tcm_area *p;
431
432	/* check scan area co-ordinates */
433	if (field->p0.y < field->p1.y)
434		return -EINVAL;
435
436	/**
437	 * Currently we only support full width 1D scan field, which makes sense
438	 * since 1D slot-ordering spans the full container width.
439	 */
440	if (tcm->width != field->p0.x - field->p1.x + 1)
441		return -EINVAL;
442
443	/* check if allocation would fit in scan area */
444	if (num_slots > tcm->width * LEN(field->p0.y, field->p1.y))
445		return -ENOSPC;
446
447	x = field->p0.x;
448	y = field->p0.y;
449
450	/* find num_slots consecutive free slots to the left */
451	while (found < num_slots) {
452		if (y < 0)
453			return -ENOSPC;
454
455		/* remember bottom-right corner */
456		if (found == 0) {
457			area->p1.x = x;
458			area->p1.y = y;
459		}
460
461		/* skip busy regions */
462		p = pvt->map[x][y];
463		if (p) {
464			/* move to left of 2D areas, top left of 1D */
465			x = p->p0.x;
466			if (!p->is2d)
467				y = p->p0.y;
468
469			/* start over */
470			found = 0;
471		} else {
472			/* count consecutive free slots */
473			found++;
474			if (found == num_slots)
475				break;
476		}
477
478		/* move to the left */
479		if (x == 0)
480			y--;
481		x = (x ? : tcm->width) - 1;
482
483	}
484
485	/* set top-left corner */
486	area->p0.x = x;
487	area->p0.y = y;
488	return 0;
489}
490
491/**
492 * Find a place for a 2D area of given size inside a scan field based on its
493 * alignment needs.
494 *
495 * @param w	width of desired area
496 * @param h	height of desired area
497 * @param align	desired area alignment
498 * @param area	pointer to the area that will be set to the best position
499 *
500 * @return 0 on success, non-0 error value on failure.
501 */
502static s32 scan_areas_and_find_fit(struct tcm *tcm, u16 w, u16 h, u16 align,
503				   struct tcm_area *area)
504{
505	s32 ret = 0;
506	struct tcm_area field = {0};
507	u16 boundary_x, boundary_y;
508	struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
509
510	if (align > 1) {
511		/* prefer top-left corner */
512		boundary_x = pvt->div_pt.x - 1;
513		boundary_y = pvt->div_pt.y - 1;
514
515		/* expand width and height if needed */
516		if (w > pvt->div_pt.x)
517			boundary_x = tcm->width - 1;
518		if (h > pvt->div_pt.y)
519			boundary_y = tcm->height - 1;
520
521		assign(&field, 0, 0, boundary_x, boundary_y);
522		ret = scan_l2r_t2b(tcm, w, h, align, &field, area);
523
524		/* scan whole container if failed, but do not scan 2x */
525		if (ret != 0 && (boundary_x != tcm->width - 1 ||
526				 boundary_y != tcm->height - 1)) {
527			/* scan the entire container if nothing found */
528			assign(&field, 0, 0, tcm->width - 1, tcm->height - 1);
529			ret = scan_l2r_t2b(tcm, w, h, align, &field, area);
530		}
531	} else if (align == 1) {
532		/* prefer top-right corner */
533		boundary_x = pvt->div_pt.x;
534		boundary_y = pvt->div_pt.y - 1;
535
536		/* expand width and height if needed */
537		if (w > (tcm->width - pvt->div_pt.x))
538			boundary_x = 0;
539		if (h > pvt->div_pt.y)
540			boundary_y = tcm->height - 1;
541
542		assign(&field, tcm->width - 1, 0, boundary_x, boundary_y);
543		ret = scan_r2l_t2b(tcm, w, h, align, &field, area);
544
545		/* scan whole container if failed, but do not scan 2x */
546		if (ret != 0 && (boundary_x != 0 ||
547				 boundary_y != tcm->height - 1)) {
548			/* scan the entire container if nothing found */
549			assign(&field, tcm->width - 1, 0, 0, tcm->height - 1);
550			ret = scan_r2l_t2b(tcm, w, h, align, &field,
551					   area);
552		}
553	}
554
555	return ret;
556}
557
558/* check if an entire area is free */
559static s32 is_area_free(struct tcm_area ***map, u16 x0, u16 y0, u16 w, u16 h)
560{
561	u16 x = 0, y = 0;
562	for (y = y0; y < y0 + h; y++) {
563		for (x = x0; x < x0 + w; x++) {
564			if (map[x][y])
565				return false;
566		}
567	}
568	return true;
569}
570
571/* fills an area with a parent tcm_area */
572static void fill_area(struct tcm *tcm, struct tcm_area *area,
573			struct tcm_area *parent)
574{
575	s32 x, y;
576	struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
577	struct tcm_area a, a_;
578
579	/* set area's tcm; otherwise, enumerator considers it invalid */
580	area->tcm = tcm;
581
582	tcm_for_each_slice(a, *area, a_) {
583		for (x = a.p0.x; x <= a.p1.x; ++x)
584			for (y = a.p0.y; y <= a.p1.y; ++y)
585				pvt->map[x][y] = parent;
586
587	}
588}
589
590/**
591 * Compares a candidate area to the current best area, and if it is a better
592 * fit, it updates the best to this one.
593 *
594 * @param x0, y0, w, h		top, left, width, height of candidate area
595 * @param field			scan field
596 * @param criteria		scan criteria
597 * @param best			best candidate and its scores
598 *
599 * @return 1 (true) if the candidate area is known to be the final best, so no
600 * more searching should be performed
601 */
602static s32 update_candidate(struct tcm *tcm, u16 x0, u16 y0, u16 w, u16 h,
603			    struct tcm_area *field, s32 criteria,
604			    struct score *best)
605{
606	struct score me;	/* score for area */
607
608	/*
609	 * NOTE: For horizontal bias we always give the first found, because our
610	 * scan is horizontal-raster-based and the first candidate will always
611	 * have the horizontal bias.
612	 */
613	bool first = criteria & CR_BIAS_HORIZONTAL;
614
615	assign(&me.a, x0, y0, x0 + w - 1, y0 + h - 1);
616
617	/* calculate score for current candidate */
618	if (!first) {
619		get_neighbor_stats(tcm, &me.a, &me.n);
620		me.neighs = me.n.edge + me.n.busy;
621		get_nearness_factor(field, &me.a, &me.f);
622	}
623
624	/* the 1st candidate is always the best */
625	if (!best->a.tcm)
626		goto better;
627
628	BUG_ON(first);
629
630	/* diagonal balance check */
631	if ((criteria & CR_DIAGONAL_BALANCE) &&
632		best->neighs <= me.neighs &&
633		(best->neighs < me.neighs ||
634		 /* this implies that neighs and occupied match */
635		 best->n.busy < me.n.busy ||
636		 (best->n.busy == me.n.busy &&
637		  /* check the nearness factor */
638		  best->f.x + best->f.y > me.f.x + me.f.y)))
639		goto better;
640
641	/* not better, keep going */
642	return 0;
643
644better:
645	/* save current area as best */
646	memcpy(best, &me, sizeof(me));
647	best->a.tcm = tcm;
648	return first;
649}
650
651/**
652 * Calculate the nearness factor of an area in a search field.  The nearness
653 * factor is smaller if the area is closer to the search origin.
654 */
655static void get_nearness_factor(struct tcm_area *field, struct tcm_area *area,
656				struct nearness_factor *nf)
657{
658	/**
659	 * Using signed math as field coordinates may be reversed if
660	 * search direction is right-to-left or bottom-to-top.
661	 */
662	nf->x = (s32)(area->p0.x - field->p0.x) * 1000 /
663		(field->p1.x - field->p0.x);
664	nf->y = (s32)(area->p0.y - field->p0.y) * 1000 /
665		(field->p1.y - field->p0.y);
666}
667
668/* get neighbor statistics */
669static void get_neighbor_stats(struct tcm *tcm, struct tcm_area *area,
670			 struct neighbor_stats *stat)
671{
672	s16 x = 0, y = 0;
673	struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
674
675	/* Clearing any exisiting values */
676	memset(stat, 0, sizeof(*stat));
677
678	/* process top & bottom edges */
679	for (x = area->p0.x; x <= area->p1.x; x++) {
680		if (area->p0.y == 0)
681			stat->edge++;
682		else if (pvt->map[x][area->p0.y - 1])
683			stat->busy++;
684
685		if (area->p1.y == tcm->height - 1)
686			stat->edge++;
687		else if (pvt->map[x][area->p1.y + 1])
688			stat->busy++;
689	}
690
691	/* process left & right edges */
692	for (y = area->p0.y; y <= area->p1.y; ++y) {
693		if (area->p0.x == 0)
694			stat->edge++;
695		else if (pvt->map[area->p0.x - 1][y])
696			stat->busy++;
697
698		if (area->p1.x == tcm->width - 1)
699			stat->edge++;
700		else if (pvt->map[area->p1.x + 1][y])
701			stat->busy++;
702	}
703}
704