code:
STYLE(9)
========
:doctype:       manpage
:man source:    X15
:man manual:    X15 Kernel Developer{rsquo}s Manual

NAME
----

style - kernel coding style and rules

DESCRIPTION
-----------

This document describes the preferred coding style for the X15 kernel,
which is a close variant of the modern K&R style. It probably does not
encompass all the rules, which are quite numerous despite efforts to
keep them simple and compact. As a result, developers should compare
their work against existing recent modules and infer the rules that
may not be mentioned here. If you identify multiple rules that seem
to conflict, assume any of them is valid. If in doubt, make a pragmatic
decision and move forward.

EXPLICIT PROGRAMMING
--------------------

As a general rule, the coding style for the X15 kernel emphasizes what
could be called "explicit programming", which means that it encourages
developers to clearly state their intent in the code itself. There are
various ways to attempt that, and it can never be completely achieved,
but it remains a strong guiding principle. For example, it is the main
reason behind the adoption of the C programming language, despite its
limitations, and object-oriented programming, despite the lack of support
in the language.

The price of explicit programming is verbosity. Correlations between
code quantity and bugs do exist, and they form part of the motivation
for more modern tools and languages, but such results merely hide the
confounding variable behind the correlations : inadequate programming
skills. Programming is a demanding activity, and kernel programming
even more so. Reducing the number of bugs by writing less code is
therefore not a robust strategy. Instead, developers should learn
a set of good practices, one of them (hopefully) being described in
this document. Since it is expected from developers that they spend
most of their time and efforts designing their code, the ratio of the
time spent writing code compared to the total development time should
be low, from 5 to 30% most of the time. The increase in verbosity should
therefore be close to negligible. On the other hand, the code should be
very easy to understand and follow, which matters a lot more because
there are a lot more people likely to read a piece of code compared
to developers who have written that same piece of code. Besides, authors
often find themselves in situations where they have forgotten the details
of their own code and must understand it again.

The environment around the X15 kernel closely adheres to the Unix culture.
As a result, for developers with little or no experience with Unix, it is
suggested to read {the-art-of-unix-programming} by Eric S. Raymond. Despite
its age, it is still very relevant. The section "Basics of the Unix Philosophy"
is of particular interest.

LANGUAGES
---------

The kernel is mostly written in the C programming language, conforming
to ISO/IEC 9899:2011 (C11), with GNU extensions. While many GNU extensions
are used, nested functions are forbidden. They are considered too specific
to the GCC compiler. Note that X15 can currently be built with both GCC
and Clang, and the latter has no support for nested functions. Also note
that the kernel only expects the freestanding C environment from the compiler.

Since X15 is low level system software, processor-specific assembly is
inevitable. Developers should always refrain from writing assembly code
when possible. Obviously, that code must only be used in
architecture-specific modules.

OBJECT-ORIENTED PROGRAMMING
---------------------------

The X15 kernel is a set of functional modules which often implement
objects. As a result, it naturally borrows some properties of
object-oriented programming. Structures are used to define classes,
and functions are used to implement methods, including constructors
and destructors.

Note however that only a subset of the object-oriented programming
paradigm is applied. In particular, by choice more so than by technical
lack, composition rather than inheritance is how code reuse is achieved,
because inheritance is intrinsically implicit, which is against the
general idea of explicit programming. In addition, polymorphic behaviour
can also be achieved through abstract interfaces implemented with
function pointer structures, an alternative which retains the property
of being explicit to readers.

The main purpose of OOP in X15 is to guide the structure of the code
and data, so that developers have somewhat easy ways to determine how
to group data together, assemble operations around them, and name them.
Encapsulation naturally emerges as a side-effect of keeping interfaces
as compact as possible. By restricting the selected practices of OOP,
we get the banana, and the gorilla happily remains in the jungle.

LINES
-----

Lines are normally limited to 80 columns, unless there is a compelling
reason not to. This makes it easy to identify code with too many levels
of indentation, and also allows comfortable viewing on small screens,
including smartphones and tablets, as well as using multiple buffers
side-by-side, which happens to also be convenient on larger screens.

When defining a function, always break the line right before its name,
so that qualifiers and the return type are on their own line. As a
result, there is enough space for arguments even when the function
name is long. It also makes functions easier to find with grep.

Use at most one empty line as a separator. Use empty lines around
functions and blocks, and also when you consider it appropriate
inside blocks, e.g. to isolate critical sections, and/or locking
functions.

COMMENTS
--------

Each source file must start with a copyright statement comment,
followed by a description of the file, unless the content is simple
and obvious enough not to need one. The copyright statement and the
description must be separated by two empty comment lines :

[source,c]
--------------------------------------------------------------------------------
/*
 * Copyright (c) 2017 John Smith.
 *
 * This program is free software: you can redistribute it and/or modify
 * etc...
 *
 *
 * Description of the module.
 */
--------------------------------------------------------------------------------

Comments are written in C style, not C++. Here are a few examples :

[source,c]
--------------------------------------------------------------------------------
/* Most single-line comments look like this */

/*
 * Multi-line comments look like this. They should also be used for
 * "reference" descriptions in public headers.
 */
struct dummy {
    int useless;    /* Here is a way to provide short member descriptions */
    char moot;      /* But don't hesitate to move descriptions above members
                       when they spawn too many lines on the right side. */
};

/*
 * Instead of using C comments to disable code blocks, use the #if 0
 * preprocessor directive. Remember that C comments do not nest.
 */
#if 0
...
#endif
--------------------------------------------------------------------------------

Comments should not be abused. A large number of comments creates noise
that readers must filter. Instead of writing a comment, ask yourself
whether you can improve the meaning of the code itself, e.g. by changing
names or breaking the code into smaller functions with names that are
good enough to convey the message of the comment. Prefer to describe data
over code. Comments in the code must point at details that are important
and not obvious, and quality code should have few of those.

Note that the project does not use an annotation format for documentation
generation such as Doxygen, because, despite the undeniable improvement over
other types of tools, the benefit still seems too small considering the
additional rules that developers must keep in mind, the effort spent on
checking the annotations and the duplication that they may cause, and the
actual use of the generated documentation compared to direct source code
browsing.

INDENTATION
-----------

An indentation level is 4 spaces. It is strongly recommended, although
not compulsory, to avoid using more than 3 indentation levels. More
levels are tolerated for very short blocks. Combining 4 spaces per level
with 80 columns allows the use of somewhat long, significant names, and
naturally warns that a function should be simplified when the code becomes
overly crammed to the right.

Tabulation characters are strictly forbidden in source files, and should
only be used in Makefiles where absolutely required. This allows everyone
to get the same view, whatever the tools, including editors, comparison
tools, web browsers, etc... It also removes the question of how to align
lines in the code, e.g. when a function call spans multiple lines.

In a switch statement, the case labels are aligned on the same column as
the switch statement :

[source,c]
--------------------------------------------------------------------------------
switch (var) {
case VAL1:
    do_one_thing();
    break;
case VAL2:
case VAL3:
    do_another();
    break;
}
--------------------------------------------------------------------------------

When conditions don't fit on a single line, break before operators,
and indent the new line on the same column as the associated condition.
Use parentheses to make precedence explicit, even when not strictly needed.
Here is an example :

[source,c]
--------------------------------------------------------------------------------
static void
do_something(void)
{
    if (overly_long_stupid_condition_name_that_you_shouldn_t_use
        && another_overly_long_stupid_condition_name
        && (yet_another_variable_with_an_overly_long_name
            || (a_first_long_variable_name != a_second_long_variable_name))) {
        return;
    }
}
--------------------------------------------------------------------------------

One reason for those rules is to make reviews easier, by pushing code as much
to the left as possible. The code should allow superficial reviews by just
taking a quick look at the left side of the code, e.g. control statements,
most conditions, operators, function names, their first parameter, etc...
A line which reaches the right side marks a spot that may need more careful
review.

Don't write multiple statements on a single line.

BRACES
------

Opening braces are written at the end of lines containing control statements
or struct/union/enum definitions. Closing braces are written on the same
column as their associated control statement. Opening braces for functions
are written on their own line after the arguments. Braces must also be used
for single-line blocks, as this reduces both efforts when adding debugging
code in such blocks and risks when merging conflicting code. In the case of
multi-part statements, closing braces are written one the same line as the
continuation. Here is an example :

[source,c]
--------------------------------------------------------------------------------
void
do_something(void *arg)
{
    if (arg == NULL) {
        return;
    } else {
        print_what_it_is(arg);
    }

    do {
        play_with(arg);
    } while (can_play_with(arg));
}
--------------------------------------------------------------------------------

The main reason for this style is that it allows line compression with
almost no loss of readability, since it is easy to identify where blocks
start.

SPACES
------

Spaces are used around most keywords. The exceptions are sizeof, typeof,
alignof, and pass:[__attribute__], because of their similarity with
functions. These exceptions must be used with parentheses. Spaces are also
used around operators, except unary operators. For example :

[source,c]
--------------------------------------------------------------------------------
if (!skip_copy && (memcmp(&a, &b, sizeof(a)) != 0)) {
    memcpy(&a, &b, sizeof(a));
}
--------------------------------------------------------------------------------

When declaring pointer variables, use a space before "`*`", but not after,
so that the "`*`" character and the variable name are adjacent. The main
reason is that, while pointers are variables, with a type of their own,
they are a special kind of variables, where the pointer nature is part
of the variable, rather than just the type. Another is to reduce mistakes
when declaring several variables on the same line. On the other hand, when
writing functions returning pointers, use spaces both before and after
"`*`". The reason is to always clearly separate returned types from the
function name. Here is an example :

[source,c]
--------------------------------------------------------------------------------
static struct my_type * my_function(struct my_type *var);

/* ... */

static struct my_type *
my_function(struct my_type *var)
{
    struct my_type *a, tmp;

    a = do_something(var, &tmp);
    return a;
}
--------------------------------------------------------------------------------

Don't leave trailing spaces at the end of lines.

NAMES
-----

First of all, use underscores instead of camel case to separate words
in compound names. Function and variable names are in lower case. Macro
names generally are in upper case, except for macros which behave
strictly like functions and could be replaced with inline functions
with no API change.

There are two ways to name symbols, depending on whether they're global
or not. Global symbols, either private (declared static) or public
(part of the publically exposed interface), must always be prefixed with
the namespace of the module they belong to. This makes it easy to know
that a symbol is global and where to find it in the project. It also
makes it possible to move definitions between the opaque implementation
and header files with few diffs. Names for local variables should be
short, with no prefixes, since prefixes are used to add context, and
local variables are confined to the current context.

When a module defines an object type, the type name immediately follows
the module name. Functions applying to objects (methods) are named by
adding the method name to the object type name. The name of helper
functions and methods is simply added at the end of the main function
that calls them.

Here are some examples :

[source,c]
--------------------------------------------------------------------------------
/*
 * Object type "cpu_pool" of module "kmem".
 */
struct kmem_cpu_pool;

/*
 * Method "init" of object type "cpu_pool" of module "kmem".
 */
static void kmem_cpu_pool_init(struct kmem_cpu_pool *cpu_pool,
                               struct kmem_cache *cache);

/*
 * Object type "cache" of module "kmem".
 */
struct kmem_cache;

/*
 * Helper function "verify" of method "alloc" of object type "cache" of
 * module "kmem".
 */
static void kmem_cache_alloc_verify(struct kmem_cache *cache, void *buf,
                                    int construct);

/*
 * Method "alloc" of object type "cache" of module "kmem".
 */
void *
kmem_cache_alloc(struct kmem_cache *cache)
{
    struct kmem_cpu_pool *cpu_pool;
    int filled, verify;
    void *buf;

    /* ... */;
}

/*
 * Function "info" of module "kmem".
 */
void kmem_info(void);
--------------------------------------------------------------------------------

FUNCTIONS
---------

Functions should do one thing, and do it well. Their name should be
carefully chosen to best reflect their operation. Ideally, functions
should be short enough to fit in a "page", i.e. not much more than
25 lines. The real metric developers should use to decide whether to
break a function or not is the number of variables, including parameters.
Assuming most people can remember around 5 things at the same time, you
should break functions when the number of variables gets higher than
this value. Variables such as a buffer pointer and its size can be
considered a single variable.

Do not hesitate to break functions down when things get even slightly
complicated. If that helps, remember that static functions can easily
be inlined by the compiler. See <<inline_functions,inline functions>>.

Always name arguments in function prototypes.

Common call protocols
~~~~~~~~~~~~~~~~~~~~~

Functions should match one of the following call protocols :

type get_value(...)::
  Accessor with no side effect.
void do_something(...)::
  Function that cannot fail.
struct my_struct * my_struct_lookup(...)::
  Function that returns an object, or NULL if an error occurred.
int do_something(...)::
  Function that returns an error code, unless stated otherwise.

It's easy to know when to return an object, or an error and the
object through a pointer argument : if there is a single possible
error code, let a NULL value encode that error, otherwise return
it explicitely :

struct my_struct * my_struct_create(...)::
  Return NULL if an error occurs, which may only be ENOMEM.
int my_struct_create(struct my_struct **my_structp, ...)::
  Return an error (ENOMEM or something else) if creation fails, otherwise
  pass the new object to the caller through the double pointer argument
  and return 0.

Methods, which are functions invoked on an object instance, must be
defined so that their first argument is always the object instance
on which the method is invoked.

Unconditional branch statements
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Developers are encouraged to use unconditional branches in cases where
they contribute to maintaining complexity low. Such cases include return
on invalid argument, breaking or continuing simple loops, and centralized
error handling. Note that this includes the *goto* statement. The rationale,
beyond making error handling code common, is to keep the indentation level
low. The main code flow, with the lowest indentation level, should match
the most likely case. The compiler often uses heuristics based on keywords
such as *return* or *goto* which are applied to the conditions of the
containing block. You may also use the *likely* and *unlikely* macros
to give hints about branches to the compiler in performance critical
paths.

Here is an example for object creation :

[source,c]
--------------------------------------------------------------------------------
static int
obj_create(struct obj **objp, int var)
{
    struct subobj *subobj;
    struct obj *obj;
    int error;

    obj = kmem_cache_alloc(&obj_cache);

    if (obj == NULL) {
        return ENOMEM;
    }

    error = subobj_create(&subobj);

    if (error) {
        goto error_subobj;
    }

    error = obj_check_var(var);

    if (error) {
        goto error_var;
    }

    obj_init(obj, subobj, var);
    *objp = obj;
    return 0;

error_var:
    subobj_destroy(subobj);
error_subobj:
    kmem_cache_free(&obj_cache, obj);
    return error;
}
--------------------------------------------------------------------------------

Local variables
~~~~~~~~~~~~~~~

Local variables must be declared at the beginning of their scope. An empty
line separates them from the function body. A notable exception is iterators,
which may be declared inside loop statements.

Common functions and methods
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The following list can be used to easily find appropriate standard names
for the most common operations.

*bootstrap*::
  This function is used for early module initialization. It should only
  exist if initialization must be broken down into multiple steps. If
  there is a single initialization step, run it in the *setup* function.
*setup*::
  This function is used for module initialization.
*init*::
  Object initialization that may not fail (e.g. without memory allocation).
*build*::
  Object construction, i.e. initialization that may fail.
*cleanup*::
  Object clean-up, releasing internal resources but not the object itself.
*create*::
  Object creation, including both allocation and construction.
*destroy*::
  Object destruction, releasing all resources including the object itself.
*ref*::
  Add a reference to an object.
*unref*::
  Remove a reference from an object, destroying it if there are no more
  references.
*acquire* or *lock*::
  Acquire exclusive access to an object.
*release* or *unlock*::
  Release exclusive access to an object.
*add*::
  Add an object to a container.
*remove*::
  Remove an object from a container.
*lookup*::
  Look up an object in a container.

[[inline_functions]]
Inline functions
~~~~~~~~~~~~~~~~

Do not abuse the inline keyword. First of all, this keyword is only a
hint for the compiler, with no guarantee that a function will actually
be inlined in the generated code. In addition, decent compilers can
already inline functions without the presence of the keyword. Private
functions (declared static) are easily inlined because the compiler
knows it doesn't need to produce an externally visible symbol. Besides,
with link-time optimizations (LTO), public functions can also be inlined
or even removed if unused. As a result, use inline for a few performance
critical short functions only.

Passing arrays as arguments
~~~~~~~~~~~~~~~~~~~~~~~~~~~

The C language automatically converts arrays to pointers when passed as
function arguments. As a result, declaring an argument as an array is
misleading. In particular, it may give the impression that the sizeof
operator may be used safely to get the size of the array, when it
actually always returns the size of a pointer. Therefore, declaring
arguments as arrays is strictly forbidden.

GIT COMMITS
-----------

Commits should be atomic, which means a single commit should focus on
one functional modification. The size of the diff doesn't matter.

The log format complies with the standard Git format, i.e. the log
must start with a single line describing the changes, followed by
an empty line and more details if necessary. Since any commit may be
sent as email, try to limit lines to around 70 characters, so that
there is room for replies before reaching/exceeding 80 characters.
In addition to the standard Git format, the first line should start
with the logical path of a module, e.g. *kern/kmem* or *x86/pmap*
for architecture-specific modules, when changes are local to one
or a few modules, which should be the case most of the time. For
example :

--------------------------------------------------------------------------------
kern/kmem: undefine KMEM_VERIFY

That macro was left over during the slab allocator rework.
--------------------------------------------------------------------------------

The first line being a short description, usable as an email subject,
there is no need for a final dot. This also keeps it slightly shorter.

--------------------------------------------------------------------------------
kern/{sleepq,turnstile}: handle spurious wakeups
--------------------------------------------------------------------------------

This format is based on brace expansion in the bash shell.

MISCELLANEOUS
-------------

*typedef* usage
~~~~~~~~~~~~~~~

Usage of the *typedef* keyword is generally avoided. It is used in tricky
situations, such as architecture-specific integer types, function pointers,
and truely opaque data (none of which exist at the time of this writing).
This rule is driven by the need to know as much as possible the nature of
the data being processed. Readers should quickly be able to know whether
a variable is an integer or a structure (or a union, which can cause bad
surprises), and of course if it's a pointer. This could be done with a
naming scheme, but that would only add unnecessary rules.

Developers are allowed to use *typedef* for function pointers because,
unlike a structure, without *typedef* a function pointer type has no name.
It is strongly advised to end the name of the type with the suffix _fn_t.

*sizeof* usage
~~~~~~~~~~~~~~

One of the pillars of robust C code is correct usage of the *sizeof*
operator. The main rule here is to always use *sizeof* on variables,
not types. In addition, when iterating on arrays, use the *ARRAY_SIZE*
macro, which can be thought of as *sizeof* in terms of items rather
than bytes (technically characters). It is important that sizes are
directly related to the data being processed, instead of e.g. reusing
the macro used to declare an array again in the iteration code.

Boolean Coercion
~~~~~~~~~~~~~~~~

Boolean coercion should only be used when the resulting text is semantically
valid, i.e. it can be understood that the expression is either true or false.
For example :

[source,c]
--------------------------------------------------------------------------------
int error;

error = do_something();

/* Valid */
if (error) {
    if (error != EAGAIN) {
        printf("unexpected error\n");
    }

    return error;
}

int color;

color = get_color();

/* Invalid */
if (!color) {
    print_black();
} else if (color == 1) {
    print_red();
}

--------------------------------------------------------------------------------

There are historical uses of the *int* type for boolean values, but all of
them should be converted to the C99 *bool* type.

Side effects and conditions
~~~~~~~~~~~~~~~~~~~~~~~~~~~

Conditions must never be made of expressions with side effects. This
completely removes the need to think about short-circuit evaluations.

Increment/decrement operators
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Increment and decrement operators may never be used inside larger expressions.
Their usage as expression-3 of a for loop is considered as an entire expression
and doesn't violate this rule. The rationale is to avoid tricky errors related
to sequence points. Since such operators may not be used inside larger
expressions, there is no difference between prefix and postfix operators.
The latter are preferred because they look more object-oriented, somewhat
matching the object.method() syntax.

Function-like macros with local variables
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Variable shadowing occurs in function-like macros if one of their local
variables has the same name as one of the arguments. To avoid such situations,
local variables in function-like macros must be named with an underscore
suffix. This naming scheme is reserved for function-like macro variables.

SEE
---

manpage:intro

{x15-operating-system}

{the-art-of-unix-programming}


code:
XBUILD(9)
========
:doctype:       manpage
:man source:    X15
:man manual:    X15 build system

NAME
----

xbuild - The kernel build system

DESCRIPTION
-----------

This document describes the build system of the kernel. The build system is
the software used to generate the configuration, to build the kernel, its
documentation, and install generated files.

USAGE
-----

The build system is meant to be used directly from the root directory.

Online help
~~~~~~~~~~~

In order to obtain online help from the build system, use the following
command :

[source,sh]
--------------------------------------------------------------------------------
$ make help
--------------------------------------------------------------------------------

The output of this command is a list of make targets to use to trigger
specific actions, such as generating the kernel configuration, building
the kernel, or the documentation.

Configuration
~~~~~~~~~~~~~

Before building the kernel, its configuration must be generated. The current
configuration is stored into a file named .config inside the root directory.
Most configuration targets generate this .config file. Some such as *oldconfig*
reuse an existing .config file placed by the user before invoking the build
system.

Default configurations
^^^^^^^^^^^^^^^^^^^^^^

A default configuration can be generated with the *defconfig* target. It
selects a default configuration depending on the target architecture. In
addition, each architecture may provide more predefined configurations,
all reported by the online help.

You may create your own default configuration with the *savedefconfig*
target, which creates a file named defconfig inside the root directory.
This file may then be renamed and added to the list of architecture-specific
default configurations.

Cleaning
~~~~~~~~

The following targets may be used to clean the working tree :

*clean*::
  This target removes most generated files, such as the kernel, any object
  file used to build the kernel, as well as the generated documentation files.
  It ignores the current configuration.
*distclean*::
  This target removes all generated files, including the configuration.

Building
~~~~~~~~

If no target is passed, or if the target is *all* or *x15*, the kernel is
built. There are several ways to influence a build in addition to the
configuration. Builds are incremental, meaning that, when a source file
is modified, the build system only rebuilds files that depend on the
modified source. The build system itself as well as the configuration
are considered global dependencies, so that any modification to either
will make all generated files obsolete.

Parallel builds
^^^^^^^^^^^^^^^

In order to speed up builds, it is possible to make them parallel. This
only has a real effect if your machine has multiple processors. For example :

[source,sh]
--------------------------------------------------------------------------------
make -j4
--------------------------------------------------------------------------------

If unsure about the value, use the number of available processors.

Verbosity
^^^^^^^^^

By default, or if the _V_ variable is set to 0, the build is quiet, only
reporting a short name of actions along with their target file. If the _V_
variable is set to 1, the build is verbose, showing all commands with their
arguments.

Compiler and flags
^^^^^^^^^^^^^^^^^^

In order to make the kernel easy to integrate in meta builders such as
distribution packaging systems, the compiler and its flags may be given
at configuration time through the traditional _CC_ and _CFLAGS_ variables.
For example :

[source,sh]
--------------------------------------------------------------------------------
make i386_defconfig CC=clang CFLAGS="-Os -march=geode"
--------------------------------------------------------------------------------

Out-of-tree builds
^^^^^^^^^^^^^^^^^^

The kernel may be built outside the working tree. In order to perform such a
build, simply use the -f make option with a path to the root Makefile.
For example :

[source,sh]
--------------------------------------------------------------------------------
mkdir build
cd build
make -f /path/to/x15/Makefile defconfig
make -f /path/to/x15/Makefile -j4 x15
--------------------------------------------------------------------------------

Installation
^^^^^^^^^^^^

The various *install* targets are used to install the kernel and its
documentation. The installation process can be altered with the _DESTDIR_
and _PREFIX_ variables. The _DESTDIR_ variable is normally empty, but can
be set to the root of a staging directory tree. This is particularly useful
when building images for embedded systems. The _PREFIX_ variable has the
value "/usr/local" by default, and may be changed to another insallation
path relative to _DESTDIR_.

DEVELOPMENT
-----------

Configuration
~~~~~~~~~~~~~

The configuration part of the build system is known as _kconfig_, originally
imported from the Linux kernel. Description of the format used in Kconfig
files can be found as part of the Linux kernel documentation. Module options
are however not supported.

Makefiles
~~~~~~~~~

When adding or removing source files to/from the project, the _x15_SOURCES-y_
variable should be updated accordingly. The reason for such a name is that it
makes conditional compilation very easy to achieve. When adding a source file
that should be built only when an option is enabled, use the following syntax :

[source,make]
--------------------------------------------------------------------------------
x15_SOURCES-$(CONFIG_OPTION) += path/to/source.c
--------------------------------------------------------------------------------

SEE
---

manpage:intro

{the-kconfig-language}

license: mit


code:
/*
 * Copyright (c) 2010 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef ASSERT_H
#define ASSERT_H

#define static_assert _Static_assert

#ifdef NDEBUG

/*
 * The assert() macro normally doesn't produce side effects when turned off,
 * but this may result in many "set but not used" warnings. Using sizeof()
 * silences these warnings without producing side effects.
 */
#define assert(expression) ((void)sizeof(expression))

#else /* NDEBUG */

#include <kern/macros.h>
#include <kern/panic.h>

/*
 * Panic if the given expression is false.
 */
#define assert(expression)                                          \
MACRO_BEGIN                                                         \
    if (unlikely(!(expression))) {                                  \
        panic("assertion (%s) failed in %s:%d, function %s()",      \
              __QUOTE(expression), __FILE__, __LINE__, __func__);   \
    }                                                               \
MACRO_END

#endif /* NDEBUG */

#endif /* ASSERT_H */


code:
/*
 * Copyright (c) 2018 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef ERRNO_H
#define ERRNO_H

#define ENOMEM              1
#define EAGAIN              2
#define EINVAL              3
#define EBUSY               4
#define EFAULT              5
#define ENODEV              6
#define EEXIST              7
#define EIO                 8
#define ESRCH               9
#define ETIMEDOUT           10
#define ENOENT              11

#endif /* ERRNO_H */


code:
/*
 * Copyright (c) 2010-2014 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef LIMITS_H
#define LIMITS_H

#define CHAR_BIT 8

#ifdef __LP64__
#define LONG_BIT 64
#else /* __LP64__ */
#define LONG_BIT 32
#endif /* __LP64__ */

#endif /* LIMITS_H */


code:
/*
 * Copyright (c) 2017 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef STDIO_H
#define STDIO_H

#include <kern/fmt.h>
#include <kern/printf.h>

#ifndef EOF
#define EOF (-1)
#endif

void console_putchar(char c);
char console_getchar(void);

#define getchar console_getchar
#define putchar console_putchar

#define sprintf     fmt_sprintf
#define snprintf    fmt_snprintf
#define vsprintf    fmt_vsprintf
#define vsnprintf   fmt_vsnprintf

#define sscanf      fmt_sscanf
#define vsscanf     fmt_vsscanf

#endif /* STDIO_H */


code:
/*
 * Copyright (c) 2017 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef STRING_H
#define STRING_H

#include <kern/string.h>

#endif /* STRING_H */


code:
menu "General setup"

config SMP
	bool "Multiprocessor support"
	default y
	---help---
	  Enable support for machines with multiple processors.

config MAX_CPUS
	int "Maximum number of supported CPUs" if SMP
	range 2 512 if SMP
	default "1" if !SMP
	default "128" if SMP
	---help---
	  Maximum number of supported processors.

config CLOCK_FREQ
	int "Low resolution clock frequency"
	range 100 1000
	default 200
	---help---
	  The low resolution clock frequency determines how often low
	  resolution clocks interrupt processors. These clocks drive
	  the timer system. Low values increase throughput and latencies,
	  whereas high values reduce throughput and latencies.

	  The value must be usable as an integer divisor for 1000, with
	  no remainder.

	  Recommended values are 100 for throughput, 1000 for low
	  latencies, and 200 or 250 for a good balance between throughput
	  and latencies.

choice
	prompt "Mutex implementation"
	default MUTEX_PLAIN
	---help---
	  A mutex is a sleeping synchronization object used throughout the
	  kernel and available to kernel applications. As a result, this
	  option affects all mutex users.

	  If in doubt, choose the plain implementation.

config MUTEX_ADAPTIVE
	bool "Adaptive spinning mutex"
	---help---
	  Adaptive spinning mutex, spinning instead of sleeping if the owner
	  is running, in the hope the critical section is short and the mutex
	  will be unlocked soon, to avoid expensive sleep/wakeup operations.
	  This implementation should improve overall performance at the cost
	  of increased latencies.

config MUTEX_PI
	bool "Mutex with priority inheritance"
	---help---
	  Real-time mutex with priority inheritance. This implementation
	  should improve latencies at the cost of overall performance.

config MUTEX_PLAIN
	bool "Plain mutex"
	---help---
	  Default implementation, immediately sleeping on contention.

endchoice

config RCU_WINDOW_CHECK_INTERVAL
	int "Interval between RCU window checks"
	range 1 100
	default 10
	---help---
	  Time (in milliseconds) between two RCU window checks.

	  The RCU system keeps memory used by read-side critical sections
	  until it is safe to release it, which can only be determined when
	  checking windows. As a result, checking windows more frequently
	  may help lower latencies on synchronous RCU waits, and in turn,
	  the amount of memory pending release, at the cost of increased
	  CPU overhead.

config SHELL
	bool "Embedded shell"
	default n
	---help---
	  Enable the embedded shell.

	  The embedded shell is mostly used for diagnostics.

config THREAD_STACK_GUARD
	bool "Thread stack guard pages"
	---help---
	  Enable the use of guard pages around kernel thread stacks to catch
	  overflows. Note that this feature wastes precious kernel virtual
	  memory and has some overhead during thread creation and destruction.

	  If unsure, disable.

config THREAD_MAX_TSD_KEYS
	int "Maximum number of thread-specific data (TSD) keys"
	default 0
	---help---
	  This option is intended for application code embedded in the kernel
	  which may use TSD. The kernel itself never uses them. A value of 0
	  completely disables TSD support.

	  If unsure, set to 0.

config PERFMON
	def_bool n

config PERFMON_MAX_PMCS
	int "Number of performance monitoring counters"
	default 8
	depends on PERFMON
	---help---
	  Number of performance monitoring counters.

	  This value affects the minimum duration of some critical sections
	  that run with interrupts disabled.

endmenu

menu "Debugging"

config KMEM_DEBUG
	bool "Kernel allocator debugging"
	default n
	---help---
	  Enable the debugging of the kernel allocator.

config KMEM_NO_CPU_LAYER
	bool "Disable the CPU layer of the kernel allocator"
	depends on SMP
	default n
	---help---
	  The kernel allocator is made up of two layers named
	  the CPU and slab layers. the CPU layer is responsible
	  for caching objects locally on a processor to reduce
	  contention and cache misses. When reporting kernel
	  memory usage, the CPU layer is ignored, and objects
	  stored in it are accounted as allocated, which can
	  cause confusion when checking the state of the system.

	  This option disables the CPU layer entirely, so that
	  the report usage stats match the actual allocator
	  state.

	  If unsure, disable (leave the CPU layer enabled).

config INIT_DEBUG
	bool "Initialization debugging"
	default n
	---help---
	  Enable the debugging of initialization operations.

config MUTEX_DEBUG
	bool "Mutex debugging"
	default n
	---help---
	  Enable mutex debugging and instrumentation.

config SPINLOCK_DEBUG
	bool "Spinlock debugging"
	default n
	---help---
	  Enable spinlock ownership tracking.

endmenu

path: kern/Kconfig


code:
x15_SOURCES-y += \
        kern/arg.c \
        kern/bitmap.c \
        kern/bulletin.c \
        kern/cbuf.c \
        kern/clock.c \
        kern/condition.c \
        kern/console.c \
        kern/cpumap.c \
        kern/error.c \
        kern/fmt.c \
        kern/init.c \
        kern/intr.c \
        kern/kernel.c \
        kern/kmem.c \
        kern/latomic.c \
        kern/log.c \
        kern/mutex.c \
        kern/panic.c \
        kern/percpu.c \
        kern/plist.c \
        kern/printf.c \
        kern/rbtree.c \
        kern/rcu.c \
        kern/rdxtree.c \
        kern/rtmutex.c \
        kern/semaphore.c \
        kern/shutdown.c \
        kern/sleepq.c \
        kern/spinlock.c \
        kern/sref.c \
        kern/string.c \
        kern/symbol.c \
        kern/syscnt.c \
        kern/task.c \
        kern/thread.c \
        kern/timer.c \
        kern/turnstile.c \
        kern/work.c \
        kern/xcall.c

x15_SOURCES-$(CONFIG_SHELL) += kern/shell.c

x15_SOURCES-$(CONFIG_MUTEX_ADAPTIVE) += kern/mutex/mutex_adaptive.c
x15_SOURCES-$(CONFIG_MUTEX_PLAIN) += kern/mutex/mutex_plain.c

x15_SOURCES-$(CONFIG_PERFMON) += kern/perfmon.c

path: kern/Makefile


code:
/*
 * Copyright (c) 2017 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <string.h>

#include <kern/arg.h>
#include <kern/init.h>
#include <kern/log.h>
#include <kern/macros.h>
#include <kern/panic.h>

/*
 * Internally, all space characters are turned into null bytes so that
 * values returned to callers directly point in the command line string,
 * with no need for dynamic allocation.
 */
static char arg_cmdline[ARG_CMDLINE_MAX_SIZE] __initdata;
static const char *arg_cmdline_end __initdata;

void __init
arg_set_cmdline(const char *cmdline)
{
    strlcpy(arg_cmdline, cmdline, sizeof(arg_cmdline));
}

static int __init
arg_setup(void)
{
    size_t i, length;

    length = strlen(arg_cmdline);

    for (i = 0; i < length; i++) {
        if (arg_cmdline[i] == ' ') {
            arg_cmdline[i] = '\0';
        }
    }

    arg_cmdline_end = arg_cmdline + length;
    return 0;
}

INIT_OP_DEFINE(arg_setup);

void __init
arg_log_info(void)
{
    char cmdline[sizeof(arg_cmdline)];
    size_t i;

    for (i = 0; &arg_cmdline[i] < arg_cmdline_end; i++) {
        cmdline[i] = (arg_cmdline[i] == '\0') ? ' ' : arg_cmdline[i];
    }

    cmdline[i] = '\0';
    log_info("arg: %s", cmdline);
}

static const char * __init
arg_walk(const char *s)
{
    if (s == NULL) {
        s = arg_cmdline;
    } else {
        for (;;) {
            if (s >= arg_cmdline_end) {
                return NULL;
            }

            if (*s == '\0') {
                break;
            }

            s++;
        }
    }

    for (;;) {
        if (s >= arg_cmdline_end) {
            return NULL;
        }

        if (*s != '\0') {
            return s;
        }

        s++;
    }
}

static const char * __init
arg_find_name_end(const char *arg)
{
    const char *end;

    end = strchr(arg, '=');

    if (end == NULL) {
        end = arg + strlen(arg);
    }

    return end;
}

static const char * __init
arg_find(const char *name)
{
    const char *arg, *arg_name_end;
    size_t arg_name_length, name_length;

    name_length = strlen(name);
    assert(name_length != 0);

    for (arg = arg_walk(NULL); arg != NULL; arg = arg_walk(arg)) {
        arg_name_end = arg_find_name_end(arg);
        arg_name_length = arg_name_end - arg;

        if ((arg_name_length == name_length)
            && (memcmp(arg, name, name_length) == 0)) {
            return arg;
        }
    }

    return NULL;
}

bool __init
arg_present(const char *name)
{
    return (arg_find(name) != NULL);
}

const char * __init
arg_value(const char *name)
{
    const char *arg, *value;

    arg = arg_find(name);

    if (arg == NULL) {
        return NULL;
    }

    value = strchr(arg, '=');

    if (value == NULL) {
        return "";
    }

    return value + 1;
}


code:
/*
 * Copyright (c) 2017 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *
 * Kernel command line argument parsing.
 *
 * Arguments are separated by spaces (there is no escape character).
 * They can be of the form "name" when used as boolean values (present
 * or not), or "name=value".
 */

#ifndef KERN_ARG_H
#define KERN_ARG_H

#include <stdbool.h>

#include <kern/init.h>

#define ARG_CMDLINE_MAX_SIZE 256

/*
 * Set the command line string.
 *
 * This function must be called before calling the kernel main entry point.
 */
void arg_set_cmdline(const char *cmdline);

/*
 * Log command line information.
 */
void arg_log_info(void);

/*
 * Return true if an argument with the given name is present in the
 * command line.
 */
bool arg_present(const char *name);

/*
 * Return the value of the argument with the given name in the command
 * line.
 *
 * If the argument form is "name", the empty string is returned. If the
 * argument isn't present, NULL is returned.
 */
const char * arg_value(const char *name);

/*
 * This init operation provides :
 *  - command line arguments can be retrieved
 */
INIT_OP_DECLARE(arg_setup);

#endif /* KERN_ARG_H */


code:
/*
 * Copyright (c) 2018 Richard Braun.
 * Copyright (c) 2017-2018 Agustina Arzille.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *
 * Type-generic memory-model-aware atomic operations.
 *
 * For portability reasons, this interface restricts atomic operation
 * sizes to 32-bit and 64-bit.
 *
 * Some configurations may not support 64-bit operations. Check if the
 * ATOMIC_HAVE_64B_OPS macro is defined to find out.
 *
 * TODO Replace mentions of "memory barriers" throughout the code with
 * C11 memory model terminology.
 */

#ifndef KERN_ATOMIC_H
#define KERN_ATOMIC_H

#if !defined(CONFIG_SMP) && defined(CONFIG_LATOMIC_REPLACE_ATOMIC_ON_UP)
#define ATOMIC_USE_LATOMIC
#endif

#ifdef ATOMIC_USE_LATOMIC

#include <kern/latomic.h>

/*
 * Local atomic operations always provide 64-bit support, by using the
 * generic versions which disable interrupts as a last resort.
 */
#define ATOMIC_HAVE_64B_OPS

/*
 * Memory orders.
 *
 * XXX Consume ordering is currently aliased to acquire.
 */
#define ATOMIC_RELAXED          LATOMIC_RELAXED
#define ATOMIC_CONSUME          LATOMIC_ACQUIRE
#define ATOMIC_ACQUIRE          LATOMIC_ACQUIRE
#define ATOMIC_RELEASE          LATOMIC_RELEASE
#define ATOMIC_ACQ_REL          LATOMIC_ACQ_REL
#define ATOMIC_SEQ_CST          LATOMIC_SEQ_CST

#define atomic_load             latomic_load
#define atomic_store            latomic_store

#define atomic_swap             latomic_swap
#define atomic_cas              latomic_cas

#define atomic_fetch_add        latomic_fetch_add
#define atomic_fetch_sub        latomic_fetch_sub
#define atomic_fetch_and        latomic_fetch_and
#define atomic_fetch_or         latomic_fetch_or
#define atomic_fetch_xor        latomic_fetch_xor

#define atomic_add              latomic_add
#define atomic_sub              latomic_sub
#define atomic_and              latomic_and
#define atomic_or               latomic_or
#define atomic_xor              latomic_xor

#define atomic_fence            latomic_fence

#else /* ATOMIC_USE_LATOMIC */

#include <assert.h>
#include <stdbool.h>

#include <kern/macros.h>

/*
 * Supported memory orders.
 */
#define ATOMIC_RELAXED  __ATOMIC_RELAXED
#define ATOMIC_CONSUME  __ATOMIC_CONSUME
#define ATOMIC_ACQUIRE  __ATOMIC_ACQUIRE
#define ATOMIC_RELEASE  __ATOMIC_RELEASE
#define ATOMIC_ACQ_REL  __ATOMIC_ACQ_REL
#define ATOMIC_SEQ_CST  __ATOMIC_SEQ_CST

#include <kern/atomic_i.h>

#define atomic_load(ptr, memorder)                                          \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    ((typeof(*(ptr)))atomic_select(ptr, load)(ptr, memorder));              \
MACRO_END

#define atomic_store(ptr, val, memorder)                                    \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    atomic_select(ptr, store)(ptr, val, memorder);                          \
MACRO_END

/*
 * For compare-and-swap, deviate a little from the standard, and only
 * return the value before the comparison, leaving it up to the user to
 * determine whether the swap was actually performed or not.
 *
 * Also, note that the memory order in case of failure is relaxed. This is
 * because atomic CAS is typically used in a loop. However, if a different
 * code path is taken on failure (rather than retrying), then the user
 * should be aware that a memory fence might be necessary.
 */
#define atomic_cas(ptr, oval, nval, memorder)                               \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    ((typeof(*(ptr)))atomic_select(ptr, cas)(ptr, oval, nval, memorder));   \
MACRO_END

#define atomic_swap(ptr, val, memorder)                                     \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    ((typeof(*(ptr)))atomic_select(ptr, swap)(ptr, val, memorder));         \
MACRO_END

#define atomic_fetch_add(ptr, val, memorder)                                \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    ((typeof(*(ptr)))atomic_select(ptr, fetch_add)(ptr, val, memorder));    \
MACRO_END

#define atomic_fetch_sub(ptr, val, memorder)                                \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    ((typeof(*(ptr)))atomic_select(ptr, fetch_sub)(ptr, val, memorder));    \
MACRO_END

#define atomic_fetch_and(ptr, val, memorder)                                \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    ((typeof(*(ptr)))atomic_select(ptr, fetch_and)(ptr, val, memorder));    \
MACRO_END

#define atomic_fetch_or(ptr, val, memorder)                                 \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    ((typeof(*(ptr)))atomic_select(ptr, fetch_or)(ptr, val, memorder));     \
MACRO_END

#define atomic_fetch_xor(ptr, val, memorder)                                \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    ((typeof(*(ptr)))atomic_select(ptr, fetch_xor)(ptr, val, memorder));    \
MACRO_END

#define atomic_add(ptr, val, memorder)                                      \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    atomic_select(ptr, add)(ptr, val, memorder);                            \
MACRO_END

#define atomic_sub(ptr, val, memorder)                                      \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    atomic_select(ptr, sub)(ptr, val, memorder);                            \
MACRO_END

#define atomic_and(ptr, val, memorder)                                      \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    atomic_select(ptr, and)(ptr, val, memorder);                            \
MACRO_END

#define atomic_or(ptr, val, memorder)                                       \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    atomic_select(ptr, or)(ptr, val, memorder);                             \
MACRO_END

#define atomic_xor(ptr, val, memorder)                                      \
MACRO_BEGIN                                                                 \
    assert(atomic_ptr_aligned(ptr));                                        \
    atomic_select(ptr, xor)(ptr, val, memorder);                            \
MACRO_END

#define atomic_fence(memorder) __atomic_thread_fence(memorder)

#endif /* ATOMIC_USE_LATOMIC */

#endif /* KERN_ATOMIC_H */


code:
/*
 * Copyright (c) 2018 Richard Braun.
 * Copyright (c) 2017 Agustina Arzille.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *
 * Architecture-specific code may override any of the type-specific
 * functions by defining a macro of the same name.
 */

#ifndef KERN_ATOMIC_I_H
#define KERN_ATOMIC_I_H

#include <stdbool.h>
#include <stdint.h>

#include <kern/atomic_types.h>
#include <kern/macros.h>
#include <machine/atomic.h>

#define ATOMIC_ALIGN(ptr) MIN(sizeof(*(ptr)), sizeof(ptr))
#define atomic_ptr_aligned(ptr) P2ALIGNED((uintptr_t)(ptr), ATOMIC_ALIGN(ptr))

/*
 * This macro is used to select the appropriate function for the given
 * operation. The default expression is selected for pointer types.
 * In order to avoid confusing errors, all built-in types are explicitely
 * listed, so that unsupported ones don't select pointer operations.
 * Instead, they select a function with an explicit name indicating
 * an invalid type.
 */
#define atomic_select(ptr, op)                      \
_Generic(*(ptr),                                    \
                 float: atomic_invalid_type,        \
                double: atomic_invalid_type,        \
           long double: atomic_invalid_type,        \
                  bool: atomic_invalid_type,        \
                  char: atomic_invalid_type,        \
           signed char: atomic_invalid_type,        \
         unsigned char: atomic_invalid_type,        \
                 short: atomic_invalid_type,        \
        unsigned short: atomic_invalid_type,        \
                   int: atomic_ ## op ## _32,       \
          unsigned int: atomic_ ## op ## _32,       \
                  long: atomic_ ## op ## _ul,       \
         unsigned long: atomic_ ## op ## _ul,       \
             long long: atomic_ ## op ## _64,       \
    unsigned long long: atomic_ ## op ## _64,       \
               default: atomic_ ## op ## _ptr)

void atomic_invalid_type(void);

/* atomic_load */

#ifndef atomic_load_32
static inline unsigned int
atomic_load_32(union atomic_constptr_32 ptr, int memorder)
{
    return __atomic_load_n(ptr.ui_ptr, memorder);
}
#endif /* atomic_load_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_load_64
static inline unsigned long long
atomic_load_64(union atomic_constptr_64 ptr, int memorder)
{
    return __atomic_load_n(ptr.ull_ptr, memorder);
}
#endif /* atomic_load_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_load_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_load_ul          atomic_load_64
#else /* __LP64__ */
#define atomic_load_ul          atomic_load_32
#endif /* __LP64__ */

#define atomic_load_ptr         atomic_load_ul

/* atomic_store */

#ifndef atomic_store_32
static inline void
atomic_store_32(union atomic_ptr_32 ptr, union atomic_val_32 val, int memorder)
{
    return __atomic_store_n(ptr.ui_ptr, val.ui, memorder);
}
#endif /* atomic_store_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_store_64
static inline void
atomic_store_64(union atomic_ptr_64 ptr, union atomic_val_64 val, int memorder)
{
    return __atomic_store_n(ptr.ull_ptr, val.ull, memorder);
}
#endif /* atomic_store_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_store_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_store_ul         atomic_store_64
#else /* __LP64__ */
#define atomic_store_ul         atomic_store_32
#endif /* __LP64__ */

#define atomic_store_ptr        atomic_store_ul

/* atomic_cas */

#define atomic_cas_n(ptr, oval, nval, memorder)                     \
MACRO_BEGIN                                                         \
    typeof(oval) oval_;                                             \
                                                                    \
    oval_ = (oval);                                                 \
    __atomic_compare_exchange_n(ptr, &oval_, (nval), false,         \
                                memorder, __ATOMIC_RELAXED);        \
    oval_;                                                          \
MACRO_END

#ifndef atomic_cas_32
static inline unsigned int
atomic_cas_32(union atomic_ptr_32 ptr, union atomic_val_32 oval,
              union atomic_val_32 nval, int memorder)
{
    return atomic_cas_n(ptr.ui_ptr, oval.ui, nval.ui, memorder);
}
#endif /* atomic_cas_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_cas_64
static inline unsigned long long
atomic_cas_64(union atomic_ptr_64 ptr, union atomic_val_64 oval,
              union atomic_val_64 nval, int memorder)
{
    return atomic_cas_n(ptr.ull_ptr, oval.ull, nval.ull, memorder);
}
#endif /* atomic_cas_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_cas_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_cas_ul           atomic_cas_64
#else /* __LP64__ */
#define atomic_cas_ul           atomic_cas_32
#endif /* __LP64__ */

#define atomic_cas_ptr          atomic_cas_ul

/* atomic_swap */

#ifndef atomic_swap_32
static inline unsigned int
atomic_swap_32(union atomic_ptr_32 ptr, union atomic_val_32 val, int memorder)
{
    return __atomic_exchange_n(ptr.ui_ptr, val.ui, memorder);
}
#endif /* atomic_swap_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_swap_64
static inline unsigned long long
atomic_swap_64(union atomic_ptr_64 ptr, union atomic_val_64 val, int memorder)
{
    return __atomic_exchange_n(ptr.ull_ptr, val.ull, memorder);
}
#endif /* atomic_swap_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_swap_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_swap_ul          atomic_swap_64
#else /* __LP64__ */
#define atomic_swap_ul          atomic_swap_32
#endif /* __LP64__ */

#define atomic_swap_ptr         atomic_swap_ul

/* atomic_fetch_add */

#ifndef atomic_fetch_add_32
static inline unsigned int
atomic_fetch_add_32(union atomic_ptr_32 ptr, union atomic_val_32 val,
                    int memorder)
{
    return __atomic_fetch_add(ptr.ui_ptr, val.ui, memorder);
}
#endif /* atomic_fetch_add_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_fetch_add_64
static inline unsigned long long
atomic_fetch_add_64(union atomic_ptr_64 ptr, union atomic_val_64 val,
                    int memorder)
{
    return __atomic_fetch_add(ptr.ull_ptr, val.ull, memorder);
}
#endif /* atomic_fetch_add_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_fetch_add_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_fetch_add_ul     atomic_fetch_add_64
#else /* __LP64__ */
#define atomic_fetch_add_ul     atomic_fetch_add_32
#endif /* __LP64__ */

#define atomic_fetch_add_ptr    atomic_fetch_add_ul

/* atomic_fetch_sub */

#ifndef atomic_fetch_sub_32
static inline unsigned int
atomic_fetch_sub_32(union atomic_ptr_32 ptr, union atomic_val_32 val,
                    int memorder)
{
    return __atomic_fetch_sub(ptr.ui_ptr, val.ui, memorder);
}
#endif /* atomic_fetch_sub_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_fetch_sub_64
static inline unsigned long long
atomic_fetch_sub_64(union atomic_ptr_64 ptr, union atomic_val_64 val,
                    int memorder)
{
    return __atomic_fetch_sub(ptr.ull_ptr, val.ull, memorder);
}
#endif /* atomic_fetch_sub_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_fetch_sub_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_fetch_sub_ul     atomic_fetch_sub_64
#else /* __LP64__ */
#define atomic_fetch_sub_ul     atomic_fetch_sub_32
#endif /* __LP64__ */

#define atomic_fetch_sub_ptr    atomic_fetch_sub_ul

/* atomic_fetch_and */

#ifndef atomic_fetch_and_32
static inline unsigned int
atomic_fetch_and_32(union atomic_ptr_32 ptr, union atomic_val_32 val,
                    int memorder)
{
    return __atomic_fetch_and(ptr.ui_ptr, val.ui, memorder);
}
#endif /* atomic_fetch_and_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_fetch_and_64
static inline unsigned long long
atomic_fetch_and_64(union atomic_ptr_64 ptr, union atomic_val_64 val,
                    int memorder)
{
    return __atomic_fetch_and(ptr.ull_ptr, val.ull, memorder);
}
#endif /* atomic_fetch_and_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_fetch_and_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_fetch_and_ul     atomic_fetch_and_64
#else /* __LP64__ */
#define atomic_fetch_and_ul     atomic_fetch_and_32
#endif /* __LP64__ */

#define atomic_fetch_and_ptr    atomic_fetch_and_ul

/* atomic_fetch_or */

#ifndef atomic_fetch_or_32
static inline unsigned int
atomic_fetch_or_32(union atomic_ptr_32 ptr, union atomic_val_32 val,
                   int memorder)
{
    return __atomic_fetch_or(ptr.ui_ptr, val.ui, memorder);
}
#endif /* atomic_fetch_or_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_fetch_or_64
static inline unsigned long long
atomic_fetch_or_64(union atomic_ptr_64 ptr, union atomic_val_64 val,
                   int memorder)
{
    return __atomic_fetch_or(ptr.ull_ptr, val.ull, memorder);
}
#endif /* atomic_fetch_or_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_or_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_fetch_or_ul      atomic_fetch_or_64
#else /* __LP64__ */
#define atomic_fetch_or_ul      atomic_fetch_or_32
#endif /* __LP64__ */

#define atomic_fetch_or_ptr     atomic_fetch_or_ul

/* atomic_fetch_xor */

#ifndef atomic_fetch_xor_32
static inline unsigned int
atomic_fetch_xor_32(union atomic_ptr_32 ptr, union atomic_val_32 val,
                    int memorder)
{
    return __atomic_fetch_xor(ptr.ui_ptr, val.ui, memorder);
}
#endif /* atomic_fetch_xor_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_fetch_xor_64
static inline unsigned long long
atomic_fetch_xor_64(union atomic_ptr_64 ptr, union atomic_val_64 val,
                    int memorder)
{
    return __atomic_fetch_xor(ptr.ull_ptr, val.ull, memorder);
}
#endif /* atomic_fetch_xor_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_xor_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_fetch_xor_ul     atomic_fetch_xor_64
#else /* __LP64__ */
#define atomic_fetch_xor_ul     atomic_fetch_xor_32
#endif /* __LP64__ */

#define atomic_fetch_xor_ptr    atomic_fetch_xor_ul

/* atomic_add */

#ifndef atomic_add_32
static inline void
atomic_add_32(union atomic_ptr_32 ptr, union atomic_val_32 val, int memorder)
{
    __atomic_add_fetch(ptr.ui_ptr, val.ui, memorder);
}
#endif /* atomic_add_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_add_64
static inline void
atomic_add_64(union atomic_ptr_64 ptr, union atomic_val_64 val, int memorder)
{
    __atomic_add_fetch(ptr.ull_ptr, val.ull, memorder);
}
#endif /* atomic_add_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_add_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_add_ul           atomic_add_64
#else /* __LP64__ */
#define atomic_add_ul           atomic_add_32
#endif /* __LP64__ */

#define atomic_add_ptr          atomic_add_ul

/* atomic_sub */

#ifndef atomic_sub_32
static inline void
atomic_sub_32(union atomic_ptr_32 ptr, union atomic_val_32 val, int memorder)
{
    __atomic_sub_fetch(ptr.ui_ptr, val.ui, memorder);
}
#endif /* atomic_sub_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_sub_64
static inline void
atomic_sub_64(union atomic_ptr_64 ptr, union atomic_val_64 val, int memorder)
{
    __atomic_sub_fetch(ptr.ull_ptr, val.ull, memorder);
}
#endif /* atomic_sub_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_sub_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_sub_ul           atomic_sub_64
#else /* __LP64__ */
#define atomic_sub_ul           atomic_sub_32
#endif /* __LP64__ */

#define atomic_sub_ptr          atomic_sub_ul

/* atomic_and */

#ifndef atomic_and_32
static inline void
atomic_and_32(union atomic_ptr_32 ptr, union atomic_val_32 val, int memorder)
{
    __atomic_and_fetch(ptr.ui_ptr, val.ui, memorder);
}
#endif /* atomic_and_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_and_64
static inline void
atomic_and_64(union atomic_ptr_64 ptr, union atomic_val_64 val, int memorder)
{
    __atomic_and_fetch(ptr.ull_ptr, val.ull, memorder);
}
#endif /* atomic_and_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_and_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_and_ul           atomic_and_64
#else /* __LP64__ */
#define atomic_and_ul           atomic_and_32
#endif /* __LP64__ */

#define atomic_and_ptr          atomic_and_ul

/* atomic_or */

#ifndef atomic_or_32
static inline void
atomic_or_32(union atomic_ptr_32 ptr, union atomic_val_32 val, int memorder)
{
    __atomic_or_fetch(ptr.ui_ptr, val.ui, memorder);
}
#endif /* atomic_or_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_or_64
static inline void
atomic_or_64(union atomic_ptr_64 ptr, union atomic_val_64 val, int memorder)
{
    __atomic_or_fetch(ptr.ull_ptr, val.ull, memorder);
}
#endif /* atomic_or_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_or_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_or_ul            atomic_or_64
#else /* __LP64__ */
#define atomic_or_ul            atomic_or_32
#endif /* __LP64__ */

#define atomic_or_ptr           atomic_or_ul

/* atomic_xor */

#ifndef atomic_xor_32
static inline void
atomic_xor_32(union atomic_ptr_32 ptr, union atomic_val_32 val, int memorder)
{
    __atomic_xor_fetch(ptr.ui_ptr, val.ui, memorder);
}
#endif /* atomic_xor_32 */

#ifdef ATOMIC_HAVE_64B_OPS
#ifndef atomic_xor_64
static inline void
atomic_xor_64(union atomic_ptr_64 ptr, union atomic_val_64 val, int memorder)
{
    __atomic_xor_fetch(ptr.ull_ptr, val.ull, memorder);
}
#endif /* atomic_xor_64 */

#else /* ATOMIC_HAVE_64B_OPS */
#define atomic_xor_64 atomic_invalid_type
#endif /* ATOMIC_HAVE_64B_OPS */

#ifdef __LP64__
#define atomic_xor_ul           atomic_xor_64
#else /* __LP64__ */
#define atomic_xor_ul           atomic_xor_32
#endif /* __LP64__ */

#define atomic_xor_ptr          atomic_xor_ul

#endif /* KERN_ATOMIC_I_H */


code:
/*
 * Copyright (c) 2018 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *
 * Isolated type definition used to avoid inclusion circular dependencies.
 *
 * These types are directly used by both the atomic and latomic modules.
 */

#ifndef KERN_ATOMIC_TYPES_H
#define KERN_ATOMIC_TYPES_H

/*
 * After function selection, type genericity is achieved with transparent
 * unions, a GCC extension. Here are a few things to keep in mind :
 *  - all members must have the same representation
 *  - calling conventions are inferred from the first member
 */

#ifdef __LP64__

union atomic_ptr_32 {
    int *i_ptr;
    unsigned int *ui_ptr;
} __attribute__((transparent_union));

union atomic_constptr_32 {
    const int *i_ptr;
    const unsigned int *ui_ptr;
} __attribute__((transparent_union));

union atomic_val_32 {
    int i;
    unsigned int ui;
} __attribute__((transparent_union));

union atomic_ptr_64 {
    void *ptr;
    unsigned long long *ull_ptr;
} __attribute__((transparent_union));

union atomic_constptr_64 {
    const void *ptr;
    const unsigned long long *ull_ptr;
} __attribute__((transparent_union));

union atomic_val_64 {
    void *ptr;
    long l;
    unsigned long ul;
    long long ll;
    unsigned long long ull;
} __attribute__((transparent_union));

#else /* __LP64__ */

union atomic_ptr_32 {
    void *ptr;
    unsigned int *ui_ptr;
} __attribute__((transparent_union));

union atomic_constptr_32 {
    const void *ptr;
    const unsigned int *ui_ptr;
} __attribute__((transparent_union));

union atomic_val_32 {
    void *ptr;
    int i;
    unsigned int ui;
    long l;
    unsigned long ul;
} __attribute__((transparent_union));

union atomic_ptr_64 {
    long long *ll_ptr;
    unsigned long long *ull_ptr;
} __attribute__((transparent_union));

union atomic_constptr_64 {
    const long long *ll_ptr;
    const unsigned long long *ull_ptr;
} __attribute__((transparent_union));

union atomic_val_64 {
    long long ll;
    unsigned long long ull;
} __attribute__((transparent_union));

#endif /* __LP64__ */

#endif /* KERN_ATOMIC_TYPES_H */


code:
/*
 * Copyright (c) 2013-2015 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Upstream site with license notes :
 * http://git.sceen.net/rbraun/librbraun.git/
 */

#include <limits.h>
#include <string.h>

#include <kern/bitmap.h>
#include <kern/bitmap_i.h>

int
bitmap_cmp(const unsigned long *a, const unsigned long *b, int nr_bits)
{
    unsigned long last_a, last_b, mask;
    int n, rv;

    n = BITMAP_LONGS(nr_bits) - 1;

    if (n != 0) {
        rv = memcmp(a, b, n * sizeof(unsigned long));

        if (rv != 0) {
            return rv;
        }

        nr_bits -= n * LONG_BIT;
    }

    last_a = a[n];
    last_b = b[n];

    if (nr_bits != LONG_BIT) {
        mask = (1UL << nr_bits) - 1;
        last_a &= mask;
        last_b &= mask;
    }

    if (last_a == last_b) {
        return 0;
    } else if (last_a < last_b) {
        return -1;
    } else {
        return 1;
    }
}

static inline unsigned long
bitmap_find_next_compute_complement(unsigned long word, int nr_bits)
{
    if (nr_bits < LONG_BIT) {
        word |= (((unsigned long)-1) << nr_bits);
    }

    return ~word;
}

int
bitmap_find_next_bit(const unsigned long *bm, int nr_bits, int bit,
                     int complement)
{
    const unsigned long *start, *end;
    unsigned long word;

    start = bm;
    end = bm + BITMAP_LONGS(nr_bits);

    if (bit >= LONG_BIT) {
        bitmap_lookup(&bm, &bit);
        nr_bits -= ((bm - start) * LONG_BIT);
    }

    word = *bm;

    if (complement) {
        word = bitmap_find_next_compute_complement(word, nr_bits);
    }

    if (bit < LONG_BIT) {
        word &= ~(bitmap_mask(bit) - 1);
    }

    for (;;) {
        bit = __builtin_ffsl(word);

        if (bit != 0) {
            return ((bm - start) * LONG_BIT) + bit - 1;
        }

        bm++;

        if (bm >= end) {
            return -1;
        }

        nr_bits -= LONG_BIT;
        word = *bm;

        if (complement) {
            word = bitmap_find_next_compute_complement(word, nr_bits);
        }
    }
}


code:
/*
 * Copyright (c) 2013-2015 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Upstream site with license notes :
 * http://git.sceen.net/rbraun/librbraun.git/
 *
 *
 * Arbitrary-length bit arrays.
 *
 * Most functions do not check whether the given parameters are valid. This
 * is the responsibility of the caller.
 */

#ifndef KERN_BITMAP_H
#define KERN_BITMAP_H

#include <limits.h>
#include <string.h>

#include <kern/atomic.h>
#include <kern/bitmap_i.h>

#define BITMAP_DECLARE(name, nr_bits) unsigned long name[BITMAP_LONGS(nr_bits)]

int bitmap_cmp(const unsigned long *a, const unsigned long *b, int nr_bits);

static inline void
bitmap_zero(unsigned long *bm, int nr_bits)
{
    int n;

    n = BITMAP_LONGS(nr_bits);
    memset(bm, 0, n * sizeof(unsigned long));
}

static inline void
bitmap_fill(unsigned long *bm, int nr_bits)
{
    int n;

    n = BITMAP_LONGS(nr_bits);
    memset(bm, 0xff, n * sizeof(unsigned long));
}

static inline void
bitmap_copy(unsigned long *dest, const unsigned long *src, int nr_bits)
{
    int n;

    n = BITMAP_LONGS(nr_bits);
    memcpy(dest, src, n * sizeof(unsigned long));
}

static inline void
bitmap_set(unsigned long *bm, int bit)
{
    if (bit >= LONG_BIT) {
        bitmap_lookup(&bm, &bit);
    }

    *bm |= bitmap_mask(bit);
}

static inline void
bitmap_set_atomic(unsigned long *bm, int bit)
{
    if (bit >= LONG_BIT) {
        bitmap_lookup(&bm, &bit);
    }

    atomic_or(bm, bitmap_mask(bit), ATOMIC_RELEASE);
}

static inline void
bitmap_clear(unsigned long *bm, int bit)
{
    if (bit >= LONG_BIT) {
        bitmap_lookup(&bm, &bit);
    }

    *bm &= ~bitmap_mask(bit);
}

static inline void
bitmap_clear_atomic(unsigned long *bm, int bit)
{
    if (bit >= LONG_BIT) {
        bitmap_lookup(&bm, &bit);
    }

    atomic_and(bm, ~bitmap_mask(bit), ATOMIC_RELEASE);
}

static inline int
bitmap_test(const unsigned long *bm, int bit)
{
    if (bit >= LONG_BIT) {
        bitmap_lookup(&bm, &bit);
    }

    return ((*bm & bitmap_mask(bit)) != 0);
}

static inline int
bitmap_test_atomic(const unsigned long *bm, int bit)
{
    if (bit >= LONG_BIT) {
        bitmap_lookup(&bm, &bit);
    }

    return ((atomic_load(bm, ATOMIC_ACQUIRE) & bitmap_mask(bit)) != 0);
}

static inline void
bitmap_and(unsigned long *a, const unsigned long *b, int nr_bits)
{
    int i, n;

    n = BITMAP_LONGS(nr_bits);

    for (i = 0; i < n; i++) {
        a[i] &= b[i];
    }
}

static inline void
bitmap_or(unsigned long *a, const unsigned long *b, int nr_bits)
{
    int i, n;

    n = BITMAP_LONGS(nr_bits);

    for (i = 0; i < n; i++) {
        a[i] |= b[i];
    }
}

static inline void
bitmap_xor(unsigned long *a, const unsigned long *b, int nr_bits)
{
    int i, n;

    n = BITMAP_LONGS(nr_bits);

    for (i = 0; i < n; i++) {
        a[i] ^= b[i];
    }
}

static inline int
bitmap_find_next(const unsigned long *bm, int nr_bits, int bit)
{
    return bitmap_find_next_bit(bm, nr_bits, bit, 0);
}

static inline int
bitmap_find_first(const unsigned long *bm, int nr_bits)
{
    return bitmap_find_next(bm, nr_bits, 0);
}

static inline int
bitmap_find_next_zero(const unsigned long *bm, int nr_bits, int bit)
{
    return bitmap_find_next_bit(bm, nr_bits, bit, 1);
}

static inline int
bitmap_find_first_zero(const unsigned long *bm, int nr_bits)
{
    return bitmap_find_next_zero(bm, nr_bits, 0);
}

#define bitmap_for_each(bm, nr_bits, bit)                       \
for ((bit) = 0;                                                 \
     ((bit) < nr_bits)                                          \
     && (((bit) = bitmap_find_next(bm, nr_bits, bit)) != -1);   \
     (bit)++)

#define bitmap_for_each_zero(bm, nr_bits, bit)                      \
for ((bit) = 0;                                                     \
     ((bit) < nr_bits)                                              \
     && (((bit) = bitmap_find_next_zero(bm, nr_bits, bit)) != -1);  \
     (bit)++)

#endif /* KERN_BITMAP_H */


code:
/*
 * Copyright (c) 2013-2015 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Upstream site with license notes :
 * http://git.sceen.net/rbraun/librbraun.git/
 */

#ifndef KERN_BITMAP_I_H
#define KERN_BITMAP_I_H

#include <limits.h>

#include <kern/macros.h>

#define BITMAP_LONGS(nr_bits) DIV_CEIL(nr_bits, LONG_BIT)

/*
 * Adjust the bitmap pointer and the bit index so that the latter refers
 * to a bit inside the word pointed by the former.
 *
 * Implemented as a macro for const-correctness.
 */
#define bitmap_lookup(bmp, bitp)        \
MACRO_BEGIN                             \
    int i;                              \
                                        \
    i = BITMAP_LONGS(*(bitp) + 1) - 1;  \
    *(bmp) += i;                        \
    *(bitp) -= i * LONG_BIT;            \
MACRO_END

static inline unsigned long
bitmap_mask(int bit)
{
    return (1UL << bit);
}

/*
 * Return the index of the next set bit in the bitmap, starting (and
 * including) the given bit index, or -1 if the bitmap is empty. If
 * complement is true, bits are toggled before searching so that the
 * result is the index of the next zero bit.
 */
int bitmap_find_next_bit(const unsigned long *bm, int nr_bits, int bit,
                         int complement);

#endif /* KERN_BITMAP_I_H */


code:
/*
 * Copyright (c) 2017-2018 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <assert.h>
#include <stdint.h>

#include <kern/bulletin.h>
#include <kern/list.h>
#include <kern/rcu.h>
#include <kern/spinlock.h>
#include <kern/thread.h>

static void
bulletin_sub_init(struct bulletin_sub *sub,
                  bulletin_notif_fn_t notif_fn, void *arg)
{
    sub->notif_fn = notif_fn;
    sub->arg = arg;
}

static void
bulletin_sub_notify(const struct bulletin_sub *sub, uintptr_t value)
{
    sub->notif_fn(value, sub->arg);
}

void
bulletin_init(struct bulletin *bulletin)
{
    spinlock_init(&bulletin->lock);
    list_init(&bulletin->subs);
}

void
bulletin_subscribe(struct bulletin *bulletin, struct bulletin_sub *sub,
                   bulletin_notif_fn_t notif_fn, void *arg)
{
    bulletin_sub_init(sub, notif_fn, arg);

    spinlock_lock(&bulletin->lock);
    list_rcu_insert_tail(&bulletin->subs, &sub->node);
    spinlock_unlock(&bulletin->lock);
}

void
bulletin_unsubscribe(struct bulletin *bulletin, struct bulletin_sub *sub)
{
    spinlock_lock(&bulletin->lock);
    list_rcu_remove(&sub->node);
    spinlock_unlock(&bulletin->lock);

    rcu_wait();
}

void
bulletin_publish(struct bulletin *bulletin, uintptr_t value)
{
    struct bulletin_sub *sub;

    assert(!thread_interrupted());

    rcu_read_enter();

    list_rcu_for_each_entry(&bulletin->subs, sub, node) {
        bulletin_sub_notify(sub, value);
    }

    rcu_read_leave();
}


code:
/*
 * Copyright (c) 2017-2018 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *
 * Minimalist publish-subscribe mechanism.
 */

#ifndef KERN_BULLETIN_H
#define KERN_BULLETIN_H

#include <stdint.h>

#include <kern/macros.h>
#include <kern/work.h>

/*
 * Type for bulletin notification functions.
 *
 * The value is passed from the publisher unmodified, and can safely be
 * cast into a pointer. Notification functions run in the context of the
 * publisher.
 */
typedef void (*bulletin_notif_fn_t)(uintptr_t value, void *arg);

#include <kern/bulletin_i.h>

struct bulletin;

/*
 * Bulletin subscriber.
 */
struct bulletin_sub;

void bulletin_init(struct bulletin *bulletin);

/*
 * Subscribe to a bulletin.
 *
 * Once subscribed, the notification function is called with its argument
 * each time the bulletin is published.
 */
void bulletin_subscribe(struct bulletin *bulletin, struct bulletin_sub *sub,
                        bulletin_notif_fn_t notif_fn, void *arg);

/*
 * Unsubscribe from a bulletin.
 *
 * On return, the subscriber notification function may not be called any more.
 *
 * This function synchronizes with RCU.
 */
void bulletin_unsubscribe(struct bulletin *bulletin, struct bulletin_sub *sub);

/*
 * Publish a bulletin.
 *
 * All subscribers are notified by calling their notification function, with
 * the given value passed unmodified.
 */
void bulletin_publish(struct bulletin *bulletin, uintptr_t value);

#endif /* KERN_BULLETIN_H */


code:
/*
 * Copyright (c) 2017-2018 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef KERN_BULLETIN_I_H
#define KERN_BULLETIN_I_H

#include <kern/list.h>
#include <kern/spinlock.h>

struct bulletin_sub {
    struct list node;
    bulletin_notif_fn_t notif_fn;
    void *arg;
};

struct bulletin {
    struct spinlock lock;
    struct list subs;
};

#endif /* KERN_BULLETIN_I_H */


code:
/*
 * Copyright (c) 2015-2017 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Upstream site with license notes :
 * http://git.sceen.net/rbraun/librbraun.git/
 */

#include <assert.h>
#include <errno.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>

#include <kern/cbuf.h>
#include <kern/macros.h>

/* Negative close to 0 so that an overflow occurs early */
#define CBUF_INIT_INDEX ((size_t)-500)

void
cbuf_init(struct cbuf *cbuf, void *buf, size_t capacity)
{
    assert(ISP2(capacity));

    cbuf->buf = buf;
    cbuf->capacity = capacity;
    cbuf->start = CBUF_INIT_INDEX;
    cbuf->end = cbuf->start;
}

static size_t
cbuf_index(const struct cbuf *cbuf, size_t abs_index)
{
    return abs_index & (cbuf->capacity - 1);
}

static void
cbuf_update_start(struct cbuf *cbuf)
{
    /* Mind integer overflows */
    if (cbuf_size(cbuf) > cbuf->capacity) {
        cbuf->start = cbuf->end - cbuf->capacity;
    }
}

int
cbuf_push(struct cbuf *cbuf, const void *buf, size_t size, bool erase)
{
    size_t free_size;

    if (!erase) {
        free_size = cbuf_capacity(cbuf) - cbuf_size(cbuf);

        if (size > free_size) {
            return EAGAIN;
        }
    }

    return cbuf_write(cbuf, cbuf_end(cbuf), buf, size);
}

int
cbuf_pop(struct cbuf *cbuf, void *buf, size_t *sizep)
{
    int error;

    if (cbuf_size(cbuf) == 0) {
        return EAGAIN;
    }

    error = cbuf_read(cbuf, cbuf_start(cbuf), buf, sizep);
    assert(!error);
    cbuf->start += *sizep;
    return 0;
}

int
cbuf_pushb(struct cbuf *cbuf, uint8_t byte, bool erase)
{
    size_t free_size;

    if (!erase) {
        free_size = cbuf_capacity(cbuf) - cbuf_size(cbuf);

        if (free_size == 0) {
            return EAGAIN;
        }
    }

    cbuf->buf[cbuf_index(cbuf, cbuf->end)] = byte;
    cbuf->end++;
    cbuf_update_start(cbuf);
    return 0;
}

int
cbuf_popb(struct cbuf *cbuf, void *bytep)
{
    uint8_t *ptr;

    if (cbuf_size(cbuf) == 0) {
        return EAGAIN;
    }

    ptr = bytep;
    *ptr = cbuf->buf[cbuf_index(cbuf, cbuf->start)];
    cbuf->start++;
    return 0;
}

int
cbuf_write(struct cbuf *cbuf, size_t index, const void *buf, size_t size)
{
    uint8_t *start, *end, *buf_end;
    size_t new_end, skip;

    if (!cbuf_range_valid(cbuf, index, cbuf->end)) {
        return EINVAL;
    }

    new_end = index + size;

    if (!cbuf_range_valid(cbuf, cbuf->start, new_end)) {
        cbuf->end = new_end;

        if (size > cbuf_capacity(cbuf)) {
            skip = size - cbuf_capacity(cbuf);
            buf += skip;
            index += skip;
            size = cbuf_capacity(cbuf);
        }
    }

    start = &cbuf->buf[cbuf_index(cbuf, index)];
    end = start + size;
    buf_end = cbuf->buf + cbuf->capacity;

    if ((end <= cbuf->buf) || (end > buf_end)) {
        skip = buf_end - start;
        memcpy(start, buf, skip);
        buf += skip;
        start = cbuf->buf;
        size -= skip;
    }

    memcpy(start, buf, size);
    cbuf_update_start(cbuf);
    return 0;
}

int
cbuf_read(const struct cbuf *cbuf, size_t index, void *buf, size_t *sizep)
{
    const uint8_t *start, *end, *buf_end;
    size_t size;

    /* At least one byte must be available */
    if (!cbuf_range_valid(cbuf, index, index + 1)) {
        return EINVAL;
    }

    size = cbuf->end - index;

    if (*sizep > size) {
        *sizep = size;
    }

    start = &cbuf->buf[cbuf_index(cbuf, index)];
    end = start + *sizep;
    buf_end = cbuf->buf + cbuf->capacity;

    if ((end > cbuf->buf) && (end <= buf_end)) {
        size = *sizep;
    } else {
        size = buf_end - start;
        memcpy(buf, start, size);
        buf += size;
        start = cbuf->buf;
        size = *sizep - size;
    }

    memcpy(buf, start, size);
    return 0;
}


code:
/*
 * Copyright (c) 2015-2017 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Upstream site with license notes :
 * http://git.sceen.net/rbraun/librbraun.git/
 *
 *
 * Circular byte buffer.
 */

#ifndef KERN_CBUF_H
#define KERN_CBUF_H

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

/*
 * Circular buffer descriptor.
 *
 * The buffer capacity must be a power-of-two. Indexes are absolute values
 * which can overflow. Their difference cannot exceed the capacity.
 */
struct cbuf {
    uint8_t *buf;
    size_t capacity;
    size_t start;
    size_t end;
};

static inline size_t
cbuf_capacity(const struct cbuf *cbuf)
{
    return cbuf->capacity;
}

static inline size_t
cbuf_start(const struct cbuf *cbuf)
{
    return cbuf->start;
}

static inline size_t
cbuf_end(const struct cbuf *cbuf)
{
    return cbuf->end;
}

static inline size_t
cbuf_size(const struct cbuf *cbuf)
{
    return cbuf->end - cbuf->start;
}

static inline size_t
cbuf_avail_size(const struct cbuf *cbuf)
{
    return cbuf_capacity(cbuf) - cbuf_size(cbuf);
}

static inline void
cbuf_clear(struct cbuf *cbuf)
{
    cbuf->start = cbuf->end;
}

static inline bool
cbuf_range_valid(const struct cbuf *cbuf, size_t start, size_t end)
{
    return (((end - start) <= cbuf_size(cbuf))
            && ((start - cbuf->start) <= cbuf_size(cbuf))
            && ((cbuf->end - end) <= cbuf_size(cbuf)));
}

/*
 * Initialize a circular buffer.
 *
 * The descriptor is set to use the given buffer for storage. Capacity
 * must be a power-of-two.
 */
void cbuf_init(struct cbuf *cbuf, void *buf, size_t capacity);

/*
 * Push data to a circular buffer.
 *
 * If the function isn't allowed to erase old data and the circular buffer
 * doesn't have enough unused bytes for the new data, EAGAIN is returned.
 */
int cbuf_push(struct cbuf *cbuf, const void *buf, size_t size, bool erase);

/*
 * Pop data from a circular buffer.
 *
 * On entry, the sizep argument points to the size of the output buffer.
 * On exit, it is updated to the number of bytes actually transferred.
 *
 * If the buffer is empty, EAGAIN is returned, and the size of the
 * output buffer is undefined.
 */
int cbuf_pop(struct cbuf *cbuf, void *buf, size_t *sizep);

/*
 * Push a byte to a circular buffer.
 *
 * If the function isn't allowed to erase old data and the circular buffer
 * is full, EAGAIN is returned.
 */
int cbuf_pushb(struct cbuf *cbuf, uint8_t byte, bool erase);

/*
 * Pop a byte from a circular buffer.
 *
 * If the buffer is empty, EAGAIN is returned.
 */
int cbuf_popb(struct cbuf *cbuf, void *bytep);

/*
 * Write into a circular buffer at a specific location.
 *
 * If the given index is outside buffer boundaries, EINVAL is returned.
 * The given [index, size) range may extend beyond the end of the circular
 * buffer.
 */
int cbuf_write(struct cbuf *cbuf, size_t index, const void *buf, size_t size);

/*
 * Read from a circular buffer at a specific location.
 *
 * On entry, the sizep argument points to the size of the output buffer.
 * On exit, it is updated to the number of bytes actually transferred.
 *
 * If the given index is outside buffer boundaries, EINVAL is returned.
 *
 * The circular buffer isn't changed by this operation.
 */
int cbuf_read(const struct cbuf *cbuf, size_t index, void *buf, size_t *sizep);

#endif /* KERN_CBUF_H */


code:
/*
 * Copyright (c) 2017 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <stdio.h>
#include <stdint.h>

#include <kern/atomic.h>
#include <kern/clock.h>
#include <kern/clock_i.h>
#include <kern/init.h>
#include <kern/percpu.h>
#include <kern/rcu.h>
#include <kern/sref.h>
#include <kern/syscnt.h>
#include <kern/thread.h>
#include <kern/timer.h>
#include <kern/work.h>
#include <machine/boot.h>
#include <machine/cpu.h>

struct clock_cpu_data {
    struct syscnt sc_tick_intrs;
};

static struct clock_cpu_data clock_cpu_data __percpu;

union clock_global_time clock_global_time;

static inline void __init
clock_cpu_data_init(struct clock_cpu_data *cpu_data, unsigned int cpu)
{
    char name[SYSCNT_NAME_SIZE];

    snprintf(name, sizeof(name), "clock_tick_intrs/%u", cpu);
    syscnt_register(&cpu_data->sc_tick_intrs, name);
}

static int __init
clock_setup(void)
{
    for (unsigned int cpu = 0; cpu < cpu_count(); cpu++) {
        clock_cpu_data_init(percpu_ptr(clock_cpu_data, cpu), cpu);
    }

    return 0;
}

INIT_OP_DEFINE(clock_setup,
               INIT_OP_DEP(cpu_mp_probe, true),
               INIT_OP_DEP(syscnt_setup, true));

void clock_tick_intr(void)
{
    struct clock_cpu_data *cpu_data;

    assert(thread_check_intr_context());

    if (cpu_id() == 0) {
#ifdef ATOMIC_HAVE_64B_OPS

        atomic_add(&clock_global_time.ticks, 1ULL, ATOMIC_RELAXED);

#else /* ATOMIC_HAVE_64B_OPS */

        union clock_global_time t;

        t.ticks = clock_global_time.ticks;
        t.ticks++;

        atomic_store(&clock_global_time.high2, t.high1, ATOMIC_RELAXED);
        atomic_store(&clock_global_time.low, t.low, ATOMIC_RELEASE);
        atomic_store(&clock_global_time.high1, t.high1, ATOMIC_RELEASE);

#endif /* ATOMIC_HAVE_64B_OPS */
    }

    timer_report_periodic_event();
    rcu_report_periodic_event();
    sref_report_periodic_event();
    work_report_periodic_event();
    thread_report_periodic_event();

    cpu_data = cpu_local_ptr(clock_cpu_data);
    syscnt_inc(&cpu_data->sc_tick_intrs);
}