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/kernel.h>
19 #include <linux/uwb.h>
21 #include "uwb-internal.h"
23 static void uwb_rsv_timer(unsigned long arg
);
25 static const char *rsv_states
[] = {
26 [UWB_RSV_STATE_NONE
] = "none",
27 [UWB_RSV_STATE_O_INITIATED
] = "initiated",
28 [UWB_RSV_STATE_O_PENDING
] = "pending",
29 [UWB_RSV_STATE_O_MODIFIED
] = "modified",
30 [UWB_RSV_STATE_O_ESTABLISHED
] = "established",
31 [UWB_RSV_STATE_T_ACCEPTED
] = "accepted",
32 [UWB_RSV_STATE_T_DENIED
] = "denied",
33 [UWB_RSV_STATE_T_PENDING
] = "pending",
36 static const char *rsv_types
[] = {
37 [UWB_DRP_TYPE_ALIEN_BP
] = "alien-bp",
38 [UWB_DRP_TYPE_HARD
] = "hard",
39 [UWB_DRP_TYPE_SOFT
] = "soft",
40 [UWB_DRP_TYPE_PRIVATE
] = "private",
41 [UWB_DRP_TYPE_PCA
] = "pca",
45 * uwb_rsv_state_str - return a string for a reservation state
46 * @state: the reservation state.
48 const char *uwb_rsv_state_str(enum uwb_rsv_state state
)
50 if (state
< UWB_RSV_STATE_NONE
|| state
>= UWB_RSV_STATE_LAST
)
52 return rsv_states
[state
];
54 EXPORT_SYMBOL_GPL(uwb_rsv_state_str
);
57 * uwb_rsv_type_str - return a string for a reservation type
58 * @type: the reservation type
60 const char *uwb_rsv_type_str(enum uwb_drp_type type
)
62 if (type
< UWB_DRP_TYPE_ALIEN_BP
|| type
> UWB_DRP_TYPE_PCA
)
64 return rsv_types
[type
];
66 EXPORT_SYMBOL_GPL(uwb_rsv_type_str
);
68 static void uwb_rsv_dump(struct uwb_rsv
*rsv
)
70 struct device
*dev
= &rsv
->rc
->uwb_dev
.dev
;
71 struct uwb_dev_addr devaddr
;
72 char owner
[UWB_ADDR_STRSIZE
], target
[UWB_ADDR_STRSIZE
];
74 uwb_dev_addr_print(owner
, sizeof(owner
), &rsv
->owner
->dev_addr
);
75 if (rsv
->target
.type
== UWB_RSV_TARGET_DEV
)
76 devaddr
= rsv
->target
.dev
->dev_addr
;
78 devaddr
= rsv
->target
.devaddr
;
79 uwb_dev_addr_print(target
, sizeof(target
), &devaddr
);
81 dev_dbg(dev
, "rsv %s -> %s: %s\n", owner
, target
, uwb_rsv_state_str(rsv
->state
));
84 static void uwb_rsv_release(struct kref
*kref
)
86 struct uwb_rsv
*rsv
= container_of(kref
, struct uwb_rsv
, kref
);
91 static void uwb_rsv_get(struct uwb_rsv
*rsv
)
96 static void uwb_rsv_put(struct uwb_rsv
*rsv
)
98 kref_put(&rsv
->kref
, uwb_rsv_release
);
102 * Get a free stream index for a reservation.
104 * If the target is a DevAddr (e.g., a WUSB cluster reservation) then
105 * the stream is allocated from a pool of per-RC stream indexes,
106 * otherwise a unique stream index for the target is selected.
108 static int uwb_rsv_get_stream(struct uwb_rsv
*rsv
)
110 struct uwb_rc
*rc
= rsv
->rc
;
111 unsigned long *streams_bm
;
114 switch (rsv
->target
.type
) {
115 case UWB_RSV_TARGET_DEV
:
116 streams_bm
= rsv
->target
.dev
->streams
;
118 case UWB_RSV_TARGET_DEVADDR
:
119 streams_bm
= rc
->uwb_dev
.streams
;
125 stream
= find_first_zero_bit(streams_bm
, UWB_NUM_STREAMS
);
126 if (stream
>= UWB_NUM_STREAMS
)
129 rsv
->stream
= stream
;
130 set_bit(stream
, streams_bm
);
135 static void uwb_rsv_put_stream(struct uwb_rsv
*rsv
)
137 struct uwb_rc
*rc
= rsv
->rc
;
138 unsigned long *streams_bm
;
140 switch (rsv
->target
.type
) {
141 case UWB_RSV_TARGET_DEV
:
142 streams_bm
= rsv
->target
.dev
->streams
;
144 case UWB_RSV_TARGET_DEVADDR
:
145 streams_bm
= rc
->uwb_dev
.streams
;
151 clear_bit(rsv
->stream
, streams_bm
);
155 * Generate a MAS allocation with a single row component.
157 static void uwb_rsv_gen_alloc_row(struct uwb_mas_bm
*mas
,
158 int first_mas
, int mas_per_zone
,
161 struct uwb_mas_bm col
;
164 bitmap_zero(mas
->bm
, UWB_NUM_MAS
);
165 bitmap_zero(col
.bm
, UWB_NUM_MAS
);
166 bitmap_fill(col
.bm
, mas_per_zone
);
167 bitmap_shift_left(col
.bm
, col
.bm
, first_mas
+ zs
* UWB_MAS_PER_ZONE
, UWB_NUM_MAS
);
169 for (z
= zs
; z
<= ze
; z
++) {
170 bitmap_or(mas
->bm
, mas
->bm
, col
.bm
, UWB_NUM_MAS
);
171 bitmap_shift_left(col
.bm
, col
.bm
, UWB_MAS_PER_ZONE
, UWB_NUM_MAS
);
176 * Allocate some MAS for this reservation based on current local
177 * availability, the reservation parameters (max_mas, min_mas,
178 * sparsity), and the WiMedia rules for MAS allocations.
180 * Returns -EBUSY is insufficient free MAS are available.
182 * FIXME: to simplify this, only safe reservations with a single row
183 * component in zones 1 to 15 are tried (zone 0 is skipped to avoid
184 * problems with the MAS reserved for the BP).
186 * [ECMA-368] section B.2.
188 static int uwb_rsv_alloc_mas(struct uwb_rsv
*rsv
)
190 static const int safe_mas_in_row
[UWB_NUM_ZONES
] = {
191 8, 7, 6, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1,
194 struct uwb_mas_bm mas
;
198 * Search all valid safe allocations until either: too few MAS
199 * are available; or the smallest allocation with sufficient
202 * The top of the zones are preferred, so space for larger
203 * allocations is available in the bottom of the zone (e.g., a
204 * 15 MAS allocation should start in row 14 leaving space for
205 * a 120 MAS allocation at row 0).
207 for (n
= safe_mas_in_row
[0]; n
>= 1; n
--) {
210 num_mas
= n
* (UWB_NUM_ZONES
- 1);
211 if (num_mas
< rsv
->min_mas
)
213 if (found
&& num_mas
< rsv
->max_mas
)
216 for (r
= UWB_MAS_PER_ZONE
-1; r
>= 0; r
--) {
217 if (safe_mas_in_row
[r
] < n
)
219 uwb_rsv_gen_alloc_row(&mas
, r
, n
, 1, UWB_NUM_ZONES
);
220 if (uwb_drp_avail_reserve_pending(rsv
->rc
, &mas
) == 0) {
230 bitmap_copy(rsv
->mas
.bm
, mas
.bm
, UWB_NUM_MAS
);
234 static void uwb_rsv_stroke_timer(struct uwb_rsv
*rsv
)
236 int sframes
= UWB_MAX_LOST_BEACONS
;
239 * Multicast reservations can become established within 1
240 * super frame and should not be terminated if no response is
243 if (rsv
->is_multicast
) {
244 if (rsv
->state
== UWB_RSV_STATE_O_INITIATED
)
246 if (rsv
->state
== UWB_RSV_STATE_O_ESTABLISHED
)
250 rsv
->expired
= false;
253 * Add an additional 2 superframes to account for the
254 * time to send the SET DRP IE command.
256 unsigned timeout_us
= (sframes
+ 2) * UWB_SUPERFRAME_LENGTH_US
;
257 mod_timer(&rsv
->timer
, jiffies
+ usecs_to_jiffies(timeout_us
));
259 del_timer(&rsv
->timer
);
263 * Update a reservations state, and schedule an update of the
264 * transmitted DRP IEs.
266 static void uwb_rsv_state_update(struct uwb_rsv
*rsv
,
267 enum uwb_rsv_state new_state
)
269 rsv
->state
= new_state
;
270 rsv
->ie_valid
= false;
274 uwb_rsv_stroke_timer(rsv
);
275 uwb_rsv_sched_update(rsv
->rc
);
278 static void uwb_rsv_callback(struct uwb_rsv
*rsv
)
284 void uwb_rsv_set_state(struct uwb_rsv
*rsv
, enum uwb_rsv_state new_state
)
286 if (rsv
->state
== new_state
) {
287 switch (rsv
->state
) {
288 case UWB_RSV_STATE_O_ESTABLISHED
:
289 case UWB_RSV_STATE_T_ACCEPTED
:
290 case UWB_RSV_STATE_NONE
:
291 uwb_rsv_stroke_timer(rsv
);
294 /* Expecting a state transition so leave timer
302 case UWB_RSV_STATE_NONE
:
303 uwb_drp_avail_release(rsv
->rc
, &rsv
->mas
);
304 if (uwb_rsv_is_owner(rsv
))
305 uwb_rsv_put_stream(rsv
);
306 uwb_rsv_state_update(rsv
, UWB_RSV_STATE_NONE
);
307 uwb_rsv_callback(rsv
);
309 case UWB_RSV_STATE_O_INITIATED
:
310 uwb_rsv_state_update(rsv
, UWB_RSV_STATE_O_INITIATED
);
312 case UWB_RSV_STATE_O_PENDING
:
313 uwb_rsv_state_update(rsv
, UWB_RSV_STATE_O_PENDING
);
315 case UWB_RSV_STATE_O_ESTABLISHED
:
316 uwb_drp_avail_reserve(rsv
->rc
, &rsv
->mas
);
317 uwb_rsv_state_update(rsv
, UWB_RSV_STATE_O_ESTABLISHED
);
318 uwb_rsv_callback(rsv
);
320 case UWB_RSV_STATE_T_ACCEPTED
:
321 uwb_drp_avail_reserve(rsv
->rc
, &rsv
->mas
);
322 uwb_rsv_state_update(rsv
, UWB_RSV_STATE_T_ACCEPTED
);
323 uwb_rsv_callback(rsv
);
325 case UWB_RSV_STATE_T_DENIED
:
326 uwb_rsv_state_update(rsv
, UWB_RSV_STATE_T_DENIED
);
329 dev_err(&rsv
->rc
->uwb_dev
.dev
, "unhandled state: %s (%d)\n",
330 uwb_rsv_state_str(new_state
), new_state
);
334 static struct uwb_rsv
*uwb_rsv_alloc(struct uwb_rc
*rc
)
338 rsv
= kzalloc(sizeof(struct uwb_rsv
), GFP_KERNEL
);
342 INIT_LIST_HEAD(&rsv
->rc_node
);
343 INIT_LIST_HEAD(&rsv
->pal_node
);
344 kref_init(&rsv
->kref
);
345 init_timer(&rsv
->timer
);
346 rsv
->timer
.function
= uwb_rsv_timer
;
347 rsv
->timer
.data
= (unsigned long)rsv
;
355 * uwb_rsv_create - allocate and initialize a UWB reservation structure
356 * @rc: the radio controller
357 * @cb: callback to use when the reservation completes or terminates
358 * @pal_priv: data private to the PAL to be passed in the callback
360 * The callback is called when the state of the reservation changes from:
362 * - pending to accepted
363 * - pending to denined
364 * - accepted to terminated
365 * - pending to terminated
367 struct uwb_rsv
*uwb_rsv_create(struct uwb_rc
*rc
, uwb_rsv_cb_f cb
, void *pal_priv
)
371 rsv
= uwb_rsv_alloc(rc
);
376 rsv
->pal_priv
= pal_priv
;
380 EXPORT_SYMBOL_GPL(uwb_rsv_create
);
382 void uwb_rsv_remove(struct uwb_rsv
*rsv
)
384 if (rsv
->state
!= UWB_RSV_STATE_NONE
)
385 uwb_rsv_set_state(rsv
, UWB_RSV_STATE_NONE
);
386 del_timer_sync(&rsv
->timer
);
387 uwb_dev_put(rsv
->owner
);
388 if (rsv
->target
.type
== UWB_RSV_TARGET_DEV
)
389 uwb_dev_put(rsv
->target
.dev
);
391 list_del_init(&rsv
->rc_node
);
396 * uwb_rsv_destroy - free a UWB reservation structure
397 * @rsv: the reservation to free
399 * The reservation must already be terminated.
401 void uwb_rsv_destroy(struct uwb_rsv
*rsv
)
405 EXPORT_SYMBOL_GPL(uwb_rsv_destroy
);
408 * usb_rsv_establish - start a reservation establishment
409 * @rsv: the reservation
411 * The PAL should fill in @rsv's owner, target, type, max_mas,
412 * min_mas, sparsity and is_multicast fields. If the target is a
413 * uwb_dev it must be referenced.
415 * The reservation's callback will be called when the reservation is
416 * accepted, denied or times out.
418 int uwb_rsv_establish(struct uwb_rsv
*rsv
)
420 struct uwb_rc
*rc
= rsv
->rc
;
423 mutex_lock(&rc
->rsvs_mutex
);
425 ret
= uwb_rsv_get_stream(rsv
);
429 ret
= uwb_rsv_alloc_mas(rsv
);
431 uwb_rsv_put_stream(rsv
);
436 list_add_tail(&rsv
->rc_node
, &rc
->reservations
);
437 rsv
->owner
= &rc
->uwb_dev
;
438 uwb_dev_get(rsv
->owner
);
439 uwb_rsv_set_state(rsv
, UWB_RSV_STATE_O_INITIATED
);
441 mutex_unlock(&rc
->rsvs_mutex
);
444 EXPORT_SYMBOL_GPL(uwb_rsv_establish
);
447 * uwb_rsv_modify - modify an already established reservation
448 * @rsv: the reservation to modify
449 * @max_mas: new maximum MAS to reserve
450 * @min_mas: new minimum MAS to reserve
451 * @sparsity: new sparsity to use
453 * FIXME: implement this once there are PALs that use it.
455 int uwb_rsv_modify(struct uwb_rsv
*rsv
, int max_mas
, int min_mas
, int sparsity
)
459 EXPORT_SYMBOL_GPL(uwb_rsv_modify
);
462 * uwb_rsv_terminate - terminate an established reservation
463 * @rsv: the reservation to terminate
465 * A reservation is terminated by removing the DRP IE from the beacon,
466 * the other end will consider the reservation to be terminated when
467 * it does not see the DRP IE for at least mMaxLostBeacons.
469 * If applicable, the reference to the target uwb_dev will be released.
471 void uwb_rsv_terminate(struct uwb_rsv
*rsv
)
473 struct uwb_rc
*rc
= rsv
->rc
;
475 mutex_lock(&rc
->rsvs_mutex
);
477 uwb_rsv_set_state(rsv
, UWB_RSV_STATE_NONE
);
479 mutex_unlock(&rc
->rsvs_mutex
);
481 EXPORT_SYMBOL_GPL(uwb_rsv_terminate
);
484 * uwb_rsv_accept - accept a new reservation from a peer
485 * @rsv: the reservation
486 * @cb: call back for reservation changes
487 * @pal_priv: data to be passed in the above call back
489 * Reservation requests from peers are denied unless a PAL accepts it
490 * by calling this function.
492 * The PAL call uwb_rsv_destroy() for all accepted reservations before
493 * calling uwb_pal_unregister().
495 void uwb_rsv_accept(struct uwb_rsv
*rsv
, uwb_rsv_cb_f cb
, void *pal_priv
)
500 rsv
->pal_priv
= pal_priv
;
501 rsv
->state
= UWB_RSV_STATE_T_ACCEPTED
;
503 EXPORT_SYMBOL_GPL(uwb_rsv_accept
);
506 * Is a received DRP IE for this reservation?
508 static bool uwb_rsv_match(struct uwb_rsv
*rsv
, struct uwb_dev
*src
,
509 struct uwb_ie_drp
*drp_ie
)
511 struct uwb_dev_addr
*rsv_src
;
514 stream
= uwb_ie_drp_stream_index(drp_ie
);
516 if (rsv
->stream
!= stream
)
519 switch (rsv
->target
.type
) {
520 case UWB_RSV_TARGET_DEVADDR
:
521 return rsv
->stream
== stream
;
522 case UWB_RSV_TARGET_DEV
:
523 if (uwb_ie_drp_owner(drp_ie
))
524 rsv_src
= &rsv
->owner
->dev_addr
;
526 rsv_src
= &rsv
->target
.dev
->dev_addr
;
527 return uwb_dev_addr_cmp(&src
->dev_addr
, rsv_src
) == 0;
532 static struct uwb_rsv
*uwb_rsv_new_target(struct uwb_rc
*rc
,
534 struct uwb_ie_drp
*drp_ie
)
538 enum uwb_rsv_state state
;
540 rsv
= uwb_rsv_alloc(rc
);
546 uwb_dev_get(rsv
->owner
);
547 rsv
->target
.type
= UWB_RSV_TARGET_DEV
;
548 rsv
->target
.dev
= &rc
->uwb_dev
;
549 rsv
->type
= uwb_ie_drp_type(drp_ie
);
550 rsv
->stream
= uwb_ie_drp_stream_index(drp_ie
);
551 uwb_drp_ie_to_bm(&rsv
->mas
, drp_ie
);
554 * See if any PALs are interested in this reservation. If not,
557 rsv
->state
= UWB_RSV_STATE_T_DENIED
;
558 mutex_lock(&rc
->uwb_dev
.mutex
);
559 list_for_each_entry(pal
, &rc
->pals
, node
) {
561 pal
->new_rsv(pal
, rsv
);
562 if (rsv
->state
== UWB_RSV_STATE_T_ACCEPTED
)
565 mutex_unlock(&rc
->uwb_dev
.mutex
);
567 list_add_tail(&rsv
->rc_node
, &rc
->reservations
);
569 rsv
->state
= UWB_RSV_STATE_NONE
;
570 uwb_rsv_set_state(rsv
, state
);
576 * uwb_rsv_find - find a reservation for a received DRP IE.
577 * @rc: the radio controller
578 * @src: source of the DRP IE
579 * @drp_ie: the DRP IE
581 * If the reservation cannot be found and the DRP IE is from a peer
582 * attempting to establish a new reservation, create a new reservation
583 * and add it to the list.
585 struct uwb_rsv
*uwb_rsv_find(struct uwb_rc
*rc
, struct uwb_dev
*src
,
586 struct uwb_ie_drp
*drp_ie
)
590 list_for_each_entry(rsv
, &rc
->reservations
, rc_node
) {
591 if (uwb_rsv_match(rsv
, src
, drp_ie
))
595 if (uwb_ie_drp_owner(drp_ie
))
596 return uwb_rsv_new_target(rc
, src
, drp_ie
);
602 * Go through all the reservations and check for timeouts and (if
603 * necessary) update their DRP IEs.
605 * FIXME: look at building the SET_DRP_IE command here rather than
606 * having to rescan the list in uwb_rc_send_all_drp_ie().
608 static bool uwb_rsv_update_all(struct uwb_rc
*rc
)
610 struct uwb_rsv
*rsv
, *t
;
611 bool ie_updated
= false;
613 list_for_each_entry_safe(rsv
, t
, &rc
->reservations
, rc_node
) {
615 uwb_drp_handle_timeout(rsv
);
616 if (!rsv
->ie_valid
) {
617 uwb_drp_ie_update(rsv
);
625 void uwb_rsv_sched_update(struct uwb_rc
*rc
)
627 queue_work(rc
->rsv_workq
, &rc
->rsv_update_work
);
631 * Update DRP IEs and, if necessary, the DRP Availability IE and send
632 * the updated IEs to the radio controller.
634 static void uwb_rsv_update_work(struct work_struct
*work
)
636 struct uwb_rc
*rc
= container_of(work
, struct uwb_rc
, rsv_update_work
);
639 mutex_lock(&rc
->rsvs_mutex
);
641 ie_updated
= uwb_rsv_update_all(rc
);
643 if (!rc
->drp_avail
.ie_valid
) {
644 uwb_drp_avail_ie_update(rc
);
649 uwb_rc_send_all_drp_ie(rc
);
651 mutex_unlock(&rc
->rsvs_mutex
);
654 static void uwb_rsv_timer(unsigned long arg
)
656 struct uwb_rsv
*rsv
= (struct uwb_rsv
*)arg
;
659 uwb_rsv_sched_update(rsv
->rc
);
663 * uwb_rsv_remove_all - remove all reservations
664 * @rc: the radio controller
666 * A DRP IE update is not done.
668 void uwb_rsv_remove_all(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
);
681 void uwb_rsv_init(struct uwb_rc
*rc
)
683 INIT_LIST_HEAD(&rc
->reservations
);
684 mutex_init(&rc
->rsvs_mutex
);
685 INIT_WORK(&rc
->rsv_update_work
, uwb_rsv_update_work
);
687 bitmap_complement(rc
->uwb_dev
.streams
, rc
->uwb_dev
.streams
, UWB_NUM_STREAMS
);
690 int uwb_rsv_setup(struct uwb_rc
*rc
)
694 snprintf(name
, sizeof(name
), "%s_rsvd", dev_name(&rc
->uwb_dev
.dev
));
695 rc
->rsv_workq
= create_singlethread_workqueue(name
);
696 if (rc
->rsv_workq
== NULL
)
702 void uwb_rsv_cleanup(struct uwb_rc
*rc
)
704 uwb_rsv_remove_all(rc
);
705 destroy_workqueue(rc
->rsv_workq
);