[REGRESSION] funny sched_domain build failure during resume

Hi,

On Wed, 14 May 2014 16:00:34 +0200
Peter Zijlstra <peterz@infradead.org> wrote:

> On Fri, May 09, 2014 at 12:04:55PM -0400, Tejun Heo wrote:
> > Hello, guys.
> > 
> > So, after resuming from suspend, I found my build jobs can not migrate
> > away from the CPU it started on and thus just making use of single
> > core.  It turns out the scheduler failed to build sched domains due to
> > order-3 allocation failure.
> > 

[snip]

> 
> Does something like the below help any? I noticed those things (cpudl
> and cpupri) had [NR_CPUS] arrays, which is always 'fun'.
>

Yeah, not nice :/.

> The below is a mostly no thought involved conversion of cpudl which
> boots, I'll also do cpupri and then actually stare at the algorithms to
> see if I didn't make any obvious fails.
> 
> Juri?
> 
> ---
>  kernel/sched/cpudeadline.c | 29 +++++++++++++++++++----------
>  kernel/sched/cpudeadline.h |  6 +++---
>  2 files changed, 22 insertions(+), 13 deletions(-)
> 
> diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
> index ab001b5d5048..c34ab09a790b 100644
> --- a/kernel/sched/cpudeadline.c
> +++ b/kernel/sched/cpudeadline.c
> @@ -13,6 +13,7 @@
>  
>  #include <linux/gfp.h>
>  #include <linux/kernel.h>
> +#include <linux/slab.h>
>  #include "cpudeadline.h"
>  
>  static inline int parent(int i)
> @@ -37,10 +38,7 @@ static inline int dl_time_before(u64 a, u64 b)
>  
>  static void cpudl_exchange(struct cpudl *cp, int a, int b)
>  {
> -	int cpu_a = cp->elements[a].cpu, cpu_b = cp->elements[b].cpu;
> -
>  	swap(cp->elements[a], cp->elements[b]);
> -	swap(cp->cpu_to_idx[cpu_a], cp->cpu_to_idx[cpu_b]);
>  }
>  

I think there is a problem here. Your patch "embeds" cpu_to_idx array
in elements array, but here the swap operates differently on the two.
Let me try to clarify with a simple example.

On a 4CPU system suppose we have this situation:

                      CPU 1
                      DL 50
                    /       \         
                   /         \
                  X           X
                 /
                /
               X

-- orig

elements[dl/cpu] | 50/1  |  0/0  |  0/0  |  0/0  |
                       ^
                        \
                         \
                          \
cpu_to_idx[idx]  |  -1   |   0   |  -1   |   -1  |

-- yours

elements[dl/cpu] | 50/1  |  0/0  |  0/0  |  0/0  |
                       ^
                        \
                         \
                          \
elements[idx]    |  -1   |   0   |  -1   |   -1  |

So since here all is fine.

But, what happens if I call cpudl_set(&cp, 2, 55, 1) ?

No surprises we insert the new element and then we try to bring it to
root (as it has max-dline). New situation is:

                      CPU 1
                      DL 50
                    /       \         
                   /         \
           ^    CPU2          X
           |    DL 55
                 /
                /
               X

-- orig

elements[dl/cpu] | 50/1  |  55/2  |  0/0  |  0/0  |
                       ^       ^
                        \       \
                         \       \
                          \       \
cpu_to_idx[idx]  |  -1   |   0   |  1   |   -1  |

-- yours

elements[dl/cpu] | 50/1  |  55/2  |  0/0  |  0/0  |
                       ^       ^
                        \       \
                         \       \
                          \       \
elements[idx]    |  -1   |   0   |  1   |   -1  |

Now, we do cpudl_exchange(&cp, 1, 0).

In orig we have

static void cpudl_exchange(struct cpudl *cp, int a, int b)
{
        int cpu_a = cp->elements[a].cpu, cpu_b = cp->elements[b].cpu;

        swap(cp->elements[a], cp->elements[b]);
        swap(cp->cpu_to_idx[cpu_a], cp->cpu_to_idx[cpu_b]);
}

note that here a = 1, b = 0, cpu_a = 2 and cpu_b = 1.

While in yours

static void cpudl_exchange(struct cpudl *cp, int a, int b)
{
        swap(cp->elements[a], cp->elements[b]);
}

so we end up with

-- orig

elements[dl/cpu] | 55/2  |  50/1  |  0/0  |  0/0  |
                     ^       ^
                     |       |
                     +-------|------+
                             |      |
cpu_to_idx[idx]  |  -1   |   1   |  0   |   -1  |

-- yours

elements[dl/cpu] | 55/2  |  50/1  |  0/0  |  0/0  |
                     ^        ^
                     |        |
                     |        +------+
                     |               |
elements[idx]    |   0   |   -1   |  1   |   -1  |

and this breaks how the heap works. For example, what if I want to
update CPU1 deadline? In orig I correctly get it at position 1 of
elements array. But with the patch CPU1's idx is IDX_INVALID.

Sorry for this long reply, but I had to convince also myself...

So, I think that having just one dynamic array is nicer and better, but
we still need to swap things separately. Something like (on top of
yours):

---

But, I don't know if this is too ugly and we better go with two arrays
(or a better solution, as this is the fastest thing I could come up
with :)).

In the meanwhile I'll test this more...

Thanks a lot,

- Juri

>  static void cpudl_heapify(struct cpudl *cp, int idx)
> @@ -140,7 +138,7 @@ void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid)
>  	WARN_ON(!cpu_present(cpu));
>  
>  	raw_spin_lock_irqsave(&cp->lock, flags);
> -	old_idx = cp->cpu_to_idx[cpu];
> +	old_idx = cp->elements[cpu].idx;
>  	if (!is_valid) {
>  		/* remove item */
>  		if (old_idx == IDX_INVALID) {
> @@ -155,8 +153,8 @@ void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid)
>  		cp->elements[old_idx].dl = cp->elements[cp->size - 1].dl;
>  		cp->elements[old_idx].cpu = new_cpu;
>  		cp->size--;
> -		cp->cpu_to_idx[new_cpu] = old_idx;
> -		cp->cpu_to_idx[cpu] = IDX_INVALID;
> +		cp->elements[new_cpu].idx = old_idx;
> +		cp->elements[cpu].idx = IDX_INVALID;
>  		while (old_idx > 0 && dl_time_before(
>  				cp->elements[parent(old_idx)].dl,
>  				cp->elements[old_idx].dl)) {
> @@ -173,7 +171,7 @@ void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid)
>  		cp->size++;
>  		cp->elements[cp->size - 1].dl = 0;
>  		cp->elements[cp->size - 1].cpu = cpu;
> -		cp->cpu_to_idx[cpu] = cp->size - 1;
> +		cp->elements[cpu].idx = cp->size - 1;
>  		cpudl_change_key(cp, cp->size - 1, dl);
>  		cpumask_clear_cpu(cpu, cp->free_cpus);
>  	} else {
> @@ -195,10 +193,21 @@ int cpudl_init(struct cpudl *cp)
>  	memset(cp, 0, sizeof(*cp));
>  	raw_spin_lock_init(&cp->lock);
>  	cp->size = 0;
> -	for (i = 0; i < NR_CPUS; i++)
> -		cp->cpu_to_idx[i] = IDX_INVALID;
> -	if (!alloc_cpumask_var(&cp->free_cpus, GFP_KERNEL))
> +
> +	cp->elements = kcalloc(num_possible_cpus(),
> +			       sizeof(struct cpudl_item),
> +			       GFP_KERNEL);
> +	if (!cp->elements)
> +		return -ENOMEM;
> +
> +	if (!alloc_cpumask_var(&cp->free_cpus, GFP_KERNEL)) {
> +		kfree(cp->elements);
>  		return -ENOMEM;
> +	}
> +
> +	for_each_possible_cpu(i)
> +		cp->elements[i].idx = IDX_INVALID;
> +
>  	cpumask_setall(cp->free_cpus);
>  
>  	return 0;
> diff --git a/kernel/sched/cpudeadline.h b/kernel/sched/cpudeadline.h
> index a202789a412c..538c9796ad4a 100644
> --- a/kernel/sched/cpudeadline.h
> +++ b/kernel/sched/cpudeadline.h
> @@ -5,17 +5,17 @@
>  
>  #define IDX_INVALID     -1
>  
> -struct array_item {
> +struct cpudl_item {
>  	u64 dl;
>  	int cpu;
> +	int idx;
>  };
>  
>  struct cpudl {
>  	raw_spinlock_t lock;
>  	int size;
> -	int cpu_to_idx[NR_CPUS];
> -	struct array_item elements[NR_CPUS];
>  	cpumask_var_t free_cpus;
> +	struct cpudl_item *elements;
>  };
>  
>  
--
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/

[REGRESSION] funny sched_domain build failure during resume

Commit Message

Comments

Patch