Introduce a macro to traverse LLC only inside a node. Give a node id, this macro can return the LLC cpumask in the order based on the LLC distance construct in the previous patch. Signed-off-by: Jianyong Wu --- kernel/sched/sched.h | 14 +++ kernel/sched/topology.c | 214 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 228 insertions(+) diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index 88b71e0f5ef0..38453a78c885 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -4124,6 +4124,20 @@ extern int sched_node_order_at(int cpu, int idx); ((node) = sched_node_order_at((cpu), __sn_idx)) >= 0; \ __sn_idx++) +extern int llc_node_count(int node); +extern const struct cpumask *llc_node_span_by_dist(int node, int index, int *llc_out); + +/* + * Walk each individual LLC belonging to NUMA node @node, nearest-first + * by the same-node-only llc_intra_node_distance() ordering instead of + * the plain ascending llc_id order of for_each_llc_in_node(). + */ +#define for_each_llc_node_span(node, span) \ + for (int __lns_idx = 0, __lns_nr = llc_node_count((node)); \ + __lns_idx < __lns_nr && \ + ((span) = llc_node_span_by_dist((node), __lns_idx, NULL)) != NULL; \ + __lns_idx++) + #endif void sched_domains_free_llc_id(int cpu); diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c index a47ed44f7b1f..eaaca6c9a805 100644 --- a/kernel/sched/topology.c +++ b/kernel/sched/topology.c @@ -6,6 +6,7 @@ #include #include #include +#include #include "sched.h" DEFINE_MUTEX(sched_domains_mutex); @@ -698,6 +699,7 @@ static int *sched_numa_node_distance; #ifdef CONFIG_SCHED_CACHE static int __rcu *llc_to_node_map; static void rebuild_llc_node_map(int size); +static void rebuild_llc_aggr_windows(int size); static int __rcu *sched_cache_node_dist_matrix; static int sched_cache_node_dist_size; static void rebuild_node_distance_matrix(int size); @@ -969,6 +971,24 @@ int llc_intra_node_distance(int llc1, int llc2, int node) return (rank1 + rank2) % k + 1; } +/* + * Number of LLCs in @node, sourced from llc_local_rank_topo + * (rebuild_llc_local_rank()). + */ +static int llc_local_rank_node_count(int node) +{ + struct llc_local_rank_topology *topo; + int count; + + rcu_read_lock(); + topo = rcu_dereference(llc_local_rank_topo); + count = (topo && node >= 0 && node < topo->nr_node) ? + topo->node_count[node] : 0; + rcu_read_unlock(); + + return count; +} + static void rebuild_llc_node_map(int size) { int *new_map, *old_map; @@ -1434,6 +1454,7 @@ static bool alloc_sd_llc(const struct cpumask *cpu_map, rebuild_node_distance_matrix(nr_node_ids); rebuild_node_order(nr_node_ids); rebuild_llc_local_rank(max_lid + 1); + rebuild_llc_aggr_windows(max_lid + 1); return true; err: for_each_cpu(i, cpu_map) { @@ -2585,6 +2606,199 @@ const struct cpumask *tl_mc_mask(struct sched_domain_topology_level *tl, int cpu #define llc_mask(cpu) arch_llc_mask(cpu) +#ifdef CONFIG_SCHED_CACHE +/* + * For each node we remember where its slice of the flattened per-node + * LLC-id list (node_llc[]) starts (used by the for_each_llc_in_node() + * iterator; per-node LLC counts come from llc_local_rank_topo, see + * llc_local_rank_node_count()). We also cache each LLC's own cpumask + * (llc_span[]). + */ +struct llc_aggr_topology { + int nr_llc; + int nr_node; + int *node_offset; /* [nr_node]: node's slice start in node_llc[] */ + int *node_llc; /* [nr_llc]: flattened per-node LLC ids, ascending */ + int *node_llc_by_dist; /* [nr_llc]: same slices as node_llc[], sorted by + * llc_intra_node_distance() from each node's + * lowest-id LLC instead of by id + */ + struct cpumask **llc_span; /* [nr_llc]: cpumask of each LLC */ +}; + +static struct llc_aggr_topology __rcu *llc_aggr_topo; + +static void free_llc_aggr_topology(struct llc_aggr_topology *topo) +{ + int i; + + if (!topo) + return; + + if (topo->llc_span) { + for (i = 0; i < topo->nr_llc; i++) + kfree(topo->llc_span[i]); + kfree(topo->llc_span); + } + kfree(topo->node_offset); + kfree(topo->node_llc); + kfree(topo->node_llc_by_dist); + kfree(topo); +} + +static void rebuild_llc_aggr_windows(int size) +{ + struct llc_aggr_topology *topo, *old; + int *seen; + u8 *seen_llc; + int cpu, llc, node, i; + + if (size <= 0) + return; + + topo = kzalloc_obj(*topo); + if (!topo) + return; + + topo->nr_llc = size; + topo->nr_node = nr_node_ids; + topo->node_offset = kcalloc(nr_node_ids, sizeof(int), GFP_KERNEL); + topo->node_llc = kcalloc(size, sizeof(int), GFP_KERNEL); + topo->node_llc_by_dist = kcalloc(size, sizeof(int), GFP_KERNEL); + topo->llc_span = kcalloc(size, sizeof(struct cpumask *), GFP_KERNEL); + seen = kcalloc(nr_node_ids, sizeof(int), GFP_KERNEL); + seen_llc = kcalloc(size, sizeof(*seen_llc), GFP_KERNEL); + if (!topo->node_offset || + !topo->node_llc || !topo->node_llc_by_dist || + !topo->llc_span || !seen || !seen_llc) { + kfree(seen); + kfree(seen_llc); + free_llc_aggr_topology(topo); + return; + } + + /* Cache each LLC's cpumask. */ + for_each_possible_cpu(cpu) { + llc = per_cpu(sd_llc_id, cpu); + if (llc < 0 || llc >= size || seen_llc[llc]) + continue; + seen_llc[llc] = 1; + + topo->llc_span[llc] = kzalloc(cpumask_size(), GFP_KERNEL); + if (!topo->llc_span[llc]) { + kfree(seen); + kfree(seen_llc); + free_llc_aggr_topology(topo); + return; + } + cpumask_copy(topo->llc_span[llc], llc_mask(cpu)); + } + + for (i = 1; i < nr_node_ids; i++) + topo->node_offset[i] = topo->node_offset[i - 1] + + llc_local_rank_node_count(i - 1); + + /* Fill node_llc[] (ascending llc_id per node). */ + memset(seen_llc, 0, size * sizeof(*seen_llc)); + for_each_possible_cpu(cpu) { + llc = per_cpu(sd_llc_id, cpu); + if (llc < 0 || llc >= size || seen_llc[llc]) + continue; + seen_llc[llc] = 1; + + node = llc_to_node(llc); + if (node < 0 || node >= nr_node_ids) + continue; + + topo->node_llc[topo->node_offset[node] + seen[node]] = llc; + seen[node]++; + } + kfree(seen); + kfree(seen_llc); + + /* + * fill node_llc_by_dist[], the same per-node slices as + * node_llc[] above but sorted ascending by + * llc_intra_node_distance() from that node's lowest-id LLC (the + * same one node_llc[]'s slice starts with) instead of by id. Used + * by for_each_llc_node_span() to walk a node's own LLCs + * nearest-first, unlike the plain id order of for_each_llc_in_node(). + * llc_intra_node_distance() guarantees no two same-node LLCs tie + * from a fixed anchor's point of view, so this sort is unambiguous. + */ + for (node = 0; node < nr_node_ids; node++) { + struct dist_key *cand; + int base = topo->node_offset[node]; + int cnt = llc_local_rank_node_count(node); + int anchor, k; + + if (cnt == 0) + continue; + + anchor = topo->node_llc[base]; + + cand = kmalloc_array(cnt, sizeof(*cand), GFP_KERNEL); + if (!cand) { + free_llc_aggr_topology(topo); + return; + } + + for (k = 0; k < cnt; k++) { + int llc_id = topo->node_llc[base + k]; + + cand[k].id = llc_id; + cand[k].dist = llc_intra_node_distance(anchor, llc_id, node); + } + + sort(cand, cnt, sizeof(*cand), dist_key_cmp, NULL); + + for (k = 0; k < cnt; k++) + topo->node_llc_by_dist[base + k] = cand[k].id; + kfree(cand); + } + + + old = rcu_dereference_protected(llc_aggr_topo, + lockdep_is_held(&sched_domains_mutex)); + rcu_assign_pointer(llc_aggr_topo, topo); + synchronize_rcu(); + free_llc_aggr_topology(old); +} + +/* Return the number of LLCs belonging to NUMA node @node. */ +int llc_node_count(int node) +{ + struct llc_aggr_topology *topo = rcu_dereference_all(llc_aggr_topo); + + if (!topo || node < 0 || node >= topo->nr_node) + return 0; + + return llc_local_rank_node_count(node); +} + +/* + * Return a pointer to the cached cpumask of the LLC at position @index + * within NUMA node @node, ordered ascending by + * llc_intra_node_distance() from that node's lowest-id LLC. + */ +const struct cpumask *llc_node_span_by_dist(int node, int index, int *llc_out) +{ + struct llc_aggr_topology *topo = rcu_dereference_all(llc_aggr_topo); + int llc; + + if (!topo || node < 0 || node >= topo->nr_node) + return NULL; + if (index < 0 || index >= llc_local_rank_node_count(node)) + return NULL; + + llc = topo->node_llc_by_dist[topo->node_offset[node] + index]; + if (llc_out) + *llc_out = llc; + + return topo->llc_span[llc]; +} +#endif /* CONFIG_SCHED_CACHE */ + const struct cpumask *tl_pkg_mask(struct sched_domain_topology_level *tl, int cpu) { return cpu_node_mask(cpu); -- 2.34.1