lkml.org 
[lkml]   [2006]   [Jan]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: RCU latency regression in 2.6.16-rc1
    On Mon, Jan 30, 2006 at 05:55:37AM +0100, Eric Dumazet wrote:
    > Paul E. McKenney a écrit :
    > >On Sat, Jan 28, 2006 at 08:52:02PM +0100, Eric Dumazet wrote:

    [ . . . ]

    > >>Some machines have millions of entries in their route cache.
    > >>
    > >>I suspect we cannot queue all them (or only hash heads as your previous
    > >>patch) by RCU. Latencies and/or OOM can occur.
    > >>
    > >>What can be done is :
    > >>
    > >>in rt_run_flush(), allocate a new empty hash table, and exchange the hash
    > >>tables.
    > >>
    > >>Then wait a quiescent/grace RCU period (may be the exact term is not this
    > >>one, sorry, I'm not RCU expert)
    > >>
    > >>Then free all the entries from the old hash table (direclty of course, no
    > >>need for RCU grace period), and free the hash table.
    > >>
    > >>As the hash table can be huge, we might need allocate it at boot time,
    > >>just in case a flush is needed (it usually is :) ). If we choose dynamic
    > >>allocation and this allocation fails, then fallback to what is done today.
    > >
    > >Interesting approach!
    > >
    > >If I remember correctly, the point of all of this is to perturb the hash
    > >function periodically in order to avoid DoS attacks. It will likely
    > >be necessary to avoid a big performance hit during the transition.
    > >One way of doing this, given your two-table scheme, would be to:
    > >
    > >o Allocate both tables at boot time, as you suggest above.
    > >
    > >o Keep the following additional state:
    > >
    > > o Pointer to the table that is the current table.
    > >
    > > o First valid index (fvl) into the current table -- all
    > > indexes below the fvl correspond to hash buckets that
    > > have been transferred into the non-current table.
    > > In the normal case where the tables are not being
    > > switched, fvl==-1.
    > >
    > > (To make the RCU searches work without requiring
    > > tons of explicit memory barriers, there needs to
    > > be a separate fvl for each of the tables.)
    > >
    > > o Parameters defining the hash functions for the current
    > > table and for the non-current table.
    > >
    > >o When it is time to switch tables, start removing the entries
    > > in hash bucket #fvl of the current table. Optionally put them
    > > into the non-current table (or just let them be added as they
    > > are needed. Only remove a limited number of entries (or,
    > > alternatively, stop removing them after a limited amount of
    > > time).
    > >
    > > When the current hash bucket has been completely emptied,
    > > increment fvl, and, if we have not already hit the limit,
    > > continue on the new hash bucket.
    > >
    > > When fvl runs off the end of the table, you are done with
    > > the switch. Update the pointer to reference the other
    > > table. Important -- do -not- start another switch until
    > > a grace period has elapsed!!! Otherwise, you will end
    > > up fatally confusing slow readers.
    > >
    > >o When searching, if the hash function gives a value less
    > > than fvl, search the non-current table.
    > >
    > > If the hash function gives a value equal to fvl, search
    > > the current table, and, if not found, search the non-current
    > > table.
    > >
    > > If the hash function gives a value greater than fvl, search
    > > only the current table. (It may also be necessary to search
    > > the non-current table to allow for races with fvl update.)
    > >
    > >Does this seem reasonable?
    > >
    > > Thanx, Paul
    >
    > Well, if as a bonus we are able to expand the size of the hash table, it
    > could be very very good : As of today, the boot time sizing of this hash
    > table is somewhat problematic.
    >
    > If the size is expanded by a 2 factor (or a power of too), can your
    > proposal works ?

    Yep!!!

    Add the following:

    o Add a size variable for each of the tables. It works best
    if the per-table state is stored with the table itself, for
    example:

    struct hashtbl {
    int size;
    int fvl;
    struct hash_param params;
    struct list_head buckets[0];
    };

    o When switching tables, allocate a new one of the desired size
    and free up the non-current one. (But remember to wait at least
    one grace period after the last switch before starting this!!!)

    o Compute hash parameters suitable for the new table size.

    o Continue as before.

    Note that you are not restricted to power-of-two expansion -- the
    hash parameters should handle any desired difference, and in fact
    handle contraction as well as expansion.

    Thanx, Paul
    -
    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: 2006-01-30 06:14    [W:2.352 / U:0.272 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site