Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
tjh.dev
kernel
os
linux
1/*
2 * UWB reservation management.
3 *
4 * Copyright (C) 2008 Cambridge Silicon Radio Ltd.
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License version
8 * 2 as published by the Free Software Foundation.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18#include <linux/kernel.h>
19#include <linux/uwb.h>
20
21#include "uwb-internal.h"
22
23static void uwb_rsv_fill_column_alloc(struct uwb_rsv_alloc_info *ai)
24{
25 int col, mas, safe_mas, unsafe_mas;
26 unsigned char *bm = ai->bm;
27 struct uwb_rsv_col_info *ci = ai->ci;
28 unsigned char c;
29
30 for (col = ci->csi.start_col; col < UWB_NUM_ZONES; col += ci->csi.interval) {
31
32 safe_mas = ci->csi.safe_mas_per_col;
33 unsafe_mas = ci->csi.unsafe_mas_per_col;
34
35 for (mas = 0; mas < UWB_MAS_PER_ZONE; mas++ ) {
36 if (bm[col * UWB_MAS_PER_ZONE + mas] == 0) {
37
38 if (safe_mas > 0) {
39 safe_mas--;
40 c = UWB_RSV_MAS_SAFE;
41 } else if (unsafe_mas > 0) {
42 unsafe_mas--;
43 c = UWB_RSV_MAS_UNSAFE;
44 } else {
45 break;
46 }
47 bm[col * UWB_MAS_PER_ZONE + mas] = c;
48 }
49 }
50 }
51}
52
53static void uwb_rsv_fill_row_alloc(struct uwb_rsv_alloc_info *ai)
54{
55 int mas, col, rows;
56 unsigned char *bm = ai->bm;
57 struct uwb_rsv_row_info *ri = &ai->ri;
58 unsigned char c;
59
60 rows = 1;
61 c = UWB_RSV_MAS_SAFE;
62 for (mas = UWB_MAS_PER_ZONE - 1; mas >= 0; mas--) {
63 if (ri->avail[mas] == 1) {
64
65 if (rows > ri->used_rows) {
66 break;
67 } else if (rows > 7) {
68 c = UWB_RSV_MAS_UNSAFE;
69 }
70
71 for (col = 0; col < UWB_NUM_ZONES; col++) {
72 if (bm[col * UWB_NUM_ZONES + mas] != UWB_RSV_MAS_NOT_AVAIL) {
73 bm[col * UWB_NUM_ZONES + mas] = c;
74 if(c == UWB_RSV_MAS_SAFE)
75 ai->safe_allocated_mases++;
76 else
77 ai->unsafe_allocated_mases++;
78 }
79 }
80 rows++;
81 }
82 }
83 ai->total_allocated_mases = ai->safe_allocated_mases + ai->unsafe_allocated_mases;
84}
85
86/*
87 * Find the best column set for a given availability, interval, num safe mas and
88 * num unsafe mas.
89 *
90 * The different sets are tried in order as shown below, depending on the interval.
91 *
92 * interval = 16
93 * deep = 0
94 * set 1 -> { 8 }
95 * deep = 1
96 * set 1 -> { 4 }
97 * set 2 -> { 12 }
98 * deep = 2
99 * set 1 -> { 2 }
100 * set 2 -> { 6 }
101 * set 3 -> { 10 }
102 * set 4 -> { 14 }
103 * deep = 3
104 * set 1 -> { 1 }
105 * set 2 -> { 3 }
106 * set 3 -> { 5 }
107 * set 4 -> { 7 }
108 * set 5 -> { 9 }
109 * set 6 -> { 11 }
110 * set 7 -> { 13 }
111 * set 8 -> { 15 }
112 *
113 * interval = 8
114 * deep = 0
115 * set 1 -> { 4 12 }
116 * deep = 1
117 * set 1 -> { 2 10 }
118 * set 2 -> { 6 14 }
119 * deep = 2
120 * set 1 -> { 1 9 }
121 * set 2 -> { 3 11 }
122 * set 3 -> { 5 13 }
123 * set 4 -> { 7 15 }
124 *
125 * interval = 4
126 * deep = 0
127 * set 1 -> { 2 6 10 14 }
128 * deep = 1
129 * set 1 -> { 1 5 9 13 }
130 * set 2 -> { 3 7 11 15 }
131 *
132 * interval = 2
133 * deep = 0
134 * set 1 -> { 1 3 5 7 9 11 13 15 }
135 */
136static int uwb_rsv_find_best_column_set(struct uwb_rsv_alloc_info *ai, int interval,
137 int num_safe_mas, int num_unsafe_mas)
138{
139 struct uwb_rsv_col_info *ci = ai->ci;
140 struct uwb_rsv_col_set_info *csi = &ci->csi;
141 struct uwb_rsv_col_set_info tmp_csi;
142 int deep, set, col, start_col_deep, col_start_set;
143 int start_col, max_mas_in_set, lowest_max_mas_in_deep;
144 int n_mas;
145 int found = UWB_RSV_ALLOC_NOT_FOUND;
146
147 tmp_csi.start_col = 0;
148 start_col_deep = interval;
149 n_mas = num_unsafe_mas + num_safe_mas;
150
151 for (deep = 0; ((interval >> deep) & 0x1) == 0; deep++) {
152 start_col_deep /= 2;
153 col_start_set = 0;
154 lowest_max_mas_in_deep = UWB_MAS_PER_ZONE;
155
156 for (set = 1; set <= (1 << deep); set++) {
157 max_mas_in_set = 0;
158 start_col = start_col_deep + col_start_set;
159 for (col = start_col; col < UWB_NUM_ZONES; col += interval) {
160
161 if (ci[col].max_avail_safe >= num_safe_mas &&
162 ci[col].max_avail_unsafe >= n_mas) {
163 if (ci[col].highest_mas[n_mas] > max_mas_in_set)
164 max_mas_in_set = ci[col].highest_mas[n_mas];
165 } else {
166 max_mas_in_set = 0;
167 break;
168 }
169 }
170 if ((lowest_max_mas_in_deep > max_mas_in_set) && max_mas_in_set) {
171 lowest_max_mas_in_deep = max_mas_in_set;
172
173 tmp_csi.start_col = start_col;
174 }
175 col_start_set += (interval >> deep);
176 }
177
178 if (lowest_max_mas_in_deep < 8) {
179 csi->start_col = tmp_csi.start_col;
180 found = UWB_RSV_ALLOC_FOUND;
181 break;
182 } else if ((lowest_max_mas_in_deep > 8) &&
183 (lowest_max_mas_in_deep != UWB_MAS_PER_ZONE) &&
184 (found == UWB_RSV_ALLOC_NOT_FOUND)) {
185 csi->start_col = tmp_csi.start_col;
186 found = UWB_RSV_ALLOC_FOUND;
187 }
188 }
189
190 if (found == UWB_RSV_ALLOC_FOUND) {
191 csi->interval = interval;
192 csi->safe_mas_per_col = num_safe_mas;
193 csi->unsafe_mas_per_col = num_unsafe_mas;
194
195 ai->safe_allocated_mases = (UWB_NUM_ZONES / interval) * num_safe_mas;
196 ai->unsafe_allocated_mases = (UWB_NUM_ZONES / interval) * num_unsafe_mas;
197 ai->total_allocated_mases = ai->safe_allocated_mases + ai->unsafe_allocated_mases;
198 ai->interval = interval;
199 }
200 return found;
201}
202
203static void get_row_descriptors(struct uwb_rsv_alloc_info *ai)
204{
205 unsigned char *bm = ai->bm;
206 struct uwb_rsv_row_info *ri = &ai->ri;
207 int col, mas;
208
209 ri->free_rows = 16;
210 for (mas = 0; mas < UWB_MAS_PER_ZONE; mas ++) {
211 ri->avail[mas] = 1;
212 for (col = 1; col < UWB_NUM_ZONES; col++) {
213 if (bm[col * UWB_NUM_ZONES + mas] == UWB_RSV_MAS_NOT_AVAIL) {
214 ri->free_rows--;
215 ri->avail[mas]=0;
216 break;
217 }
218 }
219 }
220}
221
222static void uwb_rsv_fill_column_info(unsigned char *bm, int column, struct uwb_rsv_col_info *rci)
223{
224 int mas;
225 int block_count = 0, start_block = 0;
226 int previous_avail = 0;
227 int available = 0;
228 int safe_mas_in_row[UWB_MAS_PER_ZONE] = {
229 8, 7, 6, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1,
230 };
231
232 rci->max_avail_safe = 0;
233
234 for (mas = 0; mas < UWB_MAS_PER_ZONE; mas ++) {
235 if (!bm[column * UWB_NUM_ZONES + mas]) {
236 available++;
237 rci->max_avail_unsafe = available;
238
239 rci->highest_mas[available] = mas;
240
241 if (previous_avail) {
242 block_count++;
243 if ((block_count > safe_mas_in_row[start_block]) &&
244 (!rci->max_avail_safe))
245 rci->max_avail_safe = available - 1;
246 } else {
247 previous_avail = 1;
248 start_block = mas;
249 block_count = 1;
250 }
251 } else {
252 previous_avail = 0;
253 }
254 }
255 if (!rci->max_avail_safe)
256 rci->max_avail_safe = rci->max_avail_unsafe;
257}
258
259static void get_column_descriptors(struct uwb_rsv_alloc_info *ai)
260{
261 unsigned char *bm = ai->bm;
262 struct uwb_rsv_col_info *ci = ai->ci;
263 int col;
264
265 for (col = 1; col < UWB_NUM_ZONES; col++) {
266 uwb_rsv_fill_column_info(bm, col, &ci[col]);
267 }
268}
269
270static int uwb_rsv_find_best_row_alloc(struct uwb_rsv_alloc_info *ai)
271{
272 int n_rows;
273 int max_rows = ai->max_mas / UWB_USABLE_MAS_PER_ROW;
274 int min_rows = ai->min_mas / UWB_USABLE_MAS_PER_ROW;
275 if (ai->min_mas % UWB_USABLE_MAS_PER_ROW)
276 min_rows++;
277 for (n_rows = max_rows; n_rows >= min_rows; n_rows--) {
278 if (n_rows <= ai->ri.free_rows) {
279 ai->ri.used_rows = n_rows;
280 ai->interval = 1; /* row reservation */
281 uwb_rsv_fill_row_alloc(ai);
282 return UWB_RSV_ALLOC_FOUND;
283 }
284 }
285 return UWB_RSV_ALLOC_NOT_FOUND;
286}
287
288static int uwb_rsv_find_best_col_alloc(struct uwb_rsv_alloc_info *ai, int interval)
289{
290 int n_safe, n_unsafe, n_mas;
291 int n_column = UWB_NUM_ZONES / interval;
292 int max_per_zone = ai->max_mas / n_column;
293 int min_per_zone = ai->min_mas / n_column;
294
295 if (ai->min_mas % n_column)
296 min_per_zone++;
297
298 if (min_per_zone > UWB_MAS_PER_ZONE) {
299 return UWB_RSV_ALLOC_NOT_FOUND;
300 }
301
302 if (max_per_zone > UWB_MAS_PER_ZONE) {
303 max_per_zone = UWB_MAS_PER_ZONE;
304 }
305
306 for (n_mas = max_per_zone; n_mas >= min_per_zone; n_mas--) {
307 if (uwb_rsv_find_best_column_set(ai, interval, 0, n_mas) == UWB_RSV_ALLOC_NOT_FOUND)
308 continue;
309 for (n_safe = n_mas; n_safe >= 0; n_safe--) {
310 n_unsafe = n_mas - n_safe;
311 if (uwb_rsv_find_best_column_set(ai, interval, n_safe, n_unsafe) == UWB_RSV_ALLOC_FOUND) {
312 uwb_rsv_fill_column_alloc(ai);
313 return UWB_RSV_ALLOC_FOUND;
314 }
315 }
316 }
317 return UWB_RSV_ALLOC_NOT_FOUND;
318}
319
320int uwb_rsv_find_best_allocation(struct uwb_rsv *rsv, struct uwb_mas_bm *available,
321 struct uwb_mas_bm *result)
322{
323 struct uwb_rsv_alloc_info *ai;
324 int interval;
325 int bit_index;
326
327 ai = kzalloc(sizeof(struct uwb_rsv_alloc_info), GFP_KERNEL);
328
329 ai->min_mas = rsv->min_mas;
330 ai->max_mas = rsv->max_mas;
331 ai->max_interval = rsv->max_interval;
332
333
334 /* fill the not available vector from the available bm */
335 for (bit_index = 0; bit_index < UWB_NUM_MAS; bit_index++) {
336 if (!test_bit(bit_index, available->bm))
337 ai->bm[bit_index] = UWB_RSV_MAS_NOT_AVAIL;
338 }
339
340 if (ai->max_interval == 1) {
341 get_row_descriptors(ai);
342 if (uwb_rsv_find_best_row_alloc(ai) == UWB_RSV_ALLOC_FOUND)
343 goto alloc_found;
344 else
345 goto alloc_not_found;
346 }
347
348 get_column_descriptors(ai);
349
350 for (interval = 16; interval >= 2; interval>>=1) {
351 if (interval > ai->max_interval)
352 continue;
353 if (uwb_rsv_find_best_col_alloc(ai, interval) == UWB_RSV_ALLOC_FOUND)
354 goto alloc_found;
355 }
356
357 /* try row reservation if no column is found */
358 get_row_descriptors(ai);
359 if (uwb_rsv_find_best_row_alloc(ai) == UWB_RSV_ALLOC_FOUND)
360 goto alloc_found;
361 else
362 goto alloc_not_found;
363
364 alloc_found:
365 bitmap_zero(result->bm, UWB_NUM_MAS);
366 bitmap_zero(result->unsafe_bm, UWB_NUM_MAS);
367 /* fill the safe and unsafe bitmaps */
368 for (bit_index = 0; bit_index < UWB_NUM_MAS; bit_index++) {
369 if (ai->bm[bit_index] == UWB_RSV_MAS_SAFE)
370 set_bit(bit_index, result->bm);
371 else if (ai->bm[bit_index] == UWB_RSV_MAS_UNSAFE)
372 set_bit(bit_index, result->unsafe_bm);
373 }
374 bitmap_or(result->bm, result->bm, result->unsafe_bm, UWB_NUM_MAS);
375
376 result->safe = ai->safe_allocated_mases;
377 result->unsafe = ai->unsafe_allocated_mases;
378
379 kfree(ai);
380 return UWB_RSV_ALLOC_FOUND;
381
382 alloc_not_found:
383 kfree(ai);
384 return UWB_RSV_ALLOC_NOT_FOUND;
385}