//	负载均衡
//		在sched_domain中进行负载均衡，检查是否可以通过最繁忙的组中迁移一些进程到本cpu
//	函数参数：
//		this_cpu, 其上执行负载均衡的cpu
//		this_rq, 其上执行负载均衡的rq
//		sd, 其上执行负载均衡的sched domain
//		idle, this_cpu的状态
//			CPU_SCHED_IDLE，this_cpu空闲
//			CPU_NOT_IDLE，this_cpu不空闲
//		balance，sd中是否均衡
//	函数任务：
//		1.获取当前在线的cpu到本地
//		2.sched domain中寻找最忙的sched group
//		3.sched group中寻找最忙的cpu
//		4.最忙cpu就绪进程数>=2,从最忙cpu移动进程到this_cpu
//			4.1 关本cpu中断
//			4.2 获取this_cpu, 最忙cpu的rq的锁
//			4.3 移动进程到this_cpu
//			4.4 如果最忙cpu中所有进程均设置亲和性，移动进程失败
//				4.4.1 从掩码中清除最忙cpu，如果掩码不空，则重复步骤2进行负载均衡
//			4.5 如果移动进程成功
//				4.5.1 如果本cpu不是this_cpu，通过ipi唤醒this_cpu重调度
//				4.5.2 更新domain负载均衡失败次数计数器为 0
//		5.最忙cpu就绪进程数<=1,或从最忙cpu移动进程失败
//			5.1 检查是否可以进行主动负载均衡(负载均衡失败次数上限)
//				5.1.1 设置最忙cpu的active_balance标志
//				5.1.2 设置最忙cpu的push_cpu为this_cpu，表示是this_cpu向其发起了主动负载均衡
//				5.1.3 唤醒最忙cpu的migration_thread进程
//				5.1.4 更新domain负载均衡失败次数计数器为 上限-1
//		6.调整负载均衡时间间隔
//			6.1 如果没有发起主动负载均衡，下次尽早到期
//			6.2 否则，推迟下次负载均衡的时间
1.1 static int load_balance(int this_cpu, struct rq *this_rq,
			struct sched_domain *sd, enum cpu_idle_type idle,
			int *balance)
{
	int ld_moved, all_pinned = 0, active_balance = 0, sd_idle = 0;
	struct sched_group *group;
	unsigned long imbalance;
	struct rq *busiest;
	unsigned long flags;
	struct cpumask *cpus = __get_cpu_var(load_balance_tmpmask);
	//在线的cpu
	cpumask_copy(cpus, cpu_active_mask);
	//SD_SHARE_CPUPOWER，Domain members share cpu power
	//SD_POWERSAVINGS_BALANCE， Balance for power savings
	//cpu空闲，共享cpu power，power saving不进行balance
	if (idle != CPU_NOT_IDLE && sd->flags & SD_SHARE_CPUPOWER &&
	    !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
		sd_idle = 1;
redo:
	//在sched domain中寻找最忙的sched group
	group = find_busiest_group(sd, this_cpu, &imbalance, idle, &sd_idle,
				   cpus, balance);
	//sched group之间已经均衡
	if (*balance == 0)
		goto out_balanced;

	//在sched group中寻找最忙的rq
	busiest = find_busiest_queue(group, idle, imbalance, cpus);
	
	//rq之间已经均衡
	if (!busiest) {
		goto out_balanced;
	}

	ld_moved = 0;
	//最忙cpu可运行的进程>=2，从最忙cpu移动进程到本cpu
	if (busiest->nr_running > 1) {
		//关本cpu中断
		local_irq_save(flags);
		//同时获取本rq和最忙rq的锁
		double_rq_lock(this_rq, busiest);
		//从最忙rq移动进程到本rq
		ld_moved = move_tasks(this_rq, this_cpu, busiest, imbalance, sd, idle, &all_pinned);
		double_rq_unlock(this_rq, busiest);
		local_irq_restore(flags);
		//成功移动进程到this_cpu，但运行负载均衡的cpu非当前cpu，唤醒this_cpu，
		if (ld_moved && this_cpu != smp_processor_id())
			resched_cpu(this_cpu);
		//最忙cpu中的进程全部设置亲和性被绑定
		if (unlikely(all_pinned)) {
			//不在考虑此最忙的cpu
			cpumask_clear_cpu(cpu_of(busiest), cpus);
			//继续在sched domain中寻找忙碌的cpu
			if (!cpumask_empty(cpus))
				goto redo;
			//domain中的所有cpu都不能进行负载均衡，退出
			goto out_balanced;
		}
	}
	//最忙cpu可运行的进程<=1或者移动进程失败
	if (!ld_moved) {
		//sd->nr_balance_failed > sd->cache_nice_tries+2时，启动主动负载均衡
		//	主动负载均衡：
		//		最忙的cpu主动向空闲cpu搬移进程
		//		步骤：
		//			1.从lowest-level scheduling domain遍历每一个CPU GROUP中的cpu
		//				1.1 如果cpu idle，则向其迁移一个进程
		//				1.2 继续寻找idle的cpu
		//			2.当最忙的cpu遍历完该scheduling domain中的每一个CPU GROUP的每一个cpu
		//				2.1 向higher-level scheduling domain，直到其只剩两个进程或者遇到
		//					没有设置SD_LOAD_BALANCE的scheduling domain
		if (need_active_balance(sd, sd_idle, idle)) {
			//关中断，获取最忙cpu rq的锁
			raw_spin_lock_irqsave(&busiest->lock, flags);
			//this_cpu不在最忙cpu允许的域中
			if (!cpumask_test_cpu(this_cpu,
					      &busiest->curr->cpus_allowed)) {
				raw_spin_unlock_irqrestore(&busiest->lock,
							    flags);
				//等价于全部设置了亲和性
				all_pinned = 1;
				goto out_one_pinned;
			}
			//发起主动负载均衡
			if (!busiest->active_balance) {
				//设置最忙cpu的active_balance标志
				busiest->active_balance = 1;
				//向其发起主动负载均衡的cpu
				busiest->push_cpu = this_cpu;
				active_balance = 1;
			}
			raw_spin_unlock_irqrestdore(&busiest->lock, flags);
			//唤醒最忙cpu的migration_thread进程
			if (active_balance)
				wake_up_process(busiest->migration_thread);
			//重置负载均衡失败次数
			sd->nr_balance_failed = sd->cache_nice_tries+1;
		}
	}
	else
	{
		//成功进行了负载均衡，nr_balance_failed设置为0
		sd->nr_balance_failed = 0;
	}
		
	//调整负载均衡时间间隔
	if (likely(!active_balance)) 
	{
		//没有发起主动负载均衡，下次尽早到期
		sd->balance_interval = sd->min_interval;
	} else {
		//推迟下一次负载均衡的时间
		if (sd->balance_interval < sd->max_interval)
			sd->balance_interval *= 2;
	}

	if (!ld_moved && !sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
	    !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
		ld_moved = -1;

	goto out;

out_balanced:
	schedstat_inc(sd, lb_balanced[idle]);

	sd->nr_balance_failed = 0;

out_one_pinned:
	
	if ((all_pinned && sd->balance_interval < MAX_PINNED_INTERVAL) ||
			(sd->balance_interval < sd->max_interval))
		sd->balance_interval *= 2;

	if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
	    !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
		ld_moved = -1;
	else
		ld_moved = 0;
out:
	if (ld_moved)
		update_shares(sd);
	return ld_moved;
}