lkml.org 
[lkml]   [2004]   [Mar]   [13]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    SubjectARP does not scale
    Date
    ARP has hash table and garbage collection scalability limitations.

    Please find attached a patch for 2.4.24 (also works for 2.4.25) that allows
    you to choose the size of your ARP hash table. Simply choosing the ARP hash
    table size that suits your network can cut the ARP list search time by an
    order of magnitude. For example, the default hash table size is 32. My
    network has over 1000 nodes. If you assume the hash function spreads those
    evenly, then there are approximately 31 hash collisions per bucket.
    Increasing the hash table size to 512 cuts down the collisions to
    approximately 2 per bucket.

    Related to scalability is the ARP entry garbage collector. It is currently
    coded such that it runs at periodic intervals and processes all ARP entries
    in all hash table buckets all within one invocation. As the number of ARP
    entries becomes large, the amount of time spent processing all of the ARP
    entries also becomes large. At a certain point I think it will begin to cause
    significant jitter in packet delivery times. In an effort to smooth out the
    garbage collector impact I've recoded it to only process one hash bucket per
    invocation. The garbage collector resets its timer so that it processes all
    buckets at least once every 60 seconds.

    rtg

    <--SNIP-->

    diff -r -u --new-file linux-2.4.24/Documentation/Configure.help
    linux-2.4.24.arp/Documentation/Configure.help
    --- linux-2.4.24/Documentation/Configure.help 2004-03-12 07:34:37.000000000
    -0700
    +++ linux-2.4.24.arp/Documentation/Configure.help 2004-03-12
    09:07:01.000000000 -0700
    @@ -6921,6 +6921,13 @@

    If unsure, say N.

    +ARP hash table size power of 2
    +CONFIG_NEIGH_NUM_HASHBITS
    + This option defines the size of the ARP hash table for each protocol. The
    default size of 5
    + bits (32) is adequate for small LANs. Larger LANs may have enough ARP
    entries that there are
    + multiple hash table collisions. In that case, increasing the number of hash
    table entries
    + improves ARP entry access performance at the expense of some RAM.
    +
    Packet socket
    CONFIG_PACKET
    The Packet protocol is used by applications which communicate
    diff -r -u --new-file linux-2.4.24/include/net/neighbour.h
    linux-2.4.24.arp/include/net/neighbour.h
    --- linux-2.4.24/include/net/neighbour.h 2004-03-12 07:34:44.000000000 -0700
    +++ linux-2.4.24.arp/include/net/neighbour.h 2004-03-12 09:35:07.000000000
    -0700
    @@ -128,7 +128,7 @@
    u8 key[0];
    };

    -#define NEIGH_HASHMASK 0x1F
    +#define NEIGH_HASHMASK ((1<<CONFIG_NEIGH_NUM_HASHBITS)-1)
    #define PNEIGH_HASHMASK 0xF

    /*
    @@ -166,6 +166,7 @@
    struct tasklet_struct gc_task;
    struct neigh_statistics stats;
    struct neighbour *hash_buckets[NEIGH_HASHMASK+1];
    + int curr_hash_bucket;
    struct pneigh_entry *phash_buckets[PNEIGH_HASHMASK+1];
    };

    diff -r -u --new-file linux-2.4.24/net/Config.in
    linux-2.4.24.arp/net/Config.in
    --- linux-2.4.24/net/Config.in 2004-03-12 07:33:30.000000000 -0700
    +++ linux-2.4.24.arp/net/Config.in 2004-03-12 09:05:10.000000000 -0700
    @@ -8,6 +8,8 @@
    bool ' Packet socket: mmapped IO' CONFIG_PACKET_MMAP
    fi

    +int 'ARP hash table size power of 2' CONFIG_NEIGH_NUM_HASHBITS 5
    +
    tristate 'Netlink device emulation' CONFIG_NETLINK_DEV

    bool 'Network packet filtering (replaces ipchains)' CONFIG_NETFILTER
    diff -r -u --new-file linux-2.4.24/net/core/neighbour.c
    linux-2.4.24.arp/net/core/neighbour.c
    --- linux-2.4.24/net/core/neighbour.c 2004-03-12 07:33:13.000000000 -0700
    +++ linux-2.4.24.arp/net/core/neighbour.c 2004-03-12 09:36:35.000000000 -0700
    @@ -566,9 +566,8 @@
    static void SMP_TIMER_NAME(neigh_periodic_timer)(unsigned long arg)
    {
    struct neigh_table *tbl = (struct neigh_table*)arg;
    + struct neighbour *n, **np;
    unsigned long now = jiffies;
    - int i;
    -

    write_lock(&tbl->lock);

    @@ -583,46 +582,48 @@
    p->reachable_time = neigh_rand_reach_time(p->base_reachable_time);
    }

    - for (i=0; i <= NEIGH_HASHMASK; i++) {
    - struct neighbour *n, **np;
    + tbl->curr_hash_bucket &= NEIGH_HASHMASK;
    + np = &tbl->hash_buckets[tbl->curr_hash_bucket++];

    - np = &tbl->hash_buckets[i];
    - while ((n = *np) != NULL) {
    - unsigned state;
    -
    - write_lock(&n->lock);
    -
    - state = n->nud_state;
    - if (state&(NUD_PERMANENT|NUD_IN_TIMER)) {
    - write_unlock(&n->lock);
    - goto next_elt;
    - }
    + while ((n = *np) != NULL) {
    + unsigned state;

    - if ((long)(n->used - n->confirmed) < 0)
    - n->used = n->confirmed;
    + write_lock(&n->lock);

    - if (atomic_read(&n->refcnt) == 1 &&
    - (state == NUD_FAILED || now - n->used > n->parms->gc_staletime)) {
    - *np = n->next;
    - n->dead = 1;
    - write_unlock(&n->lock);
    - neigh_release(n);
    - continue;
    - }
    + state = n->nud_state;
    + if (state&(NUD_PERMANENT|NUD_IN_TIMER)) {
    + write_unlock(&n->lock);
    + goto next_elt;
    + }

    - if (n->nud_state&NUD_REACHABLE &&
    - now - n->confirmed > n->parms->reachable_time) {
    - n->nud_state = NUD_STALE;
    - neigh_suspect(n);
    - }
    + if ((long)(n->used - n->confirmed) < 0)
    + n->used = n->confirmed;
    +
    + if (atomic_read(&n->refcnt) == 1 &&
    + (state == NUD_FAILED || now - n->used > n->parms->gc_staletime)) {
    + *np = n->next;
    + n->dead = 1;
    write_unlock(&n->lock);
    + neigh_release(n);
    + continue;
    + }

    -next_elt:
    - np = &n->next;
    + if (n->nud_state&NUD_REACHABLE &&
    + now - n->confirmed > n->parms->reachable_time) {
    + n->nud_state = NUD_STALE;
    + neigh_suspect(n);
    }
    + write_unlock(&n->lock);
    +
    +next_elt:
    + np = &n->next;
    }

    - mod_timer(&tbl->gc_timer, now + tbl->gc_interval);
    + /*
    + * Cycle through all hash buckets every 60 seconds.
    + */
    + mod_timer(&tbl->gc_timer, now+((HZ*60)/(NEIGH_HASHMASK+1)));
    +
    write_unlock(&tbl->lock);
    }

    --
    Tim Gardner - timg@tpi.com
    www.tpi.com 406-443-5357


    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-03-22 14:01    [W:0.029 / U:1.868 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site