lib/group_cpus.c

Source file repositories/reference/linux-study-clean/lib/group_cpus.c

File Facts

System
Linux kernel
Corpus path
lib/group_cpus.c
Extension
.c
Size
15024 bytes
Lines
586
Domain
Kernel Services
Bucket
lib
Inferred role
Kernel Services: exported/initcall integration point
Status
integration implementation candidate

Why This File Exists

Shared kernel service surface used by multiple subsystems, including helpers, cryptography, virtualization support, and async I/O infrastructure.

Dependency Surface

Detected Declarations

Annotated Snippet

struct node_groups {
	unsigned id;

	union {
		unsigned ngroups;
		unsigned ncpus;
	};
};

static int ncpus_cmp_func(const void *l, const void *r)
{
	const struct node_groups *ln = l;
	const struct node_groups *rn = r;

	return ln->ncpus - rn->ncpus;
}

static void alloc_groups_to_nodes(unsigned int numgrps,
				  unsigned int numcpus,
				  struct node_groups *node_groups,
				  unsigned int num_nodes)
{
	unsigned int n, remaining_ncpus = numcpus;
	unsigned int  ngroups, ncpus;

	sort(node_groups, num_nodes, sizeof(node_groups[0]),
	     ncpus_cmp_func, NULL);

	/*
	 * Allocate groups for each node according to the ratio of this
	 * node's nr_cpus to remaining un-assigned ncpus. 'numgrps' is
	 * bigger than number of active numa nodes. Always start the
	 * allocation from the node with minimized nr_cpus.
	 *
	 * This way guarantees that each active node gets allocated at
	 * least one group, and the theory is simple: over-allocation
	 * is only done when this node is assigned by one group, so
	 * other nodes will be allocated >= 1 groups, since 'numgrps' is
	 * bigger than number of numa nodes.
	 *
	 * One perfect invariant is that number of allocated groups for
	 * each node is <= CPU count of this node:
	 *
	 * 1) suppose there are two nodes: A and B
	 * 	ncpu(X) is CPU count of node X
	 * 	grps(X) is the group count allocated to node X via this
	 * 	algorithm
	 *
	 * 	ncpu(A) <= ncpu(B)
	 * 	ncpu(A) + ncpu(B) = N
	 * 	grps(A) + grps(B) = G
	 *
	 * 	grps(A) = max(1, round_down(G * ncpu(A) / N))
	 * 	grps(B) = G - grps(A)
	 *
	 * 	both N and G are integer, and 2 <= G <= N, suppose
	 * 	G = N - delta, and 0 <= delta <= N - 2
	 *
	 * 2) obviously grps(A) <= ncpu(A) because:
	 *
	 * 	if grps(A) is 1, then grps(A) <= ncpu(A) given
	 * 	ncpu(A) >= 1
	 *
	 * 	otherwise,
	 * 		grps(A) <= G * ncpu(A) / N <= ncpu(A), given G <= N
	 *
	 * 3) prove how grps(B) <= ncpu(B):
	 *
	 * 	if round_down(G * ncpu(A) / N) == 0, vecs(B) won't be
	 * 	over-allocated, so grps(B) <= ncpu(B),
	 *
	 * 	otherwise:
	 *
	 * 	grps(A) =
	 * 		round_down(G * ncpu(A) / N) =
	 * 		round_down((N - delta) * ncpu(A) / N) =
	 * 		round_down((N * ncpu(A) - delta * ncpu(A)) / N)	 >=
	 * 		round_down((N * ncpu(A) - delta * N) / N)	 =
	 * 		cpu(A) - delta
	 *
	 * 	then:
	 *
	 * 	grps(A) - G >= ncpu(A) - delta - G
	 * 	=>
	 * 	G - grps(A) <= G + delta - ncpu(A)
	 * 	=>
	 * 	grps(B) <= N - ncpu(A)
	 * 	=>
	 * 	grps(B) <= cpu(B)
	 *

Annotation

Implementation Notes