1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
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;
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
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
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
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}
386