drivers/firewire/core-topology.c

0001 // SPDX-License-Identifier: GPL-2.0-or-later
0002 /*
0003  * Incremental bus scan, based on bus topology
0004  *
0005  * Copyright (C) 2004-2006 Kristian Hoegsberg <krh@bitplanet.net>
0006  */
0007
0008 #include <linux/bug.h>
0009 #include <linux/errno.h>
0010 #include <linux/firewire.h>
0011 #include <linux/firewire-constants.h>
0012 #include <linux/jiffies.h>
0013 #include <linux/kernel.h>
0014 #include <linux/list.h>
0015 #include <linux/module.h>
0016 #include <linux/slab.h>
0017 #include <linux/spinlock.h>
0018
0019 #include <linux/atomic.h>
0020 #include <asm/byteorder.h>
0021
0022 #include "core.h"
0023
0024 #define SELF_ID_PHY_ID(q)       (((q) >> 24) & 0x3f)
0025 #define SELF_ID_EXTENDED(q)     (((q) >> 23) & 0x01)
0026 #define SELF_ID_LINK_ON(q)      (((q) >> 22) & 0x01)
0027 #define SELF_ID_GAP_COUNT(q)        (((q) >> 16) & 0x3f)
0028 #define SELF_ID_PHY_SPEED(q)        (((q) >> 14) & 0x03)
0029 #define SELF_ID_CONTENDER(q)        (((q) >> 11) & 0x01)
0030 #define SELF_ID_PHY_INITIATOR(q)    (((q) >>  1) & 0x01)
0031 #define SELF_ID_MORE_PACKETS(q)     (((q) >>  0) & 0x01)
0032
0033 #define SELF_ID_EXT_SEQUENCE(q)     (((q) >> 20) & 0x07)
0034
0035 #define SELFID_PORT_CHILD   0x3
0036 #define SELFID_PORT_PARENT  0x2
0037 #define SELFID_PORT_NCONN   0x1
0038 #define SELFID_PORT_NONE    0x0
0039
0040 static u32 *count_ports(u32 *sid, int *total_port_count, int *child_port_count)
0041 {
0042     u32 q;
0043     int port_type, shift, seq;
0044
0045     *total_port_count = 0;
0046     *child_port_count = 0;
0047
0048     shift = 6;
0049     q = *sid;
0050     seq = 0;
0051
0052     while (1) {
0053         port_type = (q >> shift) & 0x03;
0054         switch (port_type) {
0055         case SELFID_PORT_CHILD:
0056             (*child_port_count)++;
0057             fallthrough;
0058         case SELFID_PORT_PARENT:
0059         case SELFID_PORT_NCONN:
0060             (*total_port_count)++;
0061             fallthrough;
0062         case SELFID_PORT_NONE:
0063             break;
0064         }
0065
0066         shift -= 2;
0067         if (shift == 0) {
0068             if (!SELF_ID_MORE_PACKETS(q))
0069                 return sid + 1;
0070
0071             shift = 16;
0072             sid++;
0073             q = *sid;
0074
0075             /*
0076              * Check that the extra packets actually are
0077              * extended self ID packets and that the
0078              * sequence numbers in the extended self ID
0079              * packets increase as expected.
0080              */
0081
0082             if (!SELF_ID_EXTENDED(q) ||
0083                 seq != SELF_ID_EXT_SEQUENCE(q))
0084                 return NULL;
0085
0086             seq++;
0087         }
0088     }
0089 }
0090
0091 static int get_port_type(u32 *sid, int port_index)
0092 {
0093     int index, shift;
0094
0095     index = (port_index + 5) / 8;
0096     shift = 16 - ((port_index + 5) & 7) * 2;
0097     return (sid[index] >> shift) & 0x03;
0098 }
0099
0100 static struct fw_node *fw_node_create(u32 sid, int port_count, int color)
0101 {
0102     struct fw_node *node;
0103
0104     node = kzalloc(struct_size(node, ports, port_count), GFP_ATOMIC);
0105     if (node == NULL)
0106         return NULL;
0107
0108     node->color = color;
0109     node->node_id = LOCAL_BUS | SELF_ID_PHY_ID(sid);
0110     node->link_on = SELF_ID_LINK_ON(sid);
0111     node->phy_speed = SELF_ID_PHY_SPEED(sid);
0112     node->initiated_reset = SELF_ID_PHY_INITIATOR(sid);
0113     node->port_count = port_count;
0114
0115     refcount_set(&node->ref_count, 1);
0116     INIT_LIST_HEAD(&node->link);
0117
0118     return node;
0119 }
0120
0121 /*
0122  * Compute the maximum hop count for this node and it's children.  The
0123  * maximum hop count is the maximum number of connections between any
0124  * two nodes in the subtree rooted at this node.  We need this for
0125  * setting the gap count.  As we build the tree bottom up in
0126  * build_tree() below, this is fairly easy to do: for each node we
0127  * maintain the max hop count and the max depth, ie the number of hops
0128  * to the furthest leaf.  Computing the max hop count breaks down into
0129  * two cases: either the path goes through this node, in which case
0130  * the hop count is the sum of the two biggest child depths plus 2.
0131  * Or it could be the case that the max hop path is entirely
0132  * containted in a child tree, in which case the max hop count is just
0133  * the max hop count of this child.
0134  */
0135 static void update_hop_count(struct fw_node *node)
0136 {
0137     int depths[2] = { -1, -1 };
0138     int max_child_hops = 0;
0139     int i;
0140
0141     for (i = 0; i < node->port_count; i++) {
0142         if (node->ports[i] == NULL)
0143             continue;
0144
0145         if (node->ports[i]->max_hops > max_child_hops)
0146             max_child_hops = node->ports[i]->max_hops;
0147
0148         if (node->ports[i]->max_depth > depths[0]) {
0149             depths[1] = depths[0];
0150             depths[0] = node->ports[i]->max_depth;
0151         } else if (node->ports[i]->max_depth > depths[1])
0152             depths[1] = node->ports[i]->max_depth;
0153     }
0154
0155     node->max_depth = depths[0] + 1;
0156     node->max_hops = max(max_child_hops, depths[0] + depths[1] + 2);
0157 }
0158
0159 static inline struct fw_node *fw_node(struct list_head *l)
0160 {
0161     return list_entry(l, struct fw_node, link);
0162 }
0163
0164 /*
0165  * This function builds the tree representation of the topology given
0166  * by the self IDs from the latest bus reset.  During the construction
0167  * of the tree, the function checks that the self IDs are valid and
0168  * internally consistent.  On success this function returns the
0169  * fw_node corresponding to the local card otherwise NULL.
0170  */
0171 static struct fw_node *build_tree(struct fw_card *card,
0172                   u32 *sid, int self_id_count)
0173 {
0174     struct fw_node *node, *child, *local_node, *irm_node;
0175     struct list_head stack, *h;
0176     u32 *next_sid, *end, q;
0177     int i, port_count, child_port_count, phy_id, parent_count, stack_depth;
0178     int gap_count;
0179     bool beta_repeaters_present;
0180
0181     local_node = NULL;
0182     node = NULL;
0183     INIT_LIST_HEAD(&stack);
0184     stack_depth = 0;
0185     end = sid + self_id_count;
0186     phy_id = 0;
0187     irm_node = NULL;
0188     gap_count = SELF_ID_GAP_COUNT(*sid);
0189     beta_repeaters_present = false;
0190
0191     while (sid < end) {
0192         next_sid = count_ports(sid, &port_count, &child_port_count);
0193
0194         if (next_sid == NULL) {
0195             fw_err(card, "inconsistent extended self IDs\n");
0196             return NULL;
0197         }
0198
0199         q = *sid;
0200         if (phy_id != SELF_ID_PHY_ID(q)) {
0201             fw_err(card, "PHY ID mismatch in self ID: %d != %d\n",
0202                    phy_id, SELF_ID_PHY_ID(q));
0203             return NULL;
0204         }
0205
0206         if (child_port_count > stack_depth) {
0207             fw_err(card, "topology stack underflow\n");
0208             return NULL;
0209         }
0210
0211         /*
0212          * Seek back from the top of our stack to find the
0213          * start of the child nodes for this node.
0214          */
0215         for (i = 0, h = &stack; i < child_port_count; i++)
0216             h = h->prev;
0217         /*
0218          * When the stack is empty, this yields an invalid value,
0219          * but that pointer will never be dereferenced.
0220          */
0221         child = fw_node(h);
0222
0223         node = fw_node_create(q, port_count, card->color);
0224         if (node == NULL) {
0225             fw_err(card, "out of memory while building topology\n");
0226             return NULL;
0227         }
0228
0229         if (phy_id == (card->node_id & 0x3f))
0230             local_node = node;
0231
0232         if (SELF_ID_CONTENDER(q))
0233             irm_node = node;
0234
0235         parent_count = 0;
0236
0237         for (i = 0; i < port_count; i++) {
0238             switch (get_port_type(sid, i)) {
0239             case SELFID_PORT_PARENT:
0240                 /*
0241                  * Who's your daddy?  We dont know the
0242                  * parent node at this time, so we
0243                  * temporarily abuse node->color for
0244                  * remembering the entry in the
0245                  * node->ports array where the parent
0246                  * node should be.  Later, when we
0247                  * handle the parent node, we fix up
0248                  * the reference.
0249                  */
0250                 parent_count++;
0251                 node->color = i;
0252                 break;
0253
0254             case SELFID_PORT_CHILD:
0255                 node->ports[i] = child;
0256                 /*
0257                  * Fix up parent reference for this
0258                  * child node.
0259                  */
0260                 child->ports[child->color] = node;
0261                 child->color = card->color;
0262                 child = fw_node(child->link.next);
0263                 break;
0264             }
0265         }
0266
0267         /*
0268          * Check that the node reports exactly one parent
0269          * port, except for the root, which of course should
0270          * have no parents.
0271          */
0272         if ((next_sid == end && parent_count != 0) ||
0273             (next_sid < end && parent_count != 1)) {
0274             fw_err(card, "parent port inconsistency for node %d: "
0275                    "parent_count=%d\n", phy_id, parent_count);
0276             return NULL;
0277         }
0278
0279         /* Pop the child nodes off the stack and push the new node. */
0280         __list_del(h->prev, &stack);
0281         list_add_tail(&node->link, &stack);
0282         stack_depth += 1 - child_port_count;
0283
0284         if (node->phy_speed == SCODE_BETA &&
0285             parent_count + child_port_count > 1)
0286             beta_repeaters_present = true;
0287
0288         /*
0289          * If PHYs report different gap counts, set an invalid count
0290          * which will force a gap count reconfiguration and a reset.
0291          */
0292         if (SELF_ID_GAP_COUNT(q) != gap_count)
0293             gap_count = 0;
0294
0295         update_hop_count(node);
0296
0297         sid = next_sid;
0298         phy_id++;
0299     }
0300
0301     card->root_node = node;
0302     card->irm_node = irm_node;
0303     card->gap_count = gap_count;
0304     card->beta_repeaters_present = beta_repeaters_present;
0305
0306     return local_node;
0307 }
0308
0309 typedef void (*fw_node_callback_t)(struct fw_card * card,
0310                    struct fw_node * node,
0311                    struct fw_node * parent);
0312
0313 static void for_each_fw_node(struct fw_card *card, struct fw_node *root,
0314                  fw_node_callback_t callback)
0315 {
0316     struct list_head list;
0317     struct fw_node *node, *next, *child, *parent;
0318     int i;
0319
0320     INIT_LIST_HEAD(&list);
0321
0322     fw_node_get(root);
0323     list_add_tail(&root->link, &list);
0324     parent = NULL;
0325     list_for_each_entry(node, &list, link) {
0326         node->color = card->color;
0327
0328         for (i = 0; i < node->port_count; i++) {
0329             child = node->ports[i];
0330             if (!child)
0331                 continue;
0332             if (child->color == card->color)
0333                 parent = child;
0334             else {
0335                 fw_node_get(child);
0336                 list_add_tail(&child->link, &list);
0337             }
0338         }
0339
0340         callback(card, node, parent);
0341     }
0342
0343     list_for_each_entry_safe(node, next, &list, link)
0344         fw_node_put(node);
0345 }
0346
0347 static void report_lost_node(struct fw_card *card,
0348                  struct fw_node *node, struct fw_node *parent)
0349 {
0350     fw_node_event(card, node, FW_NODE_DESTROYED);
0351     fw_node_put(node);
0352
0353     /* Topology has changed - reset bus manager retry counter */
0354     card->bm_retries = 0;
0355 }
0356
0357 static void report_found_node(struct fw_card *card,
0358                   struct fw_node *node, struct fw_node *parent)
0359 {
0360     int b_path = (node->phy_speed == SCODE_BETA);
0361
0362     if (parent != NULL) {
0363         /* min() macro doesn't work here with gcc 3.4 */
0364         node->max_speed = parent->max_speed < node->phy_speed ?
0365                     parent->max_speed : node->phy_speed;
0366         node->b_path = parent->b_path && b_path;
0367     } else {
0368         node->max_speed = node->phy_speed;
0369         node->b_path = b_path;
0370     }
0371
0372     fw_node_event(card, node, FW_NODE_CREATED);
0373
0374     /* Topology has changed - reset bus manager retry counter */
0375     card->bm_retries = 0;
0376 }
0377
0378 /* Must be called with card->lock held */
0379 void fw_destroy_nodes(struct fw_card *card)
0380 {
0381     card->color++;
0382     if (card->local_node != NULL)
0383         for_each_fw_node(card, card->local_node, report_lost_node);
0384     card->local_node = NULL;
0385 }
0386
0387 static void move_tree(struct fw_node *node0, struct fw_node *node1, int port)
0388 {
0389     struct fw_node *tree;
0390     int i;
0391
0392     tree = node1->ports[port];
0393     node0->ports[port] = tree;
0394     for (i = 0; i < tree->port_count; i++) {
0395         if (tree->ports[i] == node1) {
0396             tree->ports[i] = node0;
0397             break;
0398         }
0399     }
0400 }
0401
0402 /*
0403  * Compare the old topology tree for card with the new one specified by root.
0404  * Queue the nodes and mark them as either found, lost or updated.
0405  * Update the nodes in the card topology tree as we go.
0406  */
0407 static void update_tree(struct fw_card *card, struct fw_node *root)
0408 {
0409     struct list_head list0, list1;
0410     struct fw_node *node0, *node1, *next1;
0411     int i, event;
0412
0413     INIT_LIST_HEAD(&list0);
0414     list_add_tail(&card->local_node->link, &list0);
0415     INIT_LIST_HEAD(&list1);
0416     list_add_tail(&root->link, &list1);
0417
0418     node0 = fw_node(list0.next);
0419     node1 = fw_node(list1.next);
0420
0421     while (&node0->link != &list0) {
0422         WARN_ON(node0->port_count != node1->port_count);
0423
0424         if (node0->link_on && !node1->link_on)
0425             event = FW_NODE_LINK_OFF;
0426         else if (!node0->link_on && node1->link_on)
0427             event = FW_NODE_LINK_ON;
0428         else if (node1->initiated_reset && node1->link_on)
0429             event = FW_NODE_INITIATED_RESET;
0430         else
0431             event = FW_NODE_UPDATED;
0432
0433         node0->node_id = node1->node_id;
0434         node0->color = card->color;
0435         node0->link_on = node1->link_on;
0436         node0->initiated_reset = node1->initiated_reset;
0437         node0->max_hops = node1->max_hops;
0438         node1->color = card->color;
0439         fw_node_event(card, node0, event);
0440
0441         if (card->root_node == node1)
0442             card->root_node = node0;
0443         if (card->irm_node == node1)
0444             card->irm_node = node0;
0445
0446         for (i = 0; i < node0->port_count; i++) {
0447             if (node0->ports[i] && node1->ports[i]) {
0448                 /*
0449                  * This port didn't change, queue the
0450                  * connected node for further
0451                  * investigation.
0452                  */
0453                 if (node0->ports[i]->color == card->color)
0454                     continue;
0455                 list_add_tail(&node0->ports[i]->link, &list0);
0456                 list_add_tail(&node1->ports[i]->link, &list1);
0457             } else if (node0->ports[i]) {
0458                 /*
0459                  * The nodes connected here were
0460                  * unplugged; unref the lost nodes and
0461                  * queue FW_NODE_LOST callbacks for
0462                  * them.
0463                  */
0464
0465                 for_each_fw_node(card, node0->ports[i],
0466                          report_lost_node);
0467                 node0->ports[i] = NULL;
0468             } else if (node1->ports[i]) {
0469                 /*
0470                  * One or more node were connected to
0471                  * this port. Move the new nodes into
0472                  * the tree and queue FW_NODE_CREATED
0473                  * callbacks for them.
0474                  */
0475                 move_tree(node0, node1, i);
0476                 for_each_fw_node(card, node0->ports[i],
0477                          report_found_node);
0478             }
0479         }
0480
0481         node0 = fw_node(node0->link.next);
0482         next1 = fw_node(node1->link.next);
0483         fw_node_put(node1);
0484         node1 = next1;
0485     }
0486 }
0487
0488 static void update_topology_map(struct fw_card *card,
0489                 u32 *self_ids, int self_id_count)
0490 {
0491     int node_count = (card->root_node->node_id & 0x3f) + 1;
0492     __be32 *map = card->topology_map;
0493
0494     *map++ = cpu_to_be32((self_id_count + 2) << 16);
0495     *map++ = cpu_to_be32(be32_to_cpu(card->topology_map[1]) + 1);
0496     *map++ = cpu_to_be32((node_count << 16) | self_id_count);
0497
0498     while (self_id_count--)
0499         *map++ = cpu_to_be32p(self_ids++);
0500
0501     fw_compute_block_crc(card->topology_map);
0502 }
0503
0504 void fw_core_handle_bus_reset(struct fw_card *card, int node_id, int generation,
0505                   int self_id_count, u32 *self_ids, bool bm_abdicate)
0506 {
0507     struct fw_node *local_node;
0508     unsigned long flags;
0509
0510     spin_lock_irqsave(&card->lock, flags);
0511
0512     /*
0513      * If the selfID buffer is not the immediate successor of the
0514      * previously processed one, we cannot reliably compare the
0515      * old and new topologies.
0516      */
0517     if (!is_next_generation(generation, card->generation) &&
0518         card->local_node != NULL) {
0519         fw_destroy_nodes(card);
0520         card->bm_retries = 0;
0521     }
0522
0523     card->broadcast_channel_allocated = card->broadcast_channel_auto_allocated;
0524     card->node_id = node_id;
0525     /*
0526      * Update node_id before generation to prevent anybody from using
0527      * a stale node_id together with a current generation.
0528      */
0529     smp_wmb();
0530     card->generation = generation;
0531     card->reset_jiffies = get_jiffies_64();
0532     card->bm_node_id  = 0xffff;
0533     card->bm_abdicate = bm_abdicate;
0534     fw_schedule_bm_work(card, 0);
0535
0536     local_node = build_tree(card, self_ids, self_id_count);
0537
0538     update_topology_map(card, self_ids, self_id_count);
0539
0540     card->color++;
0541
0542     if (local_node == NULL) {
0543         fw_err(card, "topology build failed\n");
0544         /* FIXME: We need to issue a bus reset in this case. */
0545     } else if (card->local_node == NULL) {
0546         card->local_node = local_node;
0547         for_each_fw_node(card, local_node, report_found_node);
0548     } else {
0549         update_tree(card, local_node);
0550     }
0551
0552     spin_unlock_irqrestore(&card->lock, flags);
0553 }
0554 EXPORT_SYMBOL(fw_core_handle_bus_reset);