1 // SPDX-License-Identifier: GPL-2.0
3  * padata.c - generic interface to process data streams in parallel
5  * See Documentation/core-api/padata.rst for more information.
47 static void padata_free_pd(struct parallel_data *pd);
50 static int padata_index_to_cpu(struct parallel_data *pd, int cpu_index)  in padata_index_to_cpu()  argument
54 	target_cpu = cpumask_first(pd->cpumask.pcpu);  in padata_index_to_cpu()
56 		target_cpu = cpumask_next(target_cpu, pd->cpumask.pcpu);  in padata_index_to_cpu()
61 static int padata_cpu_hash(struct parallel_data *pd, unsigned int seq_nr)  in padata_cpu_hash()  argument
67 	int cpu_index = seq_nr % cpumask_weight(pd->cpumask.pcpu);  in padata_cpu_hash()
69 	return padata_index_to_cpu(pd, cpu_index);  in padata_cpu_hash()
82 	list_del(&pw->pw_list);  in padata_work_alloc()
90 		INIT_WORK_ONSTACK(&pw->pw_work, work_fn);  in padata_work_init()
92 		INIT_WORK(&pw->pw_work, work_fn);  in padata_work_init()
93 	pw->pw_data = data;  in padata_work_init()
109 		list_add(&pw->pw_list, head);  in padata_work_alloc_mt()
119 	list_add(&pw->pw_list, &padata_free_works);  in padata_work_free()
131 		list_del(&cur->pw_list);  in padata_works_free()
141 	struct padata_priv *padata = pw->pw_data;  in padata_parallel_worker()
144 	padata->parallel(padata);  in padata_parallel_worker()
152  * padata_do_parallel - padata parallelization function
159  *          none found, returns -EINVAL.
170 	struct padata_instance *pinst = ps->pinst;  in padata_do_parallel()
172 	struct parallel_data *pd;  in padata_do_parallel()  local
177 	pd = rcu_dereference_bh(ps->pd);  in padata_do_parallel()
179 	err = -EINVAL;  in padata_do_parallel()
180 	if (!(pinst->flags & PADATA_INIT) || pinst->flags & PADATA_INVALID)  in padata_do_parallel()
183 	if (!cpumask_test_cpu(*cb_cpu, pd->cpumask.cbcpu)) {  in padata_do_parallel()
184 		if (!cpumask_weight(pd->cpumask.cbcpu))  in padata_do_parallel()
188 		cpu_index = *cb_cpu % cpumask_weight(pd->cpumask.cbcpu);  in padata_do_parallel()
190 		cpu = cpumask_first(pd->cpumask.cbcpu);  in padata_do_parallel()
192 			cpu = cpumask_next(cpu, pd->cpumask.cbcpu);  in padata_do_parallel()
197 	err =  -EBUSY;  in padata_do_parallel()
198 	if ((pinst->flags & PADATA_RESET))  in padata_do_parallel()
201 	refcount_inc(&pd->refcnt);  in padata_do_parallel()
202 	padata->pd = pd;  in padata_do_parallel()
203 	padata->cb_cpu = *cb_cpu;  in padata_do_parallel()
206 	padata->seq_nr = ++pd->seq_nr;  in padata_do_parallel()
214 		queue_work(pinst->parallel_wq, &pw->pw_work);  in padata_do_parallel()
217 		padata->parallel(padata);  in padata_do_parallel()
229  * padata_find_next - Find the next object that needs serialization.
238 static struct padata_priv *padata_find_next(struct parallel_data *pd,  in padata_find_next()  argument
243 	int cpu = pd->cpu;  in padata_find_next()
245 	reorder = per_cpu_ptr(pd->reorder_list, cpu);  in padata_find_next()
247 	spin_lock(&reorder->lock);  in padata_find_next()
248 	if (list_empty(&reorder->list)) {  in padata_find_next()
249 		spin_unlock(&reorder->lock);  in padata_find_next()
253 	padata = list_entry(reorder->list.next, struct padata_priv, list);  in padata_find_next()
259 	if (padata->seq_nr != pd->processed) {  in padata_find_next()
260 		spin_unlock(&reorder->lock);  in padata_find_next()
265 		list_del_init(&padata->list);  in padata_find_next()
266 		++pd->processed;  in padata_find_next()
267 		pd->cpu = cpumask_next_wrap(cpu, pd->cpumask.pcpu, -1, false);  in padata_find_next()
270 	spin_unlock(&reorder->lock);  in padata_find_next()
274 static void padata_reorder(struct parallel_data *pd)  in padata_reorder()  argument
276 	struct padata_instance *pinst = pd->ps->pinst;  in padata_reorder()
292 	if (!spin_trylock_bh(&pd->lock))  in padata_reorder()
296 		padata = padata_find_next(pd, true);  in padata_reorder()
306 		cb_cpu = padata->cb_cpu;  in padata_reorder()
307 		squeue = per_cpu_ptr(pd->squeue, cb_cpu);  in padata_reorder()
309 		spin_lock(&squeue->serial.lock);  in padata_reorder()
310 		list_add_tail(&padata->list, &squeue->serial.list);  in padata_reorder()
311 		spin_unlock(&squeue->serial.lock);  in padata_reorder()
313 		queue_work_on(cb_cpu, pinst->serial_wq, &squeue->work);  in padata_reorder()
316 	spin_unlock_bh(&pd->lock);  in padata_reorder()
322 	 * Ensure reorder queue is read after pd->lock is dropped so we see  in padata_reorder()
328 	reorder = per_cpu_ptr(pd->reorder_list, pd->cpu);  in padata_reorder()
329 	if (!list_empty(&reorder->list) && padata_find_next(pd, false))  in padata_reorder()
330 		queue_work(pinst->serial_wq, &pd->reorder_work);  in padata_reorder()
335 	struct parallel_data *pd;  in invoke_padata_reorder()  local
338 	pd = container_of(work, struct parallel_data, reorder_work);  in invoke_padata_reorder()
339 	padata_reorder(pd);  in invoke_padata_reorder()
346 	struct parallel_data *pd;  in padata_serial_worker()  local
352 	pd = squeue->pd;  in padata_serial_worker()
354 	spin_lock(&squeue->serial.lock);  in padata_serial_worker()
355 	list_replace_init(&squeue->serial.list, &local_list);  in padata_serial_worker()
356 	spin_unlock(&squeue->serial.lock);  in padata_serial_worker()
366 		list_del_init(&padata->list);  in padata_serial_worker()
368 		padata->serial(padata);  in padata_serial_worker()
373 	if (refcount_sub_and_test(cnt, &pd->refcnt))  in padata_serial_worker()
374 		padata_free_pd(pd);  in padata_serial_worker()
378  * padata_do_serial - padata serialization function
387 	struct parallel_data *pd = padata->pd;  in padata_do_serial()  local
388 	int hashed_cpu = padata_cpu_hash(pd, padata->seq_nr);  in padata_do_serial()
389 	struct padata_list *reorder = per_cpu_ptr(pd->reorder_list, hashed_cpu);  in padata_do_serial()
392 	spin_lock(&reorder->lock);  in padata_do_serial()
394 	list_for_each_entry_reverse(cur, &reorder->list, list)  in padata_do_serial()
395 		if (cur->seq_nr < padata->seq_nr)  in padata_do_serial()
397 	list_add(&padata->list, &cur->list);  in padata_do_serial()
398 	spin_unlock(&reorder->lock);  in padata_do_serial()
402 	 * with the trylock of pd->lock in padata_reorder.  Pairs with smp_mb  in padata_do_serial()
407 	padata_reorder(pd);  in padata_do_serial()
418 		return -ENOMEM;  in padata_setup_cpumasks()
420 	/* Restrict parallel_wq workers to pd->cpumask.pcpu. */  in padata_setup_cpumasks()
421 	cpumask_copy(attrs->cpumask, pinst->cpumask.pcpu);  in padata_setup_cpumasks()
422 	err = apply_workqueue_attrs(pinst->parallel_wq, attrs);  in padata_setup_cpumasks()
431 	struct padata_mt_job_state *ps = pw->pw_data;  in padata_mt_helper()
432 	struct padata_mt_job *job = ps->job;  in padata_mt_helper()
435 	spin_lock(&ps->lock);  in padata_mt_helper()
437 	while (job->size > 0) {  in padata_mt_helper()
440 		start = job->start;  in padata_mt_helper()
442 		size = roundup(start + 1, ps->chunk_size) - start;  in padata_mt_helper()
443 		size = min(size, job->size);  in padata_mt_helper()
446 		job->start = end;  in padata_mt_helper()
447 		job->size -= size;  in padata_mt_helper()
449 		spin_unlock(&ps->lock);  in padata_mt_helper()
450 		job->thread_fn(start, end, job->fn_arg);  in padata_mt_helper()
451 		spin_lock(&ps->lock);  in padata_mt_helper()
454 	++ps->nworks_fini;  in padata_mt_helper()
455 	done = (ps->nworks_fini == ps->nworks);  in padata_mt_helper()
456 	spin_unlock(&ps->lock);  in padata_mt_helper()
459 		complete(&ps->completion);  in padata_mt_helper()
463  * padata_do_multithreaded - run a multithreaded job
477 	if (job->size == 0)  in padata_do_multithreaded()
481 	nworks = max(job->size / job->min_chunk, 1ul);  in padata_do_multithreaded()
482 	nworks = min(nworks, job->max_threads);  in padata_do_multithreaded()
486 		job->thread_fn(job->start, job->start + job->size, job->fn_arg);  in padata_do_multithreaded()
502 	ps.chunk_size = job->size / (ps.nworks * load_balance_factor);  in padata_do_multithreaded()
503 	ps.chunk_size = max(ps.chunk_size, job->min_chunk);  in padata_do_multithreaded()
504 	ps.chunk_size = roundup(ps.chunk_size, job->align);  in padata_do_multithreaded()
507 		queue_work(system_unbound_wq, &pw->pw_work);  in padata_do_multithreaded()
522 	INIT_LIST_HEAD(&pd_list->list);  in __padata_list_init()
523 	spin_lock_init(&pd_list->lock);  in __padata_list_init()
527 static void padata_init_squeues(struct parallel_data *pd)  in padata_init_squeues()  argument
532 	for_each_cpu(cpu, pd->cpumask.cbcpu) {  in padata_init_squeues()
533 		squeue = per_cpu_ptr(pd->squeue, cpu);  in padata_init_squeues()
534 		squeue->pd = pd;  in padata_init_squeues()
535 		__padata_list_init(&squeue->serial);  in padata_init_squeues()
536 		INIT_WORK(&squeue->work, padata_serial_worker);  in padata_init_squeues()
540 /* Initialize per-CPU reorder lists */
541 static void padata_init_reorder_list(struct parallel_data *pd)  in padata_init_reorder_list()  argument
546 	for_each_cpu(cpu, pd->cpumask.pcpu) {  in padata_init_reorder_list()
547 		list = per_cpu_ptr(pd->reorder_list, cpu);  in padata_init_reorder_list()
555 	struct padata_instance *pinst = ps->pinst;  in padata_alloc_pd()
556 	struct parallel_data *pd;  in padata_alloc_pd()  local
558 	pd = kzalloc(sizeof(struct parallel_data), GFP_KERNEL);  in padata_alloc_pd()
559 	if (!pd)  in padata_alloc_pd()
562 	pd->reorder_list = alloc_percpu(struct padata_list);  in padata_alloc_pd()
563 	if (!pd->reorder_list)  in padata_alloc_pd()
566 	pd->squeue = alloc_percpu(struct padata_serial_queue);  in padata_alloc_pd()
567 	if (!pd->squeue)  in padata_alloc_pd()
570 	pd->ps = ps;  in padata_alloc_pd()
572 	if (!alloc_cpumask_var(&pd->cpumask.pcpu, GFP_KERNEL))  in padata_alloc_pd()
574 	if (!alloc_cpumask_var(&pd->cpumask.cbcpu, GFP_KERNEL))  in padata_alloc_pd()
577 	cpumask_and(pd->cpumask.pcpu, pinst->cpumask.pcpu, cpu_online_mask);  in padata_alloc_pd()
578 	cpumask_and(pd->cpumask.cbcpu, pinst->cpumask.cbcpu, cpu_online_mask);  in padata_alloc_pd()
580 	padata_init_reorder_list(pd);  in padata_alloc_pd()
581 	padata_init_squeues(pd);  in padata_alloc_pd()
582 	pd->seq_nr = -1;  in padata_alloc_pd()
583 	refcount_set(&pd->refcnt, 1);  in padata_alloc_pd()
584 	spin_lock_init(&pd->lock);  in padata_alloc_pd()
585 	pd->cpu = cpumask_first(pd->cpumask.pcpu);  in padata_alloc_pd()
586 	INIT_WORK(&pd->reorder_work, invoke_padata_reorder);  in padata_alloc_pd()
588 	return pd;  in padata_alloc_pd()
591 	free_cpumask_var(pd->cpumask.pcpu);  in padata_alloc_pd()
593 	free_percpu(pd->squeue);  in padata_alloc_pd()
595 	free_percpu(pd->reorder_list);  in padata_alloc_pd()
597 	kfree(pd);  in padata_alloc_pd()
602 static void padata_free_pd(struct parallel_data *pd)  in padata_free_pd()  argument
604 	free_cpumask_var(pd->cpumask.pcpu);  in padata_free_pd()
605 	free_cpumask_var(pd->cpumask.cbcpu);  in padata_free_pd()
606 	free_percpu(pd->reorder_list);  in padata_free_pd()
607 	free_percpu(pd->squeue);  in padata_free_pd()
608 	kfree(pd);  in padata_free_pd()
613 	pinst->flags |= PADATA_INIT;  in __padata_start()
618 	if (!(pinst->flags & PADATA_INIT))  in __padata_stop()
621 	pinst->flags &= ~PADATA_INIT;  in __padata_stop()
633 		return -ENOMEM;  in padata_replace_one()
635 	ps->opd = rcu_dereference_protected(ps->pd, 1);  in padata_replace_one()
636 	rcu_assign_pointer(ps->pd, pd_new);  in padata_replace_one()
646 	pinst->flags |= PADATA_RESET;  in padata_replace()
648 	list_for_each_entry(ps, &pinst->pslist, list) {  in padata_replace()
656 	list_for_each_entry_continue_reverse(ps, &pinst->pslist, list)  in padata_replace()
657 		if (refcount_dec_and_test(&ps->opd->refcnt))  in padata_replace()
658 			padata_free_pd(ps->opd);  in padata_replace()
660 	pinst->flags &= ~PADATA_RESET;  in padata_replace()
670 		pinst->flags |= PADATA_INVALID;  in padata_validate_cpumask()
674 	pinst->flags &= ~PADATA_INVALID;  in padata_validate_cpumask()
696 	cpumask_copy(pinst->cpumask.pcpu, pcpumask);  in __padata_set_cpumasks()
697 	cpumask_copy(pinst->cpumask.cbcpu, cbcpumask);  in __padata_set_cpumasks()
708  * padata_set_cpumask - Sets specified by @cpumask_type cpumask to the value
721 	int err = -EINVAL;  in padata_set_cpumask()
724 	mutex_lock(&pinst->lock);  in padata_set_cpumask()
728 		serial_mask = pinst->cpumask.cbcpu;  in padata_set_cpumask()
732 		parallel_mask = pinst->cpumask.pcpu;  in padata_set_cpumask()
742 	mutex_unlock(&pinst->lock);  in padata_set_cpumask()
758 		if (padata_validate_cpumask(pinst, pinst->cpumask.pcpu) &&  in __padata_add_cpu()
759 		    padata_validate_cpumask(pinst, pinst->cpumask.cbcpu))  in __padata_add_cpu()
771 		if (!padata_validate_cpumask(pinst, pinst->cpumask.pcpu) ||  in __padata_remove_cpu()
772 		    !padata_validate_cpumask(pinst, pinst->cpumask.cbcpu))  in __padata_remove_cpu()
783 	return cpumask_test_cpu(cpu, pinst->cpumask.pcpu) ||  in pinst_has_cpu()
784 		cpumask_test_cpu(cpu, pinst->cpumask.cbcpu);  in pinst_has_cpu()
787 static int padata_cpu_online(unsigned int cpu, struct hlist_node *node)  in padata_cpu_online()  argument
792 	pinst = hlist_entry_safe(node, struct padata_instance, cpu_online_node);  in padata_cpu_online()
796 	mutex_lock(&pinst->lock);  in padata_cpu_online()
798 	mutex_unlock(&pinst->lock);  in padata_cpu_online()
802 static int padata_cpu_dead(unsigned int cpu, struct hlist_node *node)  in padata_cpu_dead()  argument
807 	pinst = hlist_entry_safe(node, struct padata_instance, cpu_dead_node);  in padata_cpu_dead()
811 	mutex_lock(&pinst->lock);  in padata_cpu_dead()
813 	mutex_unlock(&pinst->lock);  in padata_cpu_dead()
824 					    &pinst->cpu_dead_node);  in __padata_free()
825 	cpuhp_state_remove_instance_nocalls(hp_online, &pinst->cpu_online_node);  in __padata_free()
828 	WARN_ON(!list_empty(&pinst->pslist));  in __padata_free()
830 	free_cpumask_var(pinst->cpumask.pcpu);  in __padata_free()
831 	free_cpumask_var(pinst->cpumask.cbcpu);  in __padata_free()
832 	destroy_workqueue(pinst->serial_wq);  in __padata_free()
833 	destroy_workqueue(pinst->parallel_wq);  in __padata_free()
861 	mutex_lock(&pinst->lock);  in show_cpumask()
862 	if (!strcmp(attr->name, "serial_cpumask"))  in show_cpumask()
863 		cpumask = pinst->cpumask.cbcpu;  in show_cpumask()
865 		cpumask = pinst->cpumask.pcpu;  in show_cpumask()
869 	mutex_unlock(&pinst->lock);  in show_cpumask()
870 	return len < PAGE_SIZE ? len : -EINVAL;  in show_cpumask()
882 		return -ENOMEM;  in store_cpumask()
889 	mask_type = !strcmp(attr->name, "serial_cpumask") ?  in store_cpumask()
912  * serial_cpumask   [RW] - cpumask for serial workers
913  * parallel_cpumask [RW] - cpumask for parallel workers
927 	ssize_t ret = -EIO;  in padata_sysfs_show()
931 	if (pentry->show)  in padata_sysfs_show()
932 		ret = pentry->show(pinst, attr, buf);  in padata_sysfs_show()
942 	ssize_t ret = -EIO;  in padata_sysfs_store()
946 	if (pentry->show)  in padata_sysfs_store()
947 		ret = pentry->store(pinst, attr, buf, count);  in padata_sysfs_store()
964  * padata_alloc - allocate and initialize a padata instance
977 	pinst->parallel_wq = alloc_workqueue("%s_parallel", WQ_UNBOUND, 0,  in padata_alloc()
979 	if (!pinst->parallel_wq)  in padata_alloc()
984 	pinst->serial_wq = alloc_workqueue("%s_serial", WQ_MEM_RECLAIM |  in padata_alloc()
986 	if (!pinst->serial_wq)  in padata_alloc()
989 	if (!alloc_cpumask_var(&pinst->cpumask.pcpu, GFP_KERNEL))  in padata_alloc()
991 	if (!alloc_cpumask_var(&pinst->cpumask.cbcpu, GFP_KERNEL)) {  in padata_alloc()
992 		free_cpumask_var(pinst->cpumask.pcpu);  in padata_alloc()
996 	INIT_LIST_HEAD(&pinst->pslist);  in padata_alloc()
998 	cpumask_copy(pinst->cpumask.pcpu, cpu_possible_mask);  in padata_alloc()
999 	cpumask_copy(pinst->cpumask.cbcpu, cpu_possible_mask);  in padata_alloc()
1006 	kobject_init(&pinst->kobj, &padata_attr_type);  in padata_alloc()
1007 	mutex_init(&pinst->lock);  in padata_alloc()
1011 						    &pinst->cpu_online_node);  in padata_alloc()
1013 						    &pinst->cpu_dead_node);  in padata_alloc()
1021 	free_cpumask_var(pinst->cpumask.pcpu);  in padata_alloc()
1022 	free_cpumask_var(pinst->cpumask.cbcpu);  in padata_alloc()
1024 	destroy_workqueue(pinst->serial_wq);  in padata_alloc()
1027 	destroy_workqueue(pinst->parallel_wq);  in padata_alloc()
1036  * padata_free - free a padata instance
1042 	kobject_put(&pinst->kobj);  in padata_free()
1047  * padata_alloc_shell - Allocate and initialize padata shell.
1055 	struct parallel_data *pd;  in padata_alloc_shell()  local
1062 	ps->pinst = pinst;  in padata_alloc_shell()
1065 	pd = padata_alloc_pd(ps);  in padata_alloc_shell()
1068 	if (!pd)  in padata_alloc_shell()
1071 	mutex_lock(&pinst->lock);  in padata_alloc_shell()
1072 	RCU_INIT_POINTER(ps->pd, pd);  in padata_alloc_shell()
1073 	list_add(&ps->list, &pinst->pslist);  in padata_alloc_shell()
1074 	mutex_unlock(&pinst->lock);  in padata_alloc_shell()
1086  * padata_free_shell - free a padata shell
1095 	mutex_lock(&ps->pinst->lock);  in padata_free_shell()
1096 	list_del(&ps->list);  in padata_free_shell()
1097 	padata_free_pd(rcu_dereference_protected(ps->pd, 1));  in padata_free_shell()
1098 	mutex_unlock(&ps->pinst->lock);  in padata_free_shell()