nfnetlink_queue -- why linear lookup ?

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



Hello,

In nfnetlink_queue.c, when receiving a verdict for a packet, its entry in the queue is looked up linearly:

  find_dequeue_entry(struct nfqnl_instance *queue, unsigned int id)
  {
    ...
    list_for_each_entry(i, &queue->queue_list, list) {
      if (i->id == id) {
        entry = i;
        break;
      }
    }
    ...
  }

As a result, in a situation of "highly asynchronous" verdicts, i.e. when we want some packets to linger in the queue for some time before reinjection, the mere existence of a large number of such "old packets" may incur a nonnegligible cost to the system.

So I'm wondering: why is the list implemented as a simple linked list instead of an array directly indexed by the id (like file descriptors) ?

Indeed, the list has a configured max size, the passed id can be bound-checked, discarded entries can simply hold a NULL, and id reuse is userspace's responsibility. So it looks like the array would yield constant-time lookup with no extra risk.

What am I missing ?

Thans in advance,

-Alex

_________________________________________________________________________________________________________________________

Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc
pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler
a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,
Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.

This message and its attachments may contain confidential or privileged information that may be protected by law;
they should not be distributed, used or copied without authorisation.
If you have received this email in error, please notify the sender and delete this message and its attachments.
As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.
Thank you.




[Index of Archives]     [Netfitler Users]     [Berkeley Packet Filter]     [LARTC]     [Bugtraq]     [Yosemite Forum]

  Powered by Linux