diff options
author | Richard Braun <rbraun@sceen.net> | 2017-10-14 23:45:04 +0200 |
---|---|---|
committer | Richard Braun <rbraun@sceen.net> | 2018-01-04 01:57:38 +0100 |
commit | 9437f135da9fab16180fc64cdd64e2a3bb3d5b7a (patch) | |
tree | 8cd3d9e769c2af24463d58e8ba416aae9de9ce7b |
Initial commit
-rw-r--r-- | .gitignore | 4 | ||||
-rw-r--r-- | COPYING | 20 | ||||
-rw-r--r-- | Makefile | 233 | ||||
-rw-r--r-- | README | 139 | ||||
-rw-r--r-- | include/assert.h | 53 | ||||
-rw-r--r-- | include/limits.h | 28 | ||||
-rw-r--r-- | include/stdio.h | 56 | ||||
-rw-r--r-- | include/stdlib.h | 31 | ||||
-rw-r--r-- | include/string.h | 35 | ||||
-rw-r--r-- | lib/cbuf.c | 203 | ||||
-rw-r--r-- | lib/cbuf.h | 150 | ||||
-rw-r--r-- | lib/fmt.c | 1468 | ||||
-rw-r--r-- | lib/fmt.h | 69 | ||||
-rw-r--r-- | lib/hash.h | 123 | ||||
-rw-r--r-- | lib/list.h | 538 | ||||
-rw-r--r-- | lib/macros.h | 94 | ||||
-rw-r--r-- | lib/shell.c | 1212 | ||||
-rw-r--r-- | lib/shell.h | 94 | ||||
-rwxr-xr-x | qemu.sh | 19 | ||||
-rw-r--r-- | src/boot.c | 43 | ||||
-rw-r--r-- | src/boot.h | 34 | ||||
-rw-r--r-- | src/boot_asm.S | 96 | ||||
-rw-r--r-- | src/condvar.c | 180 | ||||
-rw-r--r-- | src/condvar.h | 149 | ||||
-rw-r--r-- | src/cpu.c | 493 | ||||
-rw-r--r-- | src/cpu.h | 131 | ||||
-rw-r--r-- | src/cpu_asm.S | 163 | ||||
-rw-r--r-- | src/error.c | 67 | ||||
-rw-r--r-- | src/error.h | 50 | ||||
-rw-r--r-- | src/i8254.c | 72 | ||||
-rw-r--r-- | src/i8254.h | 34 | ||||
-rw-r--r-- | src/i8259.c | 257 | ||||
-rw-r--r-- | src/i8259.h | 57 | ||||
-rw-r--r-- | src/io.h | 47 | ||||
-rw-r--r-- | src/io_asm.S | 37 | ||||
-rw-r--r-- | src/kernel.lds | 113 | ||||
-rw-r--r-- | src/main.c | 69 | ||||
-rw-r--r-- | src/mem.c | 692 | ||||
-rw-r--r-- | src/mem.h | 92 | ||||
-rw-r--r-- | src/mutex.c | 151 | ||||
-rw-r--r-- | src/mutex.h | 165 | ||||
-rw-r--r-- | src/panic.c | 42 | ||||
-rw-r--r-- | src/panic.h | 32 | ||||
-rw-r--r-- | src/stdio.c | 87 | ||||
-rw-r--r-- | src/string.c | 143 | ||||
-rw-r--r-- | src/sw.c | 295 | ||||
-rw-r--r-- | src/sw.h | 34 | ||||
-rw-r--r-- | src/thread.c | 823 | ||||
-rw-r--r-- | src/thread.h | 326 | ||||
-rw-r--r-- | src/thread_asm.S | 51 | ||||
-rw-r--r-- | src/timer.c | 321 | ||||
-rw-r--r-- | src/timer.h | 136 | ||||
-rw-r--r-- | src/uart.c | 190 | ||||
-rw-r--r-- | src/uart.h | 61 |
54 files changed, 10302 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..4e24883 --- /dev/null +++ b/.gitignore @@ -0,0 +1,4 @@ +.* +*.o +x1 +cscope.out @@ -0,0 +1,20 @@ +Copyright (c) 2017 Richard Braun. +Copyright (c) 2017 Jerko Lenstra. + +Permission is hereby granted, free of charge, to any person obtaining a +copy of this software and associated documentation files (the "Software"), +to deal in the Software without restriction, including without limitation +the rights to use, copy, modify, merge, publish, distribute, sublicense, +and/or sell copies of the Software, and to permit persons to whom the +Software is furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..63d388a --- /dev/null +++ b/Makefile @@ -0,0 +1,233 @@ +MAKEFLAGS += --no-builtin-rules +MAKEFLAGS += --no-builtin-variables + +# The project version. +VERSION = 0.1 + +# The selected C compiler. +# +# Here is an example of overriding the compiler : +# $ make CC=clang +CC = gcc + +# C preprocessor flags. +# +# Use man gcc for more details. On Debian, the GNU FDL license is considered +# non free, and as a result, the gcc-doc package is part of the non-free +# components. + +# Generate code for a 32-bits environment. +X1_CPPFLAGS = -m32 + +# Do not search the standard system directories for header files. +# The kernel is a free standing environment, where no host library can +# work, at least not without (usually heavy) integration work. +X1_CPPFLAGS += -nostdinc + +# The -I option is used to add directories to the search list. +X1_CPPFLAGS += -Iinclude -I. + +# The -print-file-name=include option prints the directory where the compiler +# headers are located. This directory is normally part of the standard system +# directories for header files, excluded by the -nostdinc option. But the +# C free standing environment still assumes the availability of some headers +# which can be found there. +X1_CPPFLAGS += -isystem $(shell $(CC) -print-file-name=include) + +# Pass the project version as a macro. +X1_CPPFLAGS += -DVERSION="$(VERSION)" + +# Append user-provided preprocessor flags, if any. +# +# Here is an example that turns off assertions : +# $ make CPPFLAGS=-DNDEBUG +X1_CPPFLAGS += $(CPPFLAGS) + +# C flags. +# +# Use man gcc for more details. On Debian, the GNU FDL license is considered +# non free, and as a result, the gcc-doc package is part of the non-free +# components. + +# These are common warning options. +X1_CFLAGS = -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes + +# Enable warnings about shadow declarations. A shadow declaration occurs +# when a name, e.g. a variable name, "hides" another declaration with the +# same name, but from an outer scope. Here is an example : +# +# int +# main(void) +# { +# int a; +# +# { +# int a; +# } +# } +# +# Local variables may shadow global variables, which is why global +# names are usually prefixed with a namespace name. Another common +# case is variables declared inside function-like macros, where a +# popular solution is to prefix the names with a number of underscores. +X1_CFLAGS += -Wshadow + +# This is currently a Clang-specific warning about declarations that are +# unused, a problem that quickly occurs when using conditional compilation +# like assertions. +X1_CFLAGS += -Wno-unneeded-internal-declaration + +# Set the language as C99 with GNU extensions. +X1_CFLAGS += -std=gnu99 + +# Build with optimizations as specified by the -O2 option. +X1_CFLAGS += -O2 + +# Include debugging symbols, giving inspection tools a lot more debugging +# data to work with, e.g. allowing them to translate between addresses and +# source locations. +X1_CFLAGS += -g + +# Target a free standing environment as defined by C99. +# +# This option tells the compiler that it may not assume a hosted environment, +# e.g. that it cannot assume the availability of the C library. +# +# See ISO/IEC 9899:1999 5.1.2.1 "Freestanding environment" for all the details. +X1_CFLAGS += -ffreestanding + +# Keep using the frame pointer. +# +# When a function is called, the stack pointer (esp) points to the "end" of +# the stack frame, and the frame or base pointer (ebp) points to the +# "beginning". When optimizations are enabled, the compiler only uses the +# stack pointer as a base pointer to refer to temporary data saved on the +# stack frame, and therefore omits the base pointer to gain a register. +# But this prevents debuggers from easily unwinding the stack since the +# base pointer allowed conveniently retrieving the return address. This +# option tells the compiler to keep the base pointer so that GDB can +# produce valid backtraces. +X1_CFLAGS += -fno-omit-frame-pointer + +# Disable the generation of extra code for stack protection, as it requires +# additional support in the kernel which is beyond its scope, and may be +# enabled by default on some distributions. +X1_CFLAGS += -fno-stack-protector + +# Disable strict aliasing, a C99 rule that states that pointers of different +# types may never refer to the same memory. Strict aliasing may provide +# performance improvements for some rare cases but may also cause weird bugs +# when casting pointers. +X1_CFLAGS += -fno-strict-aliasing + +# Force all uninitialized global variables into a data section instead of +# generating them as "common blocks". If multiple definitions of the same +# global variable are made, this option will make the link fail. +X1_CFLAGS += -fno-common + +# Disable all extended intruction sets that require special kernel support. +X1_CFLAGS += -mno-sse -mno-mmx -mno-sse2 -mno-3dnow -mno-avx + +# Append user-provided compiler flags, if any. +# +# Here are some examples : +# $ make CFLAGS="-O0 -g3" +# Disable optimizations and include extra debugging information +# $ make CPPFLAGS=-DNDEBUG CFLAGS="-Os -flto -g0" +# Disable assertions, optimize for size, enable LTO (link-time optimizations), +# and don't produce debugging information +# +# Because these flags are added last, they can override any flag set in this +# Makefile. +X1_CFLAGS += $(CFLAGS) + +# Linker flags. +# +# These are also GCC options, so use man gcc for more details. On Debian, +# the GNU FDL license is considered non free, and as a result, the gcc-doc +# package is part of the non-free components. + +# Link for a 32-bits environment. +X1_LDFLAGS = -m32 + +# Build a static executable, with no shared library. +X1_LDFLAGS += -static + +# Do not use the standard system startup files or libraries when linking. +# The kernel is a free standing environment, where no host library can +# work, at least not without (usually heavy) integration work. +X1_LDFLAGS += -nostdlib + +# Disable the generation of a build ID, a feature usually enabled by default +# on many distributions. A build ID is linked in its own special section, so +# disabling it makes the linker script simpler. +X1_LDFLAGS += -Xlinker --build-id=none + +# Pass the linker script path to the linker. +X1_LDFLAGS += -Xlinker -T src/kernel.lds + +# Append user-provided linker flags, if any. +X1_LDFLAGS += $(LDFLAGS) + +# Link against libgcc. This library is a companion to the compiler and +# adds support for operations required by C99 but that the hardware +# doesn't provide. An example is 64-bits integer additions on a 32-bits +# processor or a 64-bits processor running in 32-bits protected mode. +LIBS = -lgcc + +BINARY = x1 + +SOURCES = \ + src/boot_asm.S \ + src/boot.c \ + src/condvar.c \ + src/cpu.c \ + src/cpu_asm.S \ + src/error.c \ + src/i8254.c \ + src/i8259.c \ + src/io_asm.S \ + src/main.c \ + src/mem.c \ + src/mutex.c \ + src/panic.c \ + src/stdio.c \ + src/string.c \ + src/sw.c \ + src/thread_asm.S \ + src/thread.c \ + src/timer.c \ + src/uart.c + +SOURCES += \ + lib/cbuf.c \ + lib/fmt.c \ + lib/shell.c + +OBJECTS = $(patsubst %.S,%.o,$(patsubst %.c,%.o,$(SOURCES))) + +$(BINARY): $(OBJECTS) + $(CC) -o $@ $(X1_LDFLAGS) $^ $(LIBS) + +%.o: %.c + $(CC) $(X1_CPPFLAGS) $(X1_CFLAGS) -c -o $@ $< + +%.o: %.S + $(CC) $(X1_CPPFLAGS) $(X1_CFLAGS) -c -o $@ $< + +clean: + rm -f $(BINARY) $(OBJECTS) + +# Making all sources phony means that make will always consider them and +# the targets using them as dependencies as obsolete. This basically forces +# make to rebuild all files, all the time. It's obviously not the best +# way to compile, but it's simple and reliable. +# +# The modern approach is to make compilation incremental, by generating +# dependency Makefiles with the compiler, which are then included in the +# main Makefile so that a target may only be rebuilt if any of its +# dependencies is newer. Check the X15 project [1] for an example of this +# technique. +# +# [1] https://git.sceen.net/rbraun/x15.git/ +.PHONY: clean $(SOURCES) @@ -0,0 +1,139 @@ +X1 - A minimalist educational operating system +============================================== + +X1 is a very small operating system meant to introduce students to low-level +system programming. As a result, it focuses on clarity of explanation. It's +not meant to demonstrate state-of-the-art methods and algorithms, but rather +simple, naive ones that do the job, while providing pointers and references +to the more modern ways. + +X1 is a single address space operating system, always running with the +highest privileges. There is no userspace, and no system calls. Despite +that, the operating system is also called the kernel. + + +Building +-------- + +X1 expects a Unix-like environment, including make and a GCC compilation +toolchain. It's been tested on a few Linux distributions such as Debian +and Arch. + +Building the kernel is done using the make command from the source root +directory. The end result is a statically linked ELF [1] file named x1. +On Debian, the following packages are required : + + - build-essential + Meta-package pulling the gcc and make packages, among others. + - gcc-multilib + Multilib support for GCC, which provides the 32-bits static libgcc + library required to link the kernel on 64-bits machines. + +Examining the kernel binary +--------------------------- + +The kernel can be examined with standard GNU binutils tools [2]. Here are +some common command line examples to obtain information directly from the +kernel binary : + + - objdump -d x1 | less + Disassemble the kernel machine code. + - readelf -aW x1 | less + Display ELF information, such as headers and sections. + - addr2line -e x1 0x1003f0 + Convert an address into a source location. + - nm x1 + List symbol names. + + +Running +------- + +X1 targets the x86 32-bits architecture only (i386) [3], and ignores some +advanced features such as virtual memory and SMP. It is compliant with the +original multiboot specification [4] and GRUB is the recommended boot loader. +It only supports legacy BIOS systems (no EFI/UEFI). + +A simple way to run the kernel is to use the qemu.sh shell script, which +relies on the QEMU -kernel option to act as a multiboot boot loader. +On Debian, the following packages are required : + + - qemu + The well known machine emulator. + +When QEMU is running, you may enter (and leave) its monitor prompt using +the Ctrl-a c key sequence. The most useful monitor commands are : + + - info registers + Print the content of all core registers. + - info pic + Print the state of the legacy PIC interrupt controller. + +If you're interested in the details, the following commands may be of interest : + + - info mtree + Print the various emulated address spaces. + - info qtree + Print the emulated device tree. + + +Getting started +--------------- + +Even a simple project like X1 requires broad knowledge, spanning from a basic +understanding of processors, memory, assembly and compilation toolchains. The +OSDev website [5] provides a good starting point to find information of decent +quality. Beyond that, readers are encouraged to refer to actual reference +documentation, and of course, search engines. + +Here is a non-exhaustive list of topics readers should hopefully develop their +understanding of with this project, and are encouraged to briefly learn about +even before starting playing with X1 : + + - Processor architecture, including core registers, machine instructions + and accessing memory through loads and stores. + - Control of the link step through a linker script. + - The concept of an executable format, including partitioning the content into + sections, such as code and data sections. See ELF [1]. + - The C programming language, including common extensions, such as controlling + alignment. The source code conforms to C99 [6] with some GNU extensions. + +The two files reader should use as their entry points are : + + - src/boot_asm.S + The assembly source file containing the very first instructions. + - src/kernel.lds + The linker script used to control the link step. + +Sources organization +-------------------- + +The project sources are split into three directories : + +- include + This directory may only contain standard headers, normally provided + by the "implementation" (e.g. the compiler and the C library) in a + hosted environment. Because this is a kernel, the environment is + free standing instead, so any additional standard service must be + added manually. See ISO/IEC 9899:1999 5.1.2.1 "Freestanding environment" + in the C99 specification for all the details. +- lib + This directory contains external code used as a library by the kernel. + These files are copied from the librbraun library [7] and are meant to + provide a tiny and easily embedded "development kit". +- src + This directory contains the actual kernel code. + +The coding style used is borrowed from X1's big brother X15 [8]. + +References +---------- + +[1] ELF: http://refspecs.linuxbase.org/elf/elf.pdf +[2] GNU binutils : http://sourceware.org/binutils/docs-2.29/ +[3] Intel combined manuals : https://software.intel.com/en-us/articles/intel-sdm +[4] Multiboot specification : https://www.gnu.org/software/grub/manual/multiboot/multiboot.html +[5] OSDev website : http://wiki.osdev.org/ +[6] C99 specification : http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf +[7] https://www.sceen.net/basic-modules-library-for-c/ +[8] https://www.sceen.net/~rbraun/x15/doc/style.9.html diff --git a/include/assert.h b/include/assert.h new file mode 100644 index 0000000..2d02457 --- /dev/null +++ b/include/assert.h @@ -0,0 +1,53 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#ifndef _ASSERT_H +#define _ASSERT_H + +#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 <lib/macros.h> +#include <src/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 */ diff --git a/include/limits.h b/include/limits.h new file mode 100644 index 0000000..e2b5fd6 --- /dev/null +++ b/include/limits.h @@ -0,0 +1,28 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#ifndef _LIMITS_H +#define _LIMITS_H + +#define CHAR_BIT 8 + +#endif /* _LIMITS_H */ diff --git a/include/stdio.h b/include/stdio.h new file mode 100644 index 0000000..d334ac4 --- /dev/null +++ b/include/stdio.h @@ -0,0 +1,56 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * Subset of the standard C stdio interface. + */ + +#ifndef _STDIO_H +#define _STDIO_H + +#include <stdarg.h> + +#include <lib/fmt.h> + +/* + * Keep in mind that #define really means "textually replace". As a result, + * any expression that may cause errors because of operator precedance should + * be enclosed in parentheses. + */ +#define EOF (-1) + +void putchar(unsigned char c); +int getchar(void); + +int printf(const char *format, ...) + __attribute__((format(printf, 1, 2))); + +int vprintf(const char *format, va_list ap) + __attribute__((format(printf, 1, 0))); + +#define sprintf fmt_sprintf +#define vsprintf fmt_vsprintf +#define snprintf fmt_snprintf +#define vsnprintf fmt_vsnprintf +#define sscanf fmt_sscanf +#define vsscanf fmt_vsscanf + +#endif /* _STDIO_H */ diff --git a/include/stdlib.h b/include/stdlib.h new file mode 100644 index 0000000..053396e --- /dev/null +++ b/include/stdlib.h @@ -0,0 +1,31 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#ifndef _STDLIB_H +#define _STDLIB_H + +#include <src/mem.h> + +#define malloc mem_alloc +#define free mem_free + +#endif /* _STDLIB_H */ diff --git a/include/string.h b/include/string.h new file mode 100644 index 0000000..3f7c87e --- /dev/null +++ b/include/string.h @@ -0,0 +1,35 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#ifndef _STRING_H +#define _STRING_H + +#include <stddef.h> + +void * memmove(void *dest, const void *src, size_t n); +void * memcpy(void * restrict dest, const void * restrict src, size_t n); +char * strcpy(char *dest, const char *src); +size_t strlen(const char *s); +int strcmp(const char *s1, const char *s2); +int strncmp(const char *s1, const char *s2, size_t n); + +#endif /* _STRING_H */ diff --git a/lib/cbuf.c b/lib/cbuf.c new file mode 100644 index 0000000..e405964 --- /dev/null +++ b/lib/cbuf.c @@ -0,0 +1,203 @@ +/* + * Copyright (c) 2015-2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * Upstream site with license notes : + * http://git.sceen.net/rbraun/librbraun.git/ + */ + +#include <assert.h> +#include <stddef.h> +#include <stdint.h> +#include <string.h> + +#include <lib/cbuf.h> +#include <lib/macros.h> + +#include <src/error.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 ERROR_AGAIN; + } + } + + return cbuf_write(cbuf, cbuf_end(cbuf), buf, size); +} + +int +cbuf_pop(struct cbuf *cbuf, void *buf, size_t *sizep) +{ + __unused int error; + + if (cbuf_size(cbuf) == 0) { + return ERROR_AGAIN; + } + + 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 ERROR_AGAIN; + } + } + + 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 ERROR_AGAIN; + } + + 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 ERROR_INVAL; + } + + 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 ERROR_INVAL; + } + + 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; +} diff --git a/lib/cbuf.h b/lib/cbuf.h new file mode 100644 index 0000000..eb2ec83 --- /dev/null +++ b/lib/cbuf.h @@ -0,0 +1,150 @@ +/* + * Copyright (c) 2015-2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * Upstream site with license notes : + * http://git.sceen.net/rbraun/librbraun.git/ + * + * + * Circular byte buffer. + */ + +#ifndef _CBUF_H +#define _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 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, ERROR_AGAIN 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, ERROR_AGAIN 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, ERROR_AGAIN 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, ERROR_AGAIN 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, ERROR_INVAL 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, ERROR_INVAL 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 /* _CBUF_H */ diff --git a/lib/fmt.c b/lib/fmt.c new file mode 100644 index 0000000..0940f24 --- /dev/null +++ b/lib/fmt.c @@ -0,0 +1,1468 @@ +/* + * Copyright (c) 2010-2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * Upstream site with license notes : + * http://git.sceen.net/rbraun/librbraun.git/ + */ + +#include <assert.h> +#include <limits.h> +#include <stdbool.h> +#include <stdarg.h> +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> + +#include <lib/fmt.h> +#include <lib/macros.h> + +#include <src/error.h> + +/* + * XXX This type is specified by POSIX. Directly declare it for simplicity. + */ +typedef long ssize_t; + +/* + * Size for the temporary number buffer. The minimum base is 8 so 3 bits + * are consumed per digit. Add one to round up. The conversion algorithm + * doesn't use the null byte. + */ +#define FMT_MAX_NUM_SIZE (((sizeof(unsigned long long) * CHAR_BIT) / 3) + 1) + +/* + * Special size for fmt_vsnprintf(), used when the buffer size is unknown. + */ +#define FMT_NOLIMIT ((size_t)-1) + +/* + * Formatting flags. + * + * FMT_FORMAT_LOWER must be 0x20 as it is OR'd with fmt_digits, eg. + * '0': 0x30 | 0x20 => 0x30 ('0') + * 'A': 0x41 | 0x20 => 0x61 ('a') + */ +#define FMT_FORMAT_ALT_FORM 0x0001 /* "Alternate form" */ +#define FMT_FORMAT_ZERO_PAD 0x0002 /* Zero padding on the left */ +#define FMT_FORMAT_LEFT_JUSTIFY 0x0004 /* Align text on the left */ +#define FMT_FORMAT_BLANK 0x0008 /* Blank space before positive number */ +#define FMT_FORMAT_SIGN 0x0010 /* Always place a sign (either + or -) */ +#define FMT_FORMAT_LOWER 0x0020 /* To lowercase (for %x) */ +#define FMT_FORMAT_CONV_SIGNED 0x0040 /* Format specifies signed conversion */ +#define FMT_FORMAT_DISCARD 0x0080 /* Discard output (scanf) */ +#define FMT_FORMAT_CHECK_WIDTH 0x0100 /* Check field width (scanf) */ + +enum { + FMT_MODIFIER_NONE, + FMT_MODIFIER_CHAR, + FMT_MODIFIER_SHORT, + FMT_MODIFIER_LONG, + FMT_MODIFIER_LONGLONG, + FMT_MODIFIER_PTR, /* Used only for %p */ + FMT_MODIFIER_SIZE, + FMT_MODIFIER_PTRDIFF, +}; + +enum { + FMT_SPECIFIER_INVALID, + FMT_SPECIFIER_INT, + FMT_SPECIFIER_CHAR, + FMT_SPECIFIER_STR, + FMT_SPECIFIER_NRCHARS, + FMT_SPECIFIER_PERCENT, +}; + +/* + * Note that copies of the original va_list object are made, because va_arg() + * may not reliably be used by different callee functions, and despite the + * standard explicitely allowing pointers to va_list objects, it's apparently + * very difficult for implementations to provide and is best avoided. + */ + +struct fmt_sprintf_state { + const char *format; + va_list ap; + unsigned int flags; + int width; + int precision; + unsigned int modifier; + unsigned int specifier; + unsigned int base; + char *str; + char *start; + char *end; +}; + +struct fmt_sscanf_state { + const char *str; + const char *start; + const char *format; + va_list ap; + unsigned int flags; + int width; + int precision; + unsigned int modifier; + unsigned int specifier; + unsigned int base; + int nr_convs; +}; + +static const char fmt_digits[] = "0123456789ABCDEF"; + +static char +fmt_consume(const char **strp) +{ + char c; + + c = **strp; + (*strp)++; + return c; +} + +static void +fmt_restore(const char **strp) +{ + (*strp)--; +} + +static void +fmt_vsnprintf_produce(char **strp, char *end, char c) +{ + if (*strp < end) { + **strp = c; + } + + (*strp)++; +} + +static bool +fmt_isdigit(char c) +{ + return (c >= '0') && (c <= '9'); +} + +static bool +fmt_isxdigit(char c) +{ + return fmt_isdigit(c) + || ((c >= 'a') && (c <= 'f')) + || ((c >= 'A') && (c <= 'F')); +} + +static void +fmt_sprintf_state_init(struct fmt_sprintf_state *state, + char *str, size_t size, + const char *format, va_list ap) +{ + state->format = format; + va_copy(state->ap, ap); + state->str = str; + state->start = str; + + if (size == 0) { + state->end = NULL; + } else if (size == FMT_NOLIMIT) { + state->end = (char *)-1; + } else { + state->end = state->start + size - 1; + } +} + +static int +fmt_sprintf_state_finalize(struct fmt_sprintf_state *state) +{ + va_end(state->ap); + + if (state->str < state->end) { + *state->str = '\0'; + } else if (state->end != NULL) { + *state->end = '\0'; + } + + return state->str - state->start; +} + +static char +fmt_sprintf_state_consume_format(struct fmt_sprintf_state *state) +{ + return fmt_consume(&state->format); +} + +static void +fmt_sprintf_state_restore_format(struct fmt_sprintf_state *state) +{ + fmt_restore(&state->format); +} + +static void +fmt_sprintf_state_consume_flags(struct fmt_sprintf_state *state) +{ + bool found; + char c; + + found = true; + state->flags = 0; + + do { + c = fmt_sprintf_state_consume_format(state); + + switch (c) { + case '#': + state->flags |= FMT_FORMAT_ALT_FORM; + break; + case '0': + state->flags |= FMT_FORMAT_ZERO_PAD; + break; + case '-': + state->flags |= FMT_FORMAT_LEFT_JUSTIFY; + break; + case ' ': + state->flags |= FMT_FORMAT_BLANK; + break; + case '+': + state->flags |= FMT_FORMAT_SIGN; + break; + default: + found = false; + break; + } + } while (found); + + fmt_sprintf_state_restore_format(state); +} + +static void +fmt_sprintf_state_consume_width(struct fmt_sprintf_state *state) +{ + char c; + + c = fmt_sprintf_state_consume_format(state); + + if (fmt_isdigit(c)) { + state->width = 0; + + do { + state->width = state->width * 10 + (c - '0'); + c = fmt_sprintf_state_consume_format(state); + } while (fmt_isdigit(c)); + + fmt_sprintf_state_restore_format(state); + } else if (c == '*') { + state->width = va_arg(state->ap, int); + + if (state->width < 0) { + state->flags |= FMT_FORMAT_LEFT_JUSTIFY; + state->width = -state->width; + } + } else { + state->width = 0; + fmt_sprintf_state_restore_format(state); + } +} + +static void +fmt_sprintf_state_consume_precision(struct fmt_sprintf_state *state) +{ + char c; + + c = fmt_sprintf_state_consume_format(state); + + if (c == '.') { + c = fmt_sprintf_state_consume_format(state); + + if (fmt_isdigit(c)) { + state->precision = 0; + + do { + state->precision = state->precision * 10 + (c - '0'); + c = fmt_sprintf_state_consume_format(state); + } while (fmt_isdigit(c)); + + fmt_sprintf_state_restore_format(state); + } else if (c == '*') { + state->precision = va_arg(state->ap, int); + + if (state->precision < 0) { + state->precision = 0; + } + } else { + state->precision = 0; + fmt_sprintf_state_restore_format(state); + } + } else { + /* precision is >= 0 only if explicit */ + state->precision = -1; + fmt_sprintf_state_restore_format(state); + } +} + +static void +fmt_sprintf_state_consume_modifier(struct fmt_sprintf_state *state) +{ + char c, c2; + + c = fmt_sprintf_state_consume_format(state); + + switch (c) { + case 'h': + case 'l': + c2 = fmt_sprintf_state_consume_format(state); + + if (c == c2) { + state->modifier = (c == 'h') ? FMT_MODIFIER_CHAR + : FMT_MODIFIER_LONGLONG; + } else { + state->modifier = (c == 'h') ? FMT_MODIFIER_SHORT + : FMT_MODIFIER_LONG; + fmt_sprintf_state_restore_format(state); + } + + break; + case 'z': + state->modifier = FMT_MODIFIER_SIZE; + case 't': + state->modifier = FMT_MODIFIER_PTRDIFF; + break; + default: + state->modifier = FMT_MODIFIER_NONE; + fmt_sprintf_state_restore_format(state); + break; + } +} + +static void +fmt_sprintf_state_consume_specifier(struct fmt_sprintf_state *state) +{ + char c; + + c = fmt_sprintf_state_consume_format(state); + + switch (c) { + case 'd': + case 'i': + state->flags |= FMT_FORMAT_CONV_SIGNED; + case 'u': + state->base = 10; + state->specifier = FMT_SPECIFIER_INT; + break; + case 'o': + state->base = 8; + state->specifier = FMT_SPECIFIER_INT; + break; + case 'p': + state->flags |= FMT_FORMAT_ALT_FORM; + state->modifier = FMT_MODIFIER_PTR; + case 'x': + state->flags |= FMT_FORMAT_LOWER; + case 'X': + state->base = 16; + state->specifier = FMT_SPECIFIER_INT; + break; + case 'c': + state->specifier = FMT_SPECIFIER_CHAR; + break; + case 's': + state->specifier = FMT_SPECIFIER_STR; + break; + case 'n': + state->specifier = FMT_SPECIFIER_NRCHARS; + break; + case '%': + state->specifier = FMT_SPECIFIER_PERCENT; + break; + default: + state->specifier = FMT_SPECIFIER_INVALID; + fmt_sprintf_state_restore_format(state); + break; + } +} + +static void +fmt_sprintf_state_produce_raw_char(struct fmt_sprintf_state *state, char c) +{ + fmt_vsnprintf_produce(&state->str, state->end, c); +} + +static int +fmt_sprintf_state_consume(struct fmt_sprintf_state *state) +{ + char c; + + c = fmt_consume(&state->format); + + if (c == '\0') { + return ERROR_IO; + } + + if (c != '%') { + fmt_sprintf_state_produce_raw_char(state, c); + return ERROR_AGAIN; + } + + fmt_sprintf_state_consume_flags(state); + fmt_sprintf_state_consume_width(state); + fmt_sprintf_state_consume_precision(state); + fmt_sprintf_state_consume_modifier(state); + fmt_sprintf_state_consume_specifier(state); + return 0; +} + +static void +fmt_sprintf_state_produce_int(struct fmt_sprintf_state *state) +{ + char c, sign, tmp[FMT_MAX_NUM_SIZE]; + unsigned int r, mask, shift; + unsigned long long n; + int i; + + switch (state->modifier) { + case FMT_MODIFIER_CHAR: + if (state->flags & FMT_FORMAT_CONV_SIGNED) { + n = (signed char)va_arg(state->ap, int); + } else { + n = (unsigned char)va_arg(state->ap, int); + } + + break; + case FMT_MODIFIER_SHORT: + if (state->flags & FMT_FORMAT_CONV_SIGNED) { + n = (short)va_arg(state->ap, int); + } else { + n = (unsigned short)va_arg(state->ap, int); + } + + break; + case FMT_MODIFIER_LONG: + if (state->flags & FMT_FORMAT_CONV_SIGNED) { + n = va_arg(state->ap, long); + } else { + n = va_arg(state->ap, unsigned long); + } + + break; + case FMT_MODIFIER_LONGLONG: + if (state->flags & FMT_FORMAT_CONV_SIGNED) { + n = va_arg(state->ap, long long); + } else { + n = va_arg(state->ap, unsigned long long); + } + + break; + case FMT_MODIFIER_PTR: + n = (uintptr_t)va_arg(state->ap, void *); + break; + case FMT_MODIFIER_SIZE: + if (state->flags & FMT_FORMAT_CONV_SIGNED) { + n = va_arg(state->ap, ssize_t); + } else { + n = va_arg(state->ap, size_t); + } + + break; + case FMT_MODIFIER_PTRDIFF: + n = va_arg(state->ap, ptrdiff_t); + break; + default: + if (state->flags & FMT_FORMAT_CONV_SIGNED) { + n = va_arg(state->ap, int); + } else { + n = va_arg(state->ap, unsigned int); + } + + break; + } + + if ((state->flags & FMT_FORMAT_LEFT_JUSTIFY) || (state->precision >= 0)) { + state->flags &= ~FMT_FORMAT_ZERO_PAD; + } + + sign = '\0'; + + if (state->flags & FMT_FORMAT_ALT_FORM) { + /* '0' for octal */ + state->width--; + + /* '0x' or '0X' for hexadecimal */ + if (state->base == 16) { + state->width--; + } + } else if (state->flags & FMT_FORMAT_CONV_SIGNED) { + if ((long long)n < 0) { + sign = '-'; + state->width--; + n = -(long long)n; + } else if (state->flags & FMT_FORMAT_SIGN) { + /* FMT_FORMAT_SIGN must precede FMT_FORMAT_BLANK. */ + sign = '+'; + state->width--; + } else if (state->flags & FMT_FORMAT_BLANK) { + sign = ' '; + state->width--; + } + } + + /* Conversion, in reverse order */ + + i = 0; + + if (n == 0) { + if (state->precision != 0) { + tmp[i] = '0'; + i++; + } + } else if (state->base == 10) { + /* + * Try to avoid 64 bits operations if the processor doesn't + * support them. Note that even when using modulus and + * division operators close to each other, the compiler may + * forge two functions calls to compute the quotient and the + * remainder, whereas processor instructions are generally + * correctly used once, giving both results at once, through + * plain or reciprocal division. + */ +#ifndef __LP64__ + if (state->modifier == FMT_MODIFIER_LONGLONG) { +#endif /* __LP64__ */ + do { + r = n % 10; + n /= 10; + tmp[i] = fmt_digits[r]; + i++; + } while (n != 0); +#ifndef __LP64__ + } else { + unsigned long m; + + m = (unsigned long)n; + + do { + r = m % 10; + m /= 10; + tmp[i] = fmt_digits[r]; + i++; + } while (m != 0); + } +#endif /* __LP64__ */ + } else { + mask = state->base - 1; + shift = (state->base == 8) ? 3 : 4; + + do { + r = n & mask; + n >>= shift; + tmp[i] = fmt_digits[r] | (state->flags & FMT_FORMAT_LOWER); + i++; + } while (n != 0); + } + + if (i > state->precision) { + state->precision = i; + } + + state->width -= state->precision; + + if (!(state->flags & (FMT_FORMAT_LEFT_JUSTIFY | FMT_FORMAT_ZERO_PAD))) { + while (state->width > 0) { + state->width--; + fmt_sprintf_state_produce_raw_char(state, ' '); + } + + state->width--; + } + + if (state->flags & FMT_FORMAT_ALT_FORM) { + fmt_sprintf_state_produce_raw_char(state, '0'); + + if (state->base == 16) { + c = 'X' | (state->flags & FMT_FORMAT_LOWER); + fmt_sprintf_state_produce_raw_char(state, c); + } + } else if (sign != '\0') { + fmt_sprintf_state_produce_raw_char(state, sign); + } + + if (!(state->flags & FMT_FORMAT_LEFT_JUSTIFY)) { + c = (state->flags & FMT_FORMAT_ZERO_PAD) ? '0' : ' '; + + while (state->width > 0) { + state->width--; + fmt_sprintf_state_produce_raw_char(state, c); + } + + state->width--; + } + + while (i < state->precision) { + state->precision--; + fmt_sprintf_state_produce_raw_char(state, '0'); + } + + state->precision--; + + while (i > 0) { + i--; + fmt_sprintf_state_produce_raw_char(state, tmp[i]); + } + + while (state->width > 0) { + state->width--; + fmt_sprintf_state_produce_raw_char(state, ' '); + } + + state->width--; +} + +static void +fmt_sprintf_state_produce_char(struct fmt_sprintf_state *state) +{ + char c; + + c = va_arg(state->ap, int); + + if (!(state->flags & FMT_FORMAT_LEFT_JUSTIFY)) { + for (;;) { + state->width--; + + if (state->width <= 0) { + break; + } + + fmt_sprintf_state_produce_raw_char(state, ' '); + } + } + + fmt_sprintf_state_produce_raw_char(state, c); + + for (;;) { + state->width--; + + if (state->width <= 0) { + break; + } + + fmt_sprintf_state_produce_raw_char(state, ' '); + } +} + +static void +fmt_sprintf_state_produce_str(struct fmt_sprintf_state *state) +{ + int i, len; + char *s; + + s = va_arg(state->ap, char *); + + if (s == NULL) { + s = "(null)"; + } + + len = 0; + + for (len = 0; s[len] != '\0'; len++) { + if (len == state->precision) { + break; + } + } + + if (!(state->flags & FMT_FORMAT_LEFT_JUSTIFY)) { + while (len < state->width) { + state->width--; + fmt_sprintf_state_produce_raw_char(state, ' '); + } + } + + for (i = 0; i < len; i++) { + fmt_sprintf_state_produce_raw_char(state, *s); + s++; + } + + while (len < state->width) { + state->width--; + fmt_sprintf_state_produce_raw_char(state, ' '); + } +} + +static void +fmt_sprintf_state_produce_nrchars(struct fmt_sprintf_state *state) +{ + if (state->modifier == FMT_MODIFIER_CHAR) { + signed char *ptr = va_arg(state->ap, signed char *); + *ptr = state->str - state->start; + } else if (state->modifier == FMT_MODIFIER_SHORT) { + short *ptr = va_arg(state->ap, short *); + *ptr = state->str - state->start; + } else if (state->modifier == FMT_MODIFIER_LONG) { + long *ptr = va_arg(state->ap, long *); + *ptr = state->str - state->start; + } else if (state->modifier == FMT_MODIFIER_LONGLONG) { + long long *ptr = va_arg(state->ap, long long *); + *ptr = state->str - state->start; + } else if (state->modifier == FMT_MODIFIER_SIZE) { + ssize_t *ptr = va_arg(state->ap, ssize_t *); + *ptr = state->str - state->start; + } else if (state->modifier == FMT_MODIFIER_PTRDIFF) { + ptrdiff_t *ptr = va_arg(state->ap, ptrdiff_t *); + *ptr = state->str - state->start; + } else { + int *ptr = va_arg(state->ap, int *); + *ptr = state->str - state->start; + } +} + +static void +fmt_sprintf_state_produce(struct fmt_sprintf_state *state) +{ + switch (state->specifier) { + case FMT_SPECIFIER_INT: + fmt_sprintf_state_produce_int(state); + break; + case FMT_SPECIFIER_CHAR: + fmt_sprintf_state_produce_char(state); + break; + case FMT_SPECIFIER_STR: + fmt_sprintf_state_produce_str(state); + break; + case FMT_SPECIFIER_NRCHARS: + fmt_sprintf_state_produce_nrchars(state); + break; + case FMT_SPECIFIER_PERCENT: + case FMT_SPECIFIER_INVALID: + fmt_sprintf_state_produce_raw_char(state, '%'); + break; + } +} + +int +fmt_sprintf(char *str, const char *format, ...) +{ + va_list ap; + int length; + + va_start(ap, format); + length = fmt_vsprintf(str, format, ap); + va_end(ap); + + return length; +} + +int +fmt_vsprintf(char *str, const char *format, va_list ap) +{ + return fmt_vsnprintf(str, FMT_NOLIMIT, format, ap); +} + +int +fmt_snprintf(char *str, size_t size, const char *format, ...) +{ + va_list ap; + int length; + + va_start(ap, format); + length = fmt_vsnprintf(str, size, format, ap); + va_end(ap); + + return length; +} + +int +fmt_vsnprintf(char *str, size_t size, const char *format, va_list ap) +{ + struct fmt_sprintf_state state; + int error; + + fmt_sprintf_state_init(&state, str, size, format, ap); + + for (;;) { + error = fmt_sprintf_state_consume(&state); + + if (error == ERROR_AGAIN) { + continue; + } else if (error) { + break; + } + + fmt_sprintf_state_produce(&state); + } + + return fmt_sprintf_state_finalize(&state); +} + +static char +fmt_atoi(char c) +{ + assert(fmt_isxdigit(c)); + + if (fmt_isdigit(c)) { + return c - '0'; + } else if (c >= 'a' && c <= 'f') { + return 10 + (c - 'a'); + } else { + return 10 + (c - 'A'); + } +} + +static bool +fmt_isspace(char c) +{ + if (c == ' ') { + return true; + } + + if ((c >= '\t') && (c <= '\f')) { + return true; + } + + return false; +} + +static void +fmt_skip(const char **strp) +{ + while (fmt_isspace(**strp)) { + (*strp)++; + } +} + +static void +fmt_sscanf_state_init(struct fmt_sscanf_state *state, const char *str, + const char *format, va_list ap) +{ + state->str = str; + state->start = str; + state->format = format; + state->flags = 0; + state->width = 0; + va_copy(state->ap, ap); + state->nr_convs = 0; +} + +static int +fmt_sscanf_state_finalize(struct fmt_sscanf_state *state) +{ + va_end(state->ap); + return state->nr_convs; +} + +static void +fmt_sscanf_state_report_conv(struct fmt_sscanf_state *state) +{ + if (state->nr_convs == EOF) { + state->nr_convs = 1; + return; + } + + state->nr_convs++; +} + +static void +fmt_sscanf_state_report_error(struct fmt_sscanf_state *state) +{ + if (state->nr_convs != 0) { + return; + } + + state->nr_convs = EOF; +} + +static void +fmt_sscanf_state_skip_space(struct fmt_sscanf_state *state) +{ + fmt_skip(&state->str); +} + +static char +fmt_sscanf_state_consume_string(struct fmt_sscanf_state *state) +{ + char c; + + c = fmt_consume(&state->str); + + if (state->flags & FMT_FORMAT_CHECK_WIDTH) { + if (state->width == 0) { + c = EOF; + } else { + state->width--; + } + } + + return c; +} + +static void +fmt_sscanf_state_restore_string(struct fmt_sscanf_state *state) +{ + fmt_restore(&state->str); +} + +static char +fmt_sscanf_state_consume_format(struct fmt_sscanf_state *state) +{ + return fmt_consume(&state->format); +} + +static void +fmt_sscanf_state_restore_format(struct fmt_sscanf_state *state) +{ + fmt_restore(&state->format); +} + +static void +fmt_sscanf_state_consume_flags(struct fmt_sscanf_state *state) +{ + bool found; + char c; + + found = true; + state->flags = 0; + + do { + c = fmt_sscanf_state_consume_format(state); + + switch (c) { + case '*': + state->flags |= FMT_FORMAT_DISCARD; + break; + default: + found = false; + break; + } + } while (found); + + fmt_sscanf_state_restore_format(state); +} + +static void +fmt_sscanf_state_consume_width(struct fmt_sscanf_state *state) +{ + char c; + + state->width = 0; + + for (;;) { + c = fmt_sscanf_state_consume_format(state); + + if (!fmt_isdigit(c)) { + break; + } + + state->width = state->width * 10 + (c - '0'); + } + + if (state->width != 0) { + state->flags |= FMT_FORMAT_CHECK_WIDTH; + } + + fmt_sscanf_state_restore_format(state); +} + +static void +fmt_sscanf_state_consume_modifier(struct fmt_sscanf_state *state) +{ + char c, c2; + + c = fmt_sscanf_state_consume_format(state); + + switch (c) { + case 'h': + case 'l': + c2 = fmt_sscanf_state_consume_format(state); + + if (c == c2) { + state->modifier = (c == 'h') ? FMT_MODIFIER_CHAR + : FMT_MODIFIER_LONGLONG; + } else { + state->modifier = (c == 'h') ? FMT_MODIFIER_SHORT + : FMT_MODIFIER_LONG; + fmt_sscanf_state_restore_format(state); + } + + break; + case 'z': + state->modifier = FMT_MODIFIER_SIZE; + break; + case 't': + state->modifier = FMT_MODIFIER_PTRDIFF; + break; + default: + state->modifier = FMT_MODIFIER_NONE; + fmt_sscanf_state_restore_format(state); + break; + } +} + +static void +fmt_sscanf_state_consume_specifier(struct fmt_sscanf_state *state) +{ + char c; + + c = fmt_sscanf_state_consume_format(state); + + switch (c) { + case 'i': + state->base = 0; + state->flags |= FMT_FORMAT_CONV_SIGNED; + state->specifier = FMT_SPECIFIER_INT; + break; + case 'd': + state->flags |= FMT_FORMAT_CONV_SIGNED; + case 'u': + state->base = 10; + state->specifier = FMT_SPECIFIER_INT; + break; + case 'o': + state->base = 8; + state->specifier = FMT_SPECIFIER_INT; + break; + case 'p': + state->modifier = FMT_MODIFIER_PTR; + case 'x': + case 'X': + state->base = 16; + state->specifier = FMT_SPECIFIER_INT; + break; + case 'c': + state->specifier = FMT_SPECIFIER_CHAR; + break; + case 's': + state->specifier = FMT_SPECIFIER_STR; + break; + case 'n': + state->specifier = FMT_SPECIFIER_NRCHARS; + break; + case '%': + state->specifier = FMT_SPECIFIER_PERCENT; + break; + default: + state->specifier = FMT_SPECIFIER_INVALID; + fmt_sscanf_state_restore_format(state); + break; + } +} + +static int +fmt_sscanf_state_discard_char(struct fmt_sscanf_state *state, char c) +{ + char c2; + + if (fmt_isspace(c)) { + fmt_sscanf_state_skip_space(state); + return 0; + } + + c2 = fmt_sscanf_state_consume_string(state); + + if (c != c2) { + if ((c2 == '\0') && (state->nr_convs == 0)) { + state->nr_convs = EOF; + } + + return ERROR_INVAL; + } + + return 0; +} + +static int +fmt_sscanf_state_consume(struct fmt_sscanf_state *state) +{ + int error; + char c; + + state->flags = 0; + + c = fmt_consume(&state->format); + + if (c == '\0') { + return ERROR_IO; + } + + if (c != '%') { + error = fmt_sscanf_state_discard_char(state, c); + + if (error) { + return error; + } + + return ERROR_AGAIN; + } + + fmt_sscanf_state_consume_flags(state); + fmt_sscanf_state_consume_width(state); + fmt_sscanf_state_consume_modifier(state); + fmt_sscanf_state_consume_specifier(state); + return 0; +} + +static int +fmt_sscanf_state_produce_int(struct fmt_sscanf_state *state) +{ + unsigned long long n, m, tmp; + char c, buf[FMT_MAX_NUM_SIZE]; + bool negative; + size_t i; + + negative = 0; + + fmt_sscanf_state_skip_space(state); + c = fmt_sscanf_state_consume_string(state); + + if (c == '-') { + negative = true; + c = fmt_sscanf_state_consume_string(state); + } + + if (c == '0') { + c = fmt_sscanf_state_consume_string(state); + + if ((c == 'x') || (c == 'X')) { + if (state->base == 0) { + state->base = 16; + } + + if (state->base == 16) { + c = fmt_sscanf_state_consume_string(state); + } else { + fmt_sscanf_state_restore_string(state); + c = '0'; + } + } else { + if (state->base == 0) { + state->base = 8; + } + + if (state->base != 8) { + fmt_sscanf_state_restore_string(state); + c = '0'; + } + } + } + + i = 0; + + while (c != '\0') { + if (state->base == 8) { + if (!((c >= '0') && (c <= '7'))) { + break; + } + } else if (state->base == 16) { + if (!fmt_isxdigit(c)) { + break; + } + } else { + if (!fmt_isdigit(c)) { + break; + } + } + + /* XXX Standard sscanf provides no way to cleanly handle overflows */ + if (i < (ARRAY_SIZE(buf) - 1)) { + buf[i] = c; + } else if (i == (ARRAY_SIZE(buf) - 1)) { + strcpy(buf, "1"); + negative = true; + } + + i++; + c = fmt_sscanf_state_consume_string(state); + } + + fmt_sscanf_state_restore_string(state); + + if (state->flags & FMT_FORMAT_DISCARD) { + return 0; + } + + if (i == 0) { + if (c == '\0') { + fmt_sscanf_state_report_error(state); + return ERROR_INVAL; + } + + buf[0] = '0'; + i = 1; + } + + if (i < ARRAY_SIZE(buf)) { + buf[i] = '\0'; + i--; + } else { + i = strlen(buf) - 1; + } + + n = 0; + +#ifndef __LP64__ + if (state->modifier == FMT_MODIFIER_LONGLONG) { +#endif /* __LP64__ */ + m = 1; + tmp = 0; + + while (&buf[i] >= buf) { + tmp += fmt_atoi(buf[i]) * m; + + if (tmp < n) { + n = 1; + negative = true; + break; + } + + n = tmp; + m *= state->base; + i--; + } +#ifndef __LP64__ + } else { + unsigned long _n, _m, _tmp; + + _n = 0; + _m = 1; + _tmp = 0; + + while (&buf[i] >= buf) { + _tmp += fmt_atoi(buf[i]) * _m; + + if (_tmp < _n) { + _n = 1; + negative = true; + break; + } + + _n = _tmp; + _m *= state->base; + i--; + } + + n = _n; + } +#endif /* __LP64__ */ + + if (negative) { + n = -n; + } + + switch (state->modifier) { + case FMT_MODIFIER_CHAR: + if (state->flags & FMT_FORMAT_CONV_SIGNED) { + *va_arg(state->ap, char *) = n; + } else { + *va_arg(state->ap, unsigned char *) = n; + } + + break; + case FMT_MODIFIER_SHORT: + if (state->flags & FMT_FORMAT_CONV_SIGNED) { + *va_arg(state->ap, short *) = n; + } else { + *va_arg(state->ap, unsigned short *) = n; + } + + break; + case FMT_MODIFIER_LONG: + if (state->flags & FMT_FORMAT_CONV_SIGNED) { + *va_arg(state->ap, long *) = n; + } else { + *va_arg(state->ap, unsigned long *) = n; + } + + break; + case FMT_MODIFIER_LONGLONG: + if (state->flags & FMT_FORMAT_CONV_SIGNED) { + *va_arg(state->ap, long long *) = n; + } else { + *va_arg(state->ap, unsigned long long *) = n; + } + + break; + case FMT_MODIFIER_PTR: + *va_arg(state->ap, uintptr_t *) = n; + break; + case FMT_MODIFIER_SIZE: + *va_arg(state->ap, size_t *) = n; + break; + case FMT_MODIFIER_PTRDIFF: + *va_arg(state->ap, ptrdiff_t *) = n; + break; + default: + if (state->flags & FMT_FORMAT_CONV_SIGNED) { + *va_arg(state->ap, int *) = n; + } else { + *va_arg(state->ap, unsigned int *) = n; + } + } + + fmt_sscanf_state_report_conv(state); + return 0; +} + +static int +fmt_sscanf_state_produce_char(struct fmt_sscanf_state *state) +{ + char c, *dest; + int i, width; + + if (state->flags & FMT_FORMAT_DISCARD) { + dest = NULL; + } else { + dest = va_arg(state->ap, char *); + } + + if (state->flags & FMT_FORMAT_CHECK_WIDTH) { + width = state->width; + } else { + width = 1; + } + + for (i = 0; i < width; i++) { + c = fmt_sscanf_state_consume_string(state); + + if ((c == '\0') || (c == EOF)) { + break; + } + + if (dest != NULL) { + *dest = c; + dest++; + } + } + + if (i < width) { + fmt_sscanf_state_restore_string(state); + } + + if ((dest != NULL) && (i != 0)) { + fmt_sscanf_state_report_conv(state); + } + + return 0; +} + +static int +fmt_sscanf_state_produce_str(struct fmt_sscanf_state *state) +{ + const char *orig; + char c, *dest; + + orig = state->str; + + fmt_sscanf_state_skip_space(state); + + if (state->flags & FMT_FORMAT_DISCARD) { + dest = NULL; + } else { + dest = va_arg(state->ap, char *); + } + + for (;;) { + c = fmt_sscanf_state_consume_string(state); + + if ((c == '\0') || (c == ' ') || (c == EOF)) { + break; + } + + if (dest != NULL) { + *dest = c; + dest++; + } + } + + fmt_sscanf_state_restore_string(state); + + if (state->str == orig) { + fmt_sscanf_state_report_error(state); + return ERROR_INVAL; + } + + if (dest != NULL) { + *dest = '\0'; + fmt_sscanf_state_report_conv(state); + } + + return 0; +} + +static int +fmt_sscanf_state_produce_nrchars(struct fmt_sscanf_state *state) +{ + *va_arg(state->ap, int *) = state->str - state->start; + return 0; +} + +static int +fmt_sscanf_state_produce(struct fmt_sscanf_state *state) +{ + switch (state->specifier) { + case FMT_SPECIFIER_INT: + return fmt_sscanf_state_produce_int(state); + case FMT_SPECIFIER_CHAR: + return fmt_sscanf_state_produce_char(state); + case FMT_SPECIFIER_STR: + return fmt_sscanf_state_produce_str(state); + case FMT_SPECIFIER_NRCHARS: + return fmt_sscanf_state_produce_nrchars(state); + case FMT_SPECIFIER_PERCENT: + fmt_sscanf_state_skip_space(state); + return fmt_sscanf_state_discard_char(state, '%'); + default: + fmt_sscanf_state_report_error(state); + return ERROR_INVAL; + } +} + +int +fmt_sscanf(const char *str, const char *format, ...) +{ + va_list ap; + int ret; + + va_start(ap, format); + ret = fmt_vsscanf(str, format, ap); + va_end(ap); + + return ret; +} + +int +fmt_vsscanf(const char *str, const char *format, va_list ap) +{ + struct fmt_sscanf_state state; + int error; + + fmt_sscanf_state_init(&state, str, format, ap); + + for (;;) { + error = fmt_sscanf_state_consume(&state); + + if (error == ERROR_AGAIN) { + continue; + } else if (error) { + break; + } + + error = fmt_sscanf_state_produce(&state); + + if (error) { + break; + } + } + + return fmt_sscanf_state_finalize(&state); +} diff --git a/lib/fmt.h b/lib/fmt.h new file mode 100644 index 0000000..babaa52 --- /dev/null +++ b/lib/fmt.h @@ -0,0 +1,69 @@ +/* + * Copyright (c) 2010-2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * Upstream site with license notes : + * http://git.sceen.net/rbraun/librbraun.git/ + * + * + * Formatted string functions. + * + * The functions provided by this module implement a subset of the standard + * sprintf- and sscanf-like functions. + * + * sprintf: + * - flags: # 0 - ' ' (space) + + * - field width is supported + * - precision is supported + * + * sscanf: + * - flags: * + * - field width is supported + * + * common: + * - modifiers: hh h l ll z t + * - specifiers: d i o u x X c s p n % + */ + +#ifndef _FMT_H +#define _FMT_H + +#include <stdarg.h> +#include <stddef.h> + +int fmt_sprintf(char *str, const char *format, ...) + __attribute__((format(printf, 2, 3))); + +int fmt_vsprintf(char *str, const char *format, va_list ap) + __attribute__((format(printf, 2, 0))); + +int fmt_snprintf(char *str, size_t size, const char *format, ...) + __attribute__((format(printf, 3, 4))); + +int fmt_vsnprintf(char *str, size_t size, const char *format, va_list ap) + __attribute__((format(printf, 3, 0))); + +int fmt_sscanf(const char *str, const char *format, ...) + __attribute__((format(scanf, 2, 3))); + +int fmt_vsscanf(const char *str, const char *format, va_list ap) + __attribute__((format(scanf, 2, 0))); + +#endif /* _FMT_H */ diff --git a/lib/hash.h b/lib/hash.h new file mode 100644 index 0000000..92f3180 --- /dev/null +++ b/lib/hash.h @@ -0,0 +1,123 @@ +/* + * Copyright (c) 2010-2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * Upstream site with license notes : + * http://git.sceen.net/rbraun/librbraun.git/ + * + * + * Hash functions for integers and strings. + * + * Integer hashing follows Thomas Wang's paper about his 32/64-bits mix + * functions : + * - https://gist.github.com/badboy/6267743 + * + * String hashing uses a variant of the djb2 algorithm with k=31, as in + * the implementation of the hashCode() method of the Java String class : + * - http://www.javamex.com/tutorials/collections/hash_function_technical.shtml + * + * Note that this algorithm isn't suitable to obtain usable 64-bits hashes + * and is expected to only serve as an array index producer. + * + * These functions all have a bits parameter that indicates the number of + * relevant bits the caller is interested in. When returning a hash, its + * value must be truncated so that it can fit in the requested bit size. + * It can be used by the implementation to select high or low bits, depending + * on their relative randomness. To get complete, unmasked hashes, use the + * HASH_ALLBITS macro. + */ + +#ifndef _HASH_H +#define _HASH_H + +#include <assert.h> +#include <stdint.h> + +#ifdef __LP64__ +#define HASH_ALLBITS 64 +#define hash_long(n, bits) hash_int64(n, bits) +#else /* __LP64__ */ +#define HASH_ALLBITS 32 +#define hash_long(n, bits) hash_int32(n, bits) +#endif + +static inline uint32_t +hash_int32(uint32_t n, unsigned int bits) +{ + uint32_t hash; + + hash = n; + hash = ~hash + (hash << 15); + hash ^= (hash >> 12); + hash += (hash << 2); + hash ^= (hash >> 4); + hash += (hash << 3) + (hash << 11); + hash ^= (hash >> 16); + + return hash >> (32 - bits); +} + +static inline uint64_t +hash_int64(uint64_t n, unsigned int bits) +{ + uint64_t hash; + + hash = n; + hash = ~hash + (hash << 21); + hash ^= (hash >> 24); + hash += (hash << 3) + (hash << 8); + hash ^= (hash >> 14); + hash += (hash << 2) + (hash << 4); + hash ^= (hash >> 28); + hash += (hash << 31); + + return hash >> (64 - bits); +} + +static inline uintptr_t +hash_ptr(const void *ptr, unsigned int bits) +{ + if (sizeof(uintptr_t) == 8) { + return hash_int64((uintptr_t)ptr, bits); + } else { + return hash_int32((uintptr_t)ptr, bits); + } +} + +static inline unsigned long +hash_str(const char *str, unsigned int bits) +{ + unsigned long hash; + char c; + + for (hash = 0; /* no condition */; str++) { + c = *str; + + if (c == '\0') { + break; + } + + hash = ((hash << 5) - hash) + c; + } + + return hash & ((1 << bits) - 1); +} + +#endif /* _HASH_H */ diff --git a/lib/list.h b/lib/list.h new file mode 100644 index 0000000..6e9c599 --- /dev/null +++ b/lib/list.h @@ -0,0 +1,538 @@ +/* + * Copyright (c) 2009-2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * Upstream site with license notes : + * http://git.sceen.net/rbraun/librbraun.git/ + * + * + * Doubly-linked list. + */ + +#ifndef _LIST_H +#define _LIST_H + +#include <stdbool.h> +#include <stddef.h> + +#include "macros.h" + +/* + * Structure used as both head and node. + * + * This implementation relies on using the same type for both heads and nodes. + * + * It is recommended to encode the use of struct list variables in their names, + * e.g. struct list free_list or struct list free_objects is a good hint for a + * list of free objects. A declaration like struct list free_node clearly + * indicates it is used as part of a node in the free list. + */ +struct list { + struct list *prev; + struct list *next; +}; + +/* + * Static list initializer. + */ +#define LIST_INITIALIZER(list) { &(list), &(list) } + +/* + * Initialize a list. + */ +static inline void +list_init(struct list *list) +{ + list->prev = list; + list->next = list; +} + +/* + * Initialize a list node. + * + * A node is in no list when its node members point to NULL. + */ +static inline void +list_node_init(struct list *node) +{ + node->prev = NULL; + node->next = NULL; +} + +/* + * Return true if node is in no list. + */ +static inline bool +list_node_unlinked(const struct list *node) +{ + return node->prev == NULL; +} + +/* + * Return the first node of a list. + */ +static inline struct list * +list_first(const struct list *list) +{ + return list->next; +} + +/* + * Return the last node of a list. + */ +static inline struct list * +list_last(const struct list *list) +{ + return list->prev; +} + +/* + * Return the node next to the given node. + */ +static inline struct list * +list_next(const struct list *node) +{ + return node->next; +} + +/* + * Return the node previous to the given node. + */ +static inline struct list * +list_prev(const struct list *node) +{ + return node->prev; +} + +/* + * Return true if node is invalid and denotes one of the ends of the list. + */ +static inline bool +list_end(const struct list *list, const struct list *node) +{ + return list == node; +} + +/* + * Return true if list is empty. + */ +static inline bool +list_empty(const struct list *list) +{ + return list == list->next; +} + +/* + * Return true if list contains exactly one node. + */ +static inline bool +list_singular(const struct list *list) +{ + return !list_empty(list) && (list->next == list->prev); +} + +/* + * Split list2 by moving its nodes up to, but not including, the given + * node into list1, which can be in a stale state. + * + * If list2 is empty, or node is list2 or list2->next, list1 is merely + * initialized. + */ +static inline void +list_split(struct list *list1, struct list *list2, struct list *node) +{ + if (list_empty(list2) || (list2->next == node) || list_end(list2, node)) { + list_init(list1); + return; + } + + list1->next = list2->next; + list1->next->prev = list1; + + list1->prev = node->prev; + node->prev->next = list1; + + list2->next = node; + node->prev = list2; +} + +/* + * Append the nodes of list2 at the end of list1. + * + * After completion, list2 is stale. + */ +static inline void +list_concat(struct list *list1, const struct list *list2) +{ + struct list *last1, *first2, *last2; + + if (list_empty(list2)) { + return; + } + + last1 = list1->prev; + first2 = list2->next; + last2 = list2->prev; + + last1->next = first2; + first2->prev = last1; + + last2->next = list1; + list1->prev = last2; +} + +/* + * Set the new head of a list. + * + * This function is an optimized version of : + * list_init(&new_list); + * list_concat(&new_list, &old_list); + * + * After completion, old_head is stale. + */ +static inline void +list_set_head(struct list *new_head, const struct list *old_head) +{ + if (list_empty(old_head)) { + list_init(new_head); + return; + } + + *new_head = *old_head; + new_head->next->prev = new_head; + new_head->prev->next = new_head; +} + +/* + * Add a node between two nodes. + * + * This function is private. + */ +static inline void +list_add(struct list *prev, struct list *next, struct list *node) +{ + next->prev = node; + node->next = next; + + prev->next = node; + node->prev = prev; +} + +/* + * Insert a node at the head of a list. + */ +static inline void +list_insert_head(struct list *list, struct list *node) +{ + list_add(list, list->next, node); +} + +/* + * Insert a node at the tail of a list. + */ +static inline void +list_insert_tail(struct list *list, struct list *node) +{ + list_add(list->prev, list, node); +} + +/* + * Insert a node before another node. + */ +static inline void +list_insert_before(struct list *next, struct list *node) +{ + list_add(next->prev, next, node); +} + +/* + * Insert a node after another node. + */ +static inline void +list_insert_after(struct list *prev, struct list *node) +{ + list_add(prev, prev->next, node); +} + +/* + * Remove a node from a list. + * + * After completion, the node is stale. + */ +static inline void +list_remove(struct list *node) +{ + node->prev->next = node->next; + node->next->prev = node->prev; +} + +/* + * Macro that evaluates to the address of the structure containing the + * given node based on the given type and member. + */ +#define list_entry(node, type, member) structof(node, type, member) + +/* + * Get the first entry of a list. + */ +#define list_first_entry(list, type, member) \ + list_entry(list_first(list), type, member) + +/* + * Get the last entry of a list. + */ +#define list_last_entry(list, type, member) \ + list_entry(list_last(list), type, member) + +/* + * Get the entry next to the given entry. + */ +#define list_next_entry(entry, member) \ + list_entry(list_next(&(entry)->member), typeof(*(entry)), member) + +/* + * Get the entry previous to the given entry. + */ +#define list_prev_entry(entry, member) \ + list_entry(list_prev(&(entry)->member), typeof(*(entry)), member) + +/* + * Forge a loop to process all nodes of a list. + * + * The node must not be altered during the loop. + */ +#define list_for_each(list, node) \ +for (node = list_first(list); \ + !list_end(list, node); \ + node = list_next(node)) + +/* + * Forge a loop to process all nodes of a list. + */ +#define list_for_each_safe(list, node, tmp) \ +for (node = list_first(list), tmp = list_next(node); \ + !list_end(list, node); \ + node = tmp, tmp = list_next(node)) + +/* + * Version of list_for_each() that processes nodes backward. + */ +#define list_for_each_reverse(list, node) \ +for (node = list_last(list); \ + !list_end(list, node); \ + node = list_prev(node)) + +/* + * Version of list_for_each_safe() that processes nodes backward. + */ +#define list_for_each_reverse_safe(list, node, tmp) \ +for (node = list_last(list), tmp = list_prev(node); \ + !list_end(list, node); \ + node = tmp, tmp = list_prev(node)) + +/* + * Forge a loop to process all entries of a list. + * + * The entry node must not be altered during the loop. + */ +#define list_for_each_entry(list, entry, member) \ +for (entry = list_first_entry(list, typeof(*entry), member); \ + !list_end(list, &entry->member); \ + entry = list_next_entry(entry, member)) + +/* + * Forge a loop to process all entries of a list. + */ +#define list_for_each_entry_safe(list, entry, tmp, member) \ +for (entry = list_first_entry(list, typeof(*entry), member), \ + tmp = list_next_entry(entry, member); \ + !list_end(list, &entry->member); \ + entry = tmp, tmp = list_next_entry(entry, member)) + +/* + * Version of list_for_each_entry() that processes entries backward. + */ +#define list_for_each_entry_reverse(list, entry, member) \ +for (entry = list_last_entry(list, typeof(*entry), member); \ + !list_end(list, &entry->member); \ + entry = list_prev_entry(entry, member)) + +/* + * Version of list_for_each_entry_safe() that processes entries backward. + */ +#define list_for_each_entry_reverse_safe(list, entry, tmp, member) \ +for (entry = list_last_entry(list, typeof(*entry), member), \ + tmp = list_prev_entry(entry, member); \ + !list_end(list, &entry->member); \ + entry = tmp, tmp = list_prev_entry(entry, member)) + +/* + * Lockless variants + * + * This is a subset of the main interface that only supports forward traversal. + * In addition, list_end() is also allowed in read-side critical sections. + */ + +/* + * These macros can be replaced by actual functions in an environment + * that provides lockless synchronization such as RCU. + */ +#define llsync_store_ptr(ptr, value) ((ptr) = (value)) +#define llsync_load_ptr(ptr) (ptr) + +/* + * Return the first node of a list. + */ +static inline struct list * +list_llsync_first(const struct list *list) +{ + return llsync_load_ptr(list->next); +} + +/* + * Return the node next to the given node. + */ +static inline struct list * +list_llsync_next(const struct list *node) +{ + return llsync_load_ptr(node->next); +} + +/* + * Add a node between two nodes. + * + * This function is private. + */ +static inline void +list_llsync_add(struct list *prev, struct list *next, struct list *node) +{ + node->next = next; + node->prev = prev; + llsync_store_ptr(prev->next, node); + next->prev = node; +} + +/* + * Insert a node at the head of a list. + */ +static inline void +list_llsync_insert_head(struct list *list, struct list *node) +{ + list_llsync_add(list, list->next, node); +} + +/* + * Insert a node at the tail of a list. + */ +static inline void +list_llsync_insert_tail(struct list *list, struct list *node) +{ + list_llsync_add(list->prev, list, node); +} + +/* + * Insert a node before another node. + */ +static inline void +list_llsync_insert_before(struct list *next, struct list *node) +{ + list_llsync_add(next->prev, next, node); +} + +/* + * Insert a node after another node. + */ +static inline void +list_llsync_insert_after(struct list *prev, struct list *node) +{ + list_llsync_add(prev, prev->next, node); +} + +/* + * Remove a node from a list. + * + * After completion, the node is stale. + */ +static inline void +list_llsync_remove(struct list *node) +{ + node->next->prev = node->prev; + llsync_store_ptr(node->prev->next, node->next); +} + +/* + * Macro that evaluates to the address of the structure containing the + * given node based on the given type and member. + */ +#define list_llsync_entry(node, type, member) \ + structof(llsync_load_ptr(node), type, member) + +/* + * Get the first entry of a list. + * + * Unlike list_first_entry(), this macro may evaluate to NULL, because + * the node pointer can only be read once, preventing the combination + * of lockless list_empty()/list_first_entry() variants. + */ +#define list_llsync_first_entry(list, type, member) \ +MACRO_BEGIN \ + struct list *___list; \ + struct list *___first; \ + \ + ___list = (list); \ + ___first = list_llsync_first(___list); \ + list_end(___list, ___first) \ + ? NULL \ + : list_entry(___first, type, member); \ +MACRO_END + +/* + * Get the entry next to the given entry. + * + * Unlike list_next_entry(), this macro may evaluate to NULL, because + * the node pointer can only be read once, preventing the combination + * of lockless list_empty()/list_next_entry() variants. + */ +#define list_llsync_next_entry(entry, member) \ + list_llsync_first_entry(&entry->member, typeof(*entry), member) + +/* + * Forge a loop to process all nodes of a list. + * + * The node must not be altered during the loop. + */ +#define list_llsync_for_each(list, node) \ +for (node = list_llsync_first(list); \ + !list_end(list, node); \ + node = list_llsync_next(node)) + +/* + * Forge a loop to process all entries of a list. + * + * The entry node must not be altered during the loop. + */ +#define list_llsync_for_each_entry(list, entry, member) \ +for (entry = list_llsync_entry(list_first(list), \ + typeof(*entry), member); \ + !list_end(list, &entry->member); \ + entry = list_llsync_entry(list_next(&entry->member), \ + typeof(*entry), member)) + +#endif /* _LIST_H */ diff --git a/lib/macros.h b/lib/macros.h new file mode 100644 index 0000000..a61f80e --- /dev/null +++ b/lib/macros.h @@ -0,0 +1,94 @@ +/* + * Copyright (c) 2009-2015 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * Upstream site with license notes : + * http://git.sceen.net/rbraun/librbraun.git/ + * + * + * Helper macros. + */ + +#ifndef _MACROS_H +#define _MACROS_H + +#if !defined(__GNUC__) || (__GNUC__ < 4) +#error "GCC 4+ required" +#endif + +#include <stddef.h> + +#define MACRO_BEGIN ({ +#define MACRO_END }) + +#define __QUOTE(x) #x +#define QUOTE(x) __QUOTE(x) + +#define STRLEN(x) (sizeof(x) - 1) +#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) + +#define MIN(a, b) ((a) < (b) ? (a) : (b)) +#define MAX(a, b) ((a) > (b) ? (a) : (b)) + +#define DIV_CEIL(n, d) (((n) + (d) - 1) / (d)) + +#define P2ALIGNED(x, a) (((x) & ((a) - 1)) == 0) +#define ISP2(x) P2ALIGNED(x, x) +#define P2ALIGN(x, a) ((x) & -(a)) /* decreases if not aligned */ +#define P2ROUND(x, a) (-(-(x) & -(a))) /* increases if not aligned */ +#define P2END(x, a) (-(~(x) & -(a))) /* always increases */ + +#define structof(ptr, type, member) \ + ((type *)((char *)(ptr) - offsetof(type, member))) + +#define likely(expr) __builtin_expect(!!(expr), 1) +#define unlikely(expr) __builtin_expect(!!(expr), 0) + +#define barrier() asm volatile("" : : : "memory") + +/* + * The following macros may be provided by the C environment. + */ + +#ifndef __noinline +#define __noinline __attribute__((noinline)) +#endif + +#ifndef __aligned +#define __aligned(x) __attribute__((aligned(x))) +#endif + +#ifndef __always_inline +#define __always_inline inline __attribute__((always_inline)) +#endif + +#ifndef __section +#define __section(x) __attribute__((section(x))) +#endif + +#ifndef __packed +#define __packed __attribute__((packed)) +#endif + +#ifndef __unused +#define __unused __attribute__((unused)) +#endif + +#endif /* _MACROS_H */ diff --git a/lib/shell.c b/lib/shell.c new file mode 100644 index 0000000..8272b24 --- /dev/null +++ b/lib/shell.c @@ -0,0 +1,1212 @@ +/* + * Copyright (c) 2015-2018 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * Upstream site with license notes : + * http://git.sceen.net/rbraun/librbraun.git/ + */ + +#include <stddef.h> +#include <stdio.h> +#include <stdint.h> +#include <string.h> + +#include <lib/macros.h> +#include <lib/hash.h> +#include <lib/shell.h> + +#include <src/error.h> +#include <src/mutex.h> +#include <src/panic.h> +#include <src/thread.h> +#include <src/uart.h> + +#define SHELL_STACK_SIZE 4096 + +/* + * Binary exponent and size of the hash table used to store commands. + */ +#define SHELL_HTABLE_BITS 6 +#define SHELL_HTABLE_SIZE (1 << SHELL_HTABLE_BITS) + +struct shell_bucket { + struct shell_cmd *cmd; +}; + +/* + * Hash table for quick command lookup. + */ +static struct shell_bucket shell_htable[SHELL_HTABLE_SIZE]; + +#define SHELL_COMPLETION_MATCH_FMT "-16s" +#define SHELL_COMPLETION_NR_MATCHES_PER_LINE 4 + +/* + * Sorted command list. + */ +static struct shell_cmd *shell_list; + +/* + * Lock protecting access to the hash table and list of commands. + * + * Note that this lock only protects access to the commands containers, + * not the commands themselves. In particular, it is not necessary to + * hold this lock when a command is used, i.e. when accessing a command + * name, function pointer, or description. + */ +static struct mutex shell_lock; + +/* + * Escape sequence states. + * + * Here is an incomplete description of escape sequences : + * http://en.wikipedia.org/wiki/ANSI_escape_code + * + * These values must be different from 0. + */ +#define SHELL_ESC_STATE_START 1 +#define SHELL_ESC_STATE_CSI 2 + +/* + * This value changes depending on the standard used and was chosen arbitrarily. + */ +#define SHELL_ESC_SEQ_MAX_SIZE 8 + +typedef void (*shell_esc_seq_fn)(void); + +struct shell_esc_seq { + const char *str; + shell_esc_seq_fn fn; +}; + +#define SHELL_LINE_MAX_SIZE 64 + +/* + * Line containing a shell entry. + * + * The string must be nul-terminated. The size doesn't include this + * additional nul character, the same way strlen() doesn't account for it. + */ +struct shell_line { + char str[SHELL_LINE_MAX_SIZE]; + unsigned long size; +}; + +/* + * Number of entries in the history. + * + * One of these entryes is used as the current line. + */ +#define SHELL_HISTORY_SIZE 21 + +#if SHELL_HISTORY_SIZE == 0 +#error "shell history size must be non-zero" +#endif /* SHELL_HISTORY_SIZE == 0 */ + +/* + * Shell history. + * + * The history is never empty. There is always at least one entry, the + * current line, referenced by the newest (most recent) index. The array + * is used like a circular buffer, i.e. old entries are implicitely + * erased by new ones. The index references the entry used as a template + * for the current line. + */ +static struct shell_line shell_history[SHELL_HISTORY_SIZE]; +static unsigned long shell_history_newest; +static unsigned long shell_history_oldest; +static unsigned long shell_history_index; + +/* + * Cursor within the current line. + */ +static unsigned long shell_cursor; + +#define SHELL_SEPARATOR ' ' + +/* + * Commonly used backspace control characters. + * + * XXX Adjust for your needs. + */ +#define SHELL_ERASE_BS '\b' +#define SHELL_ERASE_DEL '\x7f' + +/* + * Buffer used to store the current line during argument processing. + * + * The pointers in the argv array point inside this buffer. The + * separators immediately following the arguments are replaced with + * nul characters. + */ +static char shell_tmp_line[SHELL_LINE_MAX_SIZE]; + +#define SHELL_MAX_ARGS 16 + +static int shell_argc; +static char *shell_argv[SHELL_MAX_ARGS]; + +static const char * +shell_find_word(const char *str) +{ + for (;;) { + if ((*str == '\0') || (*str != SHELL_SEPARATOR)) { + break; + } + + str++; + } + + return str; +} + +void +shell_cmd_init(struct shell_cmd *cmd, const char *name, + shell_fn_t fn, const char *usage, + const char *short_desc, const char *long_desc) +{ + cmd->ht_next = NULL; + cmd->ls_next = NULL; + cmd->name = name; + cmd->fn = fn; + cmd->usage = usage; + cmd->short_desc = short_desc; + cmd->long_desc = long_desc; +} + +static const char * +shell_cmd_name(const struct shell_cmd *cmd) +{ + return cmd->name; +} + +static inline struct shell_bucket * +shell_bucket_get(const char *name) +{ + return &shell_htable[hash_str(name, SHELL_HTABLE_BITS)]; +} + +static void +shell_cmd_acquire(void) +{ + mutex_lock(&shell_lock); +} + +static void +shell_cmd_release(void) +{ + mutex_unlock(&shell_lock); +} + +static const struct shell_cmd * +shell_cmd_lookup(const char *name) +{ + const struct shell_bucket *bucket; + const struct shell_cmd *cmd; + + shell_cmd_acquire(); + + bucket = shell_bucket_get(name); + + for (cmd = bucket->cmd; cmd != NULL; cmd = cmd->ht_next) { + if (strcmp(cmd->name, name) == 0) { + break; + } + } + + shell_cmd_release(); + + return cmd; +} + +/* + * Look up the first command that matches a given string. + * + * The input string is defined by the given string pointer and size. + * + * The global lock must be acquired before calling this function. + */ +static const struct shell_cmd * +shell_cmd_match(const struct shell_cmd *cmd, const char *str, + unsigned long size) +{ + while (cmd != NULL) { + if (strncmp(cmd->name, str, size) == 0) { + return cmd; + } + + cmd = cmd->ls_next; + } + + return NULL; +} + +/* + * Attempt command auto-completion. + * + * The given string is the beginning of a command, or the empty string. + * The sizep parameter initially points to the size of the given string. + * If the string matches any registered command, the cmdp pointer is + * updated to point to the first matching command in the sorted list of + * commands, and sizep is updated to the number of characters in the + * command name that are common in subsequent commands. The command + * pointer and the returned size can be used to print a list of commands + * eligible for completion. + * + * If there is a single match for the given string, return 0. If there + * are more than one match, return ERROR_AGAIN. If there is no match, + * return ERROR_INVAL. + * + * The global lock must be acquired before calling this function. + */ +static int +shell_cmd_complete(const char *str, unsigned long *sizep, + const struct shell_cmd **cmdp) +{ + const struct shell_cmd *cmd, *next; + unsigned long size; + + size = *sizep; + + /* + * Start with looking up a command that matches the given argument. + * If there is no match, return an error. + */ + cmd = shell_cmd_match(shell_list, str, size); + + if (cmd == NULL) { + return ERROR_INVAL; + } + + *cmdp = cmd; + + /* + * If at least one command matches, try to complete it. + * There can be two cases : + * 1/ There is one and only one match, which is directly returned. + * 2/ There are several matches, in which case the common length is + * computed. + */ + next = cmd->ls_next; + + if ((next == NULL) + || (strncmp(cmd->name, next->name, size) != 0)) { + *sizep = strlen(cmd->name); + return 0; + } + + /* + * When computing the common length, all the commands that can match + * must be evaluated. Considering the current command is the first + * that can match, the only other variable missing is the last + * command that can match. + */ + while (next->ls_next != NULL) { + if (strncmp(cmd->name, next->ls_next->name, size) != 0) { + break; + } + + next = next->ls_next; + } + + if (size == 0) { + size = 1; + } + + while ((cmd->name[size - 1] != '\0') + && (cmd->name[size - 1] == next->name[size - 1])) { + size++; + } + + size--; + *sizep = size; + return ERROR_AGAIN; +} + +/* + * Print a list of commands eligible for completion, starting at the + * given command. Other eligible commands share the same prefix, as + * defined by the size argument. + * + * The global lock must be acquired before calling this function. + */ +static void +shell_cmd_print_matches(const struct shell_cmd *cmd, unsigned long size) +{ + const struct shell_cmd *tmp; + unsigned int i; + + printf("\n"); + + for (tmp = cmd, i = 1; tmp != NULL; tmp = tmp->ls_next, i++) { + if (strncmp(cmd->name, tmp->name, size) != 0) { + break; + } + + printf("%" SHELL_COMPLETION_MATCH_FMT, tmp->name); + + if ((i % SHELL_COMPLETION_NR_MATCHES_PER_LINE) == 0) { + printf("\n"); + } + } + + if ((i % SHELL_COMPLETION_NR_MATCHES_PER_LINE) != 1) { + printf("\n"); + } +} + +static int +shell_cmd_check_char(char c) +{ + if (((c >= 'a') && (c <= 'z')) + || ((c >= 'A') && (c <= 'Z')) + || ((c >= '0') && (c <= '9')) + || (c == '-') + || (c == '_')) { + return 0; + } + + return ERROR_INVAL; +} + +static int +shell_cmd_check(const struct shell_cmd *cmd) +{ + unsigned long i; + int error; + + for (i = 0; cmd->name[i] != '\0'; i++) { + error = shell_cmd_check_char(cmd->name[i]); + + if (error) { + return error; + } + } + + if (i == 0) { + return ERROR_INVAL; + } + + return 0; +} + +/* + * The global lock must be acquired before calling this function. + */ +static void +shell_cmd_add_list(struct shell_cmd *cmd) +{ + struct shell_cmd *prev, *next; + + prev = shell_list; + + if ((prev == NULL) + || (strcmp(cmd->name, prev->name) < 0)) { + shell_list = cmd; + cmd->ls_next = prev; + return; + } + + for (;;) { + next = prev->ls_next; + + if ((next == NULL) + || (strcmp(cmd->name, next->name) < 0)) { + break; + } + + prev = next; + } + + prev->ls_next = cmd; + cmd->ls_next = next; +} + +/* + * The global lock must be acquired before calling this function. + */ +static int +shell_cmd_add(struct shell_cmd *cmd) +{ + struct shell_bucket *bucket; + struct shell_cmd *tmp; + + bucket = shell_bucket_get(cmd->name); + tmp = bucket->cmd; + + if (tmp == NULL) { + bucket->cmd = cmd; + goto out; + } + + for (;;) { + if (strcmp(cmd->name, tmp->name) == 0) { + printf("shell: error: %s: shell command name collision", cmd->name); + return ERROR_EXIST; + } + + if (tmp->ht_next == NULL) { + break; + } + + tmp = tmp->ht_next; + } + + tmp->ht_next = cmd; + +out: + shell_cmd_add_list(cmd); + return 0; +} + +int +shell_cmd_register(struct shell_cmd *cmd) +{ + int error; + + error = shell_cmd_check(cmd); + + if (error) { + return error; + } + + shell_cmd_acquire(); + error = shell_cmd_add(cmd); + shell_cmd_release(); + + return error; +} + +static inline const char * +shell_line_str(const struct shell_line *line) +{ + return line->str; +} + +static inline unsigned long +shell_line_size(const struct shell_line *line) +{ + return line->size; +} + +static inline void +shell_line_reset(struct shell_line *line) +{ + line->str[0] = '\0'; + line->size = 0; +} + +static inline void +shell_line_copy(struct shell_line *dest, const struct shell_line *src) +{ + strcpy(dest->str, src->str); + dest->size = src->size; +} + +static inline int +shell_line_cmp(const struct shell_line *a, const struct shell_line *b) +{ + return strcmp(a->str, b->str); +} + +static int +shell_line_insert(struct shell_line *line, unsigned long index, char c) +{ + unsigned long remaining_chars; + + if (index > line->size) { + return ERROR_INVAL; + } + + if ((line->size + 1) == sizeof(line->str)) { + return ERROR_NOMEM; + } + + remaining_chars = line->size - index; + + if (remaining_chars != 0) { + memmove(&line->str[index + 1], &line->str[index], remaining_chars); + } + + line->str[index] = c; + line->size++; + line->str[line->size] = '\0'; + return 0; +} + +static int +shell_line_erase(struct shell_line *line, unsigned long index) +{ + unsigned long remaining_chars; + + if (index >= line->size) { + return ERROR_INVAL; + } + + remaining_chars = line->size - index - 1; + + if (remaining_chars != 0) { + memmove(&line->str[index], &line->str[index + 1], remaining_chars); + } + + line->size--; + line->str[line->size] = '\0'; + return 0; +} + +static struct shell_line * +shell_history_get(unsigned long index) +{ + return &shell_history[index % ARRAY_SIZE(shell_history)]; +} + +static struct shell_line * +shell_history_get_newest(void) +{ + return shell_history_get(shell_history_newest); +} + +static struct shell_line * +shell_history_get_index(void) +{ + return shell_history_get(shell_history_index); +} + +static void +shell_history_reset_index(void) +{ + shell_history_index = shell_history_newest; +} + +static inline int +shell_history_same_newest(void) +{ + return (shell_history_newest != shell_history_oldest) + && shell_line_cmp(shell_history_get_newest(), + shell_history_get(shell_history_newest - 1)) == 0; +} + +static void +shell_history_push(void) +{ + if ((shell_line_size(shell_history_get_newest()) == 0) + || shell_history_same_newest()) { + shell_history_reset_index(); + return; + } + + shell_history_newest++; + shell_history_reset_index(); + + /* Mind integer overflows */ + if ((shell_history_newest - shell_history_oldest) + >= ARRAY_SIZE(shell_history)) { + shell_history_oldest = shell_history_newest + - ARRAY_SIZE(shell_history) + 1; + } +} + +static void +shell_history_back(void) +{ + if (shell_history_index == shell_history_oldest) { + return; + } + + shell_history_index--; + shell_line_copy(shell_history_get_newest(), shell_history_get_index()); +} + +static void +shell_history_forward(void) +{ + if (shell_history_index == shell_history_newest) { + return; + } + + shell_history_index++; + + if (shell_history_index == shell_history_newest) { + shell_line_reset(shell_history_get_newest()); + } else { + shell_line_copy(shell_history_get_newest(), shell_history_get_index()); + } +} + +static void +shell_cmd_help(int argc, char *argv[]) +{ + const struct shell_cmd *cmd; + + if (argc > 2) { + argc = 2; + argv[1] = "help"; + } + + if (argc == 2) { + cmd = shell_cmd_lookup(argv[1]); + + if (cmd == NULL) { + printf("shell: help: %s: command not found\n", argv[1]); + return; + } + + printf("usage: %s\n%s\n", cmd->usage, cmd->short_desc); + + if (cmd->long_desc != NULL) { + printf("\n%s\n", cmd->long_desc); + } + + return; + } + + shell_cmd_acquire(); + + for (cmd = shell_list; cmd != NULL; cmd = cmd->ls_next) { + printf("%13s %s\n", cmd->name, cmd->short_desc); + } + + shell_cmd_release(); +} + +static void +shell_cmd_history(int argc, char *argv[]) +{ + unsigned long i; + + (void)argc; + (void)argv; + + /* Mind integer overflows */ + for (i = shell_history_oldest; i != shell_history_newest; i++) { + printf("%6lu %s\n", i - shell_history_oldest, + shell_line_str(shell_history_get(i))); + } +} + +static struct shell_cmd shell_default_cmds[] = { + SHELL_CMD_INITIALIZER("help", shell_cmd_help, + "help [command]", + "obtain help about shell commands"), + SHELL_CMD_INITIALIZER("history", shell_cmd_history, + "history", + "display history list"), +}; + +static void +shell_prompt(void) +{ + printf("shell> "); +} + +static void +shell_reset(void) +{ + shell_line_reset(shell_history_get_newest()); + shell_cursor = 0; + shell_prompt(); +} + +static void +shell_erase(void) +{ + struct shell_line *current_line; + unsigned long remaining_chars; + + current_line = shell_history_get_newest(); + remaining_chars = shell_line_size(current_line); + + while (shell_cursor != remaining_chars) { + putchar(' '); + shell_cursor++; + } + + while (remaining_chars != 0) { + printf("\b \b"); + remaining_chars--; + } + + shell_cursor = 0; +} + +static void +shell_restore(void) +{ + struct shell_line *current_line; + + current_line = shell_history_get_newest(); + printf("%s", shell_line_str(current_line)); + shell_cursor = shell_line_size(current_line); +} + +static int +shell_is_ctrl_char(char c) +{ + return ((c < ' ') || (c >= 0x7f)); +} + +static void +shell_process_left(void) +{ + if (shell_cursor == 0) { + return; + } + + shell_cursor--; + printf("\e[1D"); +} + +static int +shell_process_right(void) +{ + if (shell_cursor >= shell_line_size(shell_history_get_newest())) { + return ERROR_AGAIN; + } + + shell_cursor++; + printf("\e[1C"); + return 0; +} + +static void +shell_process_up(void) +{ + shell_erase(); + shell_history_back(); + shell_restore(); +} + +static void +shell_process_down(void) +{ + shell_erase(); + shell_history_forward(); + shell_restore(); +} + +static void +shell_process_backspace(void) +{ + struct shell_line *current_line; + unsigned long remaining_chars; + int error; + + current_line = shell_history_get_newest(); + error = shell_line_erase(current_line, shell_cursor - 1); + + if (error) { + return; + } + + shell_cursor--; + printf("\b%s ", shell_line_str(current_line) + shell_cursor); + remaining_chars = shell_line_size(current_line) - shell_cursor + 1; + + while (remaining_chars != 0) { + putchar('\b'); + remaining_chars--; + } +} + +static int +shell_process_raw_char(char c) +{ + struct shell_line *current_line; + unsigned long remaining_chars; + int error; + + current_line = shell_history_get_newest(); + error = shell_line_insert(current_line, shell_cursor, c); + + if (error) { + printf("\nshell: line too long\n"); + return error; + } + + shell_cursor++; + + if (shell_cursor == shell_line_size(current_line)) { + putchar(c); + goto out; + } + + /* + * This assumes that the backspace character only moves the cursor + * without erasing characters. + */ + printf("%s", shell_line_str(current_line) + shell_cursor - 1); + remaining_chars = shell_line_size(current_line) - shell_cursor; + + while (remaining_chars != 0) { + putchar('\b'); + remaining_chars--; + } + +out: + return 0; +} + +static int +shell_process_tabulation(void) +{ + const struct shell_cmd *cmd = NULL; /* GCC */ + const char *name, *str, *word; + unsigned long i, size, cmd_cursor; + int error; + + shell_cmd_acquire(); + + str = shell_line_str(shell_history_get_newest()); + word = shell_find_word(str); + size = shell_cursor - (word - str); + cmd_cursor = shell_cursor - size; + + error = shell_cmd_complete(word, &size, &cmd); + + if (error && (error != ERROR_AGAIN)) { + error = 0; + goto out; + } + + if (error == ERROR_AGAIN) { + unsigned long cursor; + + cursor = shell_cursor; + shell_cmd_print_matches(cmd, size); + shell_prompt(); + shell_restore(); + + /* Keep existing arguments as they are */ + while (shell_cursor != cursor) { + shell_process_left(); + } + } + + name = shell_cmd_name(cmd); + + while (shell_cursor != cmd_cursor) { + shell_process_backspace(); + } + + for (i = 0; i < size; i++) { + error = shell_process_raw_char(name[i]); + + if (error) { + goto out; + } + } + + error = 0; + +out: + shell_cmd_release(); + return error; +} + +static void +shell_esc_seq_up(void) +{ + shell_process_up(); +} + +static void +shell_esc_seq_down(void) +{ + shell_process_down(); +} + +static void +shell_esc_seq_next(void) +{ + shell_process_right(); +} + +static void +shell_esc_seq_prev(void) +{ + shell_process_left(); +} + +static void +shell_esc_seq_home(void) +{ + while (shell_cursor != 0) { + shell_process_left(); + } +} + +static void +shell_esc_seq_del(void) +{ + int error; + + error = shell_process_right(); + + if (error) { + return; + } + + shell_process_backspace(); +} + +static void +shell_esc_seq_end(void) +{ + unsigned long size; + + size = shell_line_size(shell_history_get_newest()); + + while (shell_cursor < size) { + shell_process_right(); + } +} + +static const struct shell_esc_seq shell_esc_seqs[] = { + { "A", shell_esc_seq_up }, + { "B", shell_esc_seq_down }, + { "C", shell_esc_seq_next }, + { "D", shell_esc_seq_prev }, + { "H", shell_esc_seq_home }, + { "1~", shell_esc_seq_home }, + { "3~", shell_esc_seq_del }, + { "F", shell_esc_seq_end }, + { "4~", shell_esc_seq_end }, +}; + +static const struct shell_esc_seq * +shell_esc_seq_lookup(const char *str) +{ + unsigned long i; + + for (i = 0; i < ARRAY_SIZE(shell_esc_seqs); i++) { + if (strcmp(shell_esc_seqs[i].str, str) == 0) { + return &shell_esc_seqs[i]; + } + } + + return NULL; +} + +/* + * Process a single escape sequence character. + * + * Return the next escape state or 0 if the sequence is complete. + */ +static int +shell_process_esc_sequence(char c) +{ + static char str[SHELL_ESC_SEQ_MAX_SIZE], *ptr = str; + + const struct shell_esc_seq *seq; + uintptr_t index; + + index = ptr - str; + + if (index >= (ARRAY_SIZE(str) - 1)) { + printf("shell: escape sequence too long\n"); + goto reset; + } + + *ptr = c; + ptr++; + *ptr = '\0'; + + if ((c >= '@') && (c <= '~')) { + seq = shell_esc_seq_lookup(str); + + if (seq != NULL) { + seq->fn(); + } + + goto reset; + } + + return SHELL_ESC_STATE_CSI; + +reset: + ptr = str; + return 0; +} + +static int +shell_process_args(void) +{ + unsigned long i; + char c, prev; + int j; + + snprintf(shell_tmp_line, sizeof(shell_tmp_line), "%s", + shell_line_str(shell_history_get_newest())); + + for (i = 0, j = 0, prev = SHELL_SEPARATOR; + (c = shell_tmp_line[i]) != '\0'; + i++, prev = c) { + if (c == SHELL_SEPARATOR) { + if (prev != SHELL_SEPARATOR) { + shell_tmp_line[i] = '\0'; + } + } else { + if (prev == SHELL_SEPARATOR) { + shell_argv[j] = &shell_tmp_line[i]; + j++; + + if (j == ARRAY_SIZE(shell_argv)) { + printf("shell: too many arguments\n"); + return ERROR_INVAL; + } + + shell_argv[j] = NULL; + } + } + } + + shell_argc = j; + return 0; +} + +static void +shell_process_line(void) +{ + const struct shell_cmd *cmd; + int error; + + cmd = NULL; + error = shell_process_args(); + + if (error) { + goto out; + } + + if (shell_argc == 0) { + goto out; + } + + cmd = shell_cmd_lookup(shell_argv[0]); + + if (cmd == NULL) { + printf("shell: %s: command not found\n", shell_argv[0]); + goto out; + } + +out: + shell_history_push(); + + if (cmd != NULL) { + cmd->fn(shell_argc, shell_argv); + } +} + +/* + * Process a single control character. + * + * Return an error if the caller should reset the current line state. + */ +static int +shell_process_ctrl_char(char c) +{ + switch (c) { + case SHELL_ERASE_BS: + case SHELL_ERASE_DEL: + shell_process_backspace(); + break; + case '\t': + return shell_process_tabulation(); + case '\n': + case '\r': + putchar('\n'); + shell_process_line(); + return ERROR_AGAIN; + default: + return 0; + } + + return 0; +} + +static void +shell_run(void *arg) +{ + int c, error, escape; + + (void)arg; + + for (;;) { + shell_reset(); + escape = 0; + + for (;;) { + c = getchar(); + + if (escape) { + switch (escape) { + case SHELL_ESC_STATE_START: + /* XXX CSI and SS3 sequence processing is the same */ + if ((c == '[') || (c == 'O')) { + escape = SHELL_ESC_STATE_CSI; + } else { + escape = 0; + } + + break; + case SHELL_ESC_STATE_CSI: + escape = shell_process_esc_sequence(c); + break; + default: + escape = 0; + } + + error = 0; + } else if (shell_is_ctrl_char(c)) { + if (c == '\e') { + escape = SHELL_ESC_STATE_START; + error = 0; + } else { + error = shell_process_ctrl_char(c); + + if (error) { + break; + } + } + } else { + error = shell_process_raw_char(c); + } + + if (error) { + break; + } + } + } +} + +void +shell_setup(void) +{ + int error; + + mutex_init(&shell_lock); + SHELL_REGISTER_CMDS(shell_default_cmds); + + error = thread_create(NULL, shell_run, NULL, "shell", + SHELL_STACK_SIZE, THREAD_MIN_PRIORITY); + + if (error) { + panic("shell: unable to create shell thread"); + } +} diff --git a/lib/shell.h b/lib/shell.h new file mode 100644 index 0000000..f66fbf7 --- /dev/null +++ b/lib/shell.h @@ -0,0 +1,94 @@ +/* + * Copyright (c) 2015-2018 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * Upstream site with license notes : + * http://git.sceen.net/rbraun/librbraun.git/ + * + * + * Minimalist shell for embedded systems. + */ + +#ifndef _SHELL_H +#define _SHELL_H + +#include <stddef.h> + +#include <lib/macros.h> + +#include <src/error.h> + +#define SHELL_REGISTER_CMDS(cmds) \ +MACRO_BEGIN \ + size_t ___i; \ + int ___error; \ + \ + for (___i = 0; ___i < ARRAY_SIZE(cmds); ___i++) { \ + ___error = shell_cmd_register(&(cmds)[___i]); \ + error_check(___error, __func__); \ + } \ +MACRO_END + +typedef void (*shell_fn_t)(int argc, char *argv[]); + +struct shell_cmd { + struct shell_cmd *ht_next; + struct shell_cmd *ls_next; + const char *name; + shell_fn_t fn; + const char *usage; + const char *short_desc; + const char *long_desc; +}; + +/* + * Static shell command initializers. + */ +#define SHELL_CMD_INITIALIZER(name, fn, usage, short_desc) \ + { NULL, NULL, name, fn, usage, short_desc, NULL } +#define SHELL_CMD_INITIALIZER2(name, fn, usage, short_desc, long_desc) \ + { NULL, NULL, name, fn, usage, short_desc, long_desc } + +/* + * Initialize a shell command structure. + */ +void shell_cmd_init(struct shell_cmd *cmd, const char *name, + shell_fn_t fn, const char *usage, + const char *short_desc, const char *long_desc); + +/* + * Initialize the shell module. + * + * On return, shell commands can be registered. + */ +void shell_setup(void); + +/* + * Register a shell command. + * + * The command name must be unique. It must not include characters outside + * the [a-zA-Z0-9-_] class. + * + * The structure passed when calling this function is directly reused by + * the shell module and must persist in memory. + */ +int shell_cmd_register(struct shell_cmd *cmd); + +#endif /* _SHELL_H */ @@ -0,0 +1,19 @@ +#!/bin/sh + +# Start the QEMU emulator with options doing the following : +# - GDB remote access on the local TCP port 1234 +# - 64MB of physical memory (RAM) +# - No video device (automatically sets the first COM port as the console) +# - Boot from the generated cdrom image. +# +# In order to dump all exceptions and interrupts to a log file, you may add +# the following options : +# -d int \ +# -D int_debug.log \ +# +# Note that these debugging options do not work when KVM is enabled. +qemu-system-i386 \ + -gdb tcp::1234 \ + -m 64 \ + -nographic \ + -kernel x1 diff --git a/src/boot.c b/src/boot.c new file mode 100644 index 0000000..ac08818 --- /dev/null +++ b/src/boot.c @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2017 Richard Braun. + * Copyright (c) 2017 Jerko Lenstra. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <stdint.h> + +#include <lib/macros.h> + +#include "boot.h" + +/* + * This is the boot stack, used by the boot code to set the value of + * the ESP register very early once control is passed to the kernel. + * + * It is aligned to 4 bytes to comply with the System V Intel 386 ABI [1]. + * While not strictly required since x86 supports unaligned accesses, + * aligned accesses are faster, and the compiler generates instructions + * accessing the stack that assume it's aligned. + * + * See the assembly code at the boot_start label in boot_asm.S. + * + * [1] http://www.sco.com/developers/devspecs/abi386-4.pdf + */ +uint8_t boot_stack[BOOT_STACK_SIZE] __aligned(4); diff --git a/src/boot.h b/src/boot.h new file mode 100644 index 0000000..d813605 --- /dev/null +++ b/src/boot.h @@ -0,0 +1,34 @@ +/* + * Copyright (c) 2017 Richard Braun. + * Copyright (c) 2017 Jerko Lenstra. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#ifndef _BOOT_H +#define _BOOT_H + +/* + * The size of the boot stack. + * + * See the boot_stack variable in boot.c. + */ +#define BOOT_STACK_SIZE 4096 + +#endif /* _BOOT_H */ diff --git a/src/boot_asm.S b/src/boot_asm.S new file mode 100644 index 0000000..018f096 --- /dev/null +++ b/src/boot_asm.S @@ -0,0 +1,96 @@ +/* + * Copyright (c) 2017 Richard Braun. + * Copyright (c) 2017 Jerko Lenstra. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include "boot.h" + +/* + * These are values used in the OS image header, as defined by the multiboot + * specification. + * + * See https://www.gnu.org/software/grub/manual/multiboot/multiboot.html. + */ +#define BOOT_HDR_MAGIC 0x1BADB002 +#define BOOT_HDR_CHECK 0x2BADB002 +#define BOOT_HDR_FLAGS 0x0 + +/* + * The .section directive tells the assembler which section the following + * instructions should go into. + * + * The "a" flag makes the section allocatable, meaning memory will be + * allocated for that section at load time. + * + * See https://sourceware.org/binutils/docs-2.29/as/Section.html#Section. + */ +.section .hdr, "a" + +/* Generate code for i386 */ +.code32 + +/* + * The .int directive is used to emit verbatim machine words. Here, the + * third word is the checksum of the first two, defined as "a 32-bit + * unsigned value which, when added to the other magic fields (i.e. + * ‘magic’ and ‘flags’), must have a 32-bit unsigned sum of zero". + * Intuitively, adding the two first words and making the result negative + * gives a value that, when added to the other fields, gives 0, despite + * the word being unsigned. This trick works because values use two's + * complement representation. + * + * See https://en.wikipedia.org/wiki/Two%27s_complement. + */ +.int BOOT_HDR_MAGIC +.int BOOT_HDR_FLAGS +.int -(BOOT_HDR_FLAGS + BOOT_HDR_MAGIC) + +/* + * Put the following instructions into the .text section, which is + * allocatable and executable. + */ +.section .text, "ax" + +/* + * This symbol is the entry point, i.e. the first instruction that should + * be run when control is passed to the kernel. The address of this symbol + * is what the following command returns : + * readelf -aW x1 | grep "Entry point" + * + * The .global directive tells the assembler to make the symbol global, + * i.e. to make it visible to other compilation units. + * + * When this code is run, the machine state should comply with what the + * multiboot specification defines. + */ +.global boot_start +boot_start: + cmp $BOOT_HDR_CHECK, %eax /* Compare EAX against the expected value */ + jne . /* If not equal, jump to the current address. + This is an infinite loop. */ + mov $boot_stack, %esp /* Set up a stack */ + add $BOOT_STACK_SIZE, %esp /* On x86, stacks grow downwards, so start + at the top */ + jmp main /* Jump to the C main function */ + +loop: + hlt /* Never reached, for safety */ + jmp loop diff --git a/src/condvar.c b/src/condvar.c new file mode 100644 index 0000000..2424e7d --- /dev/null +++ b/src/condvar.c @@ -0,0 +1,180 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <stdbool.h> + +#include <lib/list.h> + +#include "condvar.h" +#include "mutex.h" +#include "thread.h" + +/* + * Structure used to bind a waiting thread and a condition variable. + * + * The purpose of this structure is to avoid adding the node to the thread + * structure. Instead, it's allocated from the stack and only exists while + * the thread is waiting for the condition variable to be signalled. + * + * When another thread signals the condition variable, it finds threads + * to wake up by accessing the condition variable list of waiters. + * + * The awaken member records whether the waiting thread has actually been + * awaken, to guard against spurious wake-ups. + * + * Preemption must be disabled when accessing a waiter. + */ +struct condvar_waiter { + struct list node; + struct thread *thread; + bool awaken; +}; + +static void +condvar_waiter_init(struct condvar_waiter *waiter, struct thread *thread) +{ + waiter->thread = thread; + waiter->awaken = false; +} + +static bool +condvar_waiter_awaken(const struct condvar_waiter *waiter) +{ + return waiter->awaken; +} + +static bool +condvar_waiter_wakeup(struct condvar_waiter *waiter) +{ + if (condvar_waiter_awaken(waiter)) { + return false; + } + + thread_wakeup(waiter->thread); + waiter->awaken = true; + return true; +} + +void +condvar_init(struct condvar *condvar) +{ + list_init(&condvar->waiters); +} + +void +condvar_signal(struct condvar *condvar) +{ + struct condvar_waiter *waiter; + bool awaken; + + thread_preempt_disable(); + + list_for_each_entry(&condvar->waiters, waiter, node) { + awaken = condvar_waiter_wakeup(waiter); + + if (awaken) { + break; + } + } + + thread_preempt_enable(); +} + +void +condvar_broadcast(struct condvar *condvar) +{ + struct condvar_waiter *waiter; + + /* + * Note that this broadcast implementation, a very simple and naive one, + * allows a situation known as the "thundering herd problem" [1]. + * + * Remember that a condition variable is always associated with a mutex + * when waiting on it. This means that, when broadcasting a condition + * variable on which many threads are waiting, they will all be awaken, + * but only one of them acquires the associated mutex. All the others + * will sleep, waiting for the mutex to be unlocked. This unnecessary + * round of wake-ups closely followed by sleeps may be very expensive + * compared to the cost of the critical sections around the wait, and + * that cost increases linearly with the number of waiting threads. + * + * Smarter but more complicated implementations can avoid this problem, + * e.g. by directly queuing the current waiters on the associated mutex. + * + * [1] https://en.wikipedia.org/wiki/Thundering_herd_problem + */ + + thread_preempt_disable(); + + list_for_each_entry(&condvar->waiters, waiter, node) { + condvar_waiter_wakeup(waiter); + } + + thread_preempt_enable(); +} + +void +condvar_wait(struct condvar *condvar, struct mutex *mutex) +{ + struct condvar_waiter waiter; + struct thread *thread; + + thread = thread_self(); + condvar_waiter_init(&waiter, thread); + + thread_preempt_disable(); + + /* + * Unlocking the mutex associated with the condition variable after + * acquiring the condition variable (done here by disabling preemption) + * is what makes waiting "atomic". Note that atomicity isn't absolute. + * Here, the wait is atomic with respect to concurrent signals. + * + * Signalling a condition variable is always safe in the sense that + * it is permitted and won't make the system crash, but signals may be + * "missed" if the associated mutex isn't locked when signalling. + */ + mutex_unlock(mutex); + + list_insert_tail(&condvar->waiters, &waiter.node); + + do { + thread_sleep(); + } while (!condvar_waiter_awaken(&waiter)); + + list_remove(&waiter.node); + + thread_preempt_enable(); + + /* + * Unlike releasing the mutex earlier, relocking the mutex may be + * done before or after releasing the condition variable. In this + * case, it may not be done before because acquiring the condition + * variable is achieved by disabling preemption, which forbids + * sleeping, and therefore locking a mutex, but another implementation + * may use a different synchronization mechanism. + * + * It's also slightly better to relock outside the previous critical + * section in order to make it shorter. + */ + mutex_lock(mutex); +} diff --git a/src/condvar.h b/src/condvar.h new file mode 100644 index 0000000..1448d69 --- /dev/null +++ b/src/condvar.h @@ -0,0 +1,149 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * Condition variable module. + * + * A condition variable is a thread synchronization tool used to wait until + * a predicate, in the form of data shared between multiple threads, becomes + * true. One or more thread may be waiting on a condition variable for the + * predicate to become true, and other threads may set the predicate and + * signal the condition variable, waking up one or all the waiters. + * + * This interface of condition variables closely matches the core + * requirements of the POSIX specification [1]. In particular, a condition + * variable must always be associated with a mutex, and waiting on a + * condition variable must always be done in a loop rechecking the + * predicate to guard against spurious wake-ups, which may occur for + * various reasons, ranging from implementation details to C/Unix signals, + * such as SIGINT, sent by a user (this kernel doesn't implement such + * signals, they're given as a real life example on modern systems). + * + * [1] http://pubs.opengroup.org/onlinepubs/9699919799/ + */ + +#ifndef _CONDVAR_H +#define _CONDVAR_H + +#include <lib/list.h> + +#include "mutex.h" + +/* + * Condition variable type. + * + * All members are private. + */ +struct condvar { + struct list waiters; +}; + +/* + * Initialize a condition variable. + */ +void condvar_init(struct condvar *condvar); + +/* + * Signal a condition variable. + * + * At least one thread is awaken if any threads are waiting on the + * condition variable. + * + * Signalling a condition variable is always safe in the sense that + * it is permitted and won't make the system crash, but signals may be + * "missed" if the mutex associated with the condition variable isn't + * locked when signalling. + */ +void condvar_signal(struct condvar *condvar); + +/* + * Broadcast a condition variable. + * + * Same as signalling except all threads waiting on the given condition + * variable are awaken. + */ +void condvar_broadcast(struct condvar *condvar); + +/* + * Wait on a condition variable. + * + * This function makes the calling thread sleep until the given + * condition variable is signalled. A condition variable is always + * associated with a mutex when waiting. That mutex is used to + * serialize access to the variables shared between the waiting + * thread, and the signalling thread, including the predicate the + * calling thread is waiting on. + * + * When calling this function, the mutex must be locked, so that + * checking the predicate and waiting on the condition variable is + * done atomically with respect to signalling. Obviously, while + * waiting, the mutex must be unlocked, to allow another thread to + * set the predicate and signal any waiting thread. As a result, + * this function unlocks the mutex before sleeping, and relocks + * it before returning. + * + * Note that this function may return for other reasons than the + * condition variable being signalled. These wake-ups are called + * spurious wake-ups and may be caused by implementation details + * as well as manually waking up threads (e.g. with C/Unix signals + * such as SIGINT). This is why waiting on a condition variable + * should always be enclosed in a loop, rechecking the predicate + * on each iteration. + * + * Here is an example of waiting and signalling : + * + * static bool predicate; + * static struct mutex m; + * static struct condvar cv; + * + * void + * init(void) + * { + * predicate = false; + * mutex_init(&m); + * condvar_init(&cv); + * } + * + * void + * wait(void) + * { + * mutex_lock(&m); + * + * while (!predicate) { Checking the predicate and waiting + * condvar_wait(&cv, &m); on the condition variable is atomic + * } with respect to setting the predicate + * and signalling. + * mutex_unlock(&m); + * } + * + * void + * signal(void) + * { + * mutex_lock(&m); Because the mutex is locked, setting + * predicate = true; the predicate and signalling is + * condvar_signal(&cv); atomic with respect to checking the + * mutex_unlock(&m); predicate and waiting on the condition + * variable. + * } + */ +void condvar_wait(struct condvar *condvar, struct mutex *mutex); + +#endif /* _CONDVAR_H */ diff --git a/src/cpu.c b/src/cpu.c new file mode 100644 index 0000000..c336c5e --- /dev/null +++ b/src/cpu.c @@ -0,0 +1,493 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * All references to the Intel 64 and IA-32 Architecture Software Developer's + * Manual are valid for order number: 325462-061US, December 2016. + */ + +#include <assert.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> + +#include <lib/macros.h> + +#include "cpu.h" +#include "error.h" +#include "i8259.h" +#include "thread.h" + +/* + * Segment flags. + * + * See Intel 64 and IA-32 Architecture Software Developer's Manual, Volume 3 + * System Programming Guide : + * - 3.4.5 Segment Descriptors + * - 3.5 System Descriptor Types + */ +#define CPU_SEG_DATA_RW 0x00000200 +#define CPU_SEG_CODE_RX 0x00000900 +#define CPU_SEG_S 0x00001000 +#define CPU_SEG_P 0x00008000 +#define CPU_SEG_DB 0x00400000 +#define CPU_SEG_G 0x00800000 + +#define CPU_IDT_SIZE (CPU_IDT_VECT_IRQ_BASE + I8259_NR_IRQ_VECTORS) + +/* + * Segment descriptor. + * + * These entries are found in the GDT and IDT tables (described below). + * When loading a segment register, the value of the register is a + * segment selector, which is an index (in bytes) along with flags. + * + * See Intel 64 and IA-32 Architecture Software Developer's Manual, + * Volume 3 System Programming Guide : + * - 3.4.2 Segment Selectors + * - 3.4.5 Segment Descriptors + */ +struct cpu_seg_desc { + uint32_t low; + uint32_t high; +}; + +/* + * A pseudo descriptor is an operand for the LGDT/LIDT instructions. + * + * See Intel 64 and IA-32 Architecture Software Developer's Manual, + * Volume 3 System Programming Guide, 3.5.1 Segment Descriptor Tables, + * Figure 3-11 Pseudo-Descriptor Formats. + * + * This structure is packed to prevent any holes between limit and base. + */ +struct cpu_pseudo_desc { + uint16_t limit; + uint32_t base; +} __packed; + +/* + * These segment descriptor tables are the Global Descriptor Table (GDT) + * and the Interrupt Descriptor Table (IDT) respectively. The GDT was + * historically used to create segments. Segmentation could be used to run + * multiple instances of the same program at different locations in memory, + * by changing the base address of segments. It could implement a simple + * form of memory protection by restricting the length of segments. With + * modern virtual memory based entirely on paging, segmentation has become + * obsolete, and all modern systems use a flat memory model, where all + * segments span the entire physical space. Segments may still be used to + * provide per-processor or per-thread variables (e.g. this is how TLS, + * thread-local storage, is implemented). + * + * The IDT is used for exception and interrupt handling, collectively known + * as interrupts. Here, "exception" refers to interrupts originating from + * the CPU such as a division by zero exception, whereas "IRQ" refers to + * interrupts raised by external devices. These terms are often used + * interchangeably. What's important to keep in mind is that interrupts + * divert the flow of execution of the processor. The IDT tells the processor + * where to branch when an interrupt occurs. + * + * The GDT and IDT should be 8-byte aligned for best performance. + * + * See Intel 64 and IA-32 Architecture Software Developer's Manual, Volume 3 + * System Programming Guide : + * - 3.5.1 Segment Descriptor Tables (GDT) + * - 6.10 Interrupt Descriptor Table (IDT) + */ +static struct cpu_seg_desc cpu_gdt[CPU_GDT_SIZE] __aligned(8); +static struct cpu_seg_desc cpu_idt[CPU_IDT_SIZE] __aligned(8); + +/* + * Handler for external interrupt requests. + */ +struct cpu_irq_handler { + cpu_irq_handler_fn_t fn; + void *arg; +}; + +/* + * Array where driver IRQ handlers are registered. + * + * Interrupts and preemption must be disabled when accessing the handlers. + */ +static struct cpu_irq_handler cpu_irq_handlers[I8259_NR_IRQ_VECTORS]; + +/* + * The interrupt frame is the stack content forged by interrupt handlers. + * They store the data needed to restore the processor to its state prior + * to the interrupt. + */ +struct cpu_intr_frame { + /* These members are pushed by the low level ISRs */ + uint32_t edi; + uint32_t esi; + uint32_t ebp; + uint32_t edx; + uint32_t ecx; + uint32_t ebx; + uint32_t eax; + uint32_t vector; + + /* + * This member may be pushed by either the CPU or the low level ISRs + * for exceptions/interrupts that don't emit such an error code. + */ + uint32_t error; + + /* These members are automatically pushed by the CPU */ + uint32_t eip; + uint32_t cs; + uint32_t eflags; +}; + +/* + * Declarations for C/assembly functions that are global so that they can + * be shared between cpu.c and cpu_asm.S, but are considered private to + * the cpu module. + */ +uint32_t cpu_get_eflags(void); +void cpu_set_eflags(uint32_t eflags); +void cpu_load_gdt(const struct cpu_pseudo_desc *desc); +void cpu_load_idt(const struct cpu_pseudo_desc *desc); +void cpu_intr_main(const struct cpu_intr_frame *frame); + +/* + * Low level interrupt service routines. + * + * These are the addresses where the CPU directly branches to when an + * interrupt is received. + */ +void cpu_isr_divide_error(void); +void cpu_isr_general_protection(void); +void cpu_isr_32(void); +void cpu_isr_33(void); +void cpu_isr_34(void); +void cpu_isr_35(void); +void cpu_isr_36(void); +void cpu_isr_37(void); +void cpu_isr_38(void); +void cpu_isr_39(void); +void cpu_isr_40(void); +void cpu_isr_41(void); +void cpu_isr_42(void); +void cpu_isr_43(void); +void cpu_isr_44(void); +void cpu_isr_45(void); +void cpu_isr_46(void); +void cpu_isr_47(void); + +uint32_t +cpu_intr_save(void) +{ + uint32_t eflags; + + eflags = cpu_get_eflags(); + cpu_intr_disable(); + return eflags; +} + +void +cpu_intr_restore(uint32_t eflags) +{ + cpu_set_eflags(eflags); +} + +bool +cpu_intr_enabled(void) +{ + uint32_t eflags; + + eflags = cpu_get_eflags(); + return eflags & CPU_EFL_IF; +} + +void +cpu_halt(void) +{ + cpu_intr_disable(); + + for (;;) { + cpu_idle(); + } +} + +static void +cpu_default_intr_handler(void) +{ + printf("cpu: error: unhandled interrupt\n"); + cpu_halt(); +} + +static void +cpu_seg_desc_init_null(struct cpu_seg_desc *desc) +{ + desc->low = 0; + desc->high = 0; +} + +static void +cpu_seg_desc_init_code(struct cpu_seg_desc *desc) +{ + /* + * Base: 0 + * Limit: 0xffffffff + * Privilege level: 0 (most privileged) + */ + desc->low = 0xffff; + desc->high = CPU_SEG_G + | CPU_SEG_DB + | (0xf << 16) + | CPU_SEG_P + | CPU_SEG_S + | CPU_SEG_CODE_RX; +} + +static void +cpu_seg_desc_init_data(struct cpu_seg_desc *desc) +{ + /* + * Base: 0 + * Limit: 0xffffffff + * Privilege level: 0 (most privileged) + */ + desc->low = 0xffff; + desc->high = CPU_SEG_G + | CPU_SEG_DB + | (0xf << 16) + | CPU_SEG_P + | CPU_SEG_S + | CPU_SEG_DATA_RW; +} + +static void +cpu_seg_desc_init_intr_gate(struct cpu_seg_desc *desc, + void (*handler)(void)) +{ + desc->low = (CPU_GDT_SEL_CODE << 16) + | (((uint32_t)handler) & 0xffff); + desc->high = (((uint32_t)handler) & 0xffff0000) + | CPU_SEG_P + | 0xe00; +} + +static void +cpu_pseudo_desc_init(struct cpu_pseudo_desc *desc, + const void *addr, size_t size) +{ + assert(size <= 0x10000); + desc->limit = size - 1; + desc->base = (uint32_t)addr; +} + +static struct cpu_seg_desc * +cpu_get_gdt_entry(size_t selector) +{ + size_t index; + + /* + * The first 3 bits are the TI and RPL bits + * + * See Intel 64 and IA-32 Architecture Software Developer's Manual, + * Volume 3 System Programming Guide, 3.4.2 Segment Selectors. + */ + index = selector >> 3; + assert(index < ARRAY_SIZE(cpu_gdt)); + return &cpu_gdt[index]; +} + +static void +cpu_irq_handler_init(struct cpu_irq_handler *handler) +{ + handler->fn = NULL; +} + +static struct cpu_irq_handler * +cpu_lookup_irq_handler(unsigned int irq) +{ + assert(irq < ARRAY_SIZE(cpu_irq_handlers)); + return &cpu_irq_handlers[irq]; +} + +static void +cpu_irq_handler_set_fn(struct cpu_irq_handler *handler, + cpu_irq_handler_fn_t fn, void *arg) +{ + assert(handler->fn == NULL); + handler->fn = fn; + handler->arg = arg; +} + +static void +cpu_setup_gdt(void) +{ + struct cpu_pseudo_desc pseudo_desc; + + cpu_seg_desc_init_null(cpu_get_gdt_entry(CPU_GDT_SEL_NULL)); + cpu_seg_desc_init_code(cpu_get_gdt_entry(CPU_GDT_SEL_CODE)); + cpu_seg_desc_init_data(cpu_get_gdt_entry(CPU_GDT_SEL_DATA)); + + cpu_pseudo_desc_init(&pseudo_desc, cpu_gdt, sizeof(cpu_gdt)); + cpu_load_gdt(&pseudo_desc); +} + +static void +cpu_setup_idt(void) +{ + struct cpu_pseudo_desc pseudo_desc; + + for (size_t i = 0; i < ARRAY_SIZE(cpu_irq_handlers); i++) { + cpu_irq_handler_init(cpu_lookup_irq_handler(i)); + } + + for (size_t i = 0; i < ARRAY_SIZE(cpu_idt); i++) { + cpu_seg_desc_init_intr_gate(&cpu_idt[i], cpu_default_intr_handler); + } + + cpu_seg_desc_init_intr_gate(&cpu_idt[CPU_IDT_VECT_DIV], + cpu_isr_divide_error); + cpu_seg_desc_init_intr_gate(&cpu_idt[CPU_IDT_VECT_GP], + cpu_isr_general_protection); + cpu_seg_desc_init_intr_gate(&cpu_idt[32], cpu_isr_32); + cpu_seg_desc_init_intr_gate(&cpu_idt[33], cpu_isr_33); + cpu_seg_desc_init_intr_gate(&cpu_idt[34], cpu_isr_34); + cpu_seg_desc_init_intr_gate(&cpu_idt[35], cpu_isr_35); + cpu_seg_desc_init_intr_gate(&cpu_idt[36], cpu_isr_36); + cpu_seg_desc_init_intr_gate(&cpu_idt[37], cpu_isr_37); + cpu_seg_desc_init_intr_gate(&cpu_idt[38], cpu_isr_38); + cpu_seg_desc_init_intr_gate(&cpu_idt[39], cpu_isr_39); + cpu_seg_desc_init_intr_gate(&cpu_idt[40], cpu_isr_40); + cpu_seg_desc_init_intr_gate(&cpu_idt[41], cpu_isr_41); + cpu_seg_desc_init_intr_gate(&cpu_idt[42], cpu_isr_42); + cpu_seg_desc_init_intr_gate(&cpu_idt[43], cpu_isr_43); + cpu_seg_desc_init_intr_gate(&cpu_idt[44], cpu_isr_44); + cpu_seg_desc_init_intr_gate(&cpu_idt[45], cpu_isr_45); + cpu_seg_desc_init_intr_gate(&cpu_idt[46], cpu_isr_46); + cpu_seg_desc_init_intr_gate(&cpu_idt[47], cpu_isr_47); + + cpu_pseudo_desc_init(&pseudo_desc, cpu_idt, sizeof(cpu_idt)); + cpu_load_idt(&pseudo_desc); +} + +static void +cpu_print_frame(const struct cpu_intr_frame *frame) +{ + printf("cpu: vector: %-8x eip: %08x eax: %08x ebx: %08x\n" + "cpu: error: %-8x esp: %08x ecx: %08x edx: %08x\n" + "cpu: eflags: %08x ebp: %08x esi: %08x edi: %08x\n", + (unsigned int)frame->vector, (unsigned int)frame->eip, + (unsigned int)frame->eax, (unsigned int)frame->ebx, + (unsigned int)frame->error, (unsigned int)(frame + 1), + (unsigned int)frame->ecx, (unsigned int)frame->edx, + (unsigned int)frame->eflags, (unsigned int)frame->ebp, + (unsigned int)frame->esi, (unsigned int)frame->edi); +} + +static void +cpu_exc_main(const struct cpu_intr_frame *frame) +{ + printf("cpu: exception:\n"); + cpu_print_frame(frame); + + switch (frame->vector) + { + case CPU_IDT_VECT_DIV: + panic("cpu: divide error"); + case CPU_IDT_VECT_GP: + panic("cpu: general protection fault"); + default: + cpu_default_intr_handler(); + } +} + +void +cpu_intr_main(const struct cpu_intr_frame *frame) +{ + struct cpu_irq_handler *handler; + unsigned int irq; + + assert(!cpu_intr_enabled()); + assert(frame->vector < ARRAY_SIZE(cpu_idt)); + + /* + * Interrupt handlers may call functions that may in turn yield the + * processor. When running in interrupt context, as opposed to thread + * context, there is no way to yield the processor, because the context + * isn't saved into a scheduled structure, which is what threads are + * for. As a result, disable preemption to prevent an invalid context + * switch. + */ + thread_preempt_disable(); + + if (frame->vector < CPU_IDT_VECT_IRQ_BASE) { + cpu_exc_main(frame); + } else { + irq = frame->vector - CPU_IDT_VECT_IRQ_BASE; + + /* + * Acknowledge the IRQ as early as possible to allow another one to + * be raised. + */ + i8259_irq_eoi(irq); + + handler = cpu_lookup_irq_handler(irq); + + if (!handler || !handler->fn) { + printf("cpu: error: invalid handler for irq %u\n", irq); + } else { + handler->fn(handler->arg); + } + } + + /* + * On entry, preemption could have been either enabled or disabled. + * If it was enabled, this call will reenable it. As a side effect, + * it will check if the current thread was marked for yielding, e.g. + * because the interrupt handler has awaken a higher priority thread, + * in which case a context switch is triggerred. Such context switches + * are called involuntary. + */ + thread_preempt_enable(); +} + +void +cpu_irq_register(unsigned int irq, cpu_irq_handler_fn_t fn, void *arg) +{ + struct cpu_irq_handler *handler; + uint32_t eflags; + + thread_preempt_disable(); + eflags = cpu_intr_save(); + + handler = cpu_lookup_irq_handler(irq); + cpu_irq_handler_set_fn(handler, fn, arg); + i8259_irq_enable(irq); + + thread_preempt_disable(); + cpu_intr_restore(eflags); +} + +void +cpu_setup(void) +{ + cpu_setup_gdt(); + cpu_setup_idt(); +} diff --git a/src/cpu.h b/src/cpu.h new file mode 100644 index 0000000..6326a58 --- /dev/null +++ b/src/cpu.h @@ -0,0 +1,131 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * CPU services. + * + * The main functionality of this module is to provide interrupt control, + * and registration of IRQ handlers. + * + * See the i8259 module. + */ + +#ifndef _CPU_H +#define _CPU_H + +/* + * EFLAGS register flags. + * + * See Intel 64 and IA-32 Architecture Software Developer's Manual, Volume 3 + * System Programming Guide, 2.3 System Flags and Fields in The EFLAGS Register. + */ +#define CPU_EFL_ONE 0x002 +#define CPU_EFL_IF 0x200 + +/* + * GDT segment descriptor indexes, in bytes. + * + * See Intel 64 and IA-32 Architecture Software Developer's Manual, Volume 3 + * System Programming Guide, 3.4.1 Segment Descriptor Tables. + */ +#define CPU_GDT_SEL_NULL 0x00 +#define CPU_GDT_SEL_CODE 0x08 +#define CPU_GDT_SEL_DATA 0x10 +#define CPU_GDT_SIZE 3 + +/* + * IDT segment descriptor indexes (exception and interrupt vectors). + * + * There are actually a lot more potential exceptions on x86. This list + * only includes vectors that are handled by the implementation. + * + * See Intel 64 and IA-32 Architecture Software Developer's Manual, Volume 3 + * System Programming Guide, 6.3 Sources of Interrupts. + */ +#define CPU_IDT_VECT_DIV 0 /* Divide error */ +#define CPU_IDT_VECT_GP 13 /* General protection fault */ +#define CPU_IDT_VECT_IRQ_BASE 32 /* Base vector for external IRQs */ + +/* + * Preprocessor declarations may be included by assembly source files, but + * C declarations may not. + */ +#ifndef __ASSEMBLER__ + +#include <stdbool.h> +#include <stdint.h> + +/* + * Type for IRQ handler functions. + * + * When called, interrupts and preemption are disabled. + */ +typedef void (*cpu_irq_handler_fn_t)(void *arg); + +/* + * Enable/disable interrupts. + */ +void cpu_intr_enable(void); +void cpu_intr_disable(void); + +/* + * Disable/restore interrupts. + * + * Calls to these functions can safely nest. + */ +uint32_t cpu_intr_save(void); +void cpu_intr_restore(uint32_t eflags); + +/* + * Return true if interrupts are enabled. + * + * Implies a compiler barrier. + */ +bool cpu_intr_enabled(void); + +/* + * Enter an idle state until the next interrupt. + */ +void cpu_idle(void); + +/* + * Completely halt execution on the processor. + * + * This function disables interrupts and enters an infinite idle loop. + */ +void cpu_halt(void) __attribute__((noreturn)); + +/* + * Register an IRQ handler. + * + * When the given IRQ is raised, the handler function is called with the + * given argument. + */ +void cpu_irq_register(unsigned int irq, cpu_irq_handler_fn_t fn, void *arg); + +/* + * Initialize the cpu module. + */ +void cpu_setup(void); + +#endif /* __ASSEMBLER__ */ + +#endif /* _CPU_H */ diff --git a/src/cpu_asm.S b/src/cpu_asm.S new file mode 100644 index 0000000..cdaf081 --- /dev/null +++ b/src/cpu_asm.S @@ -0,0 +1,163 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include "cpu.h" + +.section .text +.code32 + +.global cpu_get_eflags +cpu_get_eflags: + pushf + pop %eax + ret + +.global cpu_set_eflags +cpu_set_eflags: + mov 4(%esp), %eax + push %eax + popf + ret + +.global cpu_intr_enable +cpu_intr_enable: + sti + ret + +.global cpu_intr_disable +cpu_intr_disable: + cli + ret + +.global cpu_idle +cpu_idle: + hlt + ret + +.global cpu_load_gdt +cpu_load_gdt: + mov 4(%esp), %eax /* eax = &desc */ + lgdt (%eax) /* lgdt(*eax) */ + + mov $CPU_GDT_SEL_DATA, %eax + mov %eax, %ds + mov %eax, %es + mov %eax, %fs + mov %eax, %gs + mov %eax, %ss + + /* + * The code segment cannot directly be written to, and is instead + * modified by performing a long jump. + * + * See Intel 64 and IA-32 Architecture Software Developer's Manual : + * - Volume 2 Instruction Set Reference + * - 3.2 Instructions (A-L) + * - JMP + * - Far Jumps in Protected Mode + * - Volume 3 System Programming Guide: + * - 3.4.3 Segment Registers + */ + ljmp $CPU_GDT_SEL_CODE, $1f + +1: + ret + +.global cpu_load_idt +cpu_load_idt: + mov 4(%esp), %eax /* eax = &desc */ + lidt (%eax) /* lidt(*eax) */ + ret + +/* + * See struct cpu_intr_frame in cpu.c. + */ +.macro CPU_INTR_STORE_REGISTERS + push %edi + push %esi + push %ebp + push %edx + push %ecx + push %ebx + push %eax +.endm + +.macro CPU_INTR_LOAD_REGISTERS + pop %eax + pop %ebx + pop %ecx + pop %edx + pop %ebp + pop %esi + pop %edi +.endm + +/* + * Some interrupts push an error code, and some don't. + * Have a single interrupt frame layout by pushing a dummy error code. + */ +#define CPU_INTR(vector, name) \ +.global name; \ +name: \ + pushl $0; \ + pushl $(vector); \ + jmp cpu_intr_common + +#define CPU_INTR_ERROR(vector, name) \ +.global name; \ +name: \ + pushl $(vector); \ + jmp cpu_intr_common + +cpu_intr_common: + CPU_INTR_STORE_REGISTERS + push %esp /* push the address of the interrupt frame */ + call cpu_intr_main /* cpu_intr_main(frame) */ + add $4, %esp /* restore the stack pointer */ + CPU_INTR_LOAD_REGISTERS + add $8, %esp /* skip vector and error */ + iret /* return from interrupt */ + +CPU_INTR(CPU_IDT_VECT_DIV, cpu_isr_divide_error) +CPU_INTR_ERROR(CPU_IDT_VECT_GP, cpu_isr_general_protection) + +/* + * XXX There must be as many low level ISRs as there are possible IRQ vectors. + * + * See the i8259 module. + */ +CPU_INTR(32, cpu_isr_32) +CPU_INTR(33, cpu_isr_33) +CPU_INTR(34, cpu_isr_34) +CPU_INTR(35, cpu_isr_35) +CPU_INTR(36, cpu_isr_36) +CPU_INTR(37, cpu_isr_37) +CPU_INTR(38, cpu_isr_38) +CPU_INTR(39, cpu_isr_39) +CPU_INTR(40, cpu_isr_40) +CPU_INTR(41, cpu_isr_41) +CPU_INTR(42, cpu_isr_42) +CPU_INTR(43, cpu_isr_43) +CPU_INTR(44, cpu_isr_44) +CPU_INTR(45, cpu_isr_45) +CPU_INTR(46, cpu_isr_46) +CPU_INTR(47, cpu_isr_47) diff --git a/src/error.c b/src/error.c new file mode 100644 index 0000000..8bd7875 --- /dev/null +++ b/src/error.c @@ -0,0 +1,67 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <stdio.h> +#include <stdlib.h> + +#include <lib/macros.h> + +#include "error.h" +#include "panic.h" + +/* + * Error message table. + * + * This table must be consistent with the enum defined in error.h. + */ +static const char *error_msg_table[] = { + "success", + "invalid argument", + "resource temporarily unavailable", + "not enough space", + "input/output error", + "resource busy", + "entry exist", +}; + +const char * +error_str(unsigned int error) +{ + if (error >= ARRAY_SIZE(error_msg_table)) { + return "invalid error code"; + } + + return error_msg_table[error]; +} + +void +error_check(int error, const char *prefix) +{ + if (!error) { + return; + } + + panic("%s%s%s", + (prefix == NULL) ? "" : prefix, + (prefix == NULL) ? "" : ": ", + error_str(error)); +} diff --git a/src/error.h b/src/error.h new file mode 100644 index 0000000..fca3980 --- /dev/null +++ b/src/error.h @@ -0,0 +1,50 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#ifndef _ERROR_H +#define _ERROR_H + +enum { + ERROR_INVAL = 1, + ERROR_AGAIN, + ERROR_NOMEM, + ERROR_IO, + ERROR_BUSY, + ERROR_EXIST, +}; + +/* + * Return the message matching the given error. + * + * The returned address points to a statically allocated, read only, + * null-terminated string literal. The caller must not attempt to use it + * for anything else than error reporting. + */ +const char * error_str(unsigned int error); + +/* + * If error denotes an actual error (i.e. is not 0), panic, using the given + * string as a prefix for the error message. A NULL prefix is allowed. + */ +void error_check(int error, const char *prefix); + +#endif /* _ERROR_H */ diff --git a/src/i8254.c b/src/i8254.c new file mode 100644 index 0000000..fc4f48d --- /dev/null +++ b/src/i8254.c @@ -0,0 +1,72 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <lib/macros.h> + +#include "cpu.h" +#include "i8254.h" +#include "io.h" +#include "thread.h" + +#define I8254_FREQ 1193182 + +#define I8254_PORT_CHANNEL0 0x40 +#define I8254_PORT_MODE 0x43 + +#define I8254_CONTROL_BINARY 0x00 +#define I8254_CONTROL_RATE_GEN 0x04 +#define I8254_CONTROL_RW_LSB 0x10 +#define I8254_CONTROL_RW_MSB 0x20 +#define I8254_CONTROL_COUNTER0 0x00 + +#define I8254_INITIAL_COUNT DIV_CEIL(I8254_FREQ, THREAD_SCHED_FREQ) + +#define I8254_IRQ 0 + +static void +i8254_irq_handler(void *arg) +{ + (void)arg; + thread_report_tick(); +} + +void +i8254_setup(void) +{ + uint16_t value; + + /* + * Program the timer to raise an interrupt at the scheduling frequency. + */ + + io_write(I8254_PORT_MODE, I8254_CONTROL_COUNTER0 + | I8254_CONTROL_RW_MSB + | I8254_CONTROL_RW_LSB + | I8254_CONTROL_RATE_GEN + | I8254_CONTROL_BINARY); + + value = I8254_INITIAL_COUNT; + io_write(I8254_PORT_CHANNEL0, value & 0xff); + io_write(I8254_PORT_CHANNEL0, value >> 8); + + cpu_irq_register(I8254_IRQ, i8254_irq_handler, NULL); +} diff --git a/src/i8254.h b/src/i8254.h new file mode 100644 index 0000000..c70ded9 --- /dev/null +++ b/src/i8254.h @@ -0,0 +1,34 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * Intel 8254 programmable interval timer (PIT) driver. + */ + +#ifndef _I8254_H +#define _I8254_H + +/* + * Initialize the i8254 module. + */ +void i8254_setup(void); + +#endif /* _I8254_H */ diff --git a/src/i8259.c b/src/i8259.c new file mode 100644 index 0000000..589e13c --- /dev/null +++ b/src/i8259.c @@ -0,0 +1,257 @@ +/* + * Copyright (c) 2017 Richard Braun. + * Copyright (c) 2017 Jerko Lenstra. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * IRQ means Interrupt ReQuest. They're used by external hardware to signal + * the CPU, and in turn the OS, that an external event has happened and + * requires processing. The usual model is shown in the image at + * https://upload.wikimedia.org/wikipedia/commons/thumb/1/15/PIC_Hardware_interrupt_path.svg/300px-PIC_Hardware_interrupt_path.svg.png. + * + * This driver implements IRQ handling on the Intel 8259 PIC. The IBM PC/AT + * actually uses 2 of these PICs for external interrupt handling, as shown + * in https://masherz.files.wordpress.com/2010/08/217.jpg. The public + * interface completely hides this detail and considers all given IRQs + * as logical indexes, used to find the corresponding PIC (master or slave) + * and the local IRQ on that PIC. + * + * 8259 datasheet : + * https://pdos.csail.mit.edu/6.828/2010/readings/hardware/8259A.pdf + */ + +#include <assert.h> +#include <stddef.h> +#include <stdbool.h> +#include <stdint.h> + +#include <lib/macros.h> + +#include "cpu.h" +#include "error.h" +#include "i8259.h" +#include "io.h" + +#define I8259_IRQ_CASCADE 2 /* IRQ used for cascading on the master */ +#define I8259_NR_IRQS 8 + +/* + * Initialization Control Word 1 bits. + */ +#define I8259_ICW1_ICW4 0x01 /* State that a 4th ICW will be sent */ +#define I8259_ICW1_INIT 0x10 /* This bit must be set */ + +/* + * Initialization Control Word 4 bits. + */ +#define I8259_ICW4_8086 0x01 /* 8086 mode, as x86 is still compatible + with the old 8086 processor */ + +#define I8259_OCW2_EOI 0x20 /* End of interrupt control word */ + +enum { + I8259_PIC_ID_MASTER, + I8259_PIC_ID_SLAVE, + I8259_NR_PICS +}; + +/* + * Intel 8259 programmable interrupt controller. + */ +struct i8259_pic { + uint16_t cmd_port; /* Command I/O port of the PIC */ + uint16_t data_port; /* Data I/O port of the PIC */ + uint8_t imr; /* Cached value of the IMR register */ + bool master; /* True if this PIC is the master */ +}; + +/* + * Static instances of PIC objects. + */ +static struct i8259_pic i8259_pics[] = { + [I8259_PIC_ID_MASTER] = { + .cmd_port = 0x20, + .data_port = 0x21, + .imr = 0xff, + .master = true, + }, + [I8259_PIC_ID_SLAVE] = { + .cmd_port = 0xa0, + .data_port = 0xa1, + .imr = 0xff, + .master = false, + }, +}; + +static struct i8259_pic * +i8259_get_pic(unsigned int id) +{ + assert(id < ARRAY_SIZE(i8259_pics)); + return &i8259_pics[id]; +} + +static int +i8259_convert_global_irq(unsigned int irq, struct i8259_pic **pic, + unsigned int *local_irq) +{ + int error; + + if (irq < I8259_NR_IRQS) { + *pic = i8259_get_pic(I8259_PIC_ID_MASTER); + + if (local_irq) { + *local_irq = irq; + } + + error = 0; + } else if (irq < (I8259_NR_IRQS * I8259_NR_PICS)) { + *pic = i8259_get_pic(I8259_PIC_ID_SLAVE); + + if (local_irq) { + *local_irq = irq - I8259_NR_IRQS; + } + + error = 0; + } else { + *local_irq = 0; + error = ERROR_INVAL; + } + + return error; +} + +static void +i8259_pic_write_cmd(const struct i8259_pic *pic, uint8_t byte) +{ + io_write(pic->cmd_port, byte); +} + +static void +i8259_pic_write_data(const struct i8259_pic *pic, uint8_t byte) +{ + io_write(pic->data_port, byte); +} + +static void +i8259_pic_apply_imr(const struct i8259_pic *pic) +{ + io_write(pic->data_port, pic->imr); +} + +static void +i8259_pic_enable_irq(struct i8259_pic *pic, unsigned int irq) +{ + assert(irq < I8259_NR_IRQS); + + pic->imr &= ~(1 << irq); + i8259_pic_apply_imr(pic); +} + +static void +i8259_pic_disable_irq(struct i8259_pic *pic, unsigned int irq) +{ + assert(irq < I8259_NR_IRQS); + + pic->imr |= (1 << irq); + i8259_pic_apply_imr(pic); +} + +static void +i8259_pic_eoi(struct i8259_pic *pic) +{ + io_write(pic->cmd_port, I8259_OCW2_EOI); +} + +void +i8259_setup(void) +{ + struct i8259_pic *master, *slave; + + master = i8259_get_pic(I8259_PIC_ID_MASTER); + slave = i8259_get_pic(I8259_PIC_ID_SLAVE); + + i8259_pic_write_cmd(master, I8259_ICW1_INIT | I8259_ICW1_ICW4); + i8259_pic_write_cmd(slave, I8259_ICW1_INIT | I8259_ICW1_ICW4); + i8259_pic_write_data(master, CPU_IDT_VECT_IRQ_BASE); + i8259_pic_write_data(slave, CPU_IDT_VECT_IRQ_BASE + I8259_NR_IRQS); + i8259_pic_write_data(master, 1 << I8259_IRQ_CASCADE); + i8259_pic_write_data(slave, I8259_IRQ_CASCADE); + i8259_pic_write_data(master, I8259_ICW4_8086); + i8259_pic_write_data(slave, I8259_ICW4_8086); + + i8259_pic_enable_irq(master, I8259_IRQ_CASCADE); + i8259_pic_apply_imr(master); + i8259_pic_apply_imr(slave); +} + +void +i8259_irq_enable(unsigned int irq) +{ + struct i8259_pic *pic; + unsigned int local_irq; + int error; + + error = i8259_convert_global_irq(irq, &pic, &local_irq); + assert(!error); + i8259_pic_enable_irq(pic, local_irq); +} + +void +i8259_irq_disable(unsigned int irq) +{ + struct i8259_pic *pic; + unsigned int local_irq; + int error; + + error = i8259_convert_global_irq(irq, &pic, &local_irq); + assert(!error); + i8259_pic_disable_irq(pic, local_irq); +} + +void +i8259_irq_eoi(unsigned int irq) +{ + struct i8259_pic *pic; + int error; + + assert(!cpu_intr_enabled()); + + error = i8259_convert_global_irq(irq, &pic, NULL); + assert(!error); + + if (!pic->master) { + /* + * The order in which EOI messages are sent (master then slave or the + * reverse) is irrelevant : + * - If the slave is sent the EOI message first, it may raise another + * interrupt right away, in which case it will be pending at the + * master until the latter is sent the EOI message too. + * - If the master is sent the EOI message first, it may raise another + * interrupt right away, in which case it will be pending at the + * processor until interrupts are reenabled, assuming that this + * function is called with interrupts disabled, and that interrupts + * remain disabled until control is returned to the interrupted + * thread. + */ + i8259_pic_eoi(i8259_get_pic(I8259_PIC_ID_MASTER)); + } + + i8259_pic_eoi(pic); +} diff --git a/src/i8259.h b/src/i8259.h new file mode 100644 index 0000000..102d77b --- /dev/null +++ b/src/i8259.h @@ -0,0 +1,57 @@ +/* + * Copyright (c) 2017 Richard Braun. + * Copyright (c) 2017 Jerko Lenstra. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * Intel 8259 programmable interrupt controller (PIC) driver. + */ + +#ifndef _I8259_H +#define _I8259_H + +/* + * Range of vectors used for IRQ handling, 8 per PIC. + */ +#define I8259_NR_IRQ_VECTORS 16 + +/* + * Initialize the i8259 module. + */ +void i8259_setup(void); + +/* + * Enable an IRQ line on the PIC. + */ +void i8259_irq_enable(unsigned int irq); + +/* + * Disable an IRQ line on the PIC. + */ +void i8259_irq_disable(unsigned int irq); + +/* + * Report an end of interrupt. + * + * This function must be called with interrupts disabled. + */ +void i8259_irq_eoi(unsigned int irq); + +#endif /* _I8259_H */ diff --git a/src/io.h b/src/io.h new file mode 100644 index 0000000..19aa719 --- /dev/null +++ b/src/io.h @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * I/O ports access. + * + * The x86 architecture is special in that, in addition to the physical memory + * address space, it also has an I/O port space. Most modern processors use + * the physical memory address space to access memory-mapped device memory and + * registers, and that's also the case on x86, but the I/O port space is also + * used for this purpose, at least for some legacy devices. + */ + +#ifndef _IO_H +#define _IO_H + +#include <stdint.h> + +/* + * Read a byte from an I/O port. + */ +uint8_t io_read(uint16_t port); + +/* + * Write a byte to an I/O port. + */ +void io_write(uint16_t port, uint8_t byte); + +#endif /* _IO_H */ diff --git a/src/io_asm.S b/src/io_asm.S new file mode 100644 index 0000000..adf0c01 --- /dev/null +++ b/src/io_asm.S @@ -0,0 +1,37 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +.section .text +.code32 + +.global io_read +io_read: + mov 4(%esp), %edx /* edx = port */ + in %dx, %al /* al = in(dx) */ + ret + +.global io_write +io_write: + mov 8(%esp), %eax /* eax = byte */ + mov 4(%esp), %edx /* edx = port */ + out %al, %dx /* out(al, dx) */ + ret diff --git a/src/kernel.lds b/src/kernel.lds new file mode 100644 index 0000000..f4f209a --- /dev/null +++ b/src/kernel.lds @@ -0,0 +1,113 @@ +/* + * This linker script is used to drive the link step of the kernel, by e.g. + * forcing the linker to use specific addresses when allocating space for + * sections and symbols. + * + * It assumes flat physical memory (RAM) starting at 0, of size 64MB, + * of which only "upper memory", starting at 1MB, is used. + * + * On x86, the first 1MB of physical memory is where legacy BIOS mappings + * are mapped. Completely skip that region for convenience. + * + * For a map of lower memory, see http://wiki.osdev.org/Memory_Map_(x86). + */ + +/* + * Override the default entry point. This sets the address of the first + * instruction run when the boot loader passes control to the kernel. + */ +ENTRY(boot_start) + +/* + * The memory command is used to describe regions of memory. Here, a single + * region of RAM is defined. Adding another region, such as the video RAM + * at 0xa0000, would allow other commands in this script to allocate symbols + * out of that region. + * + * Describing memory regions is optional. It is best used when building for + * known devices with a specific memory layout. + */ +MEMORY +{ + RAM : ORIGIN = 1M, LENGTH = 63M +} + +/* + * The program headers define segments in the ELF image. they are used to + * fix properties on sections mapped to segments. Here, the PT_LOAD flag + * tells the boot loader that a segment must actually be loaded from the + * ELF image to memory. Some sections, such as most debugging sections, are + * normally not loaded to memory. FLAGS are used to set Unix-like + * permissions to a segment, so that a value of 4 means the segment may + * only contain read-only non-executable data, 5 (4 + 1) means read-only + * executable data (normally instructions), and 6 (4 + 2) means read-write + * non-executable data. + * + * The hdr segment is meant to contain the multiboot header. The name "text" + * is the historical name used to refer to instructions. + * + * See https://sourceware.org/binutils/docs-2.29/ld/index.html. + */ +PHDRS +{ + hdr PT_LOAD FLAGS(4); + text PT_LOAD FLAGS(5); + data PT_LOAD FLAGS(6); +} + +/* + * Sections define how the image data are partitioned. + * + * Common sections include : + * + * - .text + * The code section. + * - .data + * The section for initialized data (e.g. static int var = 123;). + * - .bss + * The section for uninitialized data (e.g. static int var;). Its name + * is historical and means "Block Started by Symbol". The .bss section + * is special in that it takes no space in the kernel image, because + * it's filled with bytes of value 0. Its size in memory is stored + * in the ELF file, and in this case, the boot loader initializes the + * memory for the .bss section. + * + * Here, an additional section is used to store the multiboot header, and + * any section for read-only data produced by the compiler is forced into + * the .data section. + * + * Sections are allocated out of the RAM memory region, and mapped to heir + * corresponding program headers segment. + * + * See https://sourceware.org/binutils/docs-2.29/ld/Input-Section-Basics.html#Input-Section-Basics + * for more information about the syntax used below. + */ +SECTIONS +{ + .hdr : { + *(.hdr) + } > RAM : hdr + + .text : { + *(.text*) + } > RAM : text + + .data : { + *(.rodata*) + *(.data*) + } > RAM : data + + .bss : { + *(.bss) + } > RAM : data + + /* + * The .eh_frame section is used by DWARF tools to unwind the stack, + * allowing software to dump stack traces. Although this section could + * safely be left in the kernel image, it may confuse people who + * disassemble it. + */ + /DISCARD/ : { + *(.eh_frame) + } +} diff --git a/src/main.c b/src/main.c new file mode 100644 index 0000000..839e273 --- /dev/null +++ b/src/main.c @@ -0,0 +1,69 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <stdbool.h> +#include <stdio.h> + +#include <lib/macros.h> +#include <lib/shell.h> + +#include "cpu.h" +#include "i8254.h" +#include "i8259.h" +#include "mem.h" +#include "panic.h" +#include "sw.h" +#include "thread.h" +#include "timer.h" +#include "uart.h" + +/* + * XXX The Clang compiler apparently doesn't like the lack of prototype for + * the main function in free standing mode. + */ +void main(void); + +/* + * This function is the main entry point for C code. It's called from + * assembly code in the boot module, very soon after control is passed + * to the kernel. + */ +void +main(void) +{ + thread_bootstrap(); + cpu_setup(); + i8259_setup(); + i8254_setup(); + uart_setup(); + mem_setup(); + thread_setup(); + timer_setup(); + shell_setup(); + sw_setup(); + + printf("X1 " QUOTE(VERSION) "\n\n"); + + thread_enable_scheduler(); + + /* Never reached */ +} diff --git a/src/mem.c b/src/mem.c new file mode 100644 index 0000000..572f2be --- /dev/null +++ b/src/mem.c @@ -0,0 +1,692 @@ +/* + * Copyright (c) 2017 Richard Braun. + * Copyright (c) 2017 Jerko Lenstra. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * Algorithm + * --------- + * This allocator is based on "The Art of Computer Programming" by Donald Knuth. + * The algorithm itself is described in : + * - Volume 1 - Fundamental Algorithms + * - Chapter 2 – Information Structures + * - 2.5 Dynamic Storage + * - Algorithm A (First-fit method) + * - Algorithm C (Liberation with boundary tags) + * + * The point of a memory allocator is to manage memory in terms of allocation + * and liberation requests. Allocation finds and reserves memory for a user, + * whereas liberation makes that memory available again for future allocations. + * Memory is not created, it must be available from the start, and the allocator + * simply tracks its usage with metadata, allocated from memory itself. + * + * Data structures + * --------------- + * Here is a somewhat graphical representation of how memory is organized in + * this implementation : + * + * allocated block free block + * +------+-----------------+ +------+-----------------+ + * | size | allocation flag | | size | allocation flag | <- header boundary + * +------+-----------------+ +------+-----------------+ tag + * | | | free list node (prev | <- payload or + * . payload . | and next pointers) | free list node + * . . +------------------------+ + * . . . . + * . . . . + * . . . . + * +------+-----------------+ +------+-----------------+ + * | size | allocation flag | | size | allocation flag | <- footer boundary + * +------+-----------------+ +------+-----------------+ tag + * + * Here is a view of multiple contiguous blocks : + * + * +------+-----------------+ <--+ + * | size | allocation flag | | + * +------+-----------------+ +- single block + * | | | + * . payload . | + * . . | + * . . | + * +------+-----------------+ | + * | size | allocation flag | | + * +------+-----------------+ <--+ + * +------+-----------------+ + * | size | allocation flag | + * +------+-----------------+ + * | | + * . payload . + * . . + * . . + * +------+-----------------+ + * | size | allocation flag | + * +------+-----------------+ + * +------+-----------------+ + * | size | allocation flag | + * +------+-----------------+ + * | | + * . payload . + * . . + * . . + * +------+-----------------+ + * | size | allocation flag | + * +------+-----------------+ + * + * The reason for the footer boundary tag is merging on liberation. When + * called, the mem_free() function is given a pointer to a payload. Since + * the size of a boundary tag is fixed, the address of the whole block + * can easily be computed. In order to reduce fragmentation, i.e. a state + * where all free blocks are small and prevent allocating bigger blocks, + * the allocator attempts to merge neighbor free blocks. Obtaining the + * address of the next block is easily achieved by simply adding the size + * of the current block, stored in the boundary tag, to the address of + * the block. But without a footer boundary tag, finding the address of + * the previous block is computationally expensive. + * + * Alignment + * --------- + * The word "aligned" and references to "alignment" in general can be + * found throughout the documentation of this module. Alignment is a + * property of a value, usually an address, to be a multiple of a size. + * This value is said to be "size-byte aligned", or "aligned on a size + * byte boundary". Common sizes include the processor word or cache line + * sizes. For example, the x86 architecture is 32-bits, making the word + * size 4 bytes. Addresses such as 0, 4, 8, 12, 512 and 516 are 4-byte + * aligned, whereas 1, 2, 3, 511, 513, 514 and 515 aren't. + * + * + * Pointers + * -------- + * The code in this module makes extensive use of pointer arithmetic and + * conversion between pointer types. It's important to keep in mind that, + * in C, the void pointer is meant as a generic reference to objects of + * any type. As a result, any pointer can be assigned to a void pointer + * without explicit casting, and a void pointer may be assigned to any + * pointer as well. + */ + +#include <assert.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> + +#include <lib/list.h> +#include <lib/macros.h> + +#include "mem.h" +#include "mutex.h" + +/* + * Total size of the backing storage heap. + * + * Note that the resulting kernel image file remains much smaller than this. + * The reason is because the heap is defined as uninitialized data, which are + * allocated out of the bss section by default. The bss section is filled + * with zeroes when the kernel image is loaded by the boot loader, as + * mandated by the ELF specification, which means there is no need to store + * the heap data, or any other statically allocated uninitialized data, in + * the kernel image file. + */ +#define MEM_HEAP_SIZE (32 * 1024 * 1024) + +/* + * Alignment required on addresses returned by mem_alloc(). + * + * See the description of mem_alloc() in the public header. + */ +#define MEM_ALIGN 4 + +/* + * Minimum size of a block. + * + * When free, the payload of a block is used as storage for the free list node. + */ +#define MEM_BLOCK_MIN_SIZE P2ROUND(((sizeof(struct mem_btag) * 2) \ + + sizeof(struct mem_free_node)), MEM_ALIGN) + +/* + * The heap itself must be aligned, so that the first block is also aligned. + * Assuming all blocks have an aligned size, the last block must also end on + * an aligned address. + * + * This kind of check increases safety and robustness when changing + * compile-time parameters such as the heap size declared above. + * + * Another relevant check would be to make sure the heap is large enough + * to contain at least one block, but since the minimum block size is + * defined using the C sizeof operator, unknown to the C preprocessor, + * this check requires C11 static assertions. + */ +#if !P2ALIGNED(MEM_HEAP_SIZE, MEM_ALIGN) +#error "invalid heap size" +#endif + +/* + * Masks applied on boundary tags to extract the size and the allocation flag. + */ +#define MEM_BTAG_ALLOCATED_MASK ((size_t)0x1) +#define MEM_BTAG_SIZE_MASK (~MEM_BTAG_ALLOCATED_MASK) + +/* + * Boundary tag. + * + * Since the alignment constraint specified for mem_alloc() applies to + * payloads, not blocks, it's important that boundary tags also be aligned. + * This is a check that would best be performed with C11 static assertions. + * + * In addition, the alignment constraint implies that the least significant + * bit is always 0. Therefore, this bit is used to store the allocation flag. + */ +struct mem_btag { + size_t value; +}; + +/* + * Memory block. + * + * Note the use of a C99 flexible array member. This construction enables + * the implementation to directly access the payload without pointer + * arithmetic or casting, and is one of the preferred ways to deal with + * headers. + */ +struct mem_block { + struct mem_btag btag; + char payload[]; +}; + +/* + * Free list node. + * + * This structure is used as the payload of free blocks. + */ +struct mem_free_node { + struct list node; +}; + +/* + * List of free nodes. + * + * Here is an example of a TODO entry, a method used to store and retrieve + * pending tasks using source code only : + * + * TODO Statistics counters. + */ +struct mem_free_list { + struct list free_nodes; +}; + +/* + * Memory heap. + * + * This allocator uses a single heap initialized with a single large free + * block. The allocator could be extended to support multiple heaps, each + * initialized with a single free block, forming an initial free list of + * more than one block. + * + * The heap must be correctly aligned, so that the first block is + * correctly aligned. + */ +static char mem_heap[MEM_HEAP_SIZE] __aligned(MEM_ALIGN); + +/* + * The unique free list. + * + * In order to improve allocation speed, multiple lists may be used, each + * for a specific size range. Such lists are called segregated free lists + * and enable more allocation policies, such as instant-fit. + */ +static struct mem_free_list mem_free_list; + +/* + * Global mutex used to serialize access to allocation data. + */ +static struct mutex mem_mutex; + +static bool +mem_aligned(size_t value) +{ + return P2ALIGNED(value, MEM_ALIGN); +} + +static void * +mem_heap_end(void) +{ + return &mem_heap[sizeof(mem_heap)]; +} + +static bool +mem_btag_allocated(const struct mem_btag *btag) +{ + return btag->value & MEM_BTAG_ALLOCATED_MASK; +} + +static void +mem_btag_set_allocated(struct mem_btag *btag) +{ + btag->value |= MEM_BTAG_ALLOCATED_MASK; +} + +static void +mem_btag_clear_allocated(struct mem_btag *btag) +{ + btag->value &= ~MEM_BTAG_ALLOCATED_MASK; +} + +static size_t +mem_btag_size(const struct mem_btag *btag) +{ + return btag->value & MEM_BTAG_SIZE_MASK; +} + +static void +mem_btag_init(struct mem_btag *btag, size_t size) +{ + btag->value = size; + mem_btag_set_allocated(btag); +} + +static size_t +mem_block_size(const struct mem_block *block) +{ + return mem_btag_size(&block->btag); +} + +static struct mem_block * +mem_block_from_payload(void *payload) +{ + size_t offset; + + /* + * Here, payload refers to the payload member in struct mem_block, not + * the local variable. + */ + offset = offsetof(struct mem_block, payload); + + /* + * Always keep pointer arithmetic in mind ! + * + * The rule is fairly simple : whenever arithmetic operators are used + * on pointers, the operation is scaled on the type size, so that e.g. + * adding 1 means pointing to the next element. A good way to remember + * this is to remember that pointers can be used as arrays, so that + * both these expressions are equivalent : + * - &ptr[1] + * - ptr + 1 + * + * As a result, when counting in bytes and not in objects, it is + * necessary to cast into a suitable pointer type. The char * type + * is specifically meant for this as C99 mandates that sizeof(char) be 1 + * (6.5.3.4 The sizeof operator). + * + * As a side note, a GNU extension allows using pointer arithmetic on + * void pointers, where the "size of void" is 1, turning pointer + * arithmetic on void pointers into byte arithmetic, allowing this + * expression to be written as : + * + * return payload - offset; + * + * See https://gcc.gnu.org/onlinedocs/gcc-6.4.0/gcc/Pointer-Arith.html + */ + return (struct mem_block *)((char *)payload - offset); +} + +static void * +mem_block_end(const struct mem_block *block) +{ + /* See mem_block_from_payload() */ + return (struct mem_block *)((char *)block + mem_block_size(block)); +} + +static struct mem_btag * +mem_block_header_btag(struct mem_block *block) +{ + return &block->btag; +} + +static struct mem_btag * +mem_block_footer_btag(struct mem_block *block) +{ + struct mem_btag *btag; + + btag = mem_block_end(block); + + /* + * See ISO/IEC 9899:1999, 6.5.2.1 "Array subscripting" : + * "A postfix expression followed by an expression in square brackets [] + * is a subscripted designation of an element of an array object. The + * definition of the subscript operator [] is that E1[E2] is identical to + * (*((E1)+(E2)))". + * + * This, by the way, implies the following equivalent expressions : + * - &btag[-1] + * - &(-1)[btag] + * - &*(btag - 1) + * - btag - 1 + */ + return &btag[-1]; +} + +static struct mem_block * +mem_block_prev(struct mem_block *block) +{ + struct mem_btag *btag; + + if ((char *)block == mem_heap) { + return NULL; + } + + btag = mem_block_header_btag(block); + return (struct mem_block *)((char *)block - mem_btag_size(&btag[-1])); +} + +static struct mem_block * +mem_block_next(struct mem_block *block) +{ + block = mem_block_end(block); + + if ((void *)block == mem_heap_end()) { + return NULL; + } + + return block; +} + +static bool +mem_block_allocated(struct mem_block *block) +{ + return mem_btag_allocated(mem_block_header_btag(block)); +} + +static void +mem_block_set_allocated(struct mem_block *block) +{ + mem_btag_set_allocated(mem_block_header_btag(block)); + mem_btag_set_allocated(mem_block_footer_btag(block)); +} + +static void +mem_block_clear_allocated(struct mem_block *block) +{ + mem_btag_clear_allocated(mem_block_header_btag(block)); + mem_btag_clear_allocated(mem_block_footer_btag(block)); +} + +static void +mem_block_init(struct mem_block *block, size_t size) +{ + mem_btag_init(mem_block_header_btag(block), size); + mem_btag_init(mem_block_footer_btag(block), size); +} + +static void * +mem_block_payload(struct mem_block *block) +{ + return block->payload; +} + +static struct mem_free_node * +mem_block_get_free_node(struct mem_block *block) +{ + assert(!mem_block_allocated(block)); + return mem_block_payload(block); +} + +static bool +mem_block_inside_heap(const struct mem_block *block) +{ + void *heap_end; + + heap_end = mem_heap_end(); + return (((char *)block >= mem_heap) + && ((void *)block->payload < heap_end) + && ((void *)mem_block_end(block) <= heap_end)); +} + +static void +mem_free_list_add(struct mem_free_list *list, struct mem_block *block) +{ + struct mem_free_node *free_node; + + assert(mem_block_allocated(block)); + + mem_block_clear_allocated(block); + free_node = mem_block_get_free_node(block); + + /* + * Free blocks may be added at either the head or the tail of a list. + * In this case, it's normally better to add at the head, because the + * first-fit algorithm implementation starts from the beginning. This + * means there is a good chance that a block recently freed may "soon" + * be allocated again. Since it's likely that this block was accessed + * before it was freed, there is a good chance that (part of) its memory + * is still in the processor cache, potentially increasing the chances + * of cache hits and saving a few expensive accesses from the processor + * to memory. This is an example of inexpensive micro-optimization. + */ + list_insert_head(&list->free_nodes, &free_node->node); +} + +static void +mem_free_list_remove(struct mem_free_list *list, struct mem_block *block) +{ + struct mem_free_node *free_node; + + (void)list; + + assert(!mem_block_allocated(block)); + + free_node = mem_block_get_free_node(block); + list_remove(&free_node->node); + mem_block_set_allocated(block); +} + +static struct mem_block * +mem_free_list_find(struct mem_free_list *list, size_t size) +{ + struct mem_free_node *free_node; + struct mem_block *block; + + /* + * The algorithmic complexity of this operation is O(n) [1] which + * basically means the maximum number of steps, and time, for the + * operation to complete depend on the number of elements in the list. + * This is one of the main reasons why memory allocation is generally + * avoided in interrupt handlers and real-time applications. Special + * allocators with guaranteed constant time or a fixed and known worst + * case time, may be used in these cases. + * + * [1] https://en.wikipedia.org/wiki/Big_O_notation + */ + list_for_each_entry(&list->free_nodes, free_node, node) { + block = mem_block_from_payload(free_node); + + if (mem_block_size(block) >= size) { + return block; + } + } + + return NULL; +} + +static void +mem_free_list_init(struct mem_free_list *list) +{ + list_init(&list->free_nodes); +} + +static bool +mem_block_inside(struct mem_block *block, void *addr) +{ + return (addr >= (void *)block) && (addr < mem_block_end(block)); +} + +static bool +mem_block_overlap(struct mem_block *block1, struct mem_block *block2) +{ + return mem_block_inside(block1, block2) + || mem_block_inside(block2, block1); +} + +static struct mem_block * +mem_block_split(struct mem_block *block, size_t size) +{ + struct mem_block *block2; + size_t total_size; + + assert(mem_block_allocated(block)); + assert(mem_aligned(size)); + + if (mem_block_size(block) < (size + MEM_BLOCK_MIN_SIZE)) { + return NULL; + } + + total_size = mem_block_size(block); + mem_block_init(block, size); + block2 = mem_block_end(block); + mem_block_init(block2, total_size - size); + + return block2; +} + +static struct mem_block * +mem_block_merge(struct mem_block *block1, struct mem_block *block2) +{ + size_t size; + + assert(!mem_block_overlap(block1, block2)); + + if (mem_block_allocated(block1) || mem_block_allocated(block2)) { + return NULL; + } + + mem_free_list_remove(&mem_free_list, block1); + mem_free_list_remove(&mem_free_list, block2); + size = mem_block_size(block1) + mem_block_size(block2); + + if (block1 > block2) { + block1 = block2; + } + + mem_block_init(block1, size); + mem_free_list_add(&mem_free_list, block1); + return block1; +} + +void +mem_setup(void) +{ + struct mem_block *block; + + block = (struct mem_block *)mem_heap; + mem_block_init(block, sizeof(mem_heap)); + mem_free_list_init(&mem_free_list); + mem_free_list_add(&mem_free_list, block); + mutex_init(&mem_mutex); +} + +static size_t +mem_convert_to_block_size(size_t size) +{ + /* + * Make sure all blocks have a correctly aligned size. That, and the fact + * that the heap address is also aligned, means all block addresses are + * aligned. + */ + size = P2ROUND(size, MEM_ALIGN); + size += sizeof(struct mem_btag) * 2; + + if (size < MEM_BLOCK_MIN_SIZE) { + size = MEM_BLOCK_MIN_SIZE; + } + + return size; +} + +void * +mem_alloc(size_t size) +{ + struct mem_block *block, *block2; + void *ptr; + + if (size == 0) { + return NULL; + } + + size = mem_convert_to_block_size(size); + + mutex_lock(&mem_mutex); + + block = mem_free_list_find(&mem_free_list, size); + + if (block == NULL) { + mutex_unlock(&mem_mutex); + return NULL; + } + + mem_free_list_remove(&mem_free_list, block); + block2 = mem_block_split(block, size); + + if (block2 != NULL) { + mem_free_list_add(&mem_free_list, block2); + } + + mutex_unlock(&mem_mutex); + + ptr = mem_block_payload(block); + assert(mem_aligned((uintptr_t)ptr)); + return ptr; +} + +void +mem_free(void *ptr) +{ + struct mem_block *block, *tmp; + + if (!ptr) { + return; + } + + assert(mem_aligned((uintptr_t)ptr)); + + block = mem_block_from_payload(ptr); + assert(mem_block_inside_heap(block)); + + mutex_lock(&mem_mutex); + + mem_free_list_add(&mem_free_list, block); + + tmp = mem_block_prev(block); + + if (tmp) { + tmp = mem_block_merge(block, tmp); + + if (tmp) { + block = tmp; + } + } + + tmp = mem_block_next(block); + + if (tmp) { + mem_block_merge(block, tmp); + } + + mutex_unlock(&mem_mutex); +} diff --git a/src/mem.h b/src/mem.h new file mode 100644 index 0000000..b04837a --- /dev/null +++ b/src/mem.h @@ -0,0 +1,92 @@ +/* + * Copyright (c) 2017 Richard Braun. + * Copyright (c) 2017 Jerko Lenstra. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * Kernel dynamic memory allocator. + * + * Here, the word "dynamic" is used in opposition to "static", which denotes + * memory allocated at compile time by the linker. + */ + +#ifndef _MEM_H +#define _MEM_H + +#include <stddef.h> + +/* + * Initialize the mem module. + */ +void mem_setup(void); + +/* + * Allocate memory. + * + * This function conforms to the specification of the standard malloc() + * function, i.e. : + * - The size argument is the allocation request size, in bytes. + * - An allocation size of 0 is permitted. + * - The content of the allocated block is uninitialized. + * - The returned value is the address of the allocated block of memory. + * - The address of the allocated block is aligned to the maximum built-in + * type size. Since this code targets the 32-bits i386 architecture, the + * largest built-in type is unsigned int, resulting in addresses aligned + * to 4 bytes boundaries. Here, "built-in" means natively supported by + * the processor. The document that defines the size of built-in types + * is the ABI (Application Binary Interface) specification, in this case + * System V Intel386 ABI [1] (see the GCC -mabi option for x86). The ABI + * normally uses one of the most common data models [2] for C types, in + * this case ILP32 (for int/long/pointers 32-bits). + * + * This last detail is important because C specifies the alignment of both + * built-in and aggregate types. In particular, the alignment of structure + * members must match the alignment of their respective types + * (ISO/IEC 9899:1999, 6.7.2.1 "Structure and union specifiers", 12 "Each + * non-bit-field member of a structure or union object is aligned in an + * implementation-defined manner appropriate to its type". A compiler may + * safely assume that structure member accesses are correctly aligned and + * generate instructions assuming this alignment. + * + * On x86, this doesn't matter too much, because unaligned accesses have + * always been supported, although they are less performant, since the + * processor potentially has more work to do. For example, if an unaligned + * variable crosses a cache line boundary, the processor may have to load + * two cache lines instead of one. + * + * On other architectures, unaligned accesses may simply not be supported, + * and generate exceptions. + * + * [1] http://www.sco.com/developers/devspecs/abi386-4.pdf + * [2] http://www.unix.org/version2/whatsnew/lp64_wp.html + */ +void * mem_alloc(size_t size); + +/* + * Free memory. + * + * This function conforms to the specification of the standard free() + * function, i.e. : + * - It may safely be called with a NULL argument. + * - Otherwise, it may only be passed memory addresses returned by mem_alloc(). + */ +void mem_free(void *ptr); + +#endif /* _MEM_H */ diff --git a/src/mutex.c b/src/mutex.c new file mode 100644 index 0000000..d70bd82 --- /dev/null +++ b/src/mutex.c @@ -0,0 +1,151 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <assert.h> +#include <stdbool.h> +#include <stddef.h> + +#include <lib/list.h> +#include <lib/macros.h> + +#include "error.h" +#include "mutex.h" +#include "thread.h" + +/* + * Structure used to bind a waiting thread and a mutex. + * + * The purpose of this structure is to avoid adding the node to the thread + * structure. Instead, it's allocated from the stack and only exists while + * the thread is waiting for the mutex to be unlocked. + * + * When the owner unlocks the mutex, it finds threads to wake up by + * accessing the mutex list of waiters. + * + * Preemption must be disabled when accessing a waiter. + */ +struct mutex_waiter { + struct list node; + struct thread *thread; +}; + +static void +mutex_waiter_init(struct mutex_waiter *waiter, struct thread *thread) +{ + waiter->thread = thread; +} + +static void +mutex_waiter_wakeup(struct mutex_waiter *waiter) +{ + thread_wakeup(waiter->thread); +} + +void +mutex_init(struct mutex *mutex) +{ + list_init(&mutex->waiters); + mutex->locked = false; +} + +static void +mutex_set_owner(struct mutex *mutex, struct thread *thread) +{ + assert(!mutex->owner); + assert(!mutex->locked); + + mutex->owner = thread; + mutex->locked = true; +} + +static void +mutex_clear_owner(struct mutex *mutex) +{ + assert(mutex->owner == thread_self()); + assert(mutex->locked); + + mutex->owner = NULL; + mutex->locked = false; +} + +void +mutex_lock(struct mutex *mutex) +{ + struct thread *thread; + + thread = thread_self(); + + thread_preempt_disable(); + + if (mutex->locked) { + struct mutex_waiter waiter; + + mutex_waiter_init(&waiter, thread); + list_insert_tail(&mutex->waiters, &waiter.node); + + do { + thread_sleep(); + } while (mutex->locked); + + list_remove(&waiter.node); + } + + mutex_set_owner(mutex, thread); + + thread_preempt_enable(); +} + +int +mutex_trylock(struct mutex *mutex) +{ + int error; + + thread_preempt_disable(); + + if (mutex->locked) { + error = ERROR_BUSY; + } else { + error = 0; + mutex_set_owner(mutex, thread_self()); + } + + thread_preempt_enable(); + + return error; +} + +void +mutex_unlock(struct mutex *mutex) +{ + struct mutex_waiter *waiter; + + thread_preempt_disable(); + + mutex_clear_owner(mutex); + + if (!list_empty(&mutex->waiters)) { + waiter = list_first_entry(&mutex->waiters, struct mutex_waiter, node); + mutex_waiter_wakeup(waiter); + } + + thread_preempt_enable(); +} diff --git a/src/mutex.h b/src/mutex.h new file mode 100644 index 0000000..c158d5e --- /dev/null +++ b/src/mutex.h @@ -0,0 +1,165 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * Mutex module. + * + * A mutex is a thread synchronization tool that provides mutual exclusion. + * The code between locking and unlocking a mutex forms a critical section + * that only one thread may be running at a time. This is true for all + * critical sections created with the same mutex, i.e. only one thread may + * be running code in all the critical sections created with the same mutex. + * + * A mutex is initially not owned. When a thread locks a mutex, it becomes + * owned until unlocked, and any other thread trying to lock the mutex + * waits for the owner to unlock it. This is called contention. Waiting + * can be active, e.g. by spinning on the mutex, constantly checking if + * it's still locked, or passive, by sleeping until the owner unlocks + * and wakes up one of the waiters. Mutexes are generally passive, and + * this is also the case for this module. + * + * Since mutexes work by blocking execution of some threads, they are a + * type of lock. Despite their apparent simplicity, they are associated + * with a number of problems, most considered difficult when compared to + * other well know problems of computer science. + * + * In particular, mutexes are vulnerable to deadlocks, i.e. a situation + * where all threads involved are waiting for events that cannot occur. + * Imagine two threads, T1 and T2, and 2 mutexes, M1 and M2. Here is + * a representation of the execution history of those threads leading to + * a deadlock : + * + * T1 : lock(M1) -> lock(M2) (M2 is locked by T2) + * T2 : lock(M2) -> lock(M1) (M1 is locked by T1) + * + * Here, both threads are waiting for the other to unlock one of the + * mutexes before unlocking the other mutex, and none can make progress. + * + * The most simple solution to avoid deadlocks is to not use locks in + * the first place, and use other synchronization tools such as disabling + * preemption, or resorting to lock-free algorithms, but this is often + * not possible (preemption cannot normally be disabled outside kernel + * code, and lock-free algorithms are difficult to implement and may + * lack other dependencies like atomic instructions on small processors). + * + * Another simple solution is to avoid holding two mutexes at the same + * time. It can often be achieved, but not always. Sometimes, holding + * multiple mutexes at the same time is a requirement. In such cases, + * the most common solution is to establish a locking order, since a + * deadlock may only occur if mutexes are acquired in different orders. + * In the example above, the locking order could be represented as + * "M1 -> M2", stating that, when hodling both mutexes, M1 must always + * be locked before M2. + * + * Another common problem with mutexes is unbounded priority inversion. + * Imagine 2 threads, T1 and T2 with priorities 1 and 2 respectively + * (higher value means higher priority). On a real-time system with + * a simple fixed priority scheduler, T2 would preempt T1 whenever it + * is active. But if it then tries to lock a mutex owned by T1, it will + * have to wait for T1 to unlock the mutex. This is priority inversion, + * because T1 is running instead of T2 despite having a lower priority. + * Priority inversion itself is common and often unavoidable in many + * cases, and if kept reliably short, it normally doesn't disturb + * real-time behaviour. But if there is no guarantee that the critical + * section is time-bounded, real-time behaviour may not be achieved. + * The classic example is three threads, T1, T2, and T3, with priorities + * 1, 2, and 3 respectively, and T3 locking a mutex already owned by T1 : + * + * time -> + * T3 lock(M) + run ... + * T2 run + run + | + * T1 lock(M) - run + unlock(M) + + * +: preemption ^^^ + * duration not known/bounded + * + * Here, T3 has to wait for T1 to unlock the mutex before making progress, + * but T2 may preempt T1 because of its higher priority. The time T2 runs, + * keeping T1 from making progress, is likely not known and unbounded, and + * it indirectly delays T3, despite T3 having a higher priority. This is + * unbounded priority inversion. It can be avoided at somewhat high cost + * with priority ceiling/inheritance, or by avoiding the use of mutexes, + * relying instead on e.g. message queues using preemption for + * synchronization. + * + * The implementation of this module is very simple and doesn't prevent + * unbounded priority inversions. + * + * When deciding whether to use a mutex or to disable preemption for + * mutual exclusion, keep in mind that all real-world mutex implementations + * disable preemption internally. As a result, it is best to use mutexes + * when critical sections are noticeably more expensive than the overhead + * of locking. Another parameter is whether or not the critical section + * must remain preemptible. + * + * This mutex interface matches the "fast" kind of POSIX mutexes. In + * particular, a mutex cannot be locked recursively. + */ + +#ifndef _MUTEX_H +#define _MUTEX_H + +#include <stdbool.h> + +#include <lib/list.h> + +#include "thread.h" + +/* + * Mutex type. + * + * All members are private. + */ +struct mutex { + struct list waiters; + struct thread *owner; + bool locked; +}; + +/* + * Initialize a mutex. + */ +void mutex_init(struct mutex *mutex); + +/* + * Lock a mutex. + * + * If the given mutex is already locked, the calling thread blocks (by + * sleeping) and resumes once it holds the mutex. + */ +void mutex_lock(struct mutex *mutex); + +/* + * Try to lock a mutex. + * + * This is the non-blocking variant of mutex_lock(). + * + * Return 0 on success, ERROR_BUSY if locking the mutex failed. + */ +int mutex_trylock(struct mutex *mutex); + +/* + * Unlock a mutex. + * + * The calling thread must be the mutex owner. + */ +void mutex_unlock(struct mutex *mutex); + +#endif /* _MUTEX_H */ diff --git a/src/panic.c b/src/panic.c new file mode 100644 index 0000000..d47330a --- /dev/null +++ b/src/panic.c @@ -0,0 +1,42 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <stdarg.h> +#include <stdio.h> + +#include "cpu.h" +#include "panic.h" +#include "thread.h" + +void +panic(const char *format, ...) +{ + va_list ap; + + thread_preempt_disable(); + cpu_intr_disable(); + printf("\npanic: "); + va_start(ap, format); + vprintf(format, ap); + printf("\n"); + cpu_halt(); +} diff --git a/src/panic.h b/src/panic.h new file mode 100644 index 0000000..be91405 --- /dev/null +++ b/src/panic.h @@ -0,0 +1,32 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#ifndef _PANIC_H +#define _PANIC_H + +#include <lib/macros.h> + +void panic(const char *format, ...) + __attribute__((noreturn)) + __attribute__((format(printf, 1, 2))); + +#endif /* _PANIC_H */ diff --git a/src/stdio.c b/src/stdio.c new file mode 100644 index 0000000..6aee7b3 --- /dev/null +++ b/src/stdio.c @@ -0,0 +1,87 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <stdarg.h> +#include <stdint.h> +#include <stdio.h> + +#include "cpu.h" +#include "thread.h" +#include "uart.h" + +#define PRINTF_BUFFER_SIZE 1024 + +/* + * This implementation uses a global buffer in order to avoid allocating + * from the stack, since stacks may be very small. + */ +static char printf_buffer[PRINTF_BUFFER_SIZE]; + +void +putchar(unsigned char c) +{ + uart_write(c); +} + +int +getchar(void) +{ + uint8_t byte; + int error; + + error = uart_read(&byte); + return error ? EOF : byte; +} + +int +printf(const char *format, ...) +{ + va_list ap; + int length; + + va_start(ap, format); + length = vprintf(format, ap); + va_end(ap); + + return length; +} + +int +vprintf(const char *format, va_list ap) +{ + uint32_t eflags; + int length; + + thread_preempt_disable(); + eflags = cpu_intr_save(); + + length = vsnprintf(printf_buffer, sizeof(printf_buffer), format, ap); + + for (const char *ptr = printf_buffer; *ptr != '\0'; ptr++) { + uart_write((uint8_t)*ptr); + } + + cpu_intr_restore(eflags); + thread_preempt_enable(); + + return length; +} diff --git a/src/string.c b/src/string.c new file mode 100644 index 0000000..210b2bc --- /dev/null +++ b/src/string.c @@ -0,0 +1,143 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <stddef.h> +#include <string.h> + +#include <lib/macros.h> + +void * +memcpy(void *dest, const void *src, size_t n) +{ + const char *src_ptr; + char *dest_ptr; + size_t i; + + dest_ptr = dest; + src_ptr = src; + + for (i = 0; i < n; i++) { + *dest_ptr = *src_ptr; + dest_ptr++; + src_ptr++; + } + + return dest; +} + +void * +memmove(void *dest, const void *src, size_t n) +{ + const char *src_ptr; + char *dest_ptr; + size_t i; + + if (dest <= src) { + dest_ptr = dest; + src_ptr = src; + + for (i = 0; i < n; i++) { + *dest_ptr = *src_ptr; + dest_ptr++; + src_ptr++; + } + } else { + dest_ptr = dest + n - 1; + src_ptr = src + n - 1; + + for (i = 0; i < n; i++) { + *dest_ptr = *src_ptr; + dest_ptr--; + src_ptr--; + } + } + + return dest; +} + +char * +strcpy(char *dest, const char *src) +{ + char *tmp; + + tmp = dest; + + while ((*dest = *src) != '\0') { + dest++; + src++; + } + + return tmp; +} + +size_t +strlen(const char *s) +{ + const char *start; + + start = s; + + while (*s != '\0') { + s++; + } + + return (s - start); +} + +int +strcmp(const char *s1, const char *s2) +{ + char c1, c2; + + while ((c1 = *s1) == (c2 = *s2)) { + if (c1 == '\0') { + return 0; + } + + s1++; + s2++; + } + + return (int)c1 - (int)c2; +} + +int +strncmp(const char *s1, const char *s2, size_t n) +{ + char c1, c2; + + if (unlikely(n == 0)) { + return 0; + } + + while ((n != 0) && (c1 = *s1) == (c2 = *s2)) { + if (c1 == '\0') { + return 0; + } + + n--; + s1++; + s2++; + } + + return (int)c1 - (int)c2; +} diff --git a/src/sw.c b/src/sw.c new file mode 100644 index 0000000..fc253a4 --- /dev/null +++ b/src/sw.c @@ -0,0 +1,295 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * Stopwatch demo application. + */ + +#include <assert.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdio.h> +#include <stdlib.h> + +#include <lib/macros.h> +#include <lib/shell.h> + +#include "condvar.h" +#include "mutex.h" +#include "panic.h" +#include "sw.h" +#include "thread.h" +#include "timer.h" + +/* + * Display interval, in seconds. + */ +#define SW_DISPLAY_INTERVAL 5 + +/* + * Maximum wait time for the sw_wait command. + */ +#define SW_MAX_WAIT 30 + +/* + * Stopwatch type. + * + * The mutex must be locked before accessing any member. + */ +struct sw { + struct mutex mutex; + struct condvar cv; + struct timer timer; + unsigned long ticks; + bool timer_scheduled; + bool thread_waiting; + unsigned long wait_ticks; +}; + +/* + * Singleton instance. + */ +static struct sw *sw_instance; + +static struct sw * +sw_get_instance(void) +{ + assert(sw_instance); + return sw_instance; +} + +static void +sw_timer_run(void *arg) +{ + struct sw *sw; + + sw = arg; + + mutex_lock(&sw->mutex); + + if (!sw->timer_scheduled) { + goto out; + } + + sw->ticks++; + + if ((sw->ticks % (THREAD_SCHED_FREQ * SW_DISPLAY_INTERVAL)) == 0) { + printf("%lu\n", sw->ticks); + } + + if (sw->thread_waiting && timer_ticks_occurred(sw->wait_ticks, sw->ticks)) { + sw->thread_waiting = false; + condvar_signal(&sw->cv); + } + + timer_schedule(&sw->timer, timer_get_time(&sw->timer) + 1); + +out: + mutex_unlock(&sw->mutex); +} + +static struct sw * +sw_create(void) +{ + struct sw *sw; + + sw = malloc(sizeof(*sw)); + + if (!sw) { + return NULL; + } + + mutex_init(&sw->mutex); + condvar_init(&sw->cv); + timer_init(&sw->timer, sw_timer_run, sw); + sw->timer_scheduled = false; + sw->thread_waiting = false; + return sw; +} + +static void +sw_schedule(struct sw *sw) +{ + if (sw->timer_scheduled) { + return; + } + + sw->timer_scheduled = true; + timer_schedule(&sw->timer, timer_now() + 1); +} + +static void +sw_start(struct sw *sw) +{ + mutex_lock(&sw->mutex); + sw->ticks = 0; + sw_schedule(sw); + mutex_unlock(&sw->mutex); +} + +static void +sw_stop(struct sw *sw) +{ + mutex_lock(&sw->mutex); + sw->timer_scheduled = false; + mutex_unlock(&sw->mutex); +} + +static void +sw_resume(struct sw *sw) +{ + mutex_lock(&sw->mutex); + sw_schedule(sw); + mutex_unlock(&sw->mutex); +} + +static unsigned long +sw_read(struct sw *sw) +{ + unsigned long ticks; + + mutex_lock(&sw->mutex); + ticks = sw->ticks; + mutex_unlock(&sw->mutex); + + return ticks; +} + +static void +sw_wait(struct sw *sw, unsigned long seconds) +{ + mutex_lock(&sw->mutex); + + if (!sw->timer_scheduled) { + printf("sw_wait: error: stopwatch disabled\n"); + goto out; + } else if (sw->thread_waiting) { + printf("sw_wait: error: thread already waiting\n"); + goto out; + } + + sw->thread_waiting = true; + sw->wait_ticks = sw->ticks + (seconds * THREAD_SCHED_FREQ); + + do { + condvar_wait(&sw->cv, &sw->mutex); + } while (sw->thread_waiting); + +out: + mutex_unlock(&sw->mutex); +} + +static void +sw_shell_start(int argc, char **argv) +{ + (void)argc; + (void)argv; + + sw_start(sw_get_instance()); +} + +static void +sw_shell_stop(int argc, char **argv) +{ + (void)argc; + (void)argv; + + sw_stop(sw_get_instance()); +} + +static void +sw_shell_resume(int argc, char **argv) +{ + (void)argc; + (void)argv; + + sw_resume(sw_get_instance()); +} + +static void +sw_shell_read(int argc, char **argv) +{ + (void)argc; + (void)argv; + + printf("%lu\n", sw_read(sw_get_instance())); +} + +static void +sw_shell_wait(int argc, char **argv) +{ + unsigned long seconds; + int ret; + + if (argc != 2) { + goto error; + } + + ret = sscanf(argv[1], "%lu", &seconds); + + if ((ret != 1) || (seconds > SW_MAX_WAIT)) { + goto error; + } + + sw_wait(sw_get_instance(), seconds); + return; + +error: + printf("sw_wait: error: invalid arguments\n"); +} + +static struct shell_cmd shell_cmds[] = { + SHELL_CMD_INITIALIZER("sw_start", sw_shell_start, + "sw_start", + "start the stopwatch"), + SHELL_CMD_INITIALIZER("sw_stop", sw_shell_stop, + "sw_stop", + "stop the stopwatch"), + SHELL_CMD_INITIALIZER("sw_resume", sw_shell_resume, + "sw_resume", + "resume the stopwatch"), + SHELL_CMD_INITIALIZER("sw_read", sw_shell_read, + "sw_read", + "read the stopwatch time"), + SHELL_CMD_INITIALIZER("sw_wait", sw_shell_wait, + "sw_wait <seconds>", + "wait for up to " QUOTE(SW_MAX_WAIT) " seconds"), +}; + +void +sw_setup(void) +{ + int error; + + sw_instance = sw_create(); + + if (!sw_instance) { + panic("sw: error: unable to create stopwatch"); + } + + for (size_t i = 0; i < ARRAY_SIZE(shell_cmds); i++) { + error = shell_cmd_register(&shell_cmds[i]); + + if (error) { + panic("unable to register shell command"); + } + } +} diff --git a/src/sw.h b/src/sw.h new file mode 100644 index 0000000..91488c3 --- /dev/null +++ b/src/sw.h @@ -0,0 +1,34 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * Stopwatch demo application. + */ + +#ifndef _SW_H +#define _SW_H + +/* + * Initialize the sw module. + */ +void sw_setup(void); + +#endif /* _SW_H */ diff --git a/src/thread.c b/src/thread.c new file mode 100644 index 0000000..e361473 --- /dev/null +++ b/src/thread.c @@ -0,0 +1,823 @@ +/* + * Copyright (c) 2017 Richard Braun. + * Copyright (c) 2017 Jerko Lenstra. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <assert.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> + +#include <lib/macros.h> +#include <lib/list.h> + +#include "cpu.h" +#include "error.h" +#include "panic.h" +#include "thread.h" +#include "timer.h" + +/* + * The compiler expects the stack pointer to be properly aligned when a + * function is called, and maintains this alignment across a call chain. + * The constraints are similar to the return value of malloc(). + * See the description of mem_alloc() in mem.h. + * + * Note that modern compilers expect the stack to be 16-byte aligned + * even on 32-bits i386 processors, to cope with SSE instructions which + * don't support unaligned accesses (see a revised version of the System V + * Intel386 ABI [1] for more details). Since all floating point support is + * disabled when building the kernel, this requirement can be safely ignored + * and the legacy 4-byte alignment used instead. + * + * [1] https://www.uclibc.org/docs/psABI-i386.pdf + */ +#define THREAD_STACK_ALIGN 4 + +/* + * List of threads sharing the same priority. + */ +struct thread_list { + struct list threads; +}; + +/* + * Run queue. + * + * Threads that aren't in the running state aren't tracked in a run queue. + * The current thread, which is the one currently running on the processor, + * isn't in any of the thread lists. + * + * The idle thread runs when no other thread is in the running state. + * + * Interrupts and preemption must be disabled when accessing a run queue. + * Interrupts must be disabled to prevent a timer interrupt from corrupting + * the run queue. Preemption must be disabled to prevent an interrupt handler + * from causing an early context switch when returning from interrupt. + */ +struct thread_runq { + struct thread *current; + unsigned int nr_threads; + struct thread_list lists[THREAD_NR_PRIORITIES]; + struct thread *idle; +}; + +enum thread_state { + THREAD_STATE_RUNNING, /* Thread is in a run queue */ + THREAD_STATE_SLEEPING, /* Thread is not running */ + THREAD_STATE_DEAD, /* Thread is sleeping and may not be awaken */ +}; + +/* + * Thread structure. + * + * The purpose of a thread is to support saving and restoring state in order + * to achieve time sharing between activities. + * + * A thread is mostly used to store the saved state of an activity, called + * its context. The context is usually made up of some registers that are + * saved on the stack, the stack itself, and the thread structure. + * When the context is saved, the stack pointer is updated to the value + * of the stack register at the time the thread context is saved. + * + * A thread may be be "voluntarily" preempted, when it yields the processor + * itself, or "involuntarily" preempted when an interrupt occurs. Since it's + * not possible to immediately yield the processor when preemption is + * disabled (including in the middle of an interrupt handler), preemption + * may only occur on specific events : + * - Calling thread_yield() with preemption enabled. + * - Preemption is reenabled, i.e. the preemption level goes back to 0. + * - Return from an interrupt. + * + * Calling thread_yield() is completely voluntary and is ignored in this + * discussion. Returning from an interrupt actually reenables preemption, + * so the only case discussed is reenabling preemption. The mechanism used + * to trigger scheduling when preemption is reenabled is the yield flag. + * When the scheduler determines that the current thread should yield the + * processor, e.g. because an interrupt handler has awaken a higher priority + * thread, it marks the current thread for yielding. When preemption is + * reenabled, the flag is checked, and if true, the current thread yields + * the processor. + */ +struct thread { + void *sp; + enum thread_state state; + bool yield; + struct list node; + unsigned int preempt_level; + unsigned int priority; + struct thread *joiner; + char name[THREAD_NAME_MAX_SIZE]; + void *stack; +}; + +/* + * Run queue singleton. + */ +static struct thread_runq thread_runq; + +/* + * Dummy thread context used to make functions that require a thread context + * work before the thread module is fully initialized. + */ +static struct thread thread_dummy; + +/* + * Declarations for C/assembly functions that are global so that they can + * be shared between thread.c and thread_asm.S, but are considered private to + * the thread module. + */ +void thread_load_context(struct thread *thread) __attribute__((noreturn)); +void thread_switch_context(struct thread *prev, struct thread *next); +void thread_main(thread_fn_t fn, void *arg); + +/* + * Function implementing the idle thread. + */ +static void +thread_idle(void *arg) +{ + (void)arg; + + for (;;) { + cpu_idle(); + } +} + +static bool +thread_is_running(const struct thread *thread) +{ + return thread->state == THREAD_STATE_RUNNING; +} + +static void +thread_set_running(struct thread *thread) +{ + thread->state = THREAD_STATE_RUNNING; +} + +static void +thread_set_sleeping(struct thread *thread) +{ + thread->state = THREAD_STATE_SLEEPING; +} + +static bool +thread_is_dead(const struct thread *thread) +{ + return thread->state == THREAD_STATE_DEAD; +} + +static void +thread_set_dead(struct thread *thread) +{ + thread->state = THREAD_STATE_DEAD; +} + +static bool +thread_should_yield(const struct thread *thread) +{ + return thread->yield; +} + +static void +thread_set_yield(struct thread *thread) +{ + thread->yield = true; +} + +static void +thread_clear_yield(struct thread *thread) +{ + thread->yield = false; +} + +static unsigned int +thread_get_priority(struct thread *thread) +{ + return thread->priority; +} + +static void +thread_remove_from_list(struct thread *thread) +{ + list_remove(&thread->node); +} + +static void +thread_yield_if_needed(void) +{ + if (thread_should_yield(thread_self())) { + thread_yield(); + } +} + +void +thread_preempt_disable(void) +{ + struct thread *thread; + + thread = thread_self(); + thread->preempt_level++; + assert(thread->preempt_level != 0); + + barrier(); +} + +static void +thread_preempt_enable_no_yield(void) +{ + struct thread *thread; + + barrier(); + + thread = thread_self(); + assert(thread->preempt_level != 0); + thread->preempt_level--; +} + +void +thread_preempt_enable(void) +{ + thread_preempt_enable_no_yield(); + thread_yield_if_needed(); +} + +bool +thread_preempt_enabled(void) +{ + struct thread *thread; + + thread = thread_self(); + return thread->preempt_level == 0; +} + +static bool +thread_scheduler_locked(void) +{ + return !cpu_intr_enabled() && !thread_preempt_enabled(); +} + +static uint32_t +thread_lock_scheduler(void) +{ + /* + * When disabling both preemption and interrupts, it is best to do it in + * this order, since, if an interrupt occurs after preemption is disabled + * but before interrupts are disabled, it may not cause a context switch. + * + * Besides, disabling interrupts first would slightly increase interrupt + * latencies. + */ + thread_preempt_disable(); + return cpu_intr_save(); +} + +static void +thread_unlock_scheduler(uint32_t eflags, bool yield) +{ + cpu_intr_restore(eflags); + + if (yield) { + thread_preempt_enable(); + } else { + thread_preempt_enable_no_yield(); + } +} + +static void +thread_list_init(struct thread_list *list) +{ + list_init(&list->threads); +} + +static void +thread_list_enqueue(struct thread_list *list, struct thread *thread) +{ + list_insert_tail(&list->threads, &thread->node); +} + +static struct thread * +thread_list_dequeue(struct thread_list *list) +{ + struct thread *thread; + + thread = list_first_entry(&list->threads, typeof(*thread), node); + thread_remove_from_list(thread); + return thread; +} + +static bool +thread_list_empty(struct thread_list *list) +{ + return list_empty(&list->threads); +} + +static struct thread_list * +thread_runq_get_list(struct thread_runq *runq, unsigned int priority) +{ + assert(priority < ARRAY_SIZE(runq->lists)); + return &runq->lists[priority]; +} + +static struct thread * +thread_runq_get_current(struct thread_runq *runq) +{ + return runq->current; +} + +static void +thread_runq_put_prev(struct thread_runq *runq, struct thread *thread) +{ + struct thread_list *list; + + if (thread == runq->idle) { + return; + } + + list = thread_runq_get_list(runq, thread_get_priority(thread)); + thread_list_enqueue(list, thread); +} + +static struct thread * +thread_runq_get_next(struct thread_runq *runq) +{ + struct thread *thread; + + assert(runq->current); + + if (runq->nr_threads == 0) { + thread = runq->idle; + } else { + struct thread_list *list; + size_t nr_lists; + + nr_lists = ARRAY_SIZE(runq->lists); + + /* + * Note that size_t is unsigned, which means that when the iterator + * is 0 and decremented, the new value is actually the maximum value + * that the type may have, which is necessarily higher than the array + * size. This behaviour is very well defined by the C specification + * (6.3.1.3 Signed and unsigned integers), and avoids warnings about + * mixing types of different signedness. + */ + for (size_t i = (nr_lists - 1); i < nr_lists; i--) { + list = thread_runq_get_list(runq, i); + + if (!thread_list_empty(list)) { + break; + } + } + + thread = thread_list_dequeue(list); + } + + runq->current = thread; + return thread; +} + +static void +thread_runq_add(struct thread_runq *runq, struct thread *thread) +{ + struct thread_list *list; + + assert(thread_scheduler_locked()); + assert(thread_is_running(thread)); + + list = thread_runq_get_list(runq, thread_get_priority(thread)); + thread_list_enqueue(list, thread); + + runq->nr_threads++; + assert(runq->nr_threads != 0); + + if (thread_get_priority(thread) > thread_get_priority(runq->current)) { + thread_set_yield(runq->current); + } +} + +static void +thread_runq_remove(struct thread_runq *runq, struct thread *thread) +{ + assert(runq->nr_threads != 0); + runq->nr_threads--; + + assert(!thread_is_running(thread)); + thread_remove_from_list(thread); +} + +static void +thread_runq_schedule(struct thread_runq *runq) +{ + struct thread *prev, *next; + + prev = thread_runq_get_current(runq); + + assert(thread_scheduler_locked()); + assert(prev->preempt_level == 1); + + thread_runq_put_prev(runq, prev); + + if (!thread_is_running(prev)) { + thread_runq_remove(runq, prev); + } + + next = thread_runq_get_next(runq); + + if (prev != next) { + /* + * When switching context, it is extremely important that no + * data access generated by the compiler "leak" across the switch. + * All operations (i.e. side effects) started before the switch + * should complete before the switch, and all operations starting + * after the switch should start after the switch. + * + * This is what allows a thread waiting for an event to reliably + * "see" that event after another thread or interrupt handler has + * triggered it. + * + * This requires a barrier, and, since this is a single-processor + * scheduler, a compiler barrier (as opposed to memory barriers) + * is enough. But there is no such barrier here. The reason is that + * the context switch is implemented in assembly, and the compiler + * is unable to understand what the assembly code does. As a result, + * even with aggressive optimizations enabled, the compiler has to + * assume that memory may have changed in completely unexpected ways, + * which is equivalent to the inline assembly expression used to + * implement compiler barriers with GCC (see barrier() in macros.h). + */ + thread_switch_context(prev, next); + } +} + +void +thread_enable_scheduler(void) +{ + struct thread *thread; + + thread = thread_runq_get_next(&thread_runq); + assert(thread); + assert(thread->preempt_level == 1); + thread_load_context(thread); + + /* Never reached */ +} + +void +thread_main(thread_fn_t fn, void *arg) +{ + assert(fn); + + assert(thread_scheduler_locked()); + assert(thread_self()->preempt_level == 1); + + cpu_intr_enable(); + thread_preempt_enable(); + + fn(arg); + + thread_exit(); +} + +const char * +thread_name(const struct thread *thread) +{ + return thread->name; +} + +static void +thread_set_name(struct thread *thread, const char *name) +{ + snprintf(thread->name, sizeof(thread->name), "%s", name); +} + +static void +thread_stack_push(uint32_t **stackp, size_t *stack_sizep, uint32_t word) +{ + uint32_t *stack; + size_t stack_size; + + stack = *stackp; + stack_size = *stack_sizep; + assert(stack_size >= sizeof(word)); + stack--; + stack_size -= sizeof(word); + *stack = word; + *stackp = stack; + *stack_sizep = stack_size; +} + +static void * +thread_stack_forge(char *stack_addr, size_t stack_size, + thread_fn_t fn, void *arg) +{ + uint32_t *stack; + + stack = (uint32_t *)(stack_addr + stack_size); + + /* + * This part of the stack makes context restoration "return" to + * thread_main() as if it were called from address 0 (which stops + * backtracing when using a debugger). + * + * This is how an assembly call to thread_main() looks like, according + * to the ABI (System V Intel 386 ABI [1]) : + * push arg + * push fn + * call thread_main + * + * Remember that the call instruction pushes the return address on the + * stack. + * + * [1] http://www.sco.com/developers/devspecs/abi386-4.pdf + */ + thread_stack_push(&stack, &stack_size, (uint32_t)arg); /* 2nd argument */ + thread_stack_push(&stack, &stack_size, (uint32_t)fn); /* 1st argument */ + thread_stack_push(&stack, &stack_size, (uint32_t)0); /* Return address */ + thread_stack_push(&stack, &stack_size, (uint32_t)thread_main); + + /* + * This part of the stack contains the registers that should be restored. + * The selection of the registers to save is made according to the + * ABI, which specifies which registers are owned by the caller, and + * which are owned by the callee. Since, in all cases, switching context + * is achieved by calling the thread_switch_context() function, it + * is safe to rely on the ABI for this selection. Naturally, the + * registers that must be saved are those owned by the caller, since + * the compiler assumes all registers owned by the callee may have + * changed on return. See the System V Intel386 ABI "Registers and the + * Stack Frame". + * + * For debugging purposes, a complete save of all the registers may be + * performed instead, allowing precise inspection of the state of a + * thread not currently running on the processor. + * + * It is recommended to read the assembly code at the thread_restore_context + * label in thread_asm.S to better understand this stack frame. + */ + thread_stack_push(&stack, &stack_size, 0); /* EBP */ + thread_stack_push(&stack, &stack_size, 0); /* EBX */ + thread_stack_push(&stack, &stack_size, 0); /* EDI */ + thread_stack_push(&stack, &stack_size, 0); /* ESI */ + + return stack; +} + +static void +thread_init(struct thread *thread, thread_fn_t fn, void *arg, + const char *name, char *stack, size_t stack_size, + unsigned int priority) +{ + assert(P2ALIGNED((uintptr_t)stack, THREAD_STACK_ALIGN)); + + /* + * New threads are created in a state that is similar to preempted threads, + * since it makes running them for the first time indistinguishable from + * redispatching a thread that has actually been preempted. This state + * is very specific and includes the following properties : + * - state is running + * - interrupts are disabled + * - preemption level must be exactly one (see the description of + * thread_sleep() in thread.h) + * + * A state is artificially forged on the new stack to make it look like + * the new thread has been preempted. + */ + + if (stack) { + thread->sp = thread_stack_forge(stack, stack_size, fn, arg); + } + + thread->state = THREAD_STATE_RUNNING; + thread->yield = false; + thread->preempt_level = 1; + thread->priority = priority; + thread->joiner = NULL; + thread_set_name(thread, name); + thread->stack = stack; +} + +int +thread_create(struct thread **threadp, thread_fn_t fn, void *arg, + const char *name, size_t stack_size, unsigned int priority) +{ + struct thread *thread; + uint32_t eflags; + void *stack; + + assert(fn); + + thread = malloc(sizeof(*thread)); + + if (!thread) { + return ERROR_NOMEM; + } + + if (stack_size < THREAD_STACK_MIN_SIZE) { + stack_size = THREAD_STACK_MIN_SIZE; + } + + stack = malloc(stack_size); + + if (!stack) { + free(thread); + return ERROR_NOMEM; + } + + thread_init(thread, fn, arg, name, stack, stack_size, priority); + + eflags = thread_lock_scheduler(); + thread_runq_add(&thread_runq, thread); + thread_unlock_scheduler(eflags, true); + + if (threadp) { + *threadp = thread; + } + + return 0; +} + +static void +thread_destroy(struct thread *thread) +{ + assert(thread_is_dead(thread)); + + free(thread->stack); + free(thread); +} + +void +thread_exit(void) +{ + struct thread *thread; + + thread = thread_self(); + + assert(thread_preempt_enabled()); + + thread_lock_scheduler(); + assert(thread_is_running(thread)); + thread_set_dead(thread); + thread_wakeup(thread->joiner); + thread_runq_schedule(&thread_runq); + + panic("thread: error: dead thread walking"); +} + +void +thread_join(struct thread *thread) +{ + uint32_t eflags; + + eflags = thread_lock_scheduler(); + + thread->joiner = thread_self(); + + while (!thread_is_dead(thread)) { + thread_sleep(); + } + + thread_unlock_scheduler(eflags, true); + + thread_destroy(thread); +} + +struct thread * +thread_self(void) +{ + return thread_runq_get_current(&thread_runq); +} + +static struct thread * +thread_create_idle(void) +{ + struct thread *idle; + void *stack; + + idle = malloc(sizeof(*idle)); + + if (!idle) { + panic("thread: unable to allocate idle thread"); + } + + stack = malloc(THREAD_STACK_MIN_SIZE); + + if (!stack) { + panic("thread: unable to allocate idle thread stack"); + } + + thread_init(idle, thread_idle, NULL, "idle", + stack, THREAD_STACK_MIN_SIZE, THREAD_IDLE_PRIORITY); + return idle; +} + +static void +thread_runq_preinit(struct thread_runq *runq) +{ + thread_init(&thread_dummy, NULL, NULL, "dummy", NULL, 0, 0); + runq->current = &thread_dummy; +} + +static void +thread_runq_init(struct thread_runq *runq) +{ + runq->nr_threads = 0; + + for (size_t i = 0; i < ARRAY_SIZE(runq->lists); i++) { + thread_list_init(&runq->lists[i]); + } + + runq->idle = thread_create_idle(); +} + +void +thread_bootstrap(void) +{ + thread_runq_preinit(&thread_runq); +} + +void +thread_setup(void) +{ + thread_runq_init(&thread_runq); +} + +void +thread_yield(void) +{ + uint32_t eflags; + + if (!thread_preempt_enabled()) { + return; + } + + eflags = thread_lock_scheduler(); + thread_clear_yield(thread_self()); + thread_runq_schedule(&thread_runq); + thread_unlock_scheduler(eflags, false); +} + +void +thread_sleep(void) +{ + struct thread *thread; + uint32_t eflags; + + thread = thread_self(); + + eflags = cpu_intr_save(); + assert(thread_is_running(thread)); + thread_set_sleeping(thread); + thread_runq_schedule(&thread_runq); + assert(thread_is_running(thread)); + cpu_intr_restore(eflags); +} + +void +thread_wakeup(struct thread *thread) +{ + uint32_t eflags; + + if (!thread || (thread == thread_self())) { + return; + } + + eflags = thread_lock_scheduler(); + + if (!thread_is_running(thread)) { + assert(!thread_is_dead(thread)); + thread_set_running(thread); + thread_runq_add(&thread_runq, thread); + } + + thread_unlock_scheduler(eflags, true); +} + +void +thread_report_tick(void) +{ + assert(thread_scheduler_locked()); + + thread_set_yield(thread_self()); + timer_report_tick(); +} diff --git a/src/thread.h b/src/thread.h new file mode 100644 index 0000000..78f87da --- /dev/null +++ b/src/thread.h @@ -0,0 +1,326 @@ +/* + * Copyright (c) 2017 Richard Braun. + * Copyright (c) 2017 Jerko Lenstra. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * Thread module. + * + * This module provides threads of execution, which encapsulate sequential + * activities that may be preempted (stopped by the scheduler) so that other + * threads may run on the processor. This is what makes an operating system + * "time sharing". + * + * Threads are usually scheduled according to a scheduling policy. This + * module implements a very simple fixed-priority based scheduling policy, + * where the thread running is ideally always the thread with the highest + * priority. Because of priority inversions, this isn't always possible. + * A real-time operating system (RTOS) strives to achieve a behaviour + * as close as possible to this ideal. + * + * Threads may also be called tasks (e.g. in many small embedded RTOS), or + * lightweight processes (BSDs, Solaris). The word "process", usually refers + * to much more heavyweight resource containers on Unix, which include both + * threads and other resources such as an address space and a file descriptor + * table. Sometimes, the word "task" also refers to this (e.g. in Linux), + * so using the word "thread" is usually much less ambiguous. + * + * Almost all modern operating systems associate a stack with each thread. + * In the past, threads could explicitely save the state they would need to + * be restored (look up "continuations"). But since preemptive scheduling + * requires the ability to preempt a thread at almost any time, a generic + * way to save and restore the thread state is needed. The most common way + * is to store that state on the stack, save the stack pointer into the + * thread structure, and later do the reverse when the thread is dispatched + * again on the processor. + * + * Stack overflows in embedded systems are a major source of bugs. The stack + * of a thread needs to be large enough to store all the data required by the + * longest call chain possible and also the saved state of the thread if + * interrupted right at the end of that chain, something that is quite + * difficult to determine from static analysis. Some systems provide tools + * to detect such overflows by e.g. filling the stack with a pattern at + * creation time, and making sure the pattern hasn't changed near the end + * of the stack. On systems with virtual memory, guard pages can be used to + * achieve an even more reliable effect, although at greater cost. + * + * A major concept around (kernel) threads is preemption. Disabling preemption + * means that the current thread may not be preempted, i.e. it will keep + * running until preemption is reenabled. Therefore, it's not possible for a + * thread to passively wait for an event if preemption is disabled. Disabling + * preemption is one of the primary means to implement critical sections. + * Many embedded systems build critical sections by disabling interrupts, + * but this lack of decoupling means that interrupts may unnecessarily be + * disabled, which increases interrupt latency. + * + * In X1, interrupts must only be disabled when data is shared between a + * thread and an interrupt handler, as a means to prevent the interrupt + * handler from running while the thread is accessing the shared data. + * Disabling preemption is the preferred way to implement short, time-bounded + * critical sections. If the cost of the critical section is "too high" + * (something quite hard to evaluate and which rests entirely on the decision + * of the developer), mutexes are the recommended tool, since they keep + * preemption enabled during the critical section. + */ + +#ifndef _THREAD_H +#define _THREAD_H + +#include <stdbool.h> +#include <stddef.h> + +/* + * The scheduling frequency is the rate at which the clock used for scheduling + * ticks. On each tick, the scheduler may mark the currently running thread to + * yield. + * + * This implementation uses periodic ticks, but if the underlying hardware + * supports reprogramming without losing track of time, a dynamic tick + * implementation could be used. + */ +#define THREAD_SCHED_FREQ 100 + +/* + * Maximum size of thread names, including the null terminating character. + */ +#define THREAD_NAME_MAX_SIZE 16 + +/* + * Minimum size of thread stacks. + */ +#define THREAD_STACK_MIN_SIZE 512 + +/* + * Total number of thread priorities. + */ +#define THREAD_NR_PRIORITIES 20 + +/* + * The lowest priority is used by the idle thread and can be used by very + * low priority (usually background) threads. + */ +#define THREAD_IDLE_PRIORITY 0 + +/* + * Range of regular priorities. + * + * Lower values mean lower priorities. + */ +#define THREAD_MIN_PRIORITY 1 +#define THREAD_MAX_PRIORITY (THREAD_NR_PRIORITIES - 1) + +/* + * Type for thread functions. + */ +typedef void (*thread_fn_t)(void *arg); + +/* + * Opaque declaration. + * + * An opaque declaration allows the interface to prevent any direct access + * to the structure itself from external users. The price is that, without + * the definition, the compiler doesn't know the size of the structure, + * which prevents allocations from the stack and composition by embedding + * in other structures, and usually requires the interface to provide + * dynamic allocation. + */ +struct thread; + +/* + * Early initialization of the thread module. + * + * This function initializes a dummy thread context so that functions that + * require a thread context, such as thread_self(), can be used before the + * thread module is initialized. + */ +void thread_bootstrap(void); + +/* + * Initialize the thread module. + * + * On return, new threads may be created. They will only run once the scheduler + * is enabled. + */ +void thread_setup(void); + +/* + * Create a thread. + * + * The new thread runs the given function, along with the given argument, + * as soon as permitted by the scheduler. + * + * A pointer to the new thread is returned into *threadp, if the latter isn't + * NULL. + */ +int thread_create(struct thread **threadp, thread_fn_t fn, void *arg, + const char *name, size_t stack_size, unsigned int priority); + +/* + * Make the current thread terminate. + * + * For the sake of simplicity, this module doesn't provide "detached" + * threads, where the resources are automatically released on exit. + * This means that all threads must be joined to avoid resource leaks. + * + * This function doesn't return. + */ +void thread_exit(void) __attribute__((noreturn)); + +/* + * Wait for a thread to terminate. + * + * When the given thread is joined, its resources are released. + */ +void thread_join(struct thread *thread); + +/* + * Return the current thread. + */ +struct thread * thread_self(void); + +/* + * Return the name of the given thread. + */ +const char * thread_name(const struct thread *thread); + +/* + * Yield the processor. + * + * The calling thread remains in the running state, and may keep running on + * the processor if the scheduler determines that it should continue. + */ +void thread_yield(void); + +/* + * Make the calling thread sleep until awaken. + * + * Preemption must be disabled exactly once before calling this function, and + * is used to reliably synchronize waiting for/triggering an event. + * + * Preemption is used to serialize access to the variables shared between + * the sleeping thread and the waking code, which may run from another thread + * (thread context) or from an interrupt handler (interrupt context). + * If serializing against an interrupt handler, the user must also disable + * interrupts. + * + * By disabling preemption, checking the predicate and sleeping is done + * atomically with respect to setting the predicate and waking up. Obviously, + * while sleeping, preemption is reenabled by this function, to allow another + * thread to set the predicate and wake up the sleeping thread, which is why + * the preemption level must be exactly one on entry. + * + * Note that this function may return for other reasons than the predicate + * becoming true. These wake-ups are called spurious wake-ups and may be + * caused by implementation details as well as manually waking up threads + * (e.g. with C/Unix signals such as SIGINT). This is why sleeping should + * always be enclosed in a loop, rechecking the predicate on each iteration. + * + * Here is an example of sleeping and waking up : + * + * static bool predicate; + * static struct thread *thread; + * + * void + * init(void) + * { + * predicate = false; + * thread_create(&thread, run, ...); + * } + * + * void + * run(void) + * { + * for (;;) { + * thread_preempt_disable(); Disable preemption exactly once. + * + * while (!predicate) { Checking the predicate and sleeping + * thread_sleep(); is atomic with respect to setting + * } the predicate and waking up. + * + * do_something(); + * + * thread_preempt_enable(); + * } + * } + * + * void + * wakeup(void) + * { + * assert(!thread_preempt_enabled()); Because preemption is disabled, + * predicate = true; setting the predicate and waking up + * thread_wakeup(thread); is atomic with respect to checking + * the predicate and sleeping. + * } + * + * This pattern is very close to the POSIX condition variable [1]. The + * differences are : + * - The mutex is replaced by preemption for serialization. + * - The condition variable isn't needed because the interface only allows + * waking up a single thread. + * - Cancellation is completely ignored. + * + * You may compare this example with the one in condvar.h for a clear view of + * the similarities. + * + * A mutex would have been difficult to use here since they rely this low + * level interface, leading to complicated dependency issues. In addition, + * this is a single processor / single run queue scheduler so using + * preemption, which is usually processor-local, is sufficient. Finally, + * it's also the cheapest way to build critical sections, which improves + * performance. + * + * [1] http://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_cond_wait.html. + */ +void thread_sleep(void); + +/* + * Wake up the given thread. + * + * For reliable event processing, preemption should be disabled. + * + * This function may safely be called from interrupt context. + */ +void thread_wakeup(struct thread *thread); + +/* + * Preemption control functions. + * + * Note that enabling preemption actually increments the preemption level + * whereas disabling preemption decrements it, allowing preemption-based + * critical sections to nest. Preemption is enabled when the preemption + * level is 0. + */ +void thread_preempt_enable(void); +void thread_preempt_disable(void); +bool thread_preempt_enabled(void); + +/* + * Report a tick. + * + * This function must be called from interrupt context. + */ +void thread_report_tick(void); + +/* + * Enable the scheduler. + */ +void thread_enable_scheduler(void) __attribute__((noreturn)); + +#endif /* _THREAD_H */ diff --git a/src/thread_asm.S b/src/thread_asm.S new file mode 100644 index 0000000..0327fce --- /dev/null +++ b/src/thread_asm.S @@ -0,0 +1,51 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +.section .text +.code32 + +.global thread_load_context +thread_load_context: + mov 4(%esp), %eax /* Load the thread address */ + mov (%eax), %esp /* Switch to the thread stack */ + jmp thread_restore_context + +.global thread_switch_context +thread_switch_context: + mov 4(%esp), %eax /* Get prev thread address */ + mov 8(%esp), %ecx /* Get next thread address */ + + push %ebp /* Save registers owned by the caller */ + push %ebx + push %edi + push %esi + + mov %esp, (%eax) /* Save prev thread stack pointer */ + mov (%ecx), %esp /* Switch to the stack of the next thread */ + +thread_restore_context: + pop %esi + pop %edi + pop %ebx + pop %ebp + + ret diff --git a/src/timer.c b/src/timer.c new file mode 100644 index 0000000..b663e10 --- /dev/null +++ b/src/timer.c @@ -0,0 +1,321 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <assert.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> + +#include <lib/list.h> +#include <lib/macros.h> + +#include "cpu.h" +#include "mutex.h" +#include "panic.h" +#include "thread.h" +#include "timer.h" + +#define TIMER_STACK_SIZE 4096 + +/* + * When determining whether a point in time is in the future or the past, + * it's important to remember that the value is always finite. Here, + * the ticks use a 32-bits type (unsigned long on i386), so, assuming + * a 100Hz frequency, time wraps around about every 497 days. Therefore, + * the implementation needs a way to partition time between the future + * and the past. To do so, it considers that all values from a reference + * up to a threshold are in the future (except the present), and all other + * values are in the past. This macro defines that threshold. + * + * Currently, the threshold is half of the maximum value, which is + * equivalent to using a signed integer where positive values would denote + * the future and negative ones the past, except that overflows on signed + * integers are undefined behaviour, whereas overflows on unsigned + * integers are well specified (3.4.3 Undefined Behaviour and 6.2.5 Types). + */ +#define TIMER_THRESHOLD (((unsigned long)-1) / 2) + +/* + * The current time, in ticks. + */ +static unsigned long timer_ticks; + +/* + * List of timers, sorted by time. + * + * The timer mutex must be locked when accessing the timer list. + */ +static struct list timer_list; +static struct mutex timer_mutex; + +/* + * The timer thread, which provides context for all timer callbacks. + */ +static struct thread *timer_thread; + +/* + * True if the timer list is empty. + * + * This is a copy of list_empty(&timer_list) which may be used from + * interrupt context, where locking a mutex is impossible. + * + * Interrupts must be disabled when accessing this variable. + */ +static bool timer_list_empty; + +/* + * Time in ticks of the first timer on the timer list. + * + * Only valid if the list isn't empty. + * + * Interrupts must be disabled when accessing this variable. + */ +static unsigned long timer_wakeup_ticks; + +bool +timer_ticks_expired(unsigned long ticks, unsigned long ref) +{ + return (ticks - ref) > TIMER_THRESHOLD; +} + +bool +timer_ticks_occurred(unsigned long ticks, unsigned long ref) +{ + return (ticks == ref) || timer_ticks_expired(ticks, ref); +} + +static bool +timer_work_pending(void) +{ + assert(!cpu_intr_enabled()); + + return !timer_list_empty + && timer_ticks_occurred(timer_wakeup_ticks, timer_ticks); +} + +static bool +timer_scheduled(const struct timer *timer) +{ + return !list_node_unlinked(&timer->node); +} + +static bool +timer_expired(const struct timer *timer, unsigned long ref) +{ + return timer_ticks_expired(timer->ticks, ref); +} + +static bool +timer_occurred(const struct timer *timer, unsigned long ref) +{ + return timer_ticks_occurred(timer->ticks, ref); +} + +static void +timer_process(struct timer *timer) +{ + timer->fn(timer->arg); +} + +static void +timer_process_list(unsigned long now) +{ + struct timer *timer; + uint32_t eflags; + + mutex_lock(&timer_mutex); + + while (!list_empty(&timer_list)) { + timer = list_first_entry(&timer_list, typeof(*timer), node); + + if (!timer_occurred(timer, now)) { + break; + } + + list_remove(&timer->node); + list_node_init(&timer->node); + mutex_unlock(&timer_mutex); + + timer_process(timer); + + mutex_lock(&timer_mutex); + } + + eflags = cpu_intr_save(); + + timer_list_empty = list_empty(&timer_list); + + if (!timer_list_empty) { + timer = list_first_entry(&timer_list, typeof(*timer), node); + timer_wakeup_ticks = timer->ticks; + } + + cpu_intr_restore(eflags); + + mutex_unlock(&timer_mutex); +} + +static void +timer_run(void *arg) +{ + unsigned long now; + uint32_t eflags; + + (void)arg; + + for (;;) { + thread_preempt_disable(); + eflags = cpu_intr_save(); + + for (;;) { + now = timer_ticks; + + if (timer_work_pending()) { + break; + } + + thread_sleep(); + } + + cpu_intr_restore(eflags); + thread_preempt_enable(); + + timer_process_list(now); + } +} + +void +timer_setup(void) +{ + int error; + + timer_ticks = 0; + timer_list_empty = true; + + list_init(&timer_list); + mutex_init(&timer_mutex); + + error = thread_create(&timer_thread, timer_run, NULL, + "timer", TIMER_STACK_SIZE, THREAD_MAX_PRIORITY); + + if (error) { + panic("timer: unable to create thread"); + } +} + +unsigned long +timer_now(void) +{ + unsigned long ticks; + uint32_t eflags; + + eflags = cpu_intr_save(); + ticks = timer_ticks; + cpu_intr_restore(eflags); + + return ticks; +} + +void +timer_init(struct timer *timer, timer_fn_t fn, void *arg) +{ + list_node_init(&timer->node); + timer->fn = fn; + timer->arg = arg; +} + +unsigned long +timer_get_time(const struct timer *timer) +{ + unsigned long ticks; + + mutex_lock(&timer_mutex); + ticks = timer->ticks; + mutex_unlock(&timer_mutex); + + return ticks; +} + +void +timer_schedule(struct timer *timer, unsigned long ticks) +{ + struct timer *tmp; + uint32_t eflags; + + mutex_lock(&timer_mutex); + + assert(!timer_scheduled(timer)); + + timer->ticks = ticks; + + /* + * Find the insertion point, + * + * This makes timer scheduling an O(n) operation, and assumes a low + * number of timers. This is also why a mutex is used instead of + * disabling preemption, since preemption then remains enabled, + * allowing higher priority threads to run. + * + * [1] https://en.wikipedia.org/wiki/Big_O_notation + */ + list_for_each_entry(&timer_list, tmp, node) { + if (!timer_expired(tmp, ticks)) { + break; + } + } + + list_insert_before(&tmp->node, &timer->node); + + timer = list_first_entry(&timer_list, typeof(*timer), node); + + /* + * This interrupt-based critical section could be moved outside the + * mutex-based one, which would make the latter shorter. The downside + * of this approach is that a timer interrupt occurring after unlocking + * the mutex but before disabling interrupts will wake up the timer + * thread, if there was work pending already. The timer thread may + * preempt the current thread and process all timers before the current + * thread resumes and clears the list empty flag. At the next timer + * interrupt, the handler will determine that there is work pending and + * wake up the timer thread, despite the fact that there is actually no + * timer in the list. + * + * By holding the mutex while clearing the list empty flag, potential + * spurious wake-ups are completely avoided. + */ + eflags = cpu_intr_save(); + timer_list_empty = false; + timer_wakeup_ticks = timer->ticks; + cpu_intr_restore(eflags); + + mutex_unlock(&timer_mutex); +} + +void +timer_report_tick(void) +{ + timer_ticks++; + + if (timer_work_pending()) { + thread_wakeup(timer_thread); + } +} diff --git a/src/timer.h b/src/timer.h new file mode 100644 index 0000000..e4a531e --- /dev/null +++ b/src/timer.h @@ -0,0 +1,136 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * Software timer module. + */ + +#ifndef _TIMER_H +#define _TIMER_H + +#include <stdbool.h> + +#include <lib/list.h> + +/* + * Type for timer callback functions. + * + * These functions run in the context of the timer thread. + */ +typedef void (*timer_fn_t)(void *arg); + +struct timer { + struct list node; + unsigned long ticks; + timer_fn_t fn; + void *arg; +}; + +/* + * Check if a time, in ticks, is considered to have expired/occurred + * compared to a given reference time, also in ticks. + * + * A time is considered expired when it's strictly in the past compared + * to the given reference time, and occurred when it's expired or equal + * to the reference time. + */ +bool timer_ticks_expired(unsigned long ticks, unsigned long ref); +bool timer_ticks_occurred(unsigned long ticks, unsigned long ref); + +/* + * Initialize the timer module. + */ +void timer_setup(void); + +/* + * Return the current time, in ticks. + */ +unsigned long timer_now(void); + +/* + * Initialize a timer. + * + * A timer may only be safely initialized when not scheduled. + */ +void timer_init(struct timer *timer, timer_fn_t fn, void *arg); + +/* + * Schedule a timer. + * + * The timer callback function is called at or after the given scheduled + * (absolute) time, in ticks. If the scheduled time denotes the past, the + * timer function is called immediately. + * + * A timer may only be safely scheduled when not already scheduled. When + * a timer expires and its callback function runs, it is not considered + * scheduled any more, and may be safely rescheduled from within the + * callback function. This is how periodic timers are implemented. + * + * Note that a timer callback function never runs immediately at its + * scheduled time. The duration between the actual scheduled time and the + * time at which the timer callback function runs is called the latency. + * Ideally, this latency should be as short as possible and never exceed + * a maximum limit, i.e. be time-bounded. That's what real-time systems + * are about. Unfortunately, it's quite difficult to achieve most of the + * time. There are many sources of unexpected latency such as thread + * scheduling (if not using a real-time scheduling algorithm), priority + * inversions, other interrupts, cache/TLB misses, contention on the system + * bus (e.g. when the CPU and a DMA controller compete to become the bus + * master for a transfer), and memory (DDR SDRAM) access requests being + * reordered by the controller, to name the most common. + * + * Also note that, in addition to latency, another parameter that affects + * the processing of a timer is resolution. In this implementation, the + * timer is configured to raise interrupts at the thread scheduler + * frequency, normally 100 Hz, making the resolution 10ms, which is + * considered a low resolution. This means that a timer cannot be + * scheduled to trigger at times that aren't multiples of 10ms on the + * clock used by the timer system. Finally, note that when scheduling + * relative timers, unless stated otherwise, the time for the timer to + * trigger is less than the time requested. This is because the "current + * time" always marks the past. For example, with the 10ms resolution + * timer system used here, timer_now() could return 1000 when the "real" + * current time is actually 1000.9. Assuming the timer is scheduled to + * trigger at 1001, this means that, instead of waiting a complete tick, + * the timer would trigger only a tenth of the requested time after being + * scheduled. + * + * What this interface guarantees is that the function never runs before + * its scheduled time. + * + * Finally, for the sake of simplicity, this function doesn't provide a + * way to cancel a timer. + */ +void timer_schedule(struct timer *timer, unsigned long ticks); + +/* + * Return the scheduled time of a timer, in ticks. + */ +unsigned long timer_get_time(const struct timer *timer); + +/* + * Report a periodic tick to the timer module. + * + * This function is called by the hardware timer driver interrupt handler. + */ +void timer_report_tick(void); + +#endif /* _TIMER_H */ diff --git a/src/uart.c b/src/uart.c new file mode 100644 index 0000000..eed7fe4 --- /dev/null +++ b/src/uart.c @@ -0,0 +1,190 @@ +/* + * Copyright (c) 2017 Richard Braun. + * Copyright (c) 2017 Jerko Lenstra. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <assert.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> + +#include <lib/cbuf.h> +#include <lib/macros.h> + +#include "cpu.h" +#include "error.h" +#include "io.h" +#include "uart.h" +#include "thread.h" + +#define UART_BAUD_RATE 115200 + +#define UART_CLOCK 115200 +#define UART_DIVISOR (UART_CLOCK / UART_BAUD_RATE) + +#define UART_IRQ 4 + +#define UART_IER_DATA 0x1 + +#define UART_LCR_8BITS 0x3 +#define UART_LCR_STOP1 0 +#define UART_LCR_PARITY_NONE 0 +#define UART_LCR_DLAB 0x80 + +#define UART_LSR_DATA_READY 0x01 +#define UART_LSR_TX_EMPTY 0x20 + +#define UART_COM1_PORT 0x3F8 +#define UART_REG_DAT 0 +#define UART_REG_DIVL 0 +#define UART_REG_IER 1 +#define UART_REG_DIVH 1 +#define UART_REG_LCR 3 +#define UART_REG_LSR 5 + +#define UART_BUFFER_SIZE 16 + +#if !ISP2(UART_BUFFER_SIZE) +#error "invalid buffer size" +#endif + +/* + * Data shared between threads and the interrupt handler. + * + * Interrupts and preemption must be disabled when accessing these data. + */ +static uint8_t uart_buffer[UART_BUFFER_SIZE]; +static struct cbuf uart_cbuf; +static struct thread *uart_waiter; + +static void +uart_irq_handler(void *arg) +{ + uint8_t byte; + int error; + bool spurious; + + (void)arg; + + spurious = true; + + for (;;) { + byte = io_read(UART_COM1_PORT + UART_REG_LSR); + + if (!(byte & UART_LSR_DATA_READY)) { + break; + } + + spurious = false; + byte = io_read(UART_COM1_PORT + UART_REG_DAT); + error = cbuf_pushb(&uart_cbuf, byte, false); + + if (error) { + printf("uart: error: buffer full\n"); + break; + } + } + + if (!spurious) { + thread_wakeup(uart_waiter); + } +} + +void +uart_setup(void) +{ + cbuf_init(&uart_cbuf, uart_buffer, sizeof(uart_buffer)); + + io_write(UART_COM1_PORT + UART_REG_LCR, UART_LCR_DLAB); + io_write(UART_COM1_PORT + UART_REG_DIVL, UART_DIVISOR); + io_write(UART_COM1_PORT + UART_REG_DIVH, UART_DIVISOR >> 8); + io_write(UART_COM1_PORT + UART_REG_LCR, UART_LCR_8BITS | UART_LCR_STOP1 + | UART_LCR_PARITY_NONE); + io_write(UART_COM1_PORT + UART_REG_IER, UART_IER_DATA); + + cpu_irq_register(UART_IRQ, uart_irq_handler, NULL); +} + +static void +uart_tx_wait(void) +{ + uint8_t byte; + + for (;;) { + byte = io_read(UART_COM1_PORT + UART_REG_LSR); + + if (byte & UART_LSR_TX_EMPTY) { + break; + } + } +} + +static void +uart_write_byte(uint8_t byte) +{ + uart_tx_wait(); + io_write(UART_COM1_PORT + UART_REG_DAT, byte); +} + +void +uart_write(uint8_t byte) +{ + if (byte == '\n') { + uart_write_byte('\r'); + } + + uart_write_byte(byte); +} + +int +uart_read(uint8_t *byte) +{ + int eflags, error; + + thread_preempt_disable(); + eflags = cpu_intr_save(); + + if (uart_waiter) { + error = ERROR_BUSY; + goto out; + } + + for (;;) { + error = cbuf_popb(&uart_cbuf, byte); + + if (!error) { + break; + } + + uart_waiter = thread_self(); + thread_sleep(); + uart_waiter = NULL; + } + + error = 0; + +out: + cpu_intr_restore(eflags); + thread_preempt_enable(); + + return error; +} diff --git a/src/uart.h b/src/uart.h new file mode 100644 index 0000000..0dd2864 --- /dev/null +++ b/src/uart.h @@ -0,0 +1,61 @@ +/* + * Copyright (c) 2017 Richard Braun. + * Copyright (c) 2017 Jerko Lenstra. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * + * UART driver. + * + * An UART is a Universal Asynchronous Receiver-Transmitter, an old, low level + * interface used for machine communication. It's typically used on embedded + * devices as the primary diagnostic interface, especially during development. + * It may also be used between remote boards that don't require fast + * communication. + */ + +#ifndef _UART_H +#define _UART_H + +#include <stdint.h> + +/* + * Initialize the uart module. + */ +void uart_setup(void); + +/* + * Write a byte to the UART. + */ +void uart_write(uint8_t byte); + +/* + * Read a byte from the UART. + * + * This function may only be called from thread context, since it blocks + * until there is data to consume. + * + * If successful, return 0. If another thread is already waiting for data, + * ERROR_BUSY is returned. + * + * Preemption must be enabled when calling this function. + */ +int uart_read(uint8_t *byte); + +#endif /* _UART_H */ |