diff options
Diffstat (limited to 'lib/ktl')
50 files changed, 1836 insertions, 0 deletions
diff --git a/lib/ktl/LICENSE b/lib/ktl/LICENSE new file mode 100644 index 0000000..8580f02 --- /dev/null +++ b/lib/ktl/LICENSE @@ -0,0 +1,21 @@ +Copyright 2016 The Fuchsia Authors +Copyright (c) 2008-2015 Travis Geiselbrecht + +Permission is hereby granted, free of charge, to any person obtaining +a copy of this software and associated documentation files +(the "Software"), to deal in the Software without restriction, +including without limitation the rights to use, copy, modify, merge, +publish, distribute, sublicense, and/or sell copies of the Software, +and to permit persons to whom the Software is furnished to do so, +subject to the following conditions: + +The above copyright notice and this permission notice shall be +included in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. diff --git a/lib/ktl/README.lume b/lib/ktl/README.lume new file mode 100644 index 0000000..7e7c8a4 --- /dev/null +++ b/lib/ktl/README.lume @@ -0,0 +1,8 @@ +KTL configuration overlay imported from Zircon + +Source: zircon/kernel/lib/ktl +Fuchsia revision: f8d670ab4bbb71bfb4d569893ba12fbb8a83bacd + +The complete KTL header overlay and its two implementation files, popcount.cc +and stub-new.cc, are imported. The KTL target is built together with the +Zircon kernel libc header layer and the version-matched libc++ snapshot. diff --git a/lib/ktl/README.md b/lib/ktl/README.md new file mode 100644 index 0000000..667c678 --- /dev/null +++ b/lib/ktl/README.md @@ -0,0 +1,36 @@ +# Kernel Template Library + +The Kernel Template Library is a curated subset of the C++ standard library API +using the `ktl` namespace rather than the `std` namespace. When a specific +interface is deemed useful, safe, and appropriate for use in the kernel, it can +be added here. No `std` APIs are ever used directly in the kernel, only `ktl`. + +The API is a strict subset of the standard C++ library API aside from the +namespace. The header file names are mostly directly mapped as well: + + <foo> -> <ktl/foo.h> + +There can be exceptions. For example, <memory> is a very broad collection of +APIs and the ktl subset is more focused. So instead of <ktl/memory.h> there +are specific headers for the standard APIs from <memory> that are included, such +as <ktl/unique_ptr.h> for `ktl::unique_ptr` (`std::unique_ptr` in <memory>). + +The implementation here simply leverages the libc++ implementation and defines +`using` aliases in the `ktl` namespace. It's expected that ktl will only ever +provide "header only" APIs. + +## ktl enforcement + +The [`<ktl/enforce.h>`](include/ktl/enforce.h) header file should be used in +most `.cc` files (but not `.h`) files meant only for the kernel environment. +That is, in `.cc` files that use the `<ktl/*.h>` headers or use kernel-only +headers that use them. + +This file must appear last in the `#include` list and `clang-format` will +arrange that automatically. + +After this `#include` any use of the `std` identifier in C++ code will cause a +compile-time error. When such errors are encountered, the kernel code should +be checked for use of C++ standard library headers (with no `.h` in the name, +like `<memory>, etc.) that should be replaced with `<ktl/*.h>` headers and for +`std::` names that should be replaced with `ktl::` names. diff --git a/lib/ktl/include-after/errno.h b/lib/ktl/include-after/errno.h new file mode 100644 index 0000000..52edc9c --- /dev/null +++ b/lib/ktl/include-after/errno.h @@ -0,0 +1,13 @@ +// Copyright 2020 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_ERRNO_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_ERRNO_H_ + +// The kernel doesn't want this file but some libc++ headers we need +// wind up including it. + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_ERRNO_H_ diff --git a/lib/ktl/include-after/wchar.h b/lib/ktl/include-after/wchar.h new file mode 100644 index 0000000..41d11ae --- /dev/null +++ b/lib/ktl/include-after/wchar.h @@ -0,0 +1,30 @@ +// Copyright 2018 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_AFTER_WCHAR_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_AFTER_WCHAR_H_ + +#include <stddef.h> + +// The kernel doesn't want this file but some libc++ headers we need wind up +// including it and they need these declarations. +// +// **NOTE** This file is include-after because libc++ headers get it via +// #include_next so as to get the "system" <wchar.h> rather than libc++'s +// own wrapper. + +typedef struct { +} mbstate_t; + +typedef unsigned int wint_t; +#define WEOF (~wint_t{0}) + +// <string_view> refers to these in code that's never actually used in ktl. +wchar_t* wmemcpy(wchar_t* __restrict, const wchar_t* __restrict, size_t); +wchar_t* wmemmove(wchar_t*, const wchar_t*, size_t); +wchar_t* wmemset(wchar_t*, wchar_t, size_t); + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_AFTER_WCHAR_H_ diff --git a/lib/ktl/include/__chrono/system_clock.h b/lib/ktl/include/__chrono/system_clock.h new file mode 100644 index 0000000..5d39243 --- /dev/null +++ b/lib/ktl/include/__chrono/system_clock.h @@ -0,0 +1,15 @@ +// Copyright 2023 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE___CHRONO_SYSTEM_CLOCK_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE___CHRONO_SYSTEM_CLOCK_H_ + +// libc++'s <atomic> includes this file via various internal headers. +// The declarations it provides aren't needed for the kernel and rely +// on other things stubbed out by the kernel. So this placeholder file +// just prevents compiling the libc++ code that doesn't work. + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE___CHRONO_SYSTEM_CLOCK_H_ diff --git a/lib/ktl/include/__config b/lib/ktl/include/__config new file mode 100644 index 0000000..e04573e --- /dev/null +++ b/lib/ktl/include/__config @@ -0,0 +1,53 @@ +// Copyright 2022 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE___CONFIG_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE___CONFIG_ + +// The libc++ internal header <__config> unconditionally responds to some +// predefines set in the EFI environment. So this header wraps it and then +// undoes the damage that our __config_site header can't prevent. + +#include_next <__config> + +#undef _LIBCPP_WIN32API +#undef _LIBCPP_MSVCRT_LIKE +#undef _LIBCPP_MSVCRT +#undef _LIBCPP_HAS_OPEN_WITH_WCHAR + +// This prevents libc++ from doing fallback to spin locks and the like for +// cases where is_always_lock_free is not true. In the kernel, we don't want +// any behind-the-scenes help like that, we want to get link errors from +// libcalls if atomics can't be lowered to real hardware instructions. +#undef _LIBCPP_ATOMIC_ONLY_USE_BUILTINS + +// These are used by <__configuration/availability.h> to decide when headers +// should expect things to be defined in the library. For the kernel, there is +// no library and so everything must be defined in headers. +#undef _LIBCPP_INTRODUCED_IN_LLVM_21 +#define _LIBCPP_INTRODUCED_IN_LLVM_21 0 +#undef _LIBCPP_INTRODUCED_IN_LLVM_20 +#define _LIBCPP_INTRODUCED_IN_LLVM_20 0 +#undef _LIBCPP_INTRODUCED_IN_LLVM_19 +#define _LIBCPP_INTRODUCED_IN_LLVM_19 0 +#undef _LIBCPP_INTRODUCED_IN_LLVM_18 +#define _LIBCPP_INTRODUCED_IN_LLVM_18 0 +#undef _LIBCPP_INTRODUCED_IN_LLVM_16 +#define _LIBCPP_INTRODUCED_IN_LLVM_16 0 +#undef _LIBCPP_INTRODUCED_IN_LLVM_15 +#define _LIBCPP_INTRODUCED_IN_LLVM_15 0 +#undef _LIBCPP_INTRODUCED_IN_LLVM_14 +#define _LIBCPP_INTRODUCED_IN_LLVM_14 0 +#undef _LIBCPP_INTRODUCED_IN_LLVM_12 +#define _LIBCPP_INTRODUCED_IN_LLVM_12 0 +#undef _LIBCPP_INTRODUCED_IN_LLVM_11 +#define _LIBCPP_INTRODUCED_IN_LLVM_11 0 +#undef _LIBCPP_INTRODUCED_IN_LLVM_9 +#define _LIBCPP_INTRODUCED_IN_LLVM_9 0 +#undef _LIBCPP_INTRODUCED_IN_LLVM_4 +#define _LIBCPP_INTRODUCED_IN_LLVM_4 0 + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE___CONFIG_ diff --git a/lib/ktl/include/__config_site b/lib/ktl/include/__config_site new file mode 100644 index 0000000..4d2236b --- /dev/null +++ b/lib/ktl/include/__config_site @@ -0,0 +1,81 @@ +// Copyright 2021 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE___CONFIG_SITE_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE___CONFIG_SITE_ + +// The libc++ internal header <__config> does #include <__config_site> to get +// definitions that vary by operating system, machine, or configuration. The +// toolchain's libc++ installation provides include/$triple/.../__config_site +// files for each $cpu-fuchsia appropriate for normal userland. But the ktl +// abuse of libc++ is different from public userland libc++, so provide special +// kernel-appropriate definitions here. This file will be in the include path +// ahead of any toolchain-supplied header. Also, some special bare-metal build +// environments such as phys32 or efi that reuse ktl and kernel libc code may +// use settings that cause the compiler to change the $triple it injects into +// the include path to one for which no runtimes are built and so there is no +// __config_site file to be found at all. + +// These two are what <__config_site> for Fuchsia userland defines. +#define _LIBCPP_ABI_VERSION 2 +#define _LIBCPP_HAS_NO_VENDOR_AVAILABILITY_ANNOTATIONS 1 + +// This has to be defined to some `__*` string but what doesn't really matter. +#define _LIBCPP_ABI_NAMESPACE __ktl + +// When compiling in the UEFI environment, the predefines look like Windows +// but there is no Windows runtime environment to use. +#define _LIBCPP_NO_VCRUNTIME 1 + +// This tells the headers not to use `extern template` declarations that +// expect specific instantiations/specializations to come from the libc++ +// library rather than the headers. In the kernel, only the headers are +// ever going to be available. +#define _LIBCPP_DISABLE_EXTERN_TEMPLATE 1 + +// This tells <atomic> not to use threading APIs. +#define _LIBCPP_HAS_NO_PLATFORM_WAIT 1 + +// This tells <atomic> et al to use <__external_threading> instead +// of expecting either POSIX or C11 threading APIs. +#define _LIBCPP_HAS_THREAD_API_EXTERNAL 1 +#define _LIBCPP_HAS_THREAD_LIBRARY_EXTERNAL 1 + +// <__config> requires that these be set if _LIBCPP_HAS_THREAD_API_EXTERNAL is. +#define _LIBCPP_HAS_THREADS 1 +#define _LIBCPP_HAS_MONOTONIC_CLOCK 1 + +// This tells <new> not to use `aligned_alloc` from <stdlib.h>. +#define _LIBCPP_HAS_NO_C11_ALIGNED_ALLOC 1 + +// This tells various headers to be strict about what includes what. +#define _LIBCPP_REMOVE_TRANSITIVE_INCLUDES 1 + +// This tells libc++ not to expect full locale APIs in some places. +#define _LIBCPP_HAS_NO_LOCALIZATION 1 + +// This is unfortunately required even though the kernel does not use wide +// characters. +#define _LIBCPP_HAS_WIDE_CHARACTERS 1 + +// This tells pstl headers to use serial algorithms and not try to +// do any multithreading. +#define _LIBCPP_PSTL_CPU_BACKEND_SERIAL 1 + +// This will probably never be used in code that ktl actually uses. +// But define it for completeness. +#define _LIBCPP_INSTRUMENTED_WITH_ASAN __has_feature(address_sanitizer) + +// TODO(https://fxbug.dev/42082322): make the hardening mode selectable through build +// configurations. +// This sets the default to tell libc++ to not enable assertions to prevent +// undefined behavior, but may be overridden if _LIBCPP_HARDENING_MODE is +// defined elsewhere. +#define _LIBCPP_HARDENING_MODE_DEFAULT _LIBCPP_HARDENING_MODE_NONE + +#define _LIBCPP_ASSERTION_SEMANTIC_DEFAULT _LIBCPP_ASSERTION_SEMANTIC_HARDENING_DEPENDENT + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE___CONFIG_SITE_ diff --git a/lib/ktl/include/__configuration/platform.h b/lib/ktl/include/__configuration/platform.h new file mode 100644 index 0000000..b15e1e0 --- /dev/null +++ b/lib/ktl/include/__configuration/platform.h @@ -0,0 +1,23 @@ +// Copyright 2025 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE___CONFIGURATION_PLATFORM_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE___CONFIGURATION_PLATFORM_H_ + +// Other libc++ headers use <__configuration/platform.h> but libc++'s +// <__configuration/platform.h> does not yet recognize the `__PE_COFF__` +// predefine. Until we support this new predefine upstream, +// we must define _LIBCPP_OBJECT_FORMAT_COFF for UEFI targets here. +// TODO(https://fxbug.dev/435771251) -- Support `__PE_COFF__` predefine +// upstream. + +#if defined(__PE_COFF__) +#define _LIBCPP_OBJECT_FORMAT_COFF 2 // Tell libc++ this is PE-COFF. +#endif // __PE_COFF__ + +#include_next <__configuration/platform.h> + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE___CONFIGURATION_PLATFORM_H_ diff --git a/lib/ktl/include/__external_threading b/lib/ktl/include/__external_threading new file mode 100644 index 0000000..9cec903 --- /dev/null +++ b/lib/ktl/include/__external_threading @@ -0,0 +1,35 @@ +// Copyright 2020 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE___EXTERNAL_THREADING +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE___EXTERNAL_THREADING + +// libc++'s <atomic> includes this file via <__threading_support>. It needs +// these types and functions declared, but only for use in interfaces that +// aren't supported in the kernel, so stub declarations are all they need. + +_LIBCPP_BEGIN_NAMESPACE_STD + +struct __libcpp_timespec_t { + long int tv_sec, tv_nsec; +}; + +using __libcpp_thread_id = int; + +bool __libcpp_thread_id_equal(__libcpp_thread_id, __libcpp_thread_id); +bool __libcpp_thread_id_less(__libcpp_thread_id, __libcpp_thread_id); +__libcpp_thread_id __libcpp_thread_get_current_id(); + +void __libcpp_thread_sleep_for(chrono::nanoseconds); +void __libcpp_thread_yield(); + +// This macro is used unconditionally in <__threading_support> but defined +// there only conditionally on when <__external_threading> is not used. +#define _LIBCPP_THREAD_ABI_VISIBILITY inline _LIBCPP_INLINE_VISIBILITY + +_LIBCPP_END_NAMESPACE_STD + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE___EXTERNAL_THREADING diff --git a/lib/ktl/include/climits b/lib/ktl/include/climits new file mode 100644 index 0000000..86e537d --- /dev/null +++ b/lib/ktl/include/climits @@ -0,0 +1,15 @@ +// Copyright 2022 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#pragma once + +// Other libc++ headers use <climits> but libc++'s <climits> complains if it +// thinks <limits.h> is not its own wrapper, which we do not need. We always +// get the kernel's <limits.h> before the libc++ with the way the include paths +// are set up, which is necessary because of other headers where preempting +// libc++'s header is unavoidable for the kernel environment. + +#include <limits.h> diff --git a/lib/ktl/include/cmath b/lib/ktl/include/cmath new file mode 100644 index 0000000..13b8e6b --- /dev/null +++ b/lib/ktl/include/cmath @@ -0,0 +1,53 @@ +// Copyright 2021 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_CMATH_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_CMATH_ + +// The kernel doesn't want this file but some libc++ headers we need +// wind up including it. They don't actually most of the math +// declarations except under #if conditions that aren't true. + +#include <__config> +#include <type_traits> + +_LIBCPP_BEGIN_NAMESPACE_STD + +// These are used in templates that won't ever be instantiated in kernel code. + +template <typename T> +constexpr bool isinf(T&& x) { + static_assert(!is_same_v<T, T>, "must not be instantiated in kernel code"); + return false; +} + +template <typename T> +constexpr bool isnan(T&& x) { + static_assert(!is_same_v<T, T>, "must not be instantiated in kernel code"); + return false; +} + +template <typename T> +constexpr bool signbit(T&& x) { + static_assert(!is_same_v<T, T>, "must not be instantiated in kernel code"); + return false; +} + +template <typename T> +constexpr T frexp(T&& x, int* exponent) { + static_assert(!is_same_v<T, T>, "must not be instantiated in kernel code"); + return x; +} + +template <typename T> +constexpr auto ceil(T&& x) { + static_assert(!is_same_v<T, T>, "must not be instantiated in kernel code"); + return x; +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_CMATH_ diff --git a/lib/ktl/include/cstdint b/lib/ktl/include/cstdint new file mode 100644 index 0000000..0ab922c --- /dev/null +++ b/lib/ktl/include/cstdint @@ -0,0 +1,18 @@ +// Copyright 2022 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#pragma once + +// Other libc++ headers use <cstdint> but libc++'s <cstdint> complains if it +// thinks <stdint.h> is not its own wrapper, so we define _LIBCPP_STDINT_H. We +// always get the real <stdint.h> before the libc++ with the way the include +// paths are set up, which is necessary because of other headers where +// preempting libc++'s header is unavoidable for the kernel environment. + +#include <stdint.h> + +#define _LIBCPP_STDINT_H +#include_next <cstdint> diff --git a/lib/ktl/include/cstdio b/lib/ktl/include/cstdio new file mode 100644 index 0000000..349e736 --- /dev/null +++ b/lib/ktl/include/cstdio @@ -0,0 +1,21 @@ +// Copyright 2020 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_CSTDIO_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_CSTDIO_ + +// The kernel doesn't want this file but some libc++ headers we need +// wind up including it and they need these declarations. +// +// Note this specifically avoids <stdio.h> because libc++ doesn't need that +// but <string_view> indirectly reaches <cstdio> and the kernel's <stdio.h> +// uses <ktl/string_view.h> so there would be a circularity. + +#include <wchar.h> + +#define EOF (-1) + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_CSTDIO_ diff --git a/lib/ktl/include/cstdlib b/lib/ktl/include/cstdlib new file mode 100644 index 0000000..25ad762 --- /dev/null +++ b/lib/ktl/include/cstdlib @@ -0,0 +1,30 @@ +// Copyright 2018 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#pragma once + +// This is used by libc++'s <new> just for std::abort, ::posix_memalign, and +// ::free. + +#include <stdlib.h> + +#include <__config> + +#define _LIBCPP_UNREACHABLE() __builtin_unreachable() + +// This is used by the __libcpp_aligned_alloc inline. Since it always fails +// that inline will trivially always return nullptr. +inline int posix_memalign(void** ptr, size_t align, size_t size) { return 1; } + +// This is used by the __libcpp_aligned_free inline, which won't really ever be +// called. The kernel does have a real free declared elsewhere. +void free(void* ptr); + +_LIBCPP_BEGIN_NAMESPACE_STD + +using ::abort; + +_LIBCPP_END_NAMESPACE_STD diff --git a/lib/ktl/include/cwchar b/lib/ktl/include/cwchar new file mode 100644 index 0000000..4f24c73 --- /dev/null +++ b/lib/ktl/include/cwchar @@ -0,0 +1,62 @@ +// Copyright 2020 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_CWCHAR +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_CWCHAR + +// The kernel doesn't want this file but some libc++ headers we need +// wind up including it and they need these declarations. + +#include <wchar.h> + +#include <__config> + +_LIBCPP_BEGIN_NAMESPACE_STD + +using ::wmemcpy; +using ::wmemmove; +using ::wmemset; + +// These are called by libc++ header code. The first two should never actually +// be called by anything that really gets instantiated in kernel code since +// wchar_t is never used. However, __constexpr_wmemchr is used by places like +// std::find not just for wchar_t per se but for any trivial type of the same +// size, e.g. uint32_t. So its code must be correct. The other two are filled +// out just in case of an unexpected use. + +constexpr size_t __constexpr_wcslen(const wchar_t* str) { + size_t len = 0; + while (*str++ != L'\0') { + ++len; + } + return len; +} + +constexpr int __constexpr_wmemcmp(const wchar_t* lhs, const wchar_t* rhs, size_t count) { + while (count-- > 0) { + if (*lhs != *rhs) { + return static_cast<int>(*lhs - *rhs); + } + ++lhs; + ++rhs; + } + return 0; +} + +template <class Tp, class Up> +constexpr Tp* __constexpr_wmemchr(Tp* str, Up wc, size_t count) { + while (count-- > 0) { + if (*str == wc) { + return str; + } + ++str; + } + return nullptr; +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_CWCHAR diff --git a/lib/ktl/include/ktl/algorithm.h b/lib/ktl/include/ktl/algorithm.h new file mode 100644 index 0000000..7b7baed --- /dev/null +++ b/lib/ktl/include/ktl/algorithm.h @@ -0,0 +1,116 @@ +// Copyright 2020 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ALGORITHM_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ALGORITHM_H_ + +#include <algorithm> + +namespace ktl { + +// "Non-modifying sequence operations" +using std::adjacent_find; +using std::all_of; +using std::any_of; +using std::count; +using std::count_if; +using std::find; +using std::find_end; +using std::find_first_of; +using std::find_if; +using std::find_if_not; +using std::for_each; +using std::for_each_n; +using std::none_of; +using std::search; +using std::search_n; + +namespace ranges { +using std::ranges::adjacent_find; +using std::ranges::all_of; +using std::ranges::any_of; +using std::ranges::count; +using std::ranges::count_if; +using std::ranges::find; +using std::ranges::find_end; +using std::ranges::find_first_of; +using std::ranges::find_if; +using std::ranges::find_if_not; +using std::ranges::for_each; +using std::ranges::for_each_n; +using std::ranges::none_of; +using std::ranges::search; +using std::ranges::search_n; +} // namespace ranges + +// "Modifying sequence operations" (subset) +using std::copy; +using std::copy_if; +using std::fill; +using std::fill_n; +using std::reverse; +using std::shuffle; +using std::transform; + +namespace ranges { +using std::ranges::copy; +using std::ranges::copy_if; +using std::ranges::fill; +using std::ranges::fill_n; +using std::ranges::reverse; +using std::ranges::shuffle; +using std::ranges::transform; +} // namespace ranges + +// "Sorting operations" (subset) +using std::is_sorted; +using std::is_sorted_until; +using std::sort; +using std::stable_sort; + +namespace ranges { +using std::ranges::is_sorted; +using std::ranges::is_sorted_until; +using std::ranges::sort; +using std::ranges::stable_sort; +} // namespace ranges + +// "Binary search operations (on sorted ranges)" +using std::binary_search; +using std::equal_range; +using std::lower_bound; +using std::upper_bound; + +namespace ranges { +using std::ranges::binary_search; +using std::ranges::equal_range; +using std::ranges::lower_bound; +using std::ranges::upper_bound; +} // namespace ranges + +// "Minimum/maximum operations" +using std::clamp; +using std::equal; +using std::max; +using std::max_element; +using std::min; +using std::min_element; +using std::minmax; +using std::minmax_element; + +namespace ranges { +using std::ranges::clamp; +using std::ranges::max; +using std::ranges::max_element; +using std::ranges::min; +using std::ranges::min_element; +using std::ranges::minmax; +using std::ranges::minmax_element; +} // namespace ranges + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ALGORITHM_H_ diff --git a/lib/ktl/include/ktl/array.h b/lib/ktl/include/ktl/array.h new file mode 100644 index 0000000..90d445a --- /dev/null +++ b/lib/ktl/include/ktl/array.h @@ -0,0 +1,19 @@ +// Copyright 2019 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ARRAY_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ARRAY_H_ + +#include <array> + +namespace ktl { + +using std::array; +using std::to_array; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ARRAY_H_ diff --git a/lib/ktl/include/ktl/atomic.h b/lib/ktl/include/ktl/atomic.h new file mode 100644 index 0000000..017db6b --- /dev/null +++ b/lib/ktl/include/ktl/atomic.h @@ -0,0 +1,40 @@ +// Copyright 2019 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ATOMIC_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ATOMIC_H_ + +#include <atomic> + +// On arm64 and x86-64, lock-free 128-bit (16-byte) atomics are available. +// But riscv64 does not support them. +#ifdef __riscv +#define HAVE_ATOMIC_128 0 +#else +#define HAVE_ATOMIC_128 1 +#endif + +namespace ktl { + +using std::atomic; +using std::atomic_init; +using std::atomic_ref; + +using std::memory_order; + +using std::memory_order_acq_rel; +using std::memory_order_acquire; +using std::memory_order_consume; +using std::memory_order_relaxed; +using std::memory_order_release; +using std::memory_order_seq_cst; + +using std::atomic_signal_fence; +using std::atomic_thread_fence; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ATOMIC_H_ diff --git a/lib/ktl/include/ktl/bit.h b/lib/ktl/include/ktl/bit.h new file mode 100644 index 0000000..c3ccb7e --- /dev/null +++ b/lib/ktl/include/ktl/bit.h @@ -0,0 +1,30 @@ +// Copyright 2021 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_BIT_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_BIT_H_ + +#include <bit> + +namespace ktl { + +using std::bit_cast; +using std::bit_ceil; +using std::bit_floor; +using std::bit_width; +using std::countl_one; +using std::countl_zero; +using std::countr_one; +using std::countr_zero; +using std::endian; +using std::has_single_bit; +using std::popcount; +using std::rotl; +using std::rotr; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_BIT_H_ diff --git a/lib/ktl/include/ktl/byte.h b/lib/ktl/include/ktl/byte.h new file mode 100644 index 0000000..26b1294 --- /dev/null +++ b/lib/ktl/include/ktl/byte.h @@ -0,0 +1,18 @@ +// Copyright 2020 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_BYTE_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_BYTE_H_ + +#include <cstddef> + +namespace ktl { + +using std::byte; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_BYTE_H_ diff --git a/lib/ktl/include/ktl/concepts.h b/lib/ktl/include/ktl/concepts.h new file mode 100644 index 0000000..93b3f62 --- /dev/null +++ b/lib/ktl/include/ktl/concepts.h @@ -0,0 +1,46 @@ +// Copyright 2025 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_CONCEPTS_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_CONCEPTS_H_ + +#include <concepts> + +namespace ktl { + +using std::assignable_from; +using std::common_reference_with; +using std::common_with; +using std::constructible_from; +using std::copy_constructible; +using std::copyable; +using std::default_initializable; +using std::derived_from; +using std::destructible; +using std::equality_comparable; +using std::equality_comparable_with; +using std::equivalence_relation; +using std::integral; +using std::invocable; +using std::movable; +using std::move_constructible; +using std::predicate; +using std::regular; +using std::regular_invocable; +using std::relation; +using std::same_as; +using std::semiregular; +using std::signed_integral; +using std::strict_weak_order; +using std::swappable; +using std::swappable_with; +using std::totally_ordered; +using std::totally_ordered_with; +using std::unsigned_integral; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_CONCEPTS_H_ diff --git a/lib/ktl/include/ktl/declval.h b/lib/ktl/include/ktl/declval.h new file mode 100644 index 0000000..925fe9c --- /dev/null +++ b/lib/ktl/include/ktl/declval.h @@ -0,0 +1,18 @@ +// Copyright 2021 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_DECLVAL_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_DECLVAL_H_ + +#include <utility> + +namespace ktl { + +using std::declval; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_DECLVAL_H_ diff --git a/lib/ktl/include/ktl/enforce.h b/lib/ktl/include/ktl/enforce.h new file mode 100644 index 0000000..9c948d2 --- /dev/null +++ b/lib/ktl/include/ktl/enforce.h @@ -0,0 +1,37 @@ +// Copyright 2021 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ENFORCE_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ENFORCE_H_ + +// `#include <ktl/enforce.h>` should appear last in the include list of any +// kernel .cc file that uses `ktl` headers. Since many other kernel headers +// use ktl headers and this must appear after *all* uses of any ktl headers, +// whether direct or indirect, it's a good idea to just make sure that +// `#include <ktl/enforce.h>` in each .cc file of kernel-only code (i.e. code +// that might ever use ktl directly). +// +// The //.clang-format file has a rule to ensure this file is placed last and +// separate from the other #include lines, so just adding the `#include` line +// to each source file should make sure its placement stays correct. + +// This directive tells the preprocessor that the identifier `std` cannot +// appear in any context (except the expansion of a macro already defined +// before now). This ensures that any stray use of std::name in kernel code +// can get caught at compile time so people remember to use ktl::name instead +// and ensure that what they're using is in the approved ktl subset of std. +// +// It also affects harmless use of `std` as a local variable name or whatever, +// but we can live without kernel code being able to use that one name. +#pragma GCC poison std + +// Also poison the stdcompat namespaces, as the same rules for ktl wrappers +// apply to those as std proper. +#pragma GCC poison cpp17 +#pragma GCC poison cpp20 +#pragma GCC poison cpp23 + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ENFORCE_H_ diff --git a/lib/ktl/include/ktl/forward.h b/lib/ktl/include/ktl/forward.h new file mode 100644 index 0000000..62874e6 --- /dev/null +++ b/lib/ktl/include/ktl/forward.h @@ -0,0 +1,18 @@ +// Copyright 2018 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_INCLUDE_KTL_FORWARD_H_ +#define ZIRCON_KERNEL_INCLUDE_KTL_FORWARD_H_ + +#include <utility> + +namespace ktl { + +using std::forward; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_INCLUDE_KTL_FORWARD_H_ diff --git a/lib/ktl/include/ktl/functional.h b/lib/ktl/include/ktl/functional.h new file mode 100644 index 0000000..026f4cf --- /dev/null +++ b/lib/ktl/include/ktl/functional.h @@ -0,0 +1,19 @@ +// Copyright 2023 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_FUNCTIONAL_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_FUNCTIONAL_H_ + +#include <functional> + +namespace ktl { + +using std::bind_front; +using std::invoke; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_FUNCTIONAL_H_ diff --git a/lib/ktl/include/ktl/initializer_list.h b/lib/ktl/include/ktl/initializer_list.h new file mode 100644 index 0000000..3a69abb --- /dev/null +++ b/lib/ktl/include/ktl/initializer_list.h @@ -0,0 +1,18 @@ +// Copyright 2021 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_INITIALIZER_LIST_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_INITIALIZER_LIST_H_ + +#include <initializer_list> + +namespace ktl { + +using std::initializer_list; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_INITIALIZER_LIST_H_ diff --git a/lib/ktl/include/ktl/inplace_vector.h b/lib/ktl/include/ktl/inplace_vector.h new file mode 100644 index 0000000..4eaf92b --- /dev/null +++ b/lib/ktl/include/ktl/inplace_vector.h @@ -0,0 +1,18 @@ +// Copyright 2025 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_INPLACE_VECTOR_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_INPLACE_VECTOR_H_ + +#include <lib/stdcompat/inplace_vector.h> + +namespace ktl { + +using cpp26::inplace_vector; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_INPLACE_VECTOR_H_ diff --git a/lib/ktl/include/ktl/iterator.h b/lib/ktl/include/ktl/iterator.h new file mode 100644 index 0000000..58d92be --- /dev/null +++ b/lib/ktl/include/ktl/iterator.h @@ -0,0 +1,38 @@ +// Copyright 2020 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ITERATOR_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ITERATOR_H_ + +#include <iterator> + +namespace ktl { + +// This includes only the "iterator operations" and "range access" subsets +// of the <iterator> API. These are useful for treating all sorts of +// container types, raw arrays, pointers, and {...} literal lists uniformly. +// It leaves out iterator_traits and the "iterator adaptors" subset, which +// have not yet seemed desirable to employ in kernel code. + +using std::advance; +using std::begin; +using std::cbegin; +using std::cend; +using std::crbegin; +using std::crend; +using std::data; +using std::distance; +using std::empty; +using std::end; +using std::next; +using std::prev; +using std::rbegin; +using std::rend; +using std::size; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_ITERATOR_H_ diff --git a/lib/ktl/include/ktl/limits.h b/lib/ktl/include/ktl/limits.h new file mode 100644 index 0000000..8f6adf4 --- /dev/null +++ b/lib/ktl/include/ktl/limits.h @@ -0,0 +1,18 @@ +// Copyright 2019 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_INCLUDE_KTL_LIMITS_H_ +#define ZIRCON_KERNEL_INCLUDE_KTL_LIMITS_H_ + +#include <limits> + +namespace ktl { + +using std::numeric_limits; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_INCLUDE_KTL_LIMITS_H_ diff --git a/lib/ktl/include/ktl/memory.h b/lib/ktl/include/ktl/memory.h new file mode 100644 index 0000000..caf8d47 --- /dev/null +++ b/lib/ktl/include/ktl/memory.h @@ -0,0 +1,41 @@ +// Copyright 2024 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_MEMORY_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_MEMORY_H_ + +#include <memory> + +namespace ktl { + +using std::addressof; +using std::to_address; + +using std::align; +using std::assume_aligned; + +using std::default_delete; + +using std::pointer_traits; + +using std::construct_at; +using std::destroy; +using std::destroy_at; +using std::destroy_n; +using std::uninitialized_copy; +using std::uninitialized_copy_n; +using std::uninitialized_default_construct; +using std::uninitialized_default_construct_n; +using std::uninitialized_fill; +using std::uninitialized_fill_n; +using std::uninitialized_move; +using std::uninitialized_move_n; +using std::uninitialized_value_construct; +using std::uninitialized_value_construct_n; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_MEMORY_H_ diff --git a/lib/ktl/include/ktl/new.h b/lib/ktl/include/ktl/new.h new file mode 100644 index 0000000..12def96 --- /dev/null +++ b/lib/ktl/include/ktl/new.h @@ -0,0 +1,25 @@ +// Copyright 2026 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_NEW_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_NEW_H_ + +#include <new> + +namespace ktl { + +using std::align_val_t; + +using std::destroying_delete; +using std::destroying_delete_t; +using std::nothrow; +using std::nothrow_t; + +using std::launder; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_NEW_H_ diff --git a/lib/ktl/include/ktl/numeric.h b/lib/ktl/include/ktl/numeric.h new file mode 100644 index 0000000..18cad1f --- /dev/null +++ b/lib/ktl/include/ktl/numeric.h @@ -0,0 +1,20 @@ +// Copyright 2023 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_NUMERIC_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_NUMERIC_H_ + +#include <numeric> + +namespace ktl { + +// "Numeric operations" +using std::accumulate; +using std::reduce; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_NUMERIC_H_ diff --git a/lib/ktl/include/ktl/optional.h b/lib/ktl/include/ktl/optional.h new file mode 100644 index 0000000..e08451d --- /dev/null +++ b/lib/ktl/include/ktl/optional.h @@ -0,0 +1,23 @@ +// Copyright 2020 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_OPTIONAL_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_OPTIONAL_H_ + +#include <optional> + +namespace ktl { + +using std::in_place; +using std::in_place_t; +using std::make_optional; +using std::nullopt; +using std::nullopt_t; +using std::optional; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_OPTIONAL_H_ diff --git a/lib/ktl/include/ktl/ranges.h b/lib/ktl/include/ktl/ranges.h new file mode 100644 index 0000000..8e3ee09 --- /dev/null +++ b/lib/ktl/include/ktl/ranges.h @@ -0,0 +1,25 @@ +// Copyright 2025 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_RANGES_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_RANGES_H_ + +#include <ranges> + +namespace ktl { + +// This can't be a namespace alias like `views` because <ktl/algorithm.h> also +// adds things to ktl::ranges and redundant namespace aliases aren't allowed. +namespace ranges { +using namespace std::ranges; +} // namespace ranges + +// Only this header defines this namespace, so a simple namespace alias works. +namespace views = std::views; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_RANGES_H_ diff --git a/lib/ktl/include/ktl/ref.h b/lib/ktl/include/ktl/ref.h new file mode 100644 index 0000000..fdaddc4 --- /dev/null +++ b/lib/ktl/include/ktl/ref.h @@ -0,0 +1,19 @@ +// Copyright 2023 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_REF_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_REF_H_ + +#include <functional> + +namespace ktl { + +using std::cref; +using std::ref; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_REF_H_ diff --git a/lib/ktl/include/ktl/source_location.h b/lib/ktl/include/ktl/source_location.h new file mode 100644 index 0000000..121668d --- /dev/null +++ b/lib/ktl/include/ktl/source_location.h @@ -0,0 +1,18 @@ +// Copyright 2025 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_SOURCE_LOCATION_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_SOURCE_LOCATION_H_ + +#include <source_location> + +namespace ktl { + +using std::source_location; + +} + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_SOURCE_LOCATION_H_ diff --git a/lib/ktl/include/ktl/span.h b/lib/ktl/include/ktl/span.h new file mode 100644 index 0000000..deb1df3 --- /dev/null +++ b/lib/ktl/include/ktl/span.h @@ -0,0 +1,26 @@ +// Copyright 2020 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_SPAN_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_SPAN_H_ + +#include <span> + +namespace ktl { + +using std::span; + +using std::as_bytes; +using std::as_writable_bytes; + +using std::dynamic_extent; + +using std::data; +using std::size; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_SPAN_H_ diff --git a/lib/ktl/include/ktl/string_view.h b/lib/ktl/include/ktl/string_view.h new file mode 100644 index 0000000..9ba949f --- /dev/null +++ b/lib/ktl/include/ktl/string_view.h @@ -0,0 +1,22 @@ +// Copyright 2020 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_STRING_VIEW_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_STRING_VIEW_H_ + +#include <string_view> + +namespace ktl { + +using std::basic_string_view; +using std::string_view; + +} // namespace ktl + +// Just including <ktl/string_view.h> enables "foo"sv literals. +using namespace std::literals::string_view_literals; + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_STRING_VIEW_H_ diff --git a/lib/ktl/include/ktl/tuple.h b/lib/ktl/include/ktl/tuple.h new file mode 100644 index 0000000..b00c7e0 --- /dev/null +++ b/lib/ktl/include/ktl/tuple.h @@ -0,0 +1,30 @@ +// Copyright 2024 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_TUPLE_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_TUPLE_H_ + +#include <tuple> + +namespace ktl { + +using std::apply; +using std::forward_as_tuple; +using std::get; +using std::ignore; +using std::make_from_tuple; +using std::make_tuple; +using std::tie; +using std::tuple; +using std::tuple_cat; +using std::tuple_element; +using std::tuple_element_t; +using std::tuple_size; +using std::tuple_size_v; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_TUPLE_H_ diff --git a/lib/ktl/include/ktl/type_traits.h b/lib/ktl/include/ktl/type_traits.h new file mode 100644 index 0000000..fc0a2f0 --- /dev/null +++ b/lib/ktl/include/ktl/type_traits.h @@ -0,0 +1,165 @@ +// Copyright 2019 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_TYPE_TRAITS_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_TYPE_TRAITS_H_ + +#include <type_traits> + +namespace ktl { + +using std::add_const; +using std::add_const_t; + +using std::is_array; +using std::is_array_v; +using std::is_bounded_array; +using std::is_bounded_array_v; +using std::is_unbounded_array; +using std::is_unbounded_array_v; + +using std::false_type; +using std::true_type; + +using std::conjunction; +using std::conjunction_v; + +using std::disjunction; +using std::disjunction_v; + +using std::conditional; +using std::conditional_t; + +using std::decay; +using std::decay_t; + +using std::void_t; + +using std::enable_if; +using std::enable_if_t; + +using std::has_unique_object_representations; +using std::has_unique_object_representations_v; + +using std::is_base_of; +using std::is_base_of_v; + +using std::is_const; +using std::is_const_v; + +using std::is_constructible; +using std::is_constructible_v; + +using std::is_copy_constructible; +using std::is_copy_constructible_v; + +using std::is_copy_assignable; +using std::is_copy_assignable_v; + +using std::is_default_constructible; +using std::is_default_constructible_v; + +using std::is_class; +using std::is_class_v; + +using std::is_enum; +using std::is_enum_v; + +using std::is_floating_point; +using std::is_floating_point_v; + +using std::is_function; +using std::is_function_v; + +using std::is_integral; +using std::is_integral_v; + +using std::invoke_result_t; +using std::is_invocable; +using std::is_invocable_r; +using std::is_invocable_r_v; +using std::is_invocable_v; + +using std::is_lvalue_reference; +using std::is_lvalue_reference_v; + +using std::is_move_constructible; +using std::is_move_constructible_v; + +using std::is_move_assignable; +using std::is_move_assignable_v; + +using std::is_pod; +using std::is_pod_v; + +using std::is_same; +using std::is_same_v; + +using std::is_signed; +using std::is_signed_v; + +using std::is_standard_layout; +using std::is_standard_layout_v; + +using std::is_empty; +using std::is_empty_v; + +using std::is_trivial; +using std::is_trivial_v; + +using std::is_trivially_copy_assignable; +using std::is_trivially_copy_assignable_v; + +using std::is_trivially_copy_constructible; +using std::is_trivially_copy_constructible_v; + +using std::is_trivially_constructible; +using std::is_trivially_constructible_v; + +using std::is_trivially_destructible; +using std::is_trivially_destructible_v; + +using std::is_trivially_move_assignable; +using std::is_trivially_move_assignable_v; + +using std::is_trivially_move_constructible; +using std::is_trivially_move_constructible_v; + +using std::is_member_object_pointer; +using std::is_member_object_pointer_v; + +using std::is_unsigned; +using std::is_unsigned_v; + +using std::is_void; +using std::is_void_v; + +using std::make_signed; +using std::make_signed_t; +using std::make_unsigned; +using std::make_unsigned_t; + +using std::remove_all_extents; +using std::remove_all_extents_t; + +using std::remove_const; +using std::remove_const_t; + +using std::remove_extent; +using std::remove_extent_t; + +using std::remove_pointer; +using std::remove_pointer_t; + +using std::remove_reference; +using std::remove_reference_t; + +using std::underlying_type; +using std::underlying_type_t; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_TYPE_TRAITS_H_ diff --git a/lib/ktl/include/ktl/unique_ptr.h b/lib/ktl/include/ktl/unique_ptr.h new file mode 100644 index 0000000..e2d2f39 --- /dev/null +++ b/lib/ktl/include/ktl/unique_ptr.h @@ -0,0 +1,37 @@ +// Copyright 2018 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_INCLUDE_KTL_UNIQUE_PTR_H_ +#define ZIRCON_KERNEL_INCLUDE_KTL_UNIQUE_PTR_H_ + +#include <memory> +#include <new> + +#include <fbl/alloc_checker.h> +#include <ktl/type_traits.h> + +namespace ktl { + +using std::align_val_t; +using std::unique_ptr; + +template <typename T, typename... Args> +ktl::enable_if_t<!ktl::is_array_v<T>, unique_ptr<T>> make_unique(fbl::AllocChecker* ac, + Args&&... args) { + return unique_ptr<T>(new (ac) T(std::forward<Args>(args)...)); +} + +// For an unbounded array of given size, each element is value-initialized. +// This is different from plain `new (ac) T[n]`, which performs default-initialization. +template <typename T, typename... Args> +ktl::enable_if_t<ktl::is_unbounded_array_v<T>, unique_ptr<T>> make_unique(fbl::AllocChecker* ac, + size_t n) { + return unique_ptr<T>(new (ac) ktl::remove_extent_t<T>[n]()); +} + +} // namespace ktl + +#endif // ZIRCON_KERNEL_INCLUDE_KTL_UNIQUE_PTR_H_ diff --git a/lib/ktl/include/ktl/utility.h b/lib/ktl/include/ktl/utility.h new file mode 100644 index 0000000..1e699e2 --- /dev/null +++ b/lib/ktl/include/ktl/utility.h @@ -0,0 +1,41 @@ +// Copyright 2018 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_UTILITY_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_UTILITY_H_ + +#include <utility> + +namespace ktl { + +using std::declval; +using std::exchange; +using std::forward; +using std::move; +using std::swap; + +using std::in_place; +using std::in_place_index; +using std::in_place_index_t; +using std::in_place_t; + +using std::index_sequence; +using std::index_sequence_for; +using std::integer_sequence; +using std::make_index_sequence; +using std::make_integer_sequence; + +using std::get; +using std::make_pair; +using std::pair; +using std::piecewise_construct; +using std::piecewise_construct_t; + +using std::ignore; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_UTILITY_H_ diff --git a/lib/ktl/include/ktl/variant.h b/lib/ktl/include/ktl/variant.h new file mode 100644 index 0000000..68ef362 --- /dev/null +++ b/lib/ktl/include/ktl/variant.h @@ -0,0 +1,31 @@ +// Copyright 2020 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_VARIANT_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_VARIANT_H_ + +#include <utility> +#include <variant> + +namespace ktl { + +using std::get; +using std::get_if; +using std::holds_alternative; +using std::in_place_type; +using std::in_place_type_t; +using std::monostate; +using std::variant; +using std::variant_alternative; +using std::variant_alternative_t; +using std::variant_npos; +using std::variant_size; +using std::variant_size_v; +using std::visit; + +} // namespace ktl + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_KTL_VARIANT_H_ diff --git a/lib/ktl/include/limits b/lib/ktl/include/limits new file mode 100644 index 0000000..d8ea37d --- /dev/null +++ b/lib/ktl/include/limits @@ -0,0 +1,110 @@ +// Copyright 2018 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#pragma once + +// TODO(https://fxbug.dev/42106615): The libc++ <limits> defines specializations for +// floating-point types, which in GCC is incompatible with the command-line +// switches used for the kernel. So this header fakes out the other libc++ +// headers with a std::numeric_limits that is close enough. + +#include <limits.h> + +namespace std { + +template <class T> +class numeric_limits {}; + +#define SPECIALIZE_INT(type, sign, modulo, digits_, min_, max_) \ + template <> \ + class numeric_limits<type> { \ + public: \ + static constexpr bool is_specialized = true; \ + static constexpr bool is_signed = (sign); \ + static constexpr bool is_integer = true; \ + static constexpr bool is_exact = true; \ + static constexpr bool has_infinity = false; \ + static constexpr bool has_quiet_NaN = false; \ + static constexpr bool has_signaling_NaN = false; \ + static constexpr bool has_denorm = false; \ + static constexpr bool has_denorm_loss = false; \ + static constexpr bool round_style = false; \ + static constexpr bool is_iec559 = false; \ + static constexpr bool is_bounded = true; \ + static constexpr bool is_modulo = (modulo); \ + static constexpr int digits = (digits_); \ + static constexpr int digits10 = (digits_) * 3 / 10; \ + static constexpr int max_digits10 = 0; \ + static constexpr int radix = 2; \ + static constexpr int min_exponent = 0; \ + static constexpr int min_exponent10 = 0; \ + static constexpr int max_exponent = 0; \ + static constexpr int max_exponent10 = 0; \ + static constexpr bool traps = false; \ + static constexpr bool tinyness_before = false; \ + static constexpr type min() { \ + return (min_); \ + } \ + static constexpr type lowest() { \ + return (min_); \ + } \ + static constexpr type max() { \ + return (max_); \ + } \ + static constexpr type epsilon() { \ + return 0; \ + } \ + static constexpr type round_error() { \ + return 0; \ + } \ + static constexpr type infinity() { \ + return 0; \ + } \ + static constexpr type quiet_NaN() { \ + return 0; \ + } \ + static constexpr type signaling_NaN() { \ + return 0; \ + } \ + static constexpr type denorm_min() { \ + return 0; \ + } \ + } + +#define SPECIALIZE_SIGNED(type, min, max) \ + SPECIALIZE_INT(type, true, false, CHAR_BIT * sizeof(type) - 1, min, max) + +#define SPECIALIZE_UNSIGNED(type, min, max) \ + SPECIALIZE_INT(type, false, true, CHAR_BIT * sizeof(type), min, max) + +SPECIALIZE_INT(bool, false, true, 1, false, true); +#if CHAR_MIN == 0 +SPECIALIZE_UNSIGNED(char, CHAR_MIN, CHAR_MAX); +#else +SPECIALIZE_SIGNED(char, CHAR_MIN, CHAR_MAX); +#endif +SPECIALIZE_SIGNED(signed char, SCHAR_MIN, SCHAR_MAX); +SPECIALIZE_UNSIGNED(unsigned char, 0, UCHAR_MAX); + +SPECIALIZE_SIGNED(short, SHRT_MIN, SHRT_MAX); +SPECIALIZE_UNSIGNED(unsigned short, 0, USHRT_MAX); +SPECIALIZE_SIGNED(int, INT_MIN, INT_MAX); +SPECIALIZE_UNSIGNED(unsigned int, 0, UINT_MAX); +SPECIALIZE_SIGNED(long, LONG_MIN, LONG_MAX); +SPECIALIZE_UNSIGNED(unsigned long, 0, ULONG_MAX); +SPECIALIZE_SIGNED(long long, (-__LONG_LONG_MAX__ - 1LL), __LONG_LONG_MAX__); +SPECIALIZE_UNSIGNED(unsigned long long, 0, (__LONG_LONG_MAX__ * 2ULL + 1ULL)); + +#ifdef __SIZEOF_INT128__ +SPECIALIZE_SIGNED(__int128_t, (__int128_t{1} << 127), (~__uint128_t{0} ^ (__int128_t{1} << 127))); +SPECIALIZE_UNSIGNED(__uint128_t, 0, (~__uint128_t{0})); +#endif + +#undef SPECIALIZE_SIGNED +#undef SPECIALIZE_UNSIGNED +#undef SPECIALIZE_INT + +} // namespace std diff --git a/lib/ktl/include/time.h b/lib/ktl/include/time.h new file mode 100644 index 0000000..138801f --- /dev/null +++ b/lib/ktl/include/time.h @@ -0,0 +1,39 @@ +// Copyright 2020 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_TIME_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_TIME_H_ + +#include <stddef.h> + +// <zircon/time.h> uses these when __has_include(<time.h>). +typedef long int time_t; +struct timespec { + time_t tv_sec; + long int tv_nsec; +}; + +// The kernel doesn't want this file but some libc++ headers we need +// wind up including it and they need these declarations. + +#ifdef __cplusplus + +using clock_t = long int; +struct tm {}; +char* asctime(tm*) noexcept; +clock_t clock() noexcept; +char* ctime(const time_t*) noexcept; +double difftime(time_t, time_t) noexcept; +tm* gmtime(const time_t*) noexcept; +tm* localtime(const time_t*) noexcept; +time_t mktime(tm*) noexcept; +size_t strftime(char*, size_t, const char*, const tm*) noexcept; +time_t time(time_t*) noexcept; +int timespec_get(timespec* ts, int) noexcept; + +#endif // __cplusplus + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_TIME_H_ diff --git a/lib/ktl/include/version b/lib/ktl/include/version new file mode 100644 index 0000000..ba04749 --- /dev/null +++ b/lib/ktl/include/version @@ -0,0 +1,14 @@ +// Copyright 2024 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#pragma once + +#include_next <version> + +// We want to be able to implement specialization for std::formatter in common libraries for kernel +// and userspace. By undefing it here, we allow those libraries to avoid exposing that code to the +// kernel where it's not supported. +#undef __cpp_lib_format diff --git a/lib/ktl/include/wchar.h b/lib/ktl/include/wchar.h new file mode 100644 index 0000000..b3f2ccb --- /dev/null +++ b/lib/ktl/include/wchar.h @@ -0,0 +1,23 @@ +// Copyright 2023 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#ifndef ZIRCON_KERNEL_LIB_KTL_INCLUDE_WCHAR_H_ +#define ZIRCON_KERNEL_LIB_KTL_INCLUDE_WCHAR_H_ + +// This file is included by <cstdio> and the like that are used from other +// libc++ headers that are wrapped by ktl. This file exists to preempt those +// inclusions so that libc++'s <wchar.h> wrapper header won't be used, since +// it's not compatible with the kernel environment. However, other libc++ +// headers also use `#include_next <wchar.h>` to get to "the system libc" +// version of the header. To satisfy those, include-after/wchar.h provides the +// actual declarations needed from the standard C <wchar.h> API. So this +// header just defers to that one, but must exist separately in this directory +// so that it preempt's libc++'s wrapper. This can't itself use #include_next +// because that would reach libc++'s wrapper before the include-after file. + +#include "../include-after/wchar.h" + +#endif // ZIRCON_KERNEL_LIB_KTL_INCLUDE_WCHAR_H_ diff --git a/lib/ktl/popcount.cc b/lib/ktl/popcount.cc new file mode 100644 index 0000000..07b7888 --- /dev/null +++ b/lib/ktl/popcount.cc @@ -0,0 +1,135 @@ +// Copyright 2019 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#include <stdint.h> + +// When the compiler doesn't inline __builtin_popcount{,l}, it calls these. +extern "C" int __popcountsi2(uint32_t val); +extern "C" int __popcountdi2(uint64_t val); +// If the compiler doesn't inline __builtin_popcount % 2 it calls this. +extern "C" int __paritydi2(uint64_t val); + +extern "C" int __popcountsi2(uint32_t val) { + // Implement a log2(bits) popcount, with a few tricks to save some + // instructions. + // + // The general idea here is to simply add up the bits in the word in + // parallel, storing intermediate results in different bit positions in + // the word as we go, and eventually arriving at a sum which is the + // popcount of the word. + // + // For example, consider an 8 bit integer written as + // + // b7 b6 b5 b4 b3 b2 b1 b0 + // + // Each of the bits in the word represent a partial sum that, when added + // together, produce our result. We can compute... + // + // ( + // b7 b6 b5 b4 b3 b2 b1 b0 & + // 0 1 0 1 0 1 0 1 = + // 0 b6 0 b4 0 b2 0 b0 + // ) + ( + // b7 b6 b5 b4 b3 b2 b1 b0 >> 1 = + // 0 b7 b6 b5 b4 b3 b2 b1 & + // 0 1 0 1 0 1 0 1 = + // 0 b7 0 b5 0 b3 0 b1 + // ) = + // b7+b6 b5+b4 b3+b2 b1+b0 + // + // And now we have 4 partial sums, each of which takes two bits of + // storage instead of one. Repeating this process with appropriate + // masks and shifts will eventually give us the answer we are looking + // for. After the next step, we will have partial sums which require 3 + // bits of storage, but aligned to 4 bit boundaries; so... + // + // 0 (b7+b6+b5+b4) 0 (b3+b2+b1+b0) + // + // After the last step, we will get the final sum stored in 4 bits, with + // guaranteed 0s for the upper bits. + // aligned to ... + // + // 0 0 0 0 (b7+b6+b5+b4+b3+b2+b1+b0) + // + // While this is the general idea, it turns out that we only need to + // follow this exact process during step #2. For each of the other + // steps (there will be 5 for a 32 bit integer) we can shave a few + // cycles by taking advantage of some of the particular properties of + // each step. See the comments below. + constexpr uint32_t mask1 = 0x55555555; + constexpr uint32_t mask2 = 0x33333333; + constexpr uint32_t mask3 = 0x0F0F0F0F; + constexpr uint32_t mult1 = 0x01010101; + + // Step 1: + // While we could compute (val & mask) + ((val >> 1) & mask), we can + // actually save one of the mask operations by subtracting instead of + // adding. Consider the following truth table... + // + // In | >>1 | & | - | + // X00 | XX0 | X00 | X00 | + // X01 | XX0 | X00 | X01 | + // X10 | XX1 | X01 | X01 | + // X11 | XX1 | X01 | X10 | + // + val = val - ((val >> 1) & mask1); + + // Step 2: + // This is simply the operation described in the overview, adding a + // bunch of 2 bit partials to produce a 3 bit result, but which is + // aligned on 4 bit boundaries (where the MSB of each 4 bit nibble is + // guaranteed to be 0) + val = (val & mask2) + ((val >> 2) & mask2); + + // Step 3: + // Again, we can save a mask operation here. This time, it is because + // the we know that all bit positions ((i * 4) + 3) are guaranteed to be + // zero. We can simply shift by 4 and add the partial sums. Any + // overflow will go into the ((i * 4) + 3) position and not interfere + // with any of the other partial sums. + val = (val + (val >> 4)) & mask3; + + // Step 4 + 5: + // Finally, we can combine steps 4 and 5 using a multiply. We have 4 + // remaining partial sums, each of which is contained in 4 bits and + // aligned to 8 bit boundaries (with 4 bits of zero in-between each + // sum). Now, we have enough space that if we could perform all 4 sums + // at once, we know that the result would fit in (at most) 6 bits, which + // easily fits in our 8 bits of space. + // + // At its heart, multiplying is the equivalent of repeated shifting, and + // conditional adding. IOW - if I multiply by 0101b, it is basically + // the same as saying "shift X left by 0, then add that to shift X left + // by 2" (because bits 0 and bits 2 are the only bits set). + // + // So, we have, 0x0A0B0C0D, and want to compute (A+B+C+D). Multiplying + // our register by 0x01010101 basically does this for us. We are + // summing our register shifted left by 0 (A), 8 (B), 16 (C) and 24 (D), + // which puts A+B+C+D into the upper 8 bits of the register. The lower + // 24 bits are junk, but we know (because of the 0s which separate A-D) + // that this junk is not going to overflow into our result. All we need + // to do is right shift by 24, and we are done. + return (val * mult1) >> 24; +} + +extern "C" int __popcountdi2(uint64_t val) { + // See notes above for how this works. The 64 bit version of this is + // identical to the 32 bit version, the only difference is that during + // the final stage, we use the multiply trick to combine steps 4, 5, and + // 6 to sum all 8 4-bit partial sums at once, fitting the result into a + // 7 bit value. + constexpr uint64_t mask1 = 0x5555555555555555; + constexpr uint64_t mask2 = 0x3333333333333333; + constexpr uint64_t mask3 = 0x0F0F0F0F0F0F0F0F; + constexpr uint64_t mult1 = 0x0101010101010101; + + val = val - ((val >> 1) & mask1); + val = (val & mask2) + ((val >> 2) & mask2); + val = (val + (val >> 4)) & mask3; + return static_cast<int>((val * mult1) >> 56); +} + +extern "C" int __paritydi2(uint64_t val) { return __popcountdi2(val) % 2; } diff --git a/lib/ktl/stub-new.cc b/lib/ktl/stub-new.cc new file mode 100644 index 0000000..919d941 --- /dev/null +++ b/lib/ktl/stub-new.cc @@ -0,0 +1,25 @@ +// Copyright 2020 The Fuchsia Authors +// +// Use of this source code is governed by a MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT + +#include <new> + +// std::stable_sort (used as ktl::stable_sort) uses std::get_temporary_buffer, +// which uses operator new to request a temporary buffer but then works fine +// if it can't get one. There is no "default" memory allocation in the +// kernel, so just provide a stub operator new that always fails so +// std::stable_sort falls back to its no-allocation algorithm. + +namespace std { + +const nothrow_t nothrow; + +} // namespace std + +void* operator new(std::size_t, const std::nothrow_t&) noexcept { return nullptr; } + +void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&) noexcept { + return nullptr; +} |