]>
Commit | Line | Data |
---|---|---|
3038e353 KH |
1 | /* -*- c-basic-offset: 8 -*- |
2 | * | |
3 | * fw-topology.c - Incremental bus scan, based on bus topology | |
4 | * | |
5 | * Copyright (C) 2004-2006 Kristian Hoegsberg <krh@bitplanet.net> | |
6 | * | |
7 | * This program is free software; you can redistribute it and/or modify | |
8 | * it under the terms of the GNU General Public License as published by | |
9 | * the Free Software Foundation; either version 2 of the License, or | |
10 | * (at your option) any later version. | |
11 | * | |
12 | * This program is distributed in the hope that it will be useful, | |
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | * GNU General Public License for more details. | |
16 | * | |
17 | * You should have received a copy of the GNU General Public License | |
18 | * along with this program; if not, write to the Free Software Foundation, | |
19 | * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. | |
20 | */ | |
21 | ||
22 | #include <linux/module.h> | |
23 | #include <linux/wait.h> | |
24 | #include <linux/errno.h> | |
25 | #include "fw-transaction.h" | |
26 | #include "fw-topology.h" | |
27 | ||
28 | #define self_id_phy_id(q) (((q) >> 24) & 0x3f) | |
29 | #define self_id_extended(q) (((q) >> 23) & 0x01) | |
30 | #define self_id_link_on(q) (((q) >> 22) & 0x01) | |
31 | #define self_id_gap_count(q) (((q) >> 16) & 0x3f) | |
32 | #define self_id_phy_speed(q) (((q) >> 14) & 0x03) | |
33 | #define self_id_contender(q) (((q) >> 11) & 0x01) | |
34 | #define self_id_phy_initiator(q) (((q) >> 1) & 0x01) | |
35 | #define self_id_more_packets(q) (((q) >> 0) & 0x01) | |
36 | ||
37 | #define self_id_ext_sequence(q) (((q) >> 20) & 0x07) | |
38 | ||
39 | static u32 *count_ports(u32 *sid, int *total_port_count, int *child_port_count) | |
40 | { | |
41 | u32 q; | |
42 | int port_type, shift, seq; | |
43 | ||
44 | *total_port_count = 0; | |
45 | *child_port_count = 0; | |
46 | ||
47 | shift = 6; | |
48 | q = *sid; | |
49 | seq = 0; | |
50 | ||
51 | while (1) { | |
52 | port_type = (q >> shift) & 0x03; | |
53 | switch (port_type) { | |
54 | case SELFID_PORT_CHILD: | |
55 | (*child_port_count)++; | |
56 | case SELFID_PORT_PARENT: | |
57 | case SELFID_PORT_NCONN: | |
58 | (*total_port_count)++; | |
59 | case SELFID_PORT_NONE: | |
60 | break; | |
61 | } | |
62 | ||
63 | shift -= 2; | |
64 | if (shift == 0) { | |
65 | if (!self_id_more_packets(q)) | |
66 | return sid + 1; | |
67 | ||
68 | shift = 16; | |
69 | sid++; | |
70 | q = *sid; | |
71 | ||
72 | /* Check that the extra packets actually are | |
73 | * extended self ID packets and that the | |
74 | * sequence numbers in the extended self ID | |
75 | * packets increase as expected. */ | |
76 | ||
77 | if (!self_id_extended(q) || | |
78 | seq != self_id_ext_sequence(q)) | |
79 | return NULL; | |
80 | ||
81 | seq++; | |
82 | } | |
83 | } | |
84 | } | |
85 | ||
86 | static int get_port_type(u32 *sid, int port_index) | |
87 | { | |
88 | int index, shift; | |
89 | ||
90 | index = (port_index + 5) / 8; | |
91 | shift = 16 - ((port_index + 5) & 7) * 2; | |
92 | return (sid[index] >> shift) & 0x03; | |
93 | } | |
94 | ||
95688e97 | 95 | static struct fw_node *fw_node_create(u32 sid, int port_count, int color) |
3038e353 KH |
96 | { |
97 | struct fw_node *node; | |
98 | ||
99 | node = kzalloc(sizeof *node + port_count * sizeof node->ports[0], | |
100 | GFP_ATOMIC); | |
101 | if (node == NULL) | |
102 | return NULL; | |
103 | ||
104 | node->color = color; | |
907293d7 | 105 | node->node_id = LOCAL_BUS | self_id_phy_id(sid); |
3038e353 KH |
106 | node->link_on = self_id_link_on(sid); |
107 | node->phy_speed = self_id_phy_speed(sid); | |
108 | node->port_count = port_count; | |
109 | ||
110 | atomic_set(&node->ref_count, 1); | |
111 | INIT_LIST_HEAD(&node->link); | |
112 | ||
113 | return node; | |
114 | } | |
115 | ||
83db801c KH |
116 | /* Compute the maximum hop count for this node and it's children. The |
117 | * maximum hop count is the maximum number of connections between any | |
118 | * two nodes in the subtree rooted at this node. We need this for | |
119 | * setting the gap count. As we build the tree bottom up in | |
120 | * build_tree() below, this is fairly easy to do: for each node we | |
121 | * maintain the max hop count and the max depth, ie the number of hops | |
122 | * to the furthest leaf. Computing the max hop count breaks down into | |
123 | * two cases: either the path goes through this node, in which case | |
124 | * the hop count is the sum of the two biggest child depths plus 2. | |
125 | * Or it could be the case that the max hop path is entirely | |
126 | * containted in a child tree, in which case the max hop count is just | |
127 | * the max hop count of this child. | |
128 | */ | |
129 | static void update_hop_count(struct fw_node *node) | |
130 | { | |
131 | int depths[2] = { -1, -1 }; | |
132 | int max_child_hops = 0; | |
133 | int i; | |
134 | ||
135 | for (i = 0; i < node->port_count; i++) { | |
136 | if (node->ports[i].node == NULL) | |
137 | continue; | |
138 | ||
139 | if (node->ports[i].node->max_hops > max_child_hops) | |
140 | max_child_hops = node->ports[i].node->max_hops; | |
141 | ||
142 | if (node->ports[i].node->max_depth > depths[0]) { | |
143 | depths[1] = depths[0]; | |
144 | depths[0] = node->ports[i].node->max_depth; | |
145 | } else if (node->ports[i].node->max_depth > depths[1]) | |
146 | depths[1] = node->ports[i].node->max_depth; | |
147 | } | |
148 | ||
149 | node->max_depth = depths[0] + 1; | |
150 | node->max_hops = max(max_child_hops, depths[0] + depths[1] + 2); | |
151 | } | |
152 | ||
153 | ||
3038e353 KH |
154 | /** |
155 | * build_tree - Build the tree representation of the topology | |
156 | * @self_ids: array of self IDs to create the tree from | |
157 | * @self_id_count: the length of the self_ids array | |
158 | * @local_id: the node ID of the local node | |
159 | * | |
160 | * This function builds the tree representation of the topology given | |
161 | * by the self IDs from the latest bus reset. During the construction | |
162 | * of the tree, the function checks that the self IDs are valid and | |
163 | * internally consistent. On succcess this funtions returns the | |
164 | * fw_node corresponding to the local card otherwise NULL. | |
165 | */ | |
473d28c7 KH |
166 | static struct fw_node *build_tree(struct fw_card *card, |
167 | u32 *sid, int self_id_count) | |
3038e353 KH |
168 | { |
169 | struct fw_node *node, *child, *local_node; | |
170 | struct list_head stack, *h; | |
473d28c7 | 171 | u32 *next_sid, *end, q; |
3038e353 | 172 | int i, port_count, child_port_count, phy_id, parent_count, stack_depth; |
83db801c | 173 | int gap_count, topology_type; |
3038e353 KH |
174 | |
175 | local_node = NULL; | |
176 | node = NULL; | |
177 | INIT_LIST_HEAD(&stack); | |
178 | stack_depth = 0; | |
473d28c7 | 179 | end = sid + self_id_count; |
3038e353 KH |
180 | phy_id = 0; |
181 | card->irm_node = NULL; | |
83db801c KH |
182 | gap_count = self_id_gap_count(*sid); |
183 | topology_type = 0; | |
3038e353 KH |
184 | |
185 | while (sid < end) { | |
186 | next_sid = count_ports(sid, &port_count, &child_port_count); | |
187 | ||
188 | if (next_sid == NULL) { | |
189 | fw_error("Inconsistent extended self IDs.\n"); | |
190 | return NULL; | |
191 | } | |
192 | ||
193 | q = *sid; | |
194 | if (phy_id != self_id_phy_id(q)) { | |
195 | fw_error("PHY ID mismatch in self ID: %d != %d.\n", | |
196 | phy_id, self_id_phy_id(q)); | |
197 | return NULL; | |
198 | } | |
199 | ||
200 | if (child_port_count > stack_depth) { | |
201 | fw_error("Topology stack underflow\n"); | |
202 | return NULL; | |
203 | } | |
204 | ||
205 | /* Seek back from the top of our stack to find the | |
206 | * start of the child nodes for this node. */ | |
207 | for (i = 0, h = &stack; i < child_port_count; i++) | |
208 | h = h->prev; | |
209 | child = fw_node(h); | |
210 | ||
211 | node = fw_node_create(q, port_count, card->color); | |
212 | if (node == NULL) { | |
213 | fw_error("Out of memory while building topology."); | |
214 | return NULL; | |
215 | } | |
216 | ||
217 | if (phy_id == (card->node_id & 0x3f)) | |
218 | local_node = node; | |
219 | ||
220 | if (self_id_contender(q)) | |
221 | card->irm_node = node; | |
222 | ||
83db801c KH |
223 | if (node->phy_speed == SCODE_BETA) |
224 | topology_type |= FW_TOPOLOGY_B; | |
225 | else | |
226 | topology_type |= FW_TOPOLOGY_A; | |
227 | ||
3038e353 KH |
228 | parent_count = 0; |
229 | ||
230 | for (i = 0; i < port_count; i++) { | |
231 | switch (get_port_type(sid, i)) { | |
232 | case SELFID_PORT_PARENT: | |
233 | /* Who's your daddy? We dont know the | |
234 | * parent node at this time, so we | |
235 | * temporarily abuse node->color for | |
236 | * remembering the entry in the | |
237 | * node->ports array where the parent | |
238 | * node should be. Later, when we | |
239 | * handle the parent node, we fix up | |
240 | * the reference. | |
241 | */ | |
242 | parent_count++; | |
243 | node->color = i; | |
244 | break; | |
245 | ||
246 | case SELFID_PORT_CHILD: | |
247 | node->ports[i].node = child; | |
248 | /* Fix up parent reference for this | |
249 | * child node. */ | |
250 | child->ports[child->color].node = node; | |
251 | child->color = card->color; | |
252 | child = fw_node(child->link.next); | |
253 | break; | |
254 | } | |
255 | } | |
256 | ||
257 | /* Check that the node reports exactly one parent | |
258 | * port, except for the root, which of course should | |
259 | * have no parents. */ | |
260 | if ((next_sid == end && parent_count != 0) || | |
261 | (next_sid < end && parent_count != 1)) { | |
262 | fw_error("Parent port inconsistency for node %d: " | |
263 | "parent_count=%d\n", phy_id, parent_count); | |
264 | return NULL; | |
265 | } | |
266 | ||
267 | /* Pop the child nodes off the stack and push the new node. */ | |
268 | __list_del(h->prev, &stack); | |
269 | list_add_tail(&node->link, &stack); | |
270 | stack_depth += 1 - child_port_count; | |
271 | ||
83db801c KH |
272 | /* If all PHYs does not report the same gap count |
273 | * setting, we fall back to 63 which will force a gap | |
274 | * count reconfiguration and a reset. */ | |
275 | if (self_id_gap_count(q) != gap_count) | |
276 | gap_count = 63; | |
277 | ||
278 | update_hop_count(node); | |
279 | ||
3038e353 KH |
280 | sid = next_sid; |
281 | phy_id++; | |
282 | } | |
283 | ||
284 | card->root_node = node; | |
83db801c KH |
285 | card->gap_count = gap_count; |
286 | card->topology_type = topology_type; | |
3038e353 KH |
287 | |
288 | return local_node; | |
289 | } | |
290 | ||
291 | typedef void (*fw_node_callback_t) (struct fw_card * card, | |
292 | struct fw_node * node, | |
293 | struct fw_node * parent); | |
294 | ||
295 | static void | |
296 | for_each_fw_node(struct fw_card *card, struct fw_node *root, | |
297 | fw_node_callback_t callback) | |
298 | { | |
299 | struct list_head list; | |
300 | struct fw_node *node, *next, *child, *parent; | |
301 | int i; | |
302 | ||
303 | INIT_LIST_HEAD(&list); | |
304 | ||
305 | fw_node_get(root); | |
306 | list_add_tail(&root->link, &list); | |
307 | parent = NULL; | |
308 | list_for_each_entry(node, &list, link) { | |
309 | node->color = card->color; | |
310 | ||
311 | for (i = 0; i < node->port_count; i++) { | |
312 | child = node->ports[i].node; | |
313 | if (!child) | |
314 | continue; | |
315 | if (child->color == card->color) | |
316 | parent = child; | |
317 | else { | |
318 | fw_node_get(child); | |
319 | list_add_tail(&child->link, &list); | |
320 | } | |
321 | } | |
322 | ||
323 | callback(card, node, parent); | |
324 | } | |
325 | ||
326 | list_for_each_entry_safe(node, next, &list, link) | |
327 | fw_node_put(node); | |
328 | } | |
329 | ||
330 | static void | |
331 | report_lost_node(struct fw_card *card, | |
332 | struct fw_node *node, struct fw_node *parent) | |
333 | { | |
334 | fw_node_event(card, node, FW_NODE_DESTROYED); | |
335 | fw_node_put(node); | |
336 | } | |
337 | ||
338 | static void | |
339 | report_found_node(struct fw_card *card, | |
340 | struct fw_node *node, struct fw_node *parent) | |
341 | { | |
342 | int b_path = (node->phy_speed == SCODE_BETA); | |
343 | ||
344 | if (parent != NULL) { | |
748086eb SR |
345 | /* min() macro doesn't work here with gcc 3.4 */ |
346 | node->max_speed = parent->max_speed < node->phy_speed ? | |
347 | parent->max_speed : node->phy_speed; | |
3038e353 KH |
348 | node->b_path = parent->b_path && b_path; |
349 | } else { | |
350 | node->max_speed = node->phy_speed; | |
351 | node->b_path = b_path; | |
352 | } | |
353 | ||
354 | fw_node_event(card, node, FW_NODE_CREATED); | |
355 | } | |
356 | ||
357 | void fw_destroy_nodes(struct fw_card *card) | |
358 | { | |
359 | unsigned long flags; | |
360 | ||
361 | spin_lock_irqsave(&card->lock, flags); | |
362 | card->color++; | |
363 | if (card->local_node != NULL) | |
364 | for_each_fw_node(card, card->local_node, report_lost_node); | |
365 | spin_unlock_irqrestore(&card->lock, flags); | |
366 | } | |
367 | ||
368 | static void move_tree(struct fw_node *node0, struct fw_node *node1, int port) | |
369 | { | |
370 | struct fw_node *tree; | |
371 | int i; | |
372 | ||
373 | tree = node1->ports[port].node; | |
374 | node0->ports[port].node = tree; | |
375 | for (i = 0; i < tree->port_count; i++) { | |
376 | if (tree->ports[i].node == node1) { | |
377 | tree->ports[i].node = node0; | |
378 | break; | |
379 | } | |
380 | } | |
381 | } | |
382 | ||
383 | /** | |
384 | * update_tree - compare the old topology tree for card with the new | |
385 | * one specified by root. Queue the nodes and mark them as either | |
386 | * found, lost or updated. Update the nodes in the card topology tree | |
387 | * as we go. | |
388 | */ | |
389 | static void | |
83db801c | 390 | update_tree(struct fw_card *card, struct fw_node *root) |
3038e353 KH |
391 | { |
392 | struct list_head list0, list1; | |
393 | struct fw_node *node0, *node1; | |
394 | int i, event; | |
395 | ||
396 | INIT_LIST_HEAD(&list0); | |
397 | list_add_tail(&card->local_node->link, &list0); | |
398 | INIT_LIST_HEAD(&list1); | |
399 | list_add_tail(&root->link, &list1); | |
400 | ||
401 | node0 = fw_node(list0.next); | |
402 | node1 = fw_node(list1.next); | |
3038e353 KH |
403 | |
404 | while (&node0->link != &list0) { | |
405 | ||
406 | /* assert(node0->port_count == node1->port_count); */ | |
407 | if (node0->link_on && !node1->link_on) | |
408 | event = FW_NODE_LINK_OFF; | |
409 | else if (!node0->link_on && node1->link_on) | |
410 | event = FW_NODE_LINK_ON; | |
411 | else | |
412 | event = FW_NODE_UPDATED; | |
413 | ||
414 | node0->node_id = node1->node_id; | |
415 | node0->color = card->color; | |
416 | node0->link_on = node1->link_on; | |
417 | node0->initiated_reset = node1->initiated_reset; | |
83db801c | 418 | node0->max_hops = node1->max_hops; |
3038e353 KH |
419 | node1->color = card->color; |
420 | fw_node_event(card, node0, event); | |
421 | ||
422 | if (card->root_node == node1) | |
423 | card->root_node = node0; | |
424 | if (card->irm_node == node1) | |
425 | card->irm_node = node0; | |
426 | ||
427 | for (i = 0; i < node0->port_count; i++) { | |
428 | if (node0->ports[i].node && node1->ports[i].node) { | |
429 | /* This port didn't change, queue the | |
430 | * connected node for further | |
431 | * investigation. */ | |
432 | if (node0->ports[i].node->color == card->color) | |
433 | continue; | |
434 | list_add_tail(&node0->ports[i].node->link, | |
435 | &list0); | |
436 | list_add_tail(&node1->ports[i].node->link, | |
437 | &list1); | |
438 | } else if (node0->ports[i].node) { | |
439 | /* The nodes connected here were | |
440 | * unplugged; unref the lost nodes and | |
441 | * queue FW_NODE_LOST callbacks for | |
442 | * them. */ | |
443 | ||
444 | for_each_fw_node(card, node0->ports[i].node, | |
445 | report_lost_node); | |
446 | node0->ports[i].node = NULL; | |
3038e353 KH |
447 | } else if (node1->ports[i].node) { |
448 | /* One or more node were connected to | |
449 | * this port. Move the new nodes into | |
450 | * the tree and queue FW_NODE_CREATED | |
451 | * callbacks for them. */ | |
452 | move_tree(node0, node1, i); | |
453 | for_each_fw_node(card, node0->ports[i].node, | |
454 | report_found_node); | |
3038e353 KH |
455 | } |
456 | } | |
457 | ||
458 | node0 = fw_node(node0->link.next); | |
459 | node1 = fw_node(node1->link.next); | |
460 | } | |
461 | } | |
462 | ||
473d28c7 KH |
463 | static void |
464 | update_topology_map(struct fw_card *card, u32 *self_ids, int self_id_count) | |
465 | { | |
466 | int node_count; | |
467 | u32 crc; | |
468 | ||
469 | card->topology_map[1]++; | |
470 | node_count = (card->root_node->node_id & 0x3f) + 1; | |
471 | card->topology_map[2] = (node_count << 16) | self_id_count; | |
472 | crc = crc16_itu_t(card->topology_map + 1, self_id_count + 2); | |
473 | card->topology_map[0] = ((self_id_count + 2) << 16) | crc; | |
474 | memcpy(&card->topology_map[3], self_ids, self_id_count * 4); | |
475 | } | |
476 | ||
3038e353 KH |
477 | void |
478 | fw_core_handle_bus_reset(struct fw_card *card, | |
479 | int node_id, int generation, | |
480 | int self_id_count, u32 * self_ids) | |
481 | { | |
482 | struct fw_node *local_node; | |
483 | unsigned long flags; | |
3038e353 KH |
484 | |
485 | fw_flush_transactions(card); | |
486 | ||
487 | spin_lock_irqsave(&card->lock, flags); | |
488 | ||
83db801c KH |
489 | /* If the new topology has a different self_id_count the topology |
490 | * changed, either nodes were added or removed. In that case we | |
491 | * reset the IRM reset counter. */ | |
492 | if (card->self_id_count != self_id_count) | |
931c4834 | 493 | card->bm_retries = 0; |
83db801c | 494 | |
3038e353 | 495 | card->node_id = node_id; |
3038e353 | 496 | card->generation = generation; |
931c4834 | 497 | card->reset_jiffies = jiffies; |
993baca3 | 498 | schedule_delayed_work(&card->work, 0); |
3038e353 | 499 | |
473d28c7 KH |
500 | local_node = build_tree(card, self_ids, self_id_count); |
501 | ||
502 | update_topology_map(card, self_ids, self_id_count); | |
3038e353 KH |
503 | |
504 | card->color++; | |
505 | ||
506 | if (local_node == NULL) { | |
507 | fw_error("topology build failed\n"); | |
508 | /* FIXME: We need to issue a bus reset in this case. */ | |
509 | } else if (card->local_node == NULL) { | |
510 | card->local_node = local_node; | |
511 | for_each_fw_node(card, local_node, report_found_node); | |
512 | } else { | |
83db801c | 513 | update_tree(card, local_node); |
3038e353 KH |
514 | } |
515 | ||
516 | spin_unlock_irqrestore(&card->lock, flags); | |
517 | } | |
3038e353 | 518 | EXPORT_SYMBOL(fw_core_handle_bus_reset); |