Changli Gao wrote:
> use idr instead of list to speed up packet lookup by id.
>
> The current implementations of nfnetlink_queue, ip_queue and ip6_queue
> are all use list to save the packets queued. If the verdicts aren't
> received in order, the lookup for the corresponding packets isn't
> efficient. As the ids is generated and maintained in kernel, we can use
> idr to speed up the lookup. The side effect of this patch is fixing the
> potential id overlap in nfnetlink_queue.
This doesn't compile:
net/netfilter/nfnetlink_queue.c:57: error: field 'idr' has incomplete type
net/netfilter/nfnetlink_queue.c: In function 'instance_create':
net/netfilter/nfnetlink_queue.c:112: error: implicit declaration of
function 'idr_init'
net/netfilter/nfnetlink_queue.c: In function 'instance_destroy_rcu':
net/netfilter/nfnetlink_queue.c:143: error: implicit declaration of
function 'idr_destroy'
net/netfilter/nfnetlink_queue.c: In function 'find_dequeue_entry':
net/netfilter/nfnetlink_queue.c:170: error: implicit declaration of
function 'idr_find'
net/netfilter/nfnetlink_queue.c:170: warning: assignment makes pointer
from integer without a cast
net/netfilter/nfnetlink_queue.c:172: error: implicit declaration of
function 'idr_remove'
net/netfilter/nfnetlink_queue.c: In function 'nfqnl_flush':
net/netfilter/nfnetlink_queue.c:188: error: implicit declaration of
function 'idr_get_next'
net/netfilter/nfnetlink_queue.c:188: warning: assignment makes pointer
from integer without a cast
net/netfilter/nfnetlink_queue.c: In function 'nfqnl_build_packet_message':
net/netfilter/nfnetlink_queue.c:253: error: implicit declaration of
function 'idr_pre_get'
net/netfilter/nfnetlink_queue.c:254: error: implicit declaration of
function 'idr_get_new'
I'm interested in how this affects performance for the vast majority
of users, which process messages in order. A simple hash table looks
like a better choice here since we know the maximum number of entries
in advance and also could have the user specify the desired hash size.
> @@ -223,6 +211,7 @@ nfqnl_build_packet_message(struct nfqnl_instance *queue,
> struct sk_buff *entskb = entry->skb;
> struct net_device *indev;
> struct net_device *outdev;
> + u32 id;
>
> size = NLMSG_SPACE(sizeof(struct nfgenmsg))
> + nla_total_size(sizeof(struct nfqnl_msg_packet_hdr))
> @@ -262,7 +251,11 @@ nfqnl_build_packet_message(struct nfqnl_instance *queue,
> break;
> }
>
> - entry->id = queue->id_sequence++;
> + if (!idr_pre_get(&queue->idr, GFP_ATOMIC) ||
> + idr_get_new(&queue->idr, entry, &id) != 0) {
> + spin_unlock_bh(&queue->lock);
> + return NULL;
> + }
>
> spin_unlock_bh(&queue->lock);
You probably shouldn't be making the entry visible before the message
is successfully built and sent.
>
> @@ -279,7 +272,7 @@ nfqnl_build_packet_message(struct nfqnl_instance *queue,
> nfmsg->version = NFNETLINK_V0;
> nfmsg->res_id = htons(queue->queue_num);
>
> - pmsg.packet_id = htonl(entry->id);
> + pmsg.packet_id = htonl(id);
> pmsg.hw_protocol = entskb->protocol;
> pmsg.hook = entry->hook;
>
> @@ -375,6 +368,7 @@ nfqnl_build_packet_message(struct nfqnl_instance *queue,
> }
>
> nlh->nlmsg_len = skb->tail - old_tail;
> + *pid = id;
> return skb;
>
> nlmsg_failure:
> @@ -383,6 +377,9 @@ nla_put_failure:
> kfree_skb(skb);
> if (net_ratelimit())
> printk(KERN_ERR "nf_queue: error creating packet message\n");
> + spin_lock_bh(&queue->lock);
> + idr_remove(&queue->idr, id);
> + spin_unlock_bh(&queue->lock);
> return NULL;
> }
>
> @@ -392,6 +389,7 @@ nfqnl_enqueue_packet(struct nf_queue_entry *entry, unsigned int queuenum)
> struct sk_buff *nskb;
> struct nfqnl_instance *queue;
> int err;
> + u32 id;
>
> /* rcu_read_lock()ed by nf_hook_slow() */
> queue = instance_lookup(queuenum);
> @@ -401,7 +399,7 @@ nfqnl_enqueue_packet(struct nf_queue_entry *entry, unsigned int queuenum)
> if (queue->copy_mode == NFQNL_COPY_NONE)
> goto err_out;
>
> - nskb = nfqnl_build_packet_message(queue, entry);
> + nskb = nfqnl_build_packet_message(queue, entry, &id);
> if (nskb == NULL)
> goto err_out;
>
> @@ -426,7 +424,7 @@ nfqnl_enqueue_packet(struct nf_queue_entry *entry, unsigned int queuenum)
> goto err_out_unlock;
> }
>
> - __enqueue_entry(queue, entry);
> + queue->queue_total++;
>
> spin_unlock_bh(&queue->lock);
> return 0;
> @@ -434,6 +432,7 @@ nfqnl_enqueue_packet(struct nf_queue_entry *entry, unsigned int queuenum)
> err_out_free_nskb:
> kfree_skb(nskb);
> err_out_unlock:
> + idr_remove(&queue->idr, id);
> spin_unlock_bh(&queue->lock);
> err_out:
> return -1;
> @@ -867,7 +866,7 @@ static int seq_show(struct seq_file *s, void *v)
> inst->peer_pid, inst->queue_total,
> inst->copy_mode, inst->copy_range,
> inst->queue_dropped, inst->queue_user_dropped,
> - inst->id_sequence, 1);
> + 0, 1);
> }
>
> static const struct seq_operations nfqnl_seq_ops = {
>
> --
> To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at http://vger.kernel.org/majordomo-info.html
>
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
