kernel: improve minor number allocation

2 files changed, 29 insertions, 11 deletions

diff --git a/kernel/kernel/filesystem/device_number_registry.cpp b/kernel/kernel/filesystem/device_number_registry.cpp
index 0292ff94..cced66e0 100644
--- a/kernel/kernel/filesystem/device_number_registry.cpp
+++ b/kernel/kernel/filesystem/device_number_registry.cpp
@@ -202,16 +202,7 @@ namespace kernel::filesystem
     {
       auto guard = kstd::lock_guard{m_lock};
 
-      auto next_minor = m_next_minor.find(driver);
-      auto minor = std::uint8_t{};
-      if (next_minor != m_next_minor.end())
-      {
-        minor = next_minor->second++;
-      }
-      else
-      {
-        m_next_minor.emplace(driver, std::uint8_t{1});
-      }
+      auto minor = allocate_minor(binding->posix_type, *driver_major);
 
       numbered = entry{
         .number = {.major = *driver_major, .minor = minor},
@@ -237,6 +228,32 @@ namespace kernel::filesystem
       }
     });
   }
+
+  auto device_number_registry::allocate_minor(file_type type, std::uint8_t major) const -> std::uint8_t
+  {
+    auto used = kstd::vector<std::uint8_t>{};
+    for (auto const & entry : m_entries)
+    {
+      if (entry.type == type && entry.number.major == major)
+      {
+        used.push_back(entry.number.minor);
+      }
+    }
+    std::ranges::sort(used);
+
+    auto candidate = std::uint8_t{};
+    for (auto minor : used)
+    {
+      if (minor != candidate)
+      {
+        break;
+      }
+      ++candidate;
+    }
+
+    return candidate;
+  }
+
 }  // namespace kernel::filesystem
 
 namespace kernel::tests::filesystem::device_number_registry
diff --git a/kernel/kernel/filesystem/device_number_registry.hpp b/kernel/kernel/filesystem/device_number_registry.hpp
index 43f30f72..2391f179 100644
--- a/kernel/kernel/filesystem/device_number_registry.hpp
+++ b/kernel/kernel/filesystem/device_number_registry.hpp
@@ -86,11 +86,12 @@ namespace kernel::filesystem
 
     auto try_number(kapi::capabilities::facet_id facet, kapi::devices::facet_registry::entry const & published) -> void;
 
+    auto allocate_minor(file_type type, std::uint8_t major) const -> std::uint8_t;
+
     mutable kapi::tracked_mutex m_lock{};
 
     kstd::observer_ptr<kapi::devices::facet_registry> m_facet_registry;
     mutable kstd::vector<entry> m_entries{};
-    kstd::flat_map<kapi::devices::driver const *, std::uint8_t> m_next_minor;
     kstd::vector<kstd::weak_ptr<device_number_registry_observer>> m_observers{};
   };