2 * UWB reservation management.
4 * Copyright (C) 2008 Cambridge Silicon Radio Ltd.
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.
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.
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/>.
18 #include <linux/version.h>
19 #include <linux/kernel.h>
20 #include <linux/uwb.h>
22 #include "uwb-internal.h"
24 static void uwb_rsv_timer(unsigned long arg
);
26 static const char *rsv_states
[] = {
27 [UWB_RSV_STATE_NONE
] = "none",
28 [UWB_RSV_STATE_O_INITIATED
] = "initiated",
29 [UWB_RSV_STATE_O_PENDING
] = "pending",
30 [UWB_RSV_STATE_O_MODIFIED
] = "modified",
31 [UWB_RSV_STATE_O_ESTABLISHED
] = "established",
32 [UWB_RSV_STATE_T_ACCEPTED
] = "accepted",
33 [UWB_RSV_STATE_T_DENIED
] = "denied",
34 [UWB_RSV_STATE_T_PENDING
] = "pending",
37 static const char *rsv_types
[] = {
38 [UWB_DRP_TYPE_ALIEN_BP
] = "alien-bp",
39 [UWB_DRP_TYPE_HARD
] = "hard",
40 [UWB_DRP_TYPE_SOFT
] = "soft",
41 [UWB_DRP_TYPE_PRIVATE
] = "private",
42 [UWB_DRP_TYPE_PCA
] = "pca",
46 * uwb_rsv_state_str - return a string for a reservation state
47 * @state: the reservation state.
49 const char *uwb_rsv_state_str(enum uwb_rsv_state state
)
51 if (state
< UWB_RSV_STATE_NONE
|| state
>= UWB_RSV_STATE_LAST
)
53 return rsv_states
[state
];
55 EXPORT_SYMBOL_GPL(uwb_rsv_state_str
);
58 * uwb_rsv_type_str - return a string for a reservation type
59 * @type: the reservation type
61 const char *uwb_rsv_type_str(enum uwb_drp_type type
)
63 if (type
< UWB_DRP_TYPE_ALIEN_BP
|| type
> UWB_DRP_TYPE_PCA
)
65 return rsv_types
[type
];
67 EXPORT_SYMBOL_GPL(uwb_rsv_type_str
);
69 static void uwb_rsv_dump(struct uwb_rsv
*rsv
)
71 struct device
*dev
= &rsv
->rc
->uwb_dev
.dev
;
72 struct uwb_dev_addr devaddr
;
73 char owner
[UWB_ADDR_STRSIZE
], target
[UWB_ADDR_STRSIZE
];
75 uwb_dev_addr_print(owner
, sizeof(owner
), &rsv
->owner
->dev_addr
);
76 if (rsv
->target
.type
== UWB_RSV_TARGET_DEV
)
77 devaddr
= rsv
->target
.dev
->dev_addr
;
79 devaddr
= rsv
->target
.devaddr
;
80 uwb_dev_addr_print(target
, sizeof(target
), &devaddr
);
82 dev_dbg(dev
, "rsv %s -> %s: %s\n", owner
, target
, uwb_rsv_state_str(rsv
->state
));
86 * Get a free stream index for a reservation.
88 * If the target is a DevAddr (e.g., a WUSB cluster reservation) then
89 * the stream is allocated from a pool of per-RC stream indexes,
90 * otherwise a unique stream index for the target is selected.
92 static int uwb_rsv_get_stream(struct uwb_rsv
*rsv
)
94 struct uwb_rc
*rc
= rsv
->rc
;
95 unsigned long *streams_bm
;
98 switch (rsv
->target
.type
) {
99 case UWB_RSV_TARGET_DEV
:
100 streams_bm
= rsv
->target
.dev
->streams
;
102 case UWB_RSV_TARGET_DEVADDR
:
103 streams_bm
= rc
->uwb_dev
.streams
;
109 stream
= find_first_zero_bit(streams_bm
, UWB_NUM_STREAMS
);
110 if (stream
>= UWB_NUM_STREAMS
)
113 rsv
->stream
= stream
;
114 set_bit(stream
, streams_bm
);
119 static void uwb_rsv_put_stream(struct uwb_rsv
*rsv
)
121 struct uwb_rc
*rc
= rsv
->rc
;
122 unsigned long *streams_bm
;
124 switch (rsv
->target
.type
) {
125 case UWB_RSV_TARGET_DEV
:
126 streams_bm
= rsv
->target
.dev
->streams
;
128 case UWB_RSV_TARGET_DEVADDR
:
129 streams_bm
= rc
->uwb_dev
.streams
;
135 clear_bit(rsv
->stream
, streams_bm
);
139 * Generate a MAS allocation with a single row component.
141 static void uwb_rsv_gen_alloc_row(struct uwb_mas_bm
*mas
,
142 int first_mas
, int mas_per_zone
,
145 struct uwb_mas_bm col
;
148 bitmap_zero(mas
->bm
, UWB_NUM_MAS
);
149 bitmap_zero(col
.bm
, UWB_NUM_MAS
);
150 bitmap_fill(col
.bm
, mas_per_zone
);
151 bitmap_shift_left(col
.bm
, col
.bm
, first_mas
+ zs
* UWB_MAS_PER_ZONE
, UWB_NUM_MAS
);
153 for (z
= zs
; z
<= ze
; z
++) {
154 bitmap_or(mas
->bm
, mas
->bm
, col
.bm
, UWB_NUM_MAS
);
155 bitmap_shift_left(col
.bm
, col
.bm
, UWB_MAS_PER_ZONE
, UWB_NUM_MAS
);
160 * Allocate some MAS for this reservation based on current local
161 * availability, the reservation parameters (max_mas, min_mas,
162 * sparsity), and the WiMedia rules for MAS allocations.
164 * Returns -EBUSY is insufficient free MAS are available.
166 * FIXME: to simplify this, only safe reservations with a single row
167 * component in zones 1 to 15 are tried (zone 0 is skipped to avoid
168 * problems with the MAS reserved for the BP).
170 * [ECMA-368] section B.2.
172 static int uwb_rsv_alloc_mas(struct uwb_rsv
*rsv
)
174 static const int safe_mas_in_row
[UWB_NUM_ZONES
] = {
175 8, 7, 6, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1,
178 struct uwb_mas_bm mas
;
182 * Search all valid safe allocations until either: too few MAS
183 * are available; or the smallest allocation with sufficient
186 * The top of the zones are preferred, so space for larger
187 * allocations is available in the bottom of the zone (e.g., a
188 * 15 MAS allocation should start in row 14 leaving space for
189 * a 120 MAS allocation at row 0).
191 for (n
= safe_mas_in_row
[0]; n
>= 1; n
--) {
194 num_mas
= n
* (UWB_NUM_ZONES
- 1);
195 if (num_mas
< rsv
->min_mas
)
197 if (found
&& num_mas
< rsv
->max_mas
)
200 for (r
= UWB_MAS_PER_ZONE
-1; r
>= 0; r
--) {
201 if (safe_mas_in_row
[r
] < n
)
203 uwb_rsv_gen_alloc_row(&mas
, r
, n
, 1, UWB_NUM_ZONES
);
204 if (uwb_drp_avail_reserve_pending(rsv
->rc
, &mas
) == 0) {
214 bitmap_copy(rsv
->mas
.bm
, mas
.bm
, UWB_NUM_MAS
);
218 static void uwb_rsv_stroke_timer(struct uwb_rsv
*rsv
)
220 int sframes
= UWB_MAX_LOST_BEACONS
;
223 * Multicast reservations can become established within 1
224 * super frame and should not be terminated if no response is
227 if (rsv
->is_multicast
) {
228 if (rsv
->state
== UWB_RSV_STATE_O_INITIATED
)
230 if (rsv
->state
== UWB_RSV_STATE_O_ESTABLISHED
)
234 rsv
->expired
= false;
237 * Add an additional 2 superframes to account for the
238 * time to send the SET DRP IE command.
240 unsigned timeout_us
= (sframes
+ 2) * UWB_SUPERFRAME_LENGTH_US
;
241 mod_timer(&rsv
->timer
, jiffies
+ usecs_to_jiffies(timeout_us
));
243 del_timer(&rsv
->timer
);
247 * Update a reservations state, and schedule an update of the
248 * transmitted DRP IEs.
250 static void uwb_rsv_state_update(struct uwb_rsv
*rsv
,
251 enum uwb_rsv_state new_state
)
253 rsv
->state
= new_state
;
254 rsv
->ie_valid
= false;
258 uwb_rsv_stroke_timer(rsv
);
259 uwb_rsv_sched_update(rsv
->rc
);
262 static void uwb_rsv_callback(struct uwb_rsv
*rsv
)
268 void uwb_rsv_set_state(struct uwb_rsv
*rsv
, enum uwb_rsv_state new_state
)
270 if (rsv
->state
== new_state
) {
271 switch (rsv
->state
) {
272 case UWB_RSV_STATE_O_ESTABLISHED
:
273 case UWB_RSV_STATE_T_ACCEPTED
:
274 case UWB_RSV_STATE_NONE
:
275 uwb_rsv_stroke_timer(rsv
);
278 /* Expecting a state transition so leave timer
286 case UWB_RSV_STATE_NONE
:
287 uwb_drp_avail_release(rsv
->rc
, &rsv
->mas
);
288 if (uwb_rsv_is_owner(rsv
))
289 uwb_rsv_put_stream(rsv
);
290 uwb_rsv_state_update(rsv
, UWB_RSV_STATE_NONE
);
291 uwb_rsv_callback(rsv
);
293 case UWB_RSV_STATE_O_INITIATED
:
294 uwb_rsv_state_update(rsv
, UWB_RSV_STATE_O_INITIATED
);
296 case UWB_RSV_STATE_O_PENDING
:
297 uwb_rsv_state_update(rsv
, UWB_RSV_STATE_O_PENDING
);
299 case UWB_RSV_STATE_O_ESTABLISHED
:
300 uwb_drp_avail_reserve(rsv
->rc
, &rsv
->mas
);
301 uwb_rsv_state_update(rsv
, UWB_RSV_STATE_O_ESTABLISHED
);
302 uwb_rsv_callback(rsv
);
304 case UWB_RSV_STATE_T_ACCEPTED
:
305 uwb_drp_avail_reserve(rsv
->rc
, &rsv
->mas
);
306 uwb_rsv_state_update(rsv
, UWB_RSV_STATE_T_ACCEPTED
);
307 uwb_rsv_callback(rsv
);
309 case UWB_RSV_STATE_T_DENIED
:
310 uwb_rsv_state_update(rsv
, UWB_RSV_STATE_T_DENIED
);
313 dev_err(&rsv
->rc
->uwb_dev
.dev
, "unhandled state: %s (%d)\n",
314 uwb_rsv_state_str(new_state
), new_state
);
318 static struct uwb_rsv
*uwb_rsv_alloc(struct uwb_rc
*rc
)
322 rsv
= kzalloc(sizeof(struct uwb_rsv
), GFP_KERNEL
);
326 INIT_LIST_HEAD(&rsv
->rc_node
);
327 INIT_LIST_HEAD(&rsv
->pal_node
);
328 init_timer(&rsv
->timer
);
329 rsv
->timer
.function
= uwb_rsv_timer
;
330 rsv
->timer
.data
= (unsigned long)rsv
;
337 static void uwb_rsv_free(struct uwb_rsv
*rsv
)
339 uwb_dev_put(rsv
->owner
);
340 if (rsv
->target
.type
== UWB_RSV_TARGET_DEV
)
341 uwb_dev_put(rsv
->target
.dev
);
346 * uwb_rsv_create - allocate and initialize a UWB reservation structure
347 * @rc: the radio controller
348 * @cb: callback to use when the reservation completes or terminates
349 * @pal_priv: data private to the PAL to be passed in the callback
351 * The callback is called when the state of the reservation changes from:
353 * - pending to accepted
354 * - pending to denined
355 * - accepted to terminated
356 * - pending to terminated
358 struct uwb_rsv
*uwb_rsv_create(struct uwb_rc
*rc
, uwb_rsv_cb_f cb
, void *pal_priv
)
362 rsv
= uwb_rsv_alloc(rc
);
367 rsv
->pal_priv
= pal_priv
;
371 EXPORT_SYMBOL_GPL(uwb_rsv_create
);
373 void uwb_rsv_remove(struct uwb_rsv
*rsv
)
375 if (rsv
->state
!= UWB_RSV_STATE_NONE
)
376 uwb_rsv_set_state(rsv
, UWB_RSV_STATE_NONE
);
377 del_timer_sync(&rsv
->timer
);
378 list_del(&rsv
->rc_node
);
383 * uwb_rsv_destroy - free a UWB reservation structure
384 * @rsv: the reservation to free
386 * The reservation will be terminated if it is pending or established.
388 void uwb_rsv_destroy(struct uwb_rsv
*rsv
)
390 struct uwb_rc
*rc
= rsv
->rc
;
392 mutex_lock(&rc
->rsvs_mutex
);
394 mutex_unlock(&rc
->rsvs_mutex
);
396 EXPORT_SYMBOL_GPL(uwb_rsv_destroy
);
399 * usb_rsv_establish - start a reservation establishment
400 * @rsv: the reservation
402 * The PAL should fill in @rsv's owner, target, type, max_mas,
403 * min_mas, sparsity and is_multicast fields. If the target is a
404 * uwb_dev it must be referenced.
406 * The reservation's callback will be called when the reservation is
407 * accepted, denied or times out.
409 int uwb_rsv_establish(struct uwb_rsv
*rsv
)
411 struct uwb_rc
*rc
= rsv
->rc
;
414 mutex_lock(&rc
->rsvs_mutex
);
416 ret
= uwb_rsv_get_stream(rsv
);
420 ret
= uwb_rsv_alloc_mas(rsv
);
422 uwb_rsv_put_stream(rsv
);
426 list_add_tail(&rsv
->rc_node
, &rc
->reservations
);
427 rsv
->owner
= &rc
->uwb_dev
;
428 uwb_dev_get(rsv
->owner
);
429 uwb_rsv_set_state(rsv
, UWB_RSV_STATE_O_INITIATED
);
431 mutex_unlock(&rc
->rsvs_mutex
);
434 EXPORT_SYMBOL_GPL(uwb_rsv_establish
);
437 * uwb_rsv_modify - modify an already established reservation
438 * @rsv: the reservation to modify
439 * @max_mas: new maximum MAS to reserve
440 * @min_mas: new minimum MAS to reserve
441 * @sparsity: new sparsity to use
443 * FIXME: implement this once there are PALs that use it.
445 int uwb_rsv_modify(struct uwb_rsv
*rsv
, int max_mas
, int min_mas
, int sparsity
)
449 EXPORT_SYMBOL_GPL(uwb_rsv_modify
);
452 * uwb_rsv_terminate - terminate an established reservation
453 * @rsv: the reservation to terminate
455 * A reservation is terminated by removing the DRP IE from the beacon,
456 * the other end will consider the reservation to be terminated when
457 * it does not see the DRP IE for at least mMaxLostBeacons.
459 * If applicable, the reference to the target uwb_dev will be released.
461 void uwb_rsv_terminate(struct uwb_rsv
*rsv
)
463 struct uwb_rc
*rc
= rsv
->rc
;
465 mutex_lock(&rc
->rsvs_mutex
);
467 uwb_rsv_set_state(rsv
, UWB_RSV_STATE_NONE
);
469 mutex_unlock(&rc
->rsvs_mutex
);
471 EXPORT_SYMBOL_GPL(uwb_rsv_terminate
);
474 * uwb_rsv_accept - accept a new reservation from a peer
475 * @rsv: the reservation
476 * @cb: call back for reservation changes
477 * @pal_priv: data to be passed in the above call back
479 * Reservation requests from peers are denied unless a PAL accepts it
480 * by calling this function.
482 void uwb_rsv_accept(struct uwb_rsv
*rsv
, uwb_rsv_cb_f cb
, void *pal_priv
)
485 rsv
->pal_priv
= pal_priv
;
486 rsv
->state
= UWB_RSV_STATE_T_ACCEPTED
;
488 EXPORT_SYMBOL_GPL(uwb_rsv_accept
);
491 * Is a received DRP IE for this reservation?
493 static bool uwb_rsv_match(struct uwb_rsv
*rsv
, struct uwb_dev
*src
,
494 struct uwb_ie_drp
*drp_ie
)
496 struct uwb_dev_addr
*rsv_src
;
499 stream
= uwb_ie_drp_stream_index(drp_ie
);
501 if (rsv
->stream
!= stream
)
504 switch (rsv
->target
.type
) {
505 case UWB_RSV_TARGET_DEVADDR
:
506 return rsv
->stream
== stream
;
507 case UWB_RSV_TARGET_DEV
:
508 if (uwb_ie_drp_owner(drp_ie
))
509 rsv_src
= &rsv
->owner
->dev_addr
;
511 rsv_src
= &rsv
->target
.dev
->dev_addr
;
512 return uwb_dev_addr_cmp(&src
->dev_addr
, rsv_src
) == 0;
517 static struct uwb_rsv
*uwb_rsv_new_target(struct uwb_rc
*rc
,
519 struct uwb_ie_drp
*drp_ie
)
523 enum uwb_rsv_state state
;
525 rsv
= uwb_rsv_alloc(rc
);
531 uwb_dev_get(rsv
->owner
);
532 rsv
->target
.type
= UWB_RSV_TARGET_DEV
;
533 rsv
->target
.dev
= &rc
->uwb_dev
;
534 rsv
->type
= uwb_ie_drp_type(drp_ie
);
535 rsv
->stream
= uwb_ie_drp_stream_index(drp_ie
);
536 uwb_drp_ie_to_bm(&rsv
->mas
, drp_ie
);
539 * See if any PALs are interested in this reservation. If not,
542 rsv
->state
= UWB_RSV_STATE_T_DENIED
;
543 spin_lock(&rc
->pal_lock
);
544 list_for_each_entry(pal
, &rc
->pals
, node
) {
547 if (rsv
->state
== UWB_RSV_STATE_T_ACCEPTED
)
550 spin_unlock(&rc
->pal_lock
);
552 list_add_tail(&rsv
->rc_node
, &rc
->reservations
);
554 rsv
->state
= UWB_RSV_STATE_NONE
;
555 uwb_rsv_set_state(rsv
, state
);
561 * uwb_rsv_find - find a reservation for a received DRP IE.
562 * @rc: the radio controller
563 * @src: source of the DRP IE
564 * @drp_ie: the DRP IE
566 * If the reservation cannot be found and the DRP IE is from a peer
567 * attempting to establish a new reservation, create a new reservation
568 * and add it to the list.
570 struct uwb_rsv
*uwb_rsv_find(struct uwb_rc
*rc
, struct uwb_dev
*src
,
571 struct uwb_ie_drp
*drp_ie
)
575 list_for_each_entry(rsv
, &rc
->reservations
, rc_node
) {
576 if (uwb_rsv_match(rsv
, src
, drp_ie
))
580 if (uwb_ie_drp_owner(drp_ie
))
581 return uwb_rsv_new_target(rc
, src
, drp_ie
);
587 * Go through all the reservations and check for timeouts and (if
588 * necessary) update their DRP IEs.
590 * FIXME: look at building the SET_DRP_IE command here rather than
591 * having to rescan the list in uwb_rc_send_all_drp_ie().
593 static bool uwb_rsv_update_all(struct uwb_rc
*rc
)
595 struct uwb_rsv
*rsv
, *t
;
596 bool ie_updated
= false;
598 list_for_each_entry_safe(rsv
, t
, &rc
->reservations
, rc_node
) {
600 uwb_drp_handle_timeout(rsv
);
601 if (!rsv
->ie_valid
) {
602 uwb_drp_ie_update(rsv
);
610 void uwb_rsv_sched_update(struct uwb_rc
*rc
)
612 queue_work(rc
->rsv_workq
, &rc
->rsv_update_work
);
616 * Update DRP IEs and, if necessary, the DRP Availability IE and send
617 * the updated IEs to the radio controller.
619 static void uwb_rsv_update_work(struct work_struct
*work
)
621 struct uwb_rc
*rc
= container_of(work
, struct uwb_rc
, rsv_update_work
);
624 mutex_lock(&rc
->rsvs_mutex
);
626 ie_updated
= uwb_rsv_update_all(rc
);
628 if (!rc
->drp_avail
.ie_valid
) {
629 uwb_drp_avail_ie_update(rc
);
634 uwb_rc_send_all_drp_ie(rc
);
636 mutex_unlock(&rc
->rsvs_mutex
);
639 static void uwb_rsv_timer(unsigned long arg
)
641 struct uwb_rsv
*rsv
= (struct uwb_rsv
*)arg
;
644 uwb_rsv_sched_update(rsv
->rc
);
647 void uwb_rsv_init(struct uwb_rc
*rc
)
649 INIT_LIST_HEAD(&rc
->reservations
);
650 mutex_init(&rc
->rsvs_mutex
);
651 INIT_WORK(&rc
->rsv_update_work
, uwb_rsv_update_work
);
653 bitmap_complement(rc
->uwb_dev
.streams
, rc
->uwb_dev
.streams
, UWB_NUM_STREAMS
);
656 int uwb_rsv_setup(struct uwb_rc
*rc
)
660 snprintf(name
, sizeof(name
), "%s_rsvd", dev_name(&rc
->uwb_dev
.dev
));
661 rc
->rsv_workq
= create_singlethread_workqueue(name
);
662 if (rc
->rsv_workq
== NULL
)
668 void uwb_rsv_cleanup(struct uwb_rc
*rc
)
670 struct uwb_rsv
*rsv
, *t
;
672 mutex_lock(&rc
->rsvs_mutex
);
673 list_for_each_entry_safe(rsv
, t
, &rc
->reservations
, rc_node
) {
676 mutex_unlock(&rc
->rsvs_mutex
);
678 cancel_work_sync(&rc
->rsv_update_work
);
679 destroy_workqueue(rc
->rsv_workq
);