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