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);