[haiku-commits] BRANCH pdziepak-github.scheduler [4b44627] src/system/kernel src/system/kernel/scheduler headers/private/kernel
- From: pdziepak-github.scheduler <community@xxxxxxxxxxxx>
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Mon, 21 Oct 2013 01:45:33 +0200 (CEST)
added 2 changesets to branch 'refs/remotes/pdziepak-github/scheduler'
old head: 5cbf227236afa227e172a3ea7d5127a9ab0770dc
new head: 4b446279e6d85e37a909856a3a6d747170b22ed8
overview: https://github.com/pdziepak/Haiku/compare/5cbf227...4b44627
----------------------------------------------------------------------------
343c489: kernel: Create CPU topology tree
4b44627: scheduler_affine: Use CPU topology tree to create ID mappings
[ Pawel Dziepak <pdziepak@xxxxxxxxxxx> ]
----------------------------------------------------------------------------
4 files changed, 171 insertions(+), 61 deletions(-)
headers/private/kernel/cpu.h | 12 ++
src/system/kernel/cpu.cpp | 111 +++++++++++++++++++
src/system/kernel/main.cpp | 1 +
src/system/kernel/scheduler/scheduler_affine.cpp | 108 ++++++++----------
############################################################################
Commit: 343c4896892733387f1e1b1ed01f151107e7da5f
Author: Pawel Dziepak <pdziepak@xxxxxxxxxxx>
Date: Sun Oct 20 23:33:35 2013 UTC
kernel: Create CPU topology tree
----------------------------------------------------------------------------
diff --git a/headers/private/kernel/cpu.h b/headers/private/kernel/cpu.h
index e8fe6bc..d3cf0a8 100644
--- a/headers/private/kernel/cpu.h
+++ b/headers/private/kernel/cpu.h
@@ -39,6 +39,15 @@ typedef enum cpu_topology_level {
CPU_TOPOLOGY_LEVELS
} cpu_topology_level;
+typedef struct cpu_topology_node {
+ cpu_topology_level level;
+
+ int id;
+
+ cpu_topology_node** children;
+ int children_count;
+} cpu_topology_node;
+
/* CPU local data structure */
@@ -93,6 +102,9 @@ bigtime_t cpu_get_active_time(int32 cpu);
cpu_ent *get_cpu_struct(void);
extern inline cpu_ent *get_cpu_struct(void) { return
&gCPU[smp_get_current_cpu()]; }
+status_t cpu_build_topology_tree(void);
+cpu_topology_node* get_cpu_topology(void);
+
void _user_clear_caches(void *address, size_t length, uint32 flags);
bool _user_cpu_enabled(int32 cpu);
status_t _user_set_cpu_enabled(int32 cpu, bool enabled);
diff --git a/src/system/kernel/cpu.cpp b/src/system/kernel/cpu.cpp
index 1dfbc4d..36df9aa 100644
--- a/src/system/kernel/cpu.cpp
+++ b/src/system/kernel/cpu.cpp
@@ -21,7 +21,9 @@
/* global per-cpu structure */
cpu_ent gCPU[MAX_BOOT_CPUS];
+
uint32 gCPUCacheLevelCount;
+static cpu_topology_node sCPUTopology;
static spinlock sSetCpuLock;
@@ -88,6 +90,115 @@ clear_caches(void *address, size_t length, uint32 flags)
}
+static status_t
+cpu_create_topology_node(cpu_topology_node* node, int32* maxID, int32 id)
+{
+ cpu_topology_level level = static_cast<cpu_topology_level>(node->level
- 1);
+ ASSERT(level >= 0);
+
+ cpu_topology_node* newNode = new(std::nothrow) cpu_topology_node;
+ if (newNode == NULL)
+ return B_NO_MEMORY;
+ node->children[id] = newNode;
+
+ newNode->level = level;
+ if (level != CPU_TOPOLOGY_SMT) {
+ newNode->children_count = maxID[level - 1];
+ newNode->children
+ = new(std::nothrow) cpu_topology_node*[maxID[level -
1]];
+ if (newNode->children == NULL)
+ return B_NO_MEMORY;
+
+ memset(newNode->children, 0,
+ maxID[level - 1] * sizeof(cpu_topology_node*));
+ } else {
+ newNode->children_count = 0;
+ newNode->children = NULL;
+ }
+
+ return B_OK;
+}
+
+
+static void
+cpu_rebuild_topology_tree(cpu_topology_node* node, int32* lastID)
+{
+ if (node->children == NULL)
+ return;
+
+ int32 count = 0;
+ for (int32 i = 0; i < node->children_count; i++) {
+ if (node->children[i] == NULL)
+ continue;
+
+ if (count != i)
+ node->children[count] = node->children[i];
+
+ if (node->children[count]->level != CPU_TOPOLOGY_SMT)
+ node->children[count]->id =
lastID[node->children[count]->level]++;
+
+ cpu_rebuild_topology_tree(node->children[count], lastID);
+ count++;
+ }
+ node->children_count = count;
+}
+
+
+status_t
+cpu_build_topology_tree(void)
+{
+ sCPUTopology.level = CPU_TOPOLOGY_LEVELS;
+
+ int32 maxID[CPU_TOPOLOGY_LEVELS];
+ memset(&maxID, 0, sizeof(maxID));
+
+ const int32 kCPUCount = smp_get_num_cpus();
+ for (int32 i = 0; i < kCPUCount; i++) {
+ for (int32 j = 0; j < CPU_TOPOLOGY_LEVELS; j++)
+ maxID[j] = max_c(maxID[j], gCPU[i].topology_id[j]);
+ }
+
+ for (int32 j = 0; j < CPU_TOPOLOGY_LEVELS; j++)
+ maxID[j]++;
+
+ sCPUTopology.children_count = maxID[CPU_TOPOLOGY_LEVELS - 1];
+ sCPUTopology.children
+ = new(std::nothrow)
cpu_topology_node*[maxID[CPU_TOPOLOGY_LEVELS - 1]];
+ if (sCPUTopology.children == NULL)
+ return B_NO_MEMORY;
+ memset(sCPUTopology.children, 0,
+ maxID[CPU_TOPOLOGY_LEVELS - 1] * sizeof(cpu_topology_node*));
+
+ for (int32 i = 0; i < kCPUCount; i++) {
+ cpu_topology_node* node = &sCPUTopology;
+ for (int32 j = CPU_TOPOLOGY_LEVELS - 1; j >= 0; j--) {
+ int32 id = gCPU[i].topology_id[j];
+ if (node->children[id] == NULL) {
+ status_t result =
cpu_create_topology_node(node, maxID, id);
+ if (result != B_OK)
+ return result;
+ }
+
+ node = node->children[id];
+ }
+
+ ASSERT(node->level == CPU_TOPOLOGY_SMT);
+ node->id = i;
+ }
+
+ int32 lastID[CPU_TOPOLOGY_LEVELS];
+ memset(&lastID, 0, sizeof(lastID));
+ cpu_rebuild_topology_tree(&sCPUTopology, lastID);
+}
+
+
+cpu_topology_node*
+get_cpu_topology(void)
+{
+ return &sCPUTopology;
+}
+
+
// #pragma mark -
diff --git a/src/system/kernel/main.cpp b/src/system/kernel/main.cpp
index 938b3a6..9dedf47 100644
--- a/src/system/kernel/main.cpp
+++ b/src/system/kernel/main.cpp
@@ -165,6 +165,7 @@ _start(kernel_args *bootKernelArgs, int currentCPU)
TRACE("init SMP\n");
smp_init(&sKernelArgs);
+ cpu_build_topology_tree();
TRACE("init timer\n");
timer_init(&sKernelArgs);
TRACE("init real time clock\n");
############################################################################
Commit: 4b446279e6d85e37a909856a3a6d747170b22ed8
Author: Pawel Dziepak <pdziepak@xxxxxxxxxxx>
Date: Sun Oct 20 23:34:31 2013 UTC
scheduler_affine: Use CPU topology tree to create ID mappings
----------------------------------------------------------------------------
diff --git a/src/system/kernel/scheduler/scheduler_affine.cpp
b/src/system/kernel/scheduler/scheduler_affine.cpp
index c8cb8ea..4f4c1be 100644
--- a/src/system/kernel/scheduler/scheduler_affine.cpp
+++ b/src/system/kernel/scheduler/scheduler_affine.cpp
@@ -1108,12 +1108,34 @@ static scheduler_ops kAffineOps = {
// #pragma mark -
-status_t
-scheduler_affine_init()
+static void
+traverse_topology_tree(cpu_topology_node* node, int packageID, int coreID)
{
- int32 cpuCount = smp_get_num_cpus();
+ switch (node->level) {
+ case CPU_TOPOLOGY_SMT:
+ sCPUToCore[node->id] = coreID;
+ sCPUToPackage[node->id] = packageID;
+ return;
+
+ case CPU_TOPOLOGY_CORE:
+ coreID = node->id;
+ break;
+
+ case CPU_TOPOLOGY_PACKAGE:
+ packageID = node->id;
+ break;
+ }
+
+ for (int32 i = 0; i < node->children_count; i++)
+ traverse_topology_tree(node->children[i], packageID, coreID);
+}
+
+
+static status_t
+build_topology_mappings(int32& cpuCount, int32& coreCount, int32& packageCount)
+{
+ cpuCount = smp_get_num_cpus();
- // create logical processor to core and package mappings
sCPUToCore = new(std::nothrow) int32[cpuCount];
if (sCPUToCore == NULL)
return B_NO_MEMORY;
@@ -1124,73 +1146,39 @@ scheduler_affine_init()
return B_NO_MEMORY;
ArrayDeleter<int32> cpuToPackageDeleter(sCPUToPackage);
- int32 coreCount = 0;
+ coreCount = 0;
for (int32 i = 0; i < cpuCount; i++) {
if (gCPU[i].topology_id[CPU_TOPOLOGY_SMT] == 0)
- sCPUToCore[i] = coreCount++;
+ coreCount++;
}
- sRunQueueCount = coreCount;
- int32 packageCount = 0;
+ packageCount = 0;
for (int32 i = 0; i < cpuCount; i++) {
if (gCPU[i].topology_id[CPU_TOPOLOGY_SMT] == 0
&& gCPU[i].topology_id[CPU_TOPOLOGY_CORE] == 0) {
- sCPUToPackage[i] = packageCount++;
- }
- }
-
- // TODO: Nasty O(n^2), solutions with better complexity will require
- // creating helper data structures. This code is run only once, so it
- // probably won't be a problem until we support systems with large
- // number of processors.
- for (int32 i = 0; i < cpuCount; i++) {
- if (gCPU[i].topology_id[CPU_TOPOLOGY_SMT] == 0)
- continue;
-
- for (int32 j = 0; j < cpuCount; j++) {
- bool sameCore = true;
- for (int32 k = 0; k < CPU_TOPOLOGY_LEVELS && sameCore;
k++) {
- if (k == CPU_TOPOLOGY_SMT &&
gCPU[j].topology_id[k] == 0)
- continue;
- if (k == CPU_TOPOLOGY_SMT &&
gCPU[j].topology_id[k] != 0) {
- sameCore = false;
- continue;
- }
-
- if (gCPU[i].topology_id[k] !=
gCPU[j].topology_id[k])
- sameCore = false;
- }
-
- if (sameCore)
- sCPUToCore[i] = sCPUToCore[j];
+ packageCount++;
}
}
- // TODO: Another O(n^2), something has to be done with that... (i.e.
- // build a tree representing the topology and then use it to create
- // these mappings.
- for (int32 i = 0; i < cpuCount; i++) {
- if (gCPU[i].topology_id[CPU_TOPOLOGY_SMT] == 0
- && gCPU[i].topology_id[CPU_TOPOLOGY_CORE] == 0) {
- continue;
- }
+ cpu_topology_node* root = get_cpu_topology();
+ traverse_topology_tree(root, 0, 0);
- for (int32 j = 0; j < cpuCount; j++) {
- bool samePackage = true;
- for (int32 k = 0; k < CPU_TOPOLOGY_LEVELS &&
samePackage; k++) {
- if (k < CPU_TOPOLOGY_PACKAGE) {
- if (gCPU[j].topology_id[k] == 0)
- continue;
- samePackage = false;
- }
+ cpuToCoreDeleter.Detach();
+ cpuToPackageDeleter.Detach();
+ return B_OK;
+}
- samePackage = gCPU[i].topology_id[k] ==
gCPU[j].topology_id[k];
- }
- if (samePackage)
- sCPUToPackage[i] = sCPUToPackage[j];
- }
- }
+status_t
+scheduler_affine_init()
+{
+ // create logical processor to core and package mappings
+ int32 cpuCount, coreCount, packageCount;
+ status_t result = build_topology_mappings(cpuCount, coreCount,
+ packageCount);
+ if (result != B_OK)
+ return result;
+ sRunQueueCount = coreCount;
// create package heap and idle package stack
sPackageEntries = new(std::nothrow) PackageEntry[packageCount];
@@ -1202,7 +1190,7 @@ scheduler_affine_init()
if (sPackageUsageHeap == NULL)
return B_NO_MEMORY;
ObjectDeleter<AffinePackageHeap> packageHeapDeleter(sPackageUsageHeap);
- status_t result = sPackageUsageHeap->GrowHeap(packageCount);
+ result = sPackageUsageHeap->GrowHeap(packageCount);
if (result != B_OK)
return B_OK;
@@ -1309,7 +1297,5 @@ scheduler_affine_init()
packageEntriesDeleter.Detach();
packageHeapDeleter.Detach();
packageListDeleter.Detach();
- cpuToPackageDeleter.Detach();
- cpuToCoreDeleter.Detach();
return B_OK;
}
Other related posts:
- » [haiku-commits] BRANCH pdziepak-github.scheduler [4b44627] src/system/kernel src/system/kernel/scheduler headers/private/kernel - pdziepak-github . scheduler
