[数据结构与算法]CAN核心帧收发流程

数据结构

CAN数据接收链表dev_rcv_lists

CAN核心为每个CAN类型网络设备都关联一个该链表对象（表头为can_rx_dev_list），用于保存所有对该CAN网络设备数据感兴趣的接收者。

enum { RX_ERR, RX_ALL, RX_FIL, RX_INV, RX_EFF, RX_MAX };

struct dev_rcv_lists {
    struct hlist_node list; // 将本对象放入can_rx_dev_list中
    struct rcu_head rcu;

    struct net_device *dev; // 关联网络设备
    struct hlist_head rx[RX_MAX]; // 两个接收者链表
    struct hlist_head rx_sff[0x800];
    int remove_on_zero_entries; // 链表清理标记
    int entries;
};

CAN数据接收者receiver

struct receiver {
    struct hlist_node list;
    struct rcu_head rcu;

    canid_t can_id; // filter信息
    canid_t mask;

    unsigned long matches; // 统计有多少数据包匹配了该接收者
    // skb接收函数&参数
    void (*func)(struct sk_buff *, void *);
    void *data;

    char *ident; // 标识接收者的字符串
};

CAN帧结构

/* special address description flags for the CAN_ID */
#define CAN_EFF_FLAG 0x80000000U /* EFF/SFF is set in the MSB */
#define CAN_RTR_FLAG 0x40000000U /* remote transmission request */
#define CAN_ERR_FLAG 0x20000000U /* error frame */

/* valid bits in CAN ID for frame formats */
#define CAN_SFF_MASK 0x000007FFU /* standard frame format (SFF) */
#define CAN_EFF_MASK 0x1FFFFFFFU /* extended frame format (EFF) */
#define CAN_ERR_MASK 0x1FFFFFFFU /* omit EFF, RTR, ERR flags */

/*
 * Controller Area Network Identifier structure
 *
 * bit 0-28	: CAN identifier (11/29 bit)
 * bit 29	: error frame flag (0 = data frame, 1 = error frame)
 * bit 30	: remote transmission request flag (1 = rtr frame)
 * bit 31	: frame format flag (0 = standard 11 bit, 1 = extended 29 bit)
 */
// 低29bit对应CAN帧中的标识符字段，linux利用后3bit表示了其它帧信息
typedef __u32 canid_t;

/**
 * struct can_frame - basic CAN frame structure
 * @can_id:  the CAN ID of the frame and CAN_*_FLAG flags, see above.
 * @can_dlc: the data length field of the CAN frame
 * @data:    the CAN frame payload.
 */
struct can_frame {
    canid_t can_id;  /* 32 bit CAN_ID + EFF/RTR/ERR flags */
    __u8    can_dlc; /* data length code: 0 .. 8 */
    __u8    data[8] __attribute__((aligned(8)));
};

对于canid_t的使用主要是在接收过滤器设置和数据接收两个流程中，这里linux做的是比较混乱的，bit0~bit28没有疑问，对应的就是CAN帧中的标识符字段，但是高3bit的使用需要分情况梳理。

接收过滤器设置（can_id和mask两个参数）：

1. mask参数中这是bit29（CAN_ERR_FLAG）代表要监听错误帧；
2. can_id参数中设置bit29（CAN_INV_FILTER）代表匹配结果要取反；
3. mask的bit0~bit28都为0，表示不做过滤全匹配；

接收流程

接收者列表维护

CAN核心仅仅对接收到的CAN帧进行分发，分发过程就是围绕上面提到的can_rx_dev_list链表进行的。

在模块初始化时，CAN核心向网络设备管理层注册了notifier，对应的接收函数为can_notifier()。

/*
 * af_can notifier to create/remove CAN netdevice specific structs
 */
static int can_notifier(struct notifier_block *nb, unsigned long msg, void *data)
{
    struct net_device *dev = (struct net_device *)data;
    struct dev_rcv_lists *d;

    // 只处理CAN类型的网络设备事件
    if (!net_eq(dev_net(dev), &init_net))
        return NOTIFY_DONE;
    if (dev->type != ARPHRD_CAN)
        return NOTIFY_DONE;

    // 只处理网络设备注册和去注册事件
    switch (msg) {
    case NETDEV_REGISTER:
        // 为网络设备分配一个dev_rcv_lists对象，并将该链表加入接收列表can_rx_dev_list中
        /*
         * create new dev_rcv_lists for this device
         *
         * N.B. zeroing the struct is the correct initialization
         * for the embedded hlist_head structs.
         * Another list type, e.g. list_head, would require
         * explicit initialization.
         */
        d = kzalloc(sizeof(*d), GFP_KERNEL);
        if (!d) {
            printk(KERN_ERR
                    "can: allocation of receive list failed\n");
            return NOTIFY_DONE;
        }
        d->dev = dev; // 链表和网络设备进行了关联
        spin_lock(&can_rcvlists_lock);
        hlist_add_head_rcu(&d->list, &can_rx_dev_list);
        spin_unlock(&can_rcvlists_lock);
        break;
    case NETDEV_UNREGISTER:
        // 网络设备去注册时将其对应的dev_rcv_lists对象从can_rx_dev_list链表中移除
        spin_lock(&can_rcvlists_lock);
        d = find_dev_rcv_lists(dev);
        if (d) {
            if (d->entries) {
                d->remove_on_zero_entries = 1;
                d = NULL;
            } else
                hlist_del_rcu(&d->list);
        } else
            printk(KERN_ERR "can: notifier: receive list not "
                    "found for dev %s\n", dev->name);
        spin_unlock(&can_rcvlists_lock);
        if (d)
            call_rcu(&d->rcu, can_rx_delete_device);
        break;
    }
    return NOTIFY_DONE;
}

CAN核心为每个CAN类型的网络设备都维护了一个dev_rcv_lists链表对象。有了链表对象，需要向链表对象中注册接收者才能完成数据包的分发，注册接口为can_rx_register()，当然对应的也有can_rx_unregister()接口。

/**
 * can_rx_register - subscribe CAN frames from a specific interface
 * @dev: pointer to netdevice (NULL => subcribe from 'all' CAN devices list)
 * @can_id: CAN identifier (see description)
 * @mask: CAN mask (see description)
 * @func: callback function on filter match
 * @data: returned parameter for callback function
 * @ident: string for calling module indentification
 *
 * Description:
 *  Invokes the callback function with the received sk_buff and the given
 *  parameter 'data' on a matching receive filter. A filter matches, when
 *
 *          <received_can_id> & mask == can_id & mask
 *
 *  The filter can be inverted (CAN_INV_FILTER bit set in can_id) or it can
 *  filter for error frames (CAN_ERR_FLAG bit set in mask).
 *
 *  The provided pointer to the sk_buff is guaranteed to be valid as long as
 *  the callback function is running. The callback function must *not* free
 *  the given sk_buff while processing it's task. When the given sk_buff is
 *  needed after the end of the callback function it must be cloned inside
 *  the callback function with skb_clone().
 *
 * Return:
 *  0 on success
 *  -ENOMEM on missing cache mem to create subscription entry
 *  -ENODEV unknown device
 */
int can_rx_register(struct net_device *dev, canid_t can_id, canid_t mask,
    void (*func)(struct sk_buff *, void *), void *data, char *ident)
{
    struct receiver *r;
    struct hlist_head *rl;
    struct dev_rcv_lists *d;
    int err = 0;

    /* insert new receiver  (dev,canid,mask) -> (func,data) */
    // 分配receiver对象
    r = kmem_cache_alloc(rcv_cache, GFP_KERNEL);
    if (!r)
        return -ENOMEM;

    spin_lock(&can_rcvlists_lock);
    // 找到网络设备对应的dev_rcv_lists对象
    d = find_dev_rcv_lists(dev);
    if (d) {
        // 根据参数决定将接收者放入哪个接收者链表
        rl = find_rcv_list(&can_id, &mask, d);

        r->can_id  = can_id;
        r->mask    = mask;
        r->matches = 0;
        r->func    = func;
        r->data    = data;
        r->ident   = ident;

        // 将接收者加入链表
        hlist_add_head_rcu(&r->list, rl);
        d->entries++;

        can_pstats.rcv_entries++;
        if (can_pstats.rcv_entries_max < can_pstats.rcv_entries)
            can_pstats.rcv_entries_max = can_pstats.rcv_entries;
    } else {
        kmem_cache_free(rcv_cache, r);
        err = -ENODEV;
    }
    spin_unlock(&can_rcvlists_lock);
    return err;
}

find_rcv_list()

/**
 * find_rcv_list - determine optimal filterlist inside device filter struct
 * @can_id: pointer to CAN identifier of a given can_filter
 * @mask: pointer to CAN mask of a given can_filter
 * @d: pointer to the device filter struct
 *
 * Description:
 *  Returns the optimal filterlist to reduce the filter handling in the
 *  receive path. This function is called by service functions that need
 *  to register or unregister a can_filter in the filter lists.
 *
 *  A filter matches in general, when
 *
 *          <received_can_id> & mask == can_id & mask
 *
 *  so every bit set in the mask (even CAN_EFF_FLAG, CAN_RTR_FLAG) describe
 *  relevant bits for the filter.
 *
 *  The filter can be inverted (CAN_INV_FILTER bit set in can_id) or it can
 *  filter for error frames (CAN_ERR_FLAG bit set in mask). For error frames
 *  there is a special filterlist and a special rx path filter handling.
 *
 * Return:
 *  Pointer to optimal filterlist for the given can_id/mask pair.
 *  Constistency checked mask.
 *  Reduced can_id to have a preprocessed filter compare value.
 */
static struct hlist_head *find_rcv_list(canid_t *can_id, canid_t *mask,
					struct dev_rcv_lists *d)
{
    canid_t inv = *can_id & CAN_INV_FILTER; /* save flag before masking */

    // 调用者通过在mask中设置CAN_ERR_FLAG可以实现对错误帧的监听
    if (*mask & CAN_ERR_FLAG) {
        /* clear CAN_ERR_FLAG in filter entry */
        *mask &= CAN_ERR_MASK; // 最终在receiver->mask中保存的又去掉了CAN_ERR_FLAG
        return &d->rx[RX_ERR];
    }

    /* with cleared CAN_ERR_FLAG we have a simple mask/value filterpair */

#define CAN_EFF_RTR_FLAGS (CAN_EFF_FLAG | CAN_RTR_FLAG)

    // 校验mask和can_id的值
    /* ensure valid values in can_mask for 'SFF only' frame filtering */
    if ((*mask & CAN_EFF_FLAG) && !(*can_id & CAN_EFF_FLAG))
        *mask &= (CAN_SFF_MASK | CAN_EFF_RTR_FLAGS);
    /* reduce condition testing at receive time，保存的can_id已经是和mask相与的结果了 */
    *can_id &= *mask;

    // 将监听者放入取反匹配列表
    if (inv)
        return &d->rx[RX_INV];

    // mask的bit0~bit28都为0，那么放入全匹配列表
    if (!(*mask))
        return &d->rx[RX_ALL];

    /* extra filterlists for the subscription of a single non-RTR can_id */
    if (((*mask & CAN_EFF_RTR_FLAGS) == CAN_EFF_RTR_FLAGS) && !(*can_id & CAN_RTR_FLAG)) {
        if (*can_id & CAN_EFF_FLAG) {
            if (*mask == (CAN_EFF_MASK | CAN_EFF_RTR_FLAGS)) {
                /* RFC: a future use-case for hash-tables? */
                return &d->rx[RX_EFF];
            }
        } else {
            if (*mask == (CAN_SFF_MASK | CAN_EFF_RTR_FLAGS))
                return &d->rx_sff[*can_id];
        }
    }

    /* default: filter via can_id/can_mask */
    return &d->rx[RX_FIL];
}

CAN核心收到数据can_rcv()

在模块初始化时，CAN核心向网络设备接口层注册了数据包接收接口can_rcv()。can_rcv()就是根据网络设备找到其对应的dev_rcv_lists链表，然后根据匹配规则，将skb分发给接收者。

static struct packet_type can_packet __read_mostly = {
    .type = __constant_htons(ETH_P_CAN),
    .dev  = NULL,
    .func = can_rcv,
};

static int can_rcv(struct sk_buff *skb, struct net_device *dev,
    struct packet_type *pt, struct net_device *orig_dev)
{
    struct dev_rcv_lists *d;
    struct can_frame *cf = (struct can_frame *)skb->data;
    int matches;

    if (dev->type != ARPHRD_CAN || !net_eq(dev_net(dev), &init_net)) {
        kfree_skb(skb);
        return 0;
    }
    BUG_ON(skb->len != sizeof(struct can_frame) || cf->can_dlc > 8);

    /* update statistics */
    can_stats.rx_frames++;
    can_stats.rx_frames_delta++;

    rcu_read_lock();
    /* deliver the packet to sockets listening on all devices */
    matches = can_rcv_filter(&can_rx_alldev_list, skb);

    // 找到网络设备对象的dev_rcv_lists链表
    d = find_dev_rcv_lists(dev);
    if (d)
        matches += can_rcv_filter(d, skb);
    rcu_read_unlock();

    /* free the skbuff allocated by the netdevice driver */
    kfree_skb(skb);

    if (matches > 0) {
        can_stats.matches++;
        can_stats.matches_delta++;
    }
    return 0;
}

CAN核心分发接收数据: can_rcv_filter()

// 将数据包分发给接收者
static inline void deliver(struct sk_buff *skb, struct receiver *r)
{
    r->func(skb, r->data);
    r->matches++;
}

// 根据过滤规则分发数据
static int can_rcv_filter(struct dev_rcv_lists *d, struct sk_buff *skb)
{
    struct receiver *r;
    struct hlist_node *n;
    int matches = 0;
    struct can_frame *cf = (struct can_frame *)skb->data;
    canid_t can_id = cf->can_id;

    if (d->entries == 0)
        return 0;

    // 接收到1个错误帧，分发给对错误帧感兴趣的接收者
    if (can_id & CAN_ERR_FLAG) {
        /* check for error frame entries only */
        hlist_for_each_entry_rcu(r, n, &d->rx[RX_ERR], list) {
            if (can_id & r->mask) {
                deliver(skb, r);
                matches++;
            }
        }
        return matches;
    }

    // 将帧分发给未设置filter的接收者
    hlist_for_each_entry_rcu(r, n, &d->rx[RX_ALL], list) {
        deliver(skb, r);
        matches++;
    }

    // <received_can_id> & mask == can_id & mask
    hlist_for_each_entry_rcu(r, n, &d->rx[RX_FIL], list) {
        if ((can_id & r->mask) == r->can_id) {
            deliver(skb, r);
            matches++;
        }
    }

    // 取反过滤器: <received_can_id> & mask != can_id & mask
    hlist_for_each_entry_rcu(r, n, &d->rx[RX_INV], list) {
        if ((can_id & r->mask) != r->can_id) {
            deliver(skb, r);
            matches++;
        }
    }

    /* check filterlists for single non-RTR can_ids */
    if (can_id & CAN_RTR_FLAG)
        return matches;

    // 扩展帧和标准帧
    if (can_id & CAN_EFF_FLAG) {
        hlist_for_each_entry_rcu(r, n, &d->rx[RX_EFF], list) {
            if (r->can_id == can_id) {
                deliver(skb, r);
                matches++;
            }
        }
    } else {
        can_id &= CAN_SFF_MASK;
        hlist_for_each_entry_rcu(r, n, &d->rx_sff[can_id], list) {
            deliver(skb, r);
            matches++;
        }
    }
    return matches;
}

至此数据就交给了BCM等传输协议了。

发送流程

上层协议组织好CAN帧后，调用CAN核心的can_send()将数据包发送出去。

/**
 * can_send - transmit a CAN frame (optional with local loopback)
 * @skb: pointer to socket buffer with CAN frame in data section
 * @loop: loopback for listeners on local CAN sockets (recommended default!)
 *
 * Return:
 *  0 on success
 *  -ENETDOWN when the selected interface is down
 *  -ENOBUFS on full driver queue (see net_xmit_errno())
 *  -ENOMEM when local loopback failed at calling skb_clone()
 *  -EPERM when trying to send on a non-CAN interface
 *  -EINVAL when the skb->data does not contain a valid CAN frame
 */
int can_send(struct sk_buff *skb, int loop)
{
    struct sk_buff *newskb = NULL;
    struct can_frame *cf = (struct can_frame *)skb->data;
    int err;

    // 校验CAN帧长度
    if (skb->len != sizeof(struct can_frame) || cf->can_dlc > 8) {
        kfree_skb(skb);
        return -EINVAL;
    }
    // 校验出口网络设备必须是CAN类型网络设备
    if (skb->dev->type != ARPHRD_CAN) {
        kfree_skb(skb);
        return -EPERM;
    }
    // 网络设备已UP
    if (!(skb->dev->flags & IFF_UP)) {
        kfree_skb(skb);
        return -ENETDOWN;
    }

    // 设置数据包为CAN类型
    skb->protocol = htons(ETH_P_CAN);
    skb_reset_network_header(skb);
    skb_reset_transport_header(skb);

    if (loop) { // 发送者指示该数据包需要环回
        /* indication for the CAN driver: do loopback */
        skb->pkt_type = PACKET_LOOPBACK;
        /*
         * The reference to the originating sock may be required
         * by the receiving socket to check whether the frame is
         * its own. Example: can_raw sockopt CAN_RAW_RECV_OWN_MSGS
         * Therefore we have to ensure that skb->sk remains the
         * reference to the originating sock by restoring skb->sk
         * after each skb_clone() or skb_orphan() usage.
         */
        if (!(skb->dev->flags & IFF_ECHO)) {
            // 驱动不支持环回，这里软件来模拟：将skb复制一份，直接走netif_rx()接收流程
            newskb = skb_clone(skb, GFP_ATOMIC);
            if (!newskb) {
                kfree_skb(skb);
                return -ENOMEM;
            }
            newskb->sk = skb->sk;
            newskb->ip_summed = CHECKSUM_UNNECESSARY;
            newskb->pkt_type = PACKET_BROADCAST;
        }
    } else {
        /* indication for the CAN driver: no loopback required */
        skb->pkt_type = PACKET_HOST;
    }

    // 发送数据包给网络设备接口层
    err = dev_queue_xmit(skb);
    if (err > 0)
        err = net_xmit_errno(err);
    if (err) {
        if (newskb)
            kfree_skb(newskb);
        return err;
    }
    if (newskb)
        netif_rx(newskb);

    /* update statistics */
    can_stats.tx_frames++;
    can_stats.tx_frames_delta++;
    return 0;
}