Commit | Line | Data |
---|---|---|
5b37717a SP |
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 | */ | |
5b37717a SP |
18 | #include <linux/kernel.h> |
19 | #include <linux/uwb.h> | |
20 | ||
21 | #include "uwb-internal.h" | |
22 | ||
23 | static 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 | ||
53 | static 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 | */ | |
136 | static 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 | ||
203 | static 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 | ||
222 | static 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 | ||
259 | static 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 | ||
270 | static 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 | ||
288 | static 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 | ||
320 | int 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 | } |