]>
Commit | Line | Data |
---|---|---|
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/slab.h> | |
20 | #include <linux/uwb.h> | |
21 | ||
22 | #include "uwb-internal.h" | |
23 | ||
24 | static void uwb_rsv_fill_column_alloc(struct uwb_rsv_alloc_info *ai) | |
25 | { | |
26 | int col, mas, safe_mas, unsafe_mas; | |
27 | unsigned char *bm = ai->bm; | |
28 | struct uwb_rsv_col_info *ci = ai->ci; | |
29 | unsigned char c; | |
30 | ||
31 | for (col = ci->csi.start_col; col < UWB_NUM_ZONES; col += ci->csi.interval) { | |
32 | ||
33 | safe_mas = ci->csi.safe_mas_per_col; | |
34 | unsafe_mas = ci->csi.unsafe_mas_per_col; | |
35 | ||
36 | for (mas = 0; mas < UWB_MAS_PER_ZONE; mas++ ) { | |
37 | if (bm[col * UWB_MAS_PER_ZONE + mas] == 0) { | |
38 | ||
39 | if (safe_mas > 0) { | |
40 | safe_mas--; | |
41 | c = UWB_RSV_MAS_SAFE; | |
42 | } else if (unsafe_mas > 0) { | |
43 | unsafe_mas--; | |
44 | c = UWB_RSV_MAS_UNSAFE; | |
45 | } else { | |
46 | break; | |
47 | } | |
48 | bm[col * UWB_MAS_PER_ZONE + mas] = c; | |
49 | } | |
50 | } | |
51 | } | |
52 | } | |
53 | ||
54 | static void uwb_rsv_fill_row_alloc(struct uwb_rsv_alloc_info *ai) | |
55 | { | |
56 | int mas, col, rows; | |
57 | unsigned char *bm = ai->bm; | |
58 | struct uwb_rsv_row_info *ri = &ai->ri; | |
59 | unsigned char c; | |
60 | ||
61 | rows = 1; | |
62 | c = UWB_RSV_MAS_SAFE; | |
63 | for (mas = UWB_MAS_PER_ZONE - 1; mas >= 0; mas--) { | |
64 | if (ri->avail[mas] == 1) { | |
65 | ||
66 | if (rows > ri->used_rows) { | |
67 | break; | |
68 | } else if (rows > 7) { | |
69 | c = UWB_RSV_MAS_UNSAFE; | |
70 | } | |
71 | ||
72 | for (col = 0; col < UWB_NUM_ZONES; col++) { | |
73 | if (bm[col * UWB_NUM_ZONES + mas] != UWB_RSV_MAS_NOT_AVAIL) { | |
74 | bm[col * UWB_NUM_ZONES + mas] = c; | |
75 | if(c == UWB_RSV_MAS_SAFE) | |
76 | ai->safe_allocated_mases++; | |
77 | else | |
78 | ai->unsafe_allocated_mases++; | |
79 | } | |
80 | } | |
81 | rows++; | |
82 | } | |
83 | } | |
84 | ai->total_allocated_mases = ai->safe_allocated_mases + ai->unsafe_allocated_mases; | |
85 | } | |
86 | ||
87 | /* | |
88 | * Find the best column set for a given availability, interval, num safe mas and | |
89 | * num unsafe mas. | |
90 | * | |
91 | * The different sets are tried in order as shown below, depending on the interval. | |
92 | * | |
93 | * interval = 16 | |
94 | * deep = 0 | |
95 | * set 1 -> { 8 } | |
96 | * deep = 1 | |
97 | * set 1 -> { 4 } | |
98 | * set 2 -> { 12 } | |
99 | * deep = 2 | |
100 | * set 1 -> { 2 } | |
101 | * set 2 -> { 6 } | |
102 | * set 3 -> { 10 } | |
103 | * set 4 -> { 14 } | |
104 | * deep = 3 | |
105 | * set 1 -> { 1 } | |
106 | * set 2 -> { 3 } | |
107 | * set 3 -> { 5 } | |
108 | * set 4 -> { 7 } | |
109 | * set 5 -> { 9 } | |
110 | * set 6 -> { 11 } | |
111 | * set 7 -> { 13 } | |
112 | * set 8 -> { 15 } | |
113 | * | |
114 | * interval = 8 | |
115 | * deep = 0 | |
116 | * set 1 -> { 4 12 } | |
117 | * deep = 1 | |
118 | * set 1 -> { 2 10 } | |
119 | * set 2 -> { 6 14 } | |
120 | * deep = 2 | |
121 | * set 1 -> { 1 9 } | |
122 | * set 2 -> { 3 11 } | |
123 | * set 3 -> { 5 13 } | |
124 | * set 4 -> { 7 15 } | |
125 | * | |
126 | * interval = 4 | |
127 | * deep = 0 | |
128 | * set 1 -> { 2 6 10 14 } | |
129 | * deep = 1 | |
130 | * set 1 -> { 1 5 9 13 } | |
131 | * set 2 -> { 3 7 11 15 } | |
132 | * | |
133 | * interval = 2 | |
134 | * deep = 0 | |
135 | * set 1 -> { 1 3 5 7 9 11 13 15 } | |
136 | */ | |
137 | static int uwb_rsv_find_best_column_set(struct uwb_rsv_alloc_info *ai, int interval, | |
138 | int num_safe_mas, int num_unsafe_mas) | |
139 | { | |
140 | struct uwb_rsv_col_info *ci = ai->ci; | |
141 | struct uwb_rsv_col_set_info *csi = &ci->csi; | |
142 | struct uwb_rsv_col_set_info tmp_csi; | |
143 | int deep, set, col, start_col_deep, col_start_set; | |
144 | int start_col, max_mas_in_set, lowest_max_mas_in_deep; | |
145 | int n_mas; | |
146 | int found = UWB_RSV_ALLOC_NOT_FOUND; | |
147 | ||
148 | tmp_csi.start_col = 0; | |
149 | start_col_deep = interval; | |
150 | n_mas = num_unsafe_mas + num_safe_mas; | |
151 | ||
152 | for (deep = 0; ((interval >> deep) & 0x1) == 0; deep++) { | |
153 | start_col_deep /= 2; | |
154 | col_start_set = 0; | |
155 | lowest_max_mas_in_deep = UWB_MAS_PER_ZONE; | |
156 | ||
157 | for (set = 1; set <= (1 << deep); set++) { | |
158 | max_mas_in_set = 0; | |
159 | start_col = start_col_deep + col_start_set; | |
160 | for (col = start_col; col < UWB_NUM_ZONES; col += interval) { | |
161 | ||
162 | if (ci[col].max_avail_safe >= num_safe_mas && | |
163 | ci[col].max_avail_unsafe >= n_mas) { | |
164 | if (ci[col].highest_mas[n_mas] > max_mas_in_set) | |
165 | max_mas_in_set = ci[col].highest_mas[n_mas]; | |
166 | } else { | |
167 | max_mas_in_set = 0; | |
168 | break; | |
169 | } | |
170 | } | |
171 | if ((lowest_max_mas_in_deep > max_mas_in_set) && max_mas_in_set) { | |
172 | lowest_max_mas_in_deep = max_mas_in_set; | |
173 | ||
174 | tmp_csi.start_col = start_col; | |
175 | } | |
176 | col_start_set += (interval >> deep); | |
177 | } | |
178 | ||
179 | if (lowest_max_mas_in_deep < 8) { | |
180 | csi->start_col = tmp_csi.start_col; | |
181 | found = UWB_RSV_ALLOC_FOUND; | |
182 | break; | |
183 | } else if ((lowest_max_mas_in_deep > 8) && | |
184 | (lowest_max_mas_in_deep != UWB_MAS_PER_ZONE) && | |
185 | (found == UWB_RSV_ALLOC_NOT_FOUND)) { | |
186 | csi->start_col = tmp_csi.start_col; | |
187 | found = UWB_RSV_ALLOC_FOUND; | |
188 | } | |
189 | } | |
190 | ||
191 | if (found == UWB_RSV_ALLOC_FOUND) { | |
192 | csi->interval = interval; | |
193 | csi->safe_mas_per_col = num_safe_mas; | |
194 | csi->unsafe_mas_per_col = num_unsafe_mas; | |
195 | ||
196 | ai->safe_allocated_mases = (UWB_NUM_ZONES / interval) * num_safe_mas; | |
197 | ai->unsafe_allocated_mases = (UWB_NUM_ZONES / interval) * num_unsafe_mas; | |
198 | ai->total_allocated_mases = ai->safe_allocated_mases + ai->unsafe_allocated_mases; | |
199 | ai->interval = interval; | |
200 | } | |
201 | return found; | |
202 | } | |
203 | ||
204 | static void get_row_descriptors(struct uwb_rsv_alloc_info *ai) | |
205 | { | |
206 | unsigned char *bm = ai->bm; | |
207 | struct uwb_rsv_row_info *ri = &ai->ri; | |
208 | int col, mas; | |
209 | ||
210 | ri->free_rows = 16; | |
211 | for (mas = 0; mas < UWB_MAS_PER_ZONE; mas ++) { | |
212 | ri->avail[mas] = 1; | |
213 | for (col = 1; col < UWB_NUM_ZONES; col++) { | |
214 | if (bm[col * UWB_NUM_ZONES + mas] == UWB_RSV_MAS_NOT_AVAIL) { | |
215 | ri->free_rows--; | |
216 | ri->avail[mas]=0; | |
217 | break; | |
218 | } | |
219 | } | |
220 | } | |
221 | } | |
222 | ||
223 | static void uwb_rsv_fill_column_info(unsigned char *bm, int column, struct uwb_rsv_col_info *rci) | |
224 | { | |
225 | int mas; | |
226 | int block_count = 0, start_block = 0; | |
227 | int previous_avail = 0; | |
228 | int available = 0; | |
229 | int safe_mas_in_row[UWB_MAS_PER_ZONE] = { | |
230 | 8, 7, 6, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, | |
231 | }; | |
232 | ||
233 | rci->max_avail_safe = 0; | |
234 | ||
235 | for (mas = 0; mas < UWB_MAS_PER_ZONE; mas ++) { | |
236 | if (!bm[column * UWB_NUM_ZONES + mas]) { | |
237 | available++; | |
238 | rci->max_avail_unsafe = available; | |
239 | ||
240 | rci->highest_mas[available] = mas; | |
241 | ||
242 | if (previous_avail) { | |
243 | block_count++; | |
244 | if ((block_count > safe_mas_in_row[start_block]) && | |
245 | (!rci->max_avail_safe)) | |
246 | rci->max_avail_safe = available - 1; | |
247 | } else { | |
248 | previous_avail = 1; | |
249 | start_block = mas; | |
250 | block_count = 1; | |
251 | } | |
252 | } else { | |
253 | previous_avail = 0; | |
254 | } | |
255 | } | |
256 | if (!rci->max_avail_safe) | |
257 | rci->max_avail_safe = rci->max_avail_unsafe; | |
258 | } | |
259 | ||
260 | static void get_column_descriptors(struct uwb_rsv_alloc_info *ai) | |
261 | { | |
262 | unsigned char *bm = ai->bm; | |
263 | struct uwb_rsv_col_info *ci = ai->ci; | |
264 | int col; | |
265 | ||
266 | for (col = 1; col < UWB_NUM_ZONES; col++) { | |
267 | uwb_rsv_fill_column_info(bm, col, &ci[col]); | |
268 | } | |
269 | } | |
270 | ||
271 | static int uwb_rsv_find_best_row_alloc(struct uwb_rsv_alloc_info *ai) | |
272 | { | |
273 | int n_rows; | |
274 | int max_rows = ai->max_mas / UWB_USABLE_MAS_PER_ROW; | |
275 | int min_rows = ai->min_mas / UWB_USABLE_MAS_PER_ROW; | |
276 | if (ai->min_mas % UWB_USABLE_MAS_PER_ROW) | |
277 | min_rows++; | |
278 | for (n_rows = max_rows; n_rows >= min_rows; n_rows--) { | |
279 | if (n_rows <= ai->ri.free_rows) { | |
280 | ai->ri.used_rows = n_rows; | |
281 | ai->interval = 1; /* row reservation */ | |
282 | uwb_rsv_fill_row_alloc(ai); | |
283 | return UWB_RSV_ALLOC_FOUND; | |
284 | } | |
285 | } | |
286 | return UWB_RSV_ALLOC_NOT_FOUND; | |
287 | } | |
288 | ||
289 | static int uwb_rsv_find_best_col_alloc(struct uwb_rsv_alloc_info *ai, int interval) | |
290 | { | |
291 | int n_safe, n_unsafe, n_mas; | |
292 | int n_column = UWB_NUM_ZONES / interval; | |
293 | int max_per_zone = ai->max_mas / n_column; | |
294 | int min_per_zone = ai->min_mas / n_column; | |
295 | ||
296 | if (ai->min_mas % n_column) | |
297 | min_per_zone++; | |
298 | ||
299 | if (min_per_zone > UWB_MAS_PER_ZONE) { | |
300 | return UWB_RSV_ALLOC_NOT_FOUND; | |
301 | } | |
302 | ||
303 | if (max_per_zone > UWB_MAS_PER_ZONE) { | |
304 | max_per_zone = UWB_MAS_PER_ZONE; | |
305 | } | |
306 | ||
307 | for (n_mas = max_per_zone; n_mas >= min_per_zone; n_mas--) { | |
308 | if (uwb_rsv_find_best_column_set(ai, interval, 0, n_mas) == UWB_RSV_ALLOC_NOT_FOUND) | |
309 | continue; | |
310 | for (n_safe = n_mas; n_safe >= 0; n_safe--) { | |
311 | n_unsafe = n_mas - n_safe; | |
312 | if (uwb_rsv_find_best_column_set(ai, interval, n_safe, n_unsafe) == UWB_RSV_ALLOC_FOUND) { | |
313 | uwb_rsv_fill_column_alloc(ai); | |
314 | return UWB_RSV_ALLOC_FOUND; | |
315 | } | |
316 | } | |
317 | } | |
318 | return UWB_RSV_ALLOC_NOT_FOUND; | |
319 | } | |
320 | ||
321 | int uwb_rsv_find_best_allocation(struct uwb_rsv *rsv, struct uwb_mas_bm *available, | |
322 | struct uwb_mas_bm *result) | |
323 | { | |
324 | struct uwb_rsv_alloc_info *ai; | |
325 | int interval; | |
326 | int bit_index; | |
327 | ||
328 | ai = kzalloc(sizeof(struct uwb_rsv_alloc_info), GFP_KERNEL); | |
329 | if (!ai) | |
330 | return UWB_RSV_ALLOC_NOT_FOUND; | |
331 | ai->min_mas = rsv->min_mas; | |
332 | ai->max_mas = rsv->max_mas; | |
333 | ai->max_interval = rsv->max_interval; | |
334 | ||
335 | ||
336 | /* fill the not available vector from the available bm */ | |
337 | for_each_clear_bit(bit_index, available->bm, UWB_NUM_MAS) | |
338 | ai->bm[bit_index] = UWB_RSV_MAS_NOT_AVAIL; | |
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 | } |