Root/
1 | /* |
2 | * Incremental bus scan, based on bus topology |
3 | * |
4 | * Copyright (C) 2004-2006 Kristian Hoegsberg <krh@bitplanet.net> |
5 | * |
6 | * This program is free software; you can redistribute it and/or modify |
7 | * it under the terms of the GNU General Public License as published by |
8 | * the Free Software Foundation; either version 2 of the License, or |
9 | * (at your option) any later version. |
10 | * |
11 | * This program is distributed in the hope that it will be useful, |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 | * GNU General Public License for more details. |
15 | * |
16 | * You should have received a copy of the GNU General Public License |
17 | * along with this program; if not, write to the Free Software Foundation, |
18 | * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
19 | */ |
20 | |
21 | #include <linux/bug.h> |
22 | #include <linux/errno.h> |
23 | #include <linux/firewire.h> |
24 | #include <linux/firewire-constants.h> |
25 | #include <linux/jiffies.h> |
26 | #include <linux/kernel.h> |
27 | #include <linux/list.h> |
28 | #include <linux/module.h> |
29 | #include <linux/slab.h> |
30 | #include <linux/spinlock.h> |
31 | |
32 | #include <linux/atomic.h> |
33 | #include <asm/byteorder.h> |
34 | |
35 | #include "core.h" |
36 | |
37 | #define SELF_ID_PHY_ID(q) (((q) >> 24) & 0x3f) |
38 | #define SELF_ID_EXTENDED(q) (((q) >> 23) & 0x01) |
39 | #define SELF_ID_LINK_ON(q) (((q) >> 22) & 0x01) |
40 | #define SELF_ID_GAP_COUNT(q) (((q) >> 16) & 0x3f) |
41 | #define SELF_ID_PHY_SPEED(q) (((q) >> 14) & 0x03) |
42 | #define SELF_ID_CONTENDER(q) (((q) >> 11) & 0x01) |
43 | #define SELF_ID_PHY_INITIATOR(q) (((q) >> 1) & 0x01) |
44 | #define SELF_ID_MORE_PACKETS(q) (((q) >> 0) & 0x01) |
45 | |
46 | #define SELF_ID_EXT_SEQUENCE(q) (((q) >> 20) & 0x07) |
47 | |
48 | #define SELFID_PORT_CHILD 0x3 |
49 | #define SELFID_PORT_PARENT 0x2 |
50 | #define SELFID_PORT_NCONN 0x1 |
51 | #define SELFID_PORT_NONE 0x0 |
52 | |
53 | static u32 *count_ports(u32 *sid, int *total_port_count, int *child_port_count) |
54 | { |
55 | u32 q; |
56 | int port_type, shift, seq; |
57 | |
58 | *total_port_count = 0; |
59 | *child_port_count = 0; |
60 | |
61 | shift = 6; |
62 | q = *sid; |
63 | seq = 0; |
64 | |
65 | while (1) { |
66 | port_type = (q >> shift) & 0x03; |
67 | switch (port_type) { |
68 | case SELFID_PORT_CHILD: |
69 | (*child_port_count)++; |
70 | case SELFID_PORT_PARENT: |
71 | case SELFID_PORT_NCONN: |
72 | (*total_port_count)++; |
73 | case SELFID_PORT_NONE: |
74 | break; |
75 | } |
76 | |
77 | shift -= 2; |
78 | if (shift == 0) { |
79 | if (!SELF_ID_MORE_PACKETS(q)) |
80 | return sid + 1; |
81 | |
82 | shift = 16; |
83 | sid++; |
84 | q = *sid; |
85 | |
86 | /* |
87 | * Check that the extra packets actually are |
88 | * extended self ID packets and that the |
89 | * sequence numbers in the extended self ID |
90 | * packets increase as expected. |
91 | */ |
92 | |
93 | if (!SELF_ID_EXTENDED(q) || |
94 | seq != SELF_ID_EXT_SEQUENCE(q)) |
95 | return NULL; |
96 | |
97 | seq++; |
98 | } |
99 | } |
100 | } |
101 | |
102 | static int get_port_type(u32 *sid, int port_index) |
103 | { |
104 | int index, shift; |
105 | |
106 | index = (port_index + 5) / 8; |
107 | shift = 16 - ((port_index + 5) & 7) * 2; |
108 | return (sid[index] >> shift) & 0x03; |
109 | } |
110 | |
111 | static struct fw_node *fw_node_create(u32 sid, int port_count, int color) |
112 | { |
113 | struct fw_node *node; |
114 | |
115 | node = kzalloc(sizeof(*node) + port_count * sizeof(node->ports[0]), |
116 | GFP_ATOMIC); |
117 | if (node == NULL) |
118 | return NULL; |
119 | |
120 | node->color = color; |
121 | node->node_id = LOCAL_BUS | SELF_ID_PHY_ID(sid); |
122 | node->link_on = SELF_ID_LINK_ON(sid); |
123 | node->phy_speed = SELF_ID_PHY_SPEED(sid); |
124 | node->initiated_reset = SELF_ID_PHY_INITIATOR(sid); |
125 | node->port_count = port_count; |
126 | |
127 | atomic_set(&node->ref_count, 1); |
128 | INIT_LIST_HEAD(&node->link); |
129 | |
130 | return node; |
131 | } |
132 | |
133 | /* |
134 | * Compute the maximum hop count for this node and it's children. The |
135 | * maximum hop count is the maximum number of connections between any |
136 | * two nodes in the subtree rooted at this node. We need this for |
137 | * setting the gap count. As we build the tree bottom up in |
138 | * build_tree() below, this is fairly easy to do: for each node we |
139 | * maintain the max hop count and the max depth, ie the number of hops |
140 | * to the furthest leaf. Computing the max hop count breaks down into |
141 | * two cases: either the path goes through this node, in which case |
142 | * the hop count is the sum of the two biggest child depths plus 2. |
143 | * Or it could be the case that the max hop path is entirely |
144 | * containted in a child tree, in which case the max hop count is just |
145 | * the max hop count of this child. |
146 | */ |
147 | static void update_hop_count(struct fw_node *node) |
148 | { |
149 | int depths[2] = { -1, -1 }; |
150 | int max_child_hops = 0; |
151 | int i; |
152 | |
153 | for (i = 0; i < node->port_count; i++) { |
154 | if (node->ports[i] == NULL) |
155 | continue; |
156 | |
157 | if (node->ports[i]->max_hops > max_child_hops) |
158 | max_child_hops = node->ports[i]->max_hops; |
159 | |
160 | if (node->ports[i]->max_depth > depths[0]) { |
161 | depths[1] = depths[0]; |
162 | depths[0] = node->ports[i]->max_depth; |
163 | } else if (node->ports[i]->max_depth > depths[1]) |
164 | depths[1] = node->ports[i]->max_depth; |
165 | } |
166 | |
167 | node->max_depth = depths[0] + 1; |
168 | node->max_hops = max(max_child_hops, depths[0] + depths[1] + 2); |
169 | } |
170 | |
171 | static inline struct fw_node *fw_node(struct list_head *l) |
172 | { |
173 | return list_entry(l, struct fw_node, link); |
174 | } |
175 | |
176 | /* |
177 | * This function builds the tree representation of the topology given |
178 | * by the self IDs from the latest bus reset. During the construction |
179 | * of the tree, the function checks that the self IDs are valid and |
180 | * internally consistent. On success this function returns the |
181 | * fw_node corresponding to the local card otherwise NULL. |
182 | */ |
183 | static struct fw_node *build_tree(struct fw_card *card, |
184 | u32 *sid, int self_id_count) |
185 | { |
186 | struct fw_node *node, *child, *local_node, *irm_node; |
187 | struct list_head stack, *h; |
188 | u32 *next_sid, *end, q; |
189 | int i, port_count, child_port_count, phy_id, parent_count, stack_depth; |
190 | int gap_count; |
191 | bool beta_repeaters_present; |
192 | |
193 | local_node = NULL; |
194 | node = NULL; |
195 | INIT_LIST_HEAD(&stack); |
196 | stack_depth = 0; |
197 | end = sid + self_id_count; |
198 | phy_id = 0; |
199 | irm_node = NULL; |
200 | gap_count = SELF_ID_GAP_COUNT(*sid); |
201 | beta_repeaters_present = false; |
202 | |
203 | while (sid < end) { |
204 | next_sid = count_ports(sid, &port_count, &child_port_count); |
205 | |
206 | if (next_sid == NULL) { |
207 | fw_err(card, "inconsistent extended self IDs\n"); |
208 | return NULL; |
209 | } |
210 | |
211 | q = *sid; |
212 | if (phy_id != SELF_ID_PHY_ID(q)) { |
213 | fw_err(card, "PHY ID mismatch in self ID: %d != %d\n", |
214 | phy_id, SELF_ID_PHY_ID(q)); |
215 | return NULL; |
216 | } |
217 | |
218 | if (child_port_count > stack_depth) { |
219 | fw_err(card, "topology stack underflow\n"); |
220 | return NULL; |
221 | } |
222 | |
223 | /* |
224 | * Seek back from the top of our stack to find the |
225 | * start of the child nodes for this node. |
226 | */ |
227 | for (i = 0, h = &stack; i < child_port_count; i++) |
228 | h = h->prev; |
229 | /* |
230 | * When the stack is empty, this yields an invalid value, |
231 | * but that pointer will never be dereferenced. |
232 | */ |
233 | child = fw_node(h); |
234 | |
235 | node = fw_node_create(q, port_count, card->color); |
236 | if (node == NULL) { |
237 | fw_err(card, "out of memory while building topology\n"); |
238 | return NULL; |
239 | } |
240 | |
241 | if (phy_id == (card->node_id & 0x3f)) |
242 | local_node = node; |
243 | |
244 | if (SELF_ID_CONTENDER(q)) |
245 | irm_node = node; |
246 | |
247 | parent_count = 0; |
248 | |
249 | for (i = 0; i < port_count; i++) { |
250 | switch (get_port_type(sid, i)) { |
251 | case SELFID_PORT_PARENT: |
252 | /* |
253 | * Who's your daddy? We dont know the |
254 | * parent node at this time, so we |
255 | * temporarily abuse node->color for |
256 | * remembering the entry in the |
257 | * node->ports array where the parent |
258 | * node should be. Later, when we |
259 | * handle the parent node, we fix up |
260 | * the reference. |
261 | */ |
262 | parent_count++; |
263 | node->color = i; |
264 | break; |
265 | |
266 | case SELFID_PORT_CHILD: |
267 | node->ports[i] = child; |
268 | /* |
269 | * Fix up parent reference for this |
270 | * child node. |
271 | */ |
272 | child->ports[child->color] = node; |
273 | child->color = card->color; |
274 | child = fw_node(child->link.next); |
275 | break; |
276 | } |
277 | } |
278 | |
279 | /* |
280 | * Check that the node reports exactly one parent |
281 | * port, except for the root, which of course should |
282 | * have no parents. |
283 | */ |
284 | if ((next_sid == end && parent_count != 0) || |
285 | (next_sid < end && parent_count != 1)) { |
286 | fw_err(card, "parent port inconsistency for node %d: " |
287 | "parent_count=%d\n", phy_id, parent_count); |
288 | return NULL; |
289 | } |
290 | |
291 | /* Pop the child nodes off the stack and push the new node. */ |
292 | __list_del(h->prev, &stack); |
293 | list_add_tail(&node->link, &stack); |
294 | stack_depth += 1 - child_port_count; |
295 | |
296 | if (node->phy_speed == SCODE_BETA && |
297 | parent_count + child_port_count > 1) |
298 | beta_repeaters_present = true; |
299 | |
300 | /* |
301 | * If PHYs report different gap counts, set an invalid count |
302 | * which will force a gap count reconfiguration and a reset. |
303 | */ |
304 | if (SELF_ID_GAP_COUNT(q) != gap_count) |
305 | gap_count = 0; |
306 | |
307 | update_hop_count(node); |
308 | |
309 | sid = next_sid; |
310 | phy_id++; |
311 | } |
312 | |
313 | card->root_node = node; |
314 | card->irm_node = irm_node; |
315 | card->gap_count = gap_count; |
316 | card->beta_repeaters_present = beta_repeaters_present; |
317 | |
318 | return local_node; |
319 | } |
320 | |
321 | typedef void (*fw_node_callback_t)(struct fw_card * card, |
322 | struct fw_node * node, |
323 | struct fw_node * parent); |
324 | |
325 | static void for_each_fw_node(struct fw_card *card, struct fw_node *root, |
326 | fw_node_callback_t callback) |
327 | { |
328 | struct list_head list; |
329 | struct fw_node *node, *next, *child, *parent; |
330 | int i; |
331 | |
332 | INIT_LIST_HEAD(&list); |
333 | |
334 | fw_node_get(root); |
335 | list_add_tail(&root->link, &list); |
336 | parent = NULL; |
337 | list_for_each_entry(node, &list, link) { |
338 | node->color = card->color; |
339 | |
340 | for (i = 0; i < node->port_count; i++) { |
341 | child = node->ports[i]; |
342 | if (!child) |
343 | continue; |
344 | if (child->color == card->color) |
345 | parent = child; |
346 | else { |
347 | fw_node_get(child); |
348 | list_add_tail(&child->link, &list); |
349 | } |
350 | } |
351 | |
352 | callback(card, node, parent); |
353 | } |
354 | |
355 | list_for_each_entry_safe(node, next, &list, link) |
356 | fw_node_put(node); |
357 | } |
358 | |
359 | static void report_lost_node(struct fw_card *card, |
360 | struct fw_node *node, struct fw_node *parent) |
361 | { |
362 | fw_node_event(card, node, FW_NODE_DESTROYED); |
363 | fw_node_put(node); |
364 | |
365 | /* Topology has changed - reset bus manager retry counter */ |
366 | card->bm_retries = 0; |
367 | } |
368 | |
369 | static void report_found_node(struct fw_card *card, |
370 | struct fw_node *node, struct fw_node *parent) |
371 | { |
372 | int b_path = (node->phy_speed == SCODE_BETA); |
373 | |
374 | if (parent != NULL) { |
375 | /* min() macro doesn't work here with gcc 3.4 */ |
376 | node->max_speed = parent->max_speed < node->phy_speed ? |
377 | parent->max_speed : node->phy_speed; |
378 | node->b_path = parent->b_path && b_path; |
379 | } else { |
380 | node->max_speed = node->phy_speed; |
381 | node->b_path = b_path; |
382 | } |
383 | |
384 | fw_node_event(card, node, FW_NODE_CREATED); |
385 | |
386 | /* Topology has changed - reset bus manager retry counter */ |
387 | card->bm_retries = 0; |
388 | } |
389 | |
390 | void fw_destroy_nodes(struct fw_card *card) |
391 | { |
392 | unsigned long flags; |
393 | |
394 | spin_lock_irqsave(&card->lock, flags); |
395 | card->color++; |
396 | if (card->local_node != NULL) |
397 | for_each_fw_node(card, card->local_node, report_lost_node); |
398 | card->local_node = NULL; |
399 | spin_unlock_irqrestore(&card->lock, flags); |
400 | } |
401 | |
402 | static void move_tree(struct fw_node *node0, struct fw_node *node1, int port) |
403 | { |
404 | struct fw_node *tree; |
405 | int i; |
406 | |
407 | tree = node1->ports[port]; |
408 | node0->ports[port] = tree; |
409 | for (i = 0; i < tree->port_count; i++) { |
410 | if (tree->ports[i] == node1) { |
411 | tree->ports[i] = node0; |
412 | break; |
413 | } |
414 | } |
415 | } |
416 | |
417 | /* |
418 | * Compare the old topology tree for card with the new one specified by root. |
419 | * Queue the nodes and mark them as either found, lost or updated. |
420 | * Update the nodes in the card topology tree as we go. |
421 | */ |
422 | static void update_tree(struct fw_card *card, struct fw_node *root) |
423 | { |
424 | struct list_head list0, list1; |
425 | struct fw_node *node0, *node1, *next1; |
426 | int i, event; |
427 | |
428 | INIT_LIST_HEAD(&list0); |
429 | list_add_tail(&card->local_node->link, &list0); |
430 | INIT_LIST_HEAD(&list1); |
431 | list_add_tail(&root->link, &list1); |
432 | |
433 | node0 = fw_node(list0.next); |
434 | node1 = fw_node(list1.next); |
435 | |
436 | while (&node0->link != &list0) { |
437 | WARN_ON(node0->port_count != node1->port_count); |
438 | |
439 | if (node0->link_on && !node1->link_on) |
440 | event = FW_NODE_LINK_OFF; |
441 | else if (!node0->link_on && node1->link_on) |
442 | event = FW_NODE_LINK_ON; |
443 | else if (node1->initiated_reset && node1->link_on) |
444 | event = FW_NODE_INITIATED_RESET; |
445 | else |
446 | event = FW_NODE_UPDATED; |
447 | |
448 | node0->node_id = node1->node_id; |
449 | node0->color = card->color; |
450 | node0->link_on = node1->link_on; |
451 | node0->initiated_reset = node1->initiated_reset; |
452 | node0->max_hops = node1->max_hops; |
453 | node1->color = card->color; |
454 | fw_node_event(card, node0, event); |
455 | |
456 | if (card->root_node == node1) |
457 | card->root_node = node0; |
458 | if (card->irm_node == node1) |
459 | card->irm_node = node0; |
460 | |
461 | for (i = 0; i < node0->port_count; i++) { |
462 | if (node0->ports[i] && node1->ports[i]) { |
463 | /* |
464 | * This port didn't change, queue the |
465 | * connected node for further |
466 | * investigation. |
467 | */ |
468 | if (node0->ports[i]->color == card->color) |
469 | continue; |
470 | list_add_tail(&node0->ports[i]->link, &list0); |
471 | list_add_tail(&node1->ports[i]->link, &list1); |
472 | } else if (node0->ports[i]) { |
473 | /* |
474 | * The nodes connected here were |
475 | * unplugged; unref the lost nodes and |
476 | * queue FW_NODE_LOST callbacks for |
477 | * them. |
478 | */ |
479 | |
480 | for_each_fw_node(card, node0->ports[i], |
481 | report_lost_node); |
482 | node0->ports[i] = NULL; |
483 | } else if (node1->ports[i]) { |
484 | /* |
485 | * One or more node were connected to |
486 | * this port. Move the new nodes into |
487 | * the tree and queue FW_NODE_CREATED |
488 | * callbacks for them. |
489 | */ |
490 | move_tree(node0, node1, i); |
491 | for_each_fw_node(card, node0->ports[i], |
492 | report_found_node); |
493 | } |
494 | } |
495 | |
496 | node0 = fw_node(node0->link.next); |
497 | next1 = fw_node(node1->link.next); |
498 | fw_node_put(node1); |
499 | node1 = next1; |
500 | } |
501 | } |
502 | |
503 | static void update_topology_map(struct fw_card *card, |
504 | u32 *self_ids, int self_id_count) |
505 | { |
506 | int node_count = (card->root_node->node_id & 0x3f) + 1; |
507 | __be32 *map = card->topology_map; |
508 | |
509 | *map++ = cpu_to_be32((self_id_count + 2) << 16); |
510 | *map++ = cpu_to_be32(be32_to_cpu(card->topology_map[1]) + 1); |
511 | *map++ = cpu_to_be32((node_count << 16) | self_id_count); |
512 | |
513 | while (self_id_count--) |
514 | *map++ = cpu_to_be32p(self_ids++); |
515 | |
516 | fw_compute_block_crc(card->topology_map); |
517 | } |
518 | |
519 | void fw_core_handle_bus_reset(struct fw_card *card, int node_id, int generation, |
520 | int self_id_count, u32 *self_ids, bool bm_abdicate) |
521 | { |
522 | struct fw_node *local_node; |
523 | unsigned long flags; |
524 | |
525 | /* |
526 | * If the selfID buffer is not the immediate successor of the |
527 | * previously processed one, we cannot reliably compare the |
528 | * old and new topologies. |
529 | */ |
530 | if (!is_next_generation(generation, card->generation) && |
531 | card->local_node != NULL) { |
532 | fw_destroy_nodes(card); |
533 | card->bm_retries = 0; |
534 | } |
535 | |
536 | spin_lock_irqsave(&card->lock, flags); |
537 | |
538 | card->broadcast_channel_allocated = card->broadcast_channel_auto_allocated; |
539 | card->node_id = node_id; |
540 | /* |
541 | * Update node_id before generation to prevent anybody from using |
542 | * a stale node_id together with a current generation. |
543 | */ |
544 | smp_wmb(); |
545 | card->generation = generation; |
546 | card->reset_jiffies = get_jiffies_64(); |
547 | card->bm_node_id = 0xffff; |
548 | card->bm_abdicate = bm_abdicate; |
549 | fw_schedule_bm_work(card, 0); |
550 | |
551 | local_node = build_tree(card, self_ids, self_id_count); |
552 | |
553 | update_topology_map(card, self_ids, self_id_count); |
554 | |
555 | card->color++; |
556 | |
557 | if (local_node == NULL) { |
558 | fw_err(card, "topology build failed\n"); |
559 | /* FIXME: We need to issue a bus reset in this case. */ |
560 | } else if (card->local_node == NULL) { |
561 | card->local_node = local_node; |
562 | for_each_fw_node(card, local_node, report_found_node); |
563 | } else { |
564 | update_tree(card, local_node); |
565 | } |
566 | |
567 | spin_unlock_irqrestore(&card->lock, flags); |
568 | } |
569 | EXPORT_SYMBOL(fw_core_handle_bus_reset); |
570 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9