lkml.org 
[lkml]   [2004]   [May]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    SubjectRe: RCU scaling on large systems
    Jack Steiner wrote:

    >On Sat, May 01, 2004 at 02:17:04PM -0700, William Lee Irwin III wrote:
    >> On Sat, May 01, 2004 at 07:08:05AM -0500, Jack Steiner wrote:
    >> > On a 512p idle 2.6.5 system, each cpu spends ~6% of the time in the kernel
    >> > RCU code. The time is spent contending for shared cache lines.
    >>
    >> Would something like this help cacheline contention? This uses the
    >> per_cpu data areas to hold per-cpu booleans for needing switches.
    >> Untested/uncompiled.
    >
    >
    > [snip]
    >
    >We use 64MB granules. The percpu data structures on the individual nodes
    >are separated by addresses that differ by many GB. A scan of all percpu
    >data structures requires a TLB entry for each node. This is costly &
    >trashes the TLB. (Our max system size is currently 256 nodes).
    >
    >
    rcu_cpu_mask serves two purposes:
    - if a bit for a cpu is set, then the cpu must report quiescent states. Thus all cpus continuously poll their own bits.
    - If a cpu notices that it completed a quiescent state, it clears it's own bit, checks all bits and completes the grace period. This happens under a global spinlock.

    What about splitting that into two variables?
    A global counter could be used to inform the cpus that they should look for quiescent states. The cacheline would be mostly read-only, it shouldn't cause trashing.

    Attached is a patch - it boots uniprocessor i386. What do you think? It should remove the hotspot from scheduler_tick entirely.

    --
    Manfred

    // $Header$
    // Kernel Version:
    // VERSION = 2
    // PATCHLEVEL = 6
    // SUBLEVEL = 6
    // EXTRAVERSION = -mm4
    --- 2.6/kernel/rcupdate.c 2004-05-19 19:51:17.000000000 +0200
    +++ build-2.6/kernel/rcupdate.c 2004-05-20 13:22:59.000000000 +0200
    @@ -55,6 +55,7 @@
    static DEFINE_PER_CPU(struct tasklet_struct, rcu_tasklet) = {NULL};
    #define RCU_tasklet(cpu) (per_cpu(rcu_tasklet, cpu))

    +long rcu_global_grace_num ____cacheline_aligned_in_smp;
    /**
    * call_rcu - Queue an RCU update request.
    * @head: structure to be used for queueing the RCU updates.
    @@ -97,6 +98,23 @@
    }

    /*
    + * Grace period handling:
    + * The grace period handling consists out of two steps:
    + * - A new grace period is started.
    + * This is done by rcu_start_batch. The start is not broadcasted to
    + * all cpus, they must pick this up from rcu_global_grace_num. All cpus are
    + * recorded in the rcu_ctrlblk.rcu_cpu_mask bitmap.
    + * - All cpus must go through a quiescent state.
    + * Since the start of the grace period is not broadcasted, at least two
    + * calls to rcu_check_quiescent_state are required:
    + * The first call just notices that a new grace period is running. The
    + * following calls check if there was a quiescent state since the beginning
    + * of the grace period. If so, it updates rcu_ctrlblk.rcu_cpu_mask. If
    + * the bitmap is empty, then the grace period is completed.
    + * rcu_check_quiescent_state calls rcu_start_batch to start the next grace
    + * period.
    + */
    +/*
    * Register a new batch of callbacks, and start it up if there is currently no
    * active batch and the batch to be registered has not already occurred.
    * Caller must hold the rcu_ctrlblk lock.
    @@ -116,6 +134,8 @@
    active = nohz_cpu_mask;
    cpus_complement(active);
    cpus_and(rcu_ctrlblk.rcu_cpu_mask, cpu_online_map, active);
    + smp_wmb();
    + rcu_global_grace_num++;
    }

    /*
    @@ -127,18 +147,28 @@
    {
    int cpu = smp_processor_id();

    - if (!cpu_isset(cpu, rcu_ctrlblk.rcu_cpu_mask))
    + if (RCU_grace_num(cpu) != rcu_global_grace_num) {
    + /* new grace period: record qsctr value. */
    + BUG_ON(RCU_last_qsctr(cpu) != RCU_QSCTR_INVALID);
    + RCU_last_qsctr(cpu) = RCU_qsctr(cpu);
    + RCU_grace_num(cpu) = rcu_global_grace_num;
    + return;
    + }
    +
    + /* grace period already completed for this cpu?
    + * last_qsctr is checked instead of the actual bitmap to avoid
    + * cacheline trashing
    + */
    + if (RCU_last_qsctr(cpu) == RCU_QSCTR_INVALID) {
    + /* yes. Just leave. */
    return;
    + }

    /*
    * Races with local timer interrupt - in the worst case
    * we may miss one quiescent state of that CPU. That is
    * tolerable. So no need to disable interrupts.
    */
    - if (RCU_last_qsctr(cpu) == RCU_QSCTR_INVALID) {
    - RCU_last_qsctr(cpu) = RCU_qsctr(cpu);
    - return;
    - }
    if (RCU_qsctr(cpu) == RCU_last_qsctr(cpu))
    return;

    --- 2.6/include/linux/rcupdate.h 2004-05-19 19:42:16.000000000 +0200
    +++ build-2.6/include/linux/rcupdate.h 2004-05-20 12:46:02.000000000 +0200
    @@ -94,16 +94,19 @@
    long last_qsctr; /* value of qsctr at beginning */
    /* of rcu grace period */
    long batch; /* Batch # for current RCU batch */
    + long grace_num; /* grace period number */
    struct list_head nxtlist;
    struct list_head curlist;
    };

    DECLARE_PER_CPU(struct rcu_data, rcu_data);
    extern struct rcu_ctrlblk rcu_ctrlblk;
    +extern long rcu_global_grace_num;

    #define RCU_qsctr(cpu) (per_cpu(rcu_data, (cpu)).qsctr)
    #define RCU_last_qsctr(cpu) (per_cpu(rcu_data, (cpu)).last_qsctr)
    #define RCU_batch(cpu) (per_cpu(rcu_data, (cpu)).batch)
    +#define RCU_grace_num(cpu) (per_cpu(rcu_data, (cpu)).grace_num)
    #define RCU_nxtlist(cpu) (per_cpu(rcu_data, (cpu)).nxtlist)
    #define RCU_curlist(cpu) (per_cpu(rcu_data, (cpu)).curlist)

    @@ -115,7 +118,8 @@
    rcu_batch_before(RCU_batch(cpu), rcu_ctrlblk.curbatch)) ||
    (list_empty(&RCU_curlist(cpu)) &&
    !list_empty(&RCU_nxtlist(cpu))) ||
    - cpu_isset(cpu, rcu_ctrlblk.rcu_cpu_mask))
    + RCU_grace_num(cpu) != rcu_global_grace_num ||
    + RCU_last_qsctr(cpu) != RCU_QSCTR_INVALID)
    return 1;
    else
    return 0;
    \
     
     \ /
      Last update: 2005-03-22 14:03    [W:0.030 / U:0.952 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site