[OSy] First extended assignment
Vojtech Horky
horky at d3s.mff.cuni.cz
Wed Oct 10 17:18:49 CEST 2018
Dear all,
please see attached the assignment of the 1st extended semestral task of
the Operating Systems course. This extended assignment is intended for
those who want to solve the task independently at home in order to gain
the "conditionally fulfilled" status for this topic.
However, please read and try to understand the text of the extended
assignment even if you plan to attend the labs (schedule is on the web
and from now on respects the regular timetable). The assignment for the
labs will be related to the extended assignment (the topic will be
memory management, too) and also the required knowledge and recommended
literature will be the same.
If you choose to implement the extended assignment, please respect the
deadline of November 1st 2018 AoE.
Please send your implementation via e-mail to the following address:
nswi004 at d3s.mff.cuni.cz
You should send your implementation as an archive (zip, tar.bz2, etc.)
in the attachment of the e-mail. Please make sure to include everything
necessary to run your implementation, to run the required unit tests and
to evaluate your source code. You can also use the `make dist' target
from the main Makefile to package your solution.
We will try to evaluate your submissions as they arrive, but we cannot
guarantee a specific reply latency. Therefore please avoid (in your own
interest) sending your implementation at the last moment, because we
might not be able to point you in time to some small issues in order for
you to fix them.
If you should have any questions (either specific to the assignment or
of a generic nature), please do not hesitate to send your query to this
mailing list.
Best regards,
- Vojtech Horky
-------------- next part --------------
========================================================================
Operating Systems Course
Semestral Task
Topic no. 1: Memory Management
Extended Assignment
========================================================================
Date of assignment: October 10th 2018
Submission deadline: November 1st 2018
------------------------------------------------------------------------
The goal of the 1st semestral task is to implement the functionality
of the kernel physical memory manager. The task is defined by a
functional programming interface that needs to be implemented and it
is accompanied by a set of unit tests that the implementation must
successfully pass.
Use the source code of Kalisto version 0.9.12 as the basis for your
implementation. i.e. start with the source code of Kalisto and extend
it by the required functionality. Kalisto 0.9.12 is available for
download from the following URL:
http://d3s.mff.cuni.cz/osy/download/kalisto-0.9.12.tar.bz2
If the assignment does not define an aspect of the required
implementation specifically or precisely, then the expected behavior
of the implementation is defined by the unit tests. If even the tests
do not define an aspect of the required implementation specifically or
precisely, then use your best knowledge and professional judgement to
implement the functionality in the most reasonable way and document
your decisions using comments in your source code.
Virtual Address Space of the MIPS R4000 CPU ----------------------------
Depending on the current privilege mode of the MIPS R4000 CPU (user,
supervisor, kernel), the 32-bit virtual address space is divided into
several possible sets of segments. These segments are hard-wired on
the MIPS R4000 CPU and their general properties cannot be altered by
software. The virtual addresses are mapped to physical addresses
either in a predefined manner (such is the case of the KSEG0 and KSEG1
segments; see below) or the mapping is configurable by the operating
system by means of altering the Translation Lookaside Buffer (TLB).
In user mode, only the USEG segment is available, with the virtual
address range of [0x00000000, 0x800000000). The USEG virtual addresses
are mapped to physical addresses via the TLB. Every memory access
outside the USEG memory range in user mode causes the Address Error
exception.
In supervisor mode, the following two segments are available:
* SUSEG, with the virtual address range of [0x00000000, 0x80000000)
* SSEG, with the virtual address range of [0xC0000000, 0xE0000000)
The SUSEG and SSEG virtual addresses are mapped to physical addresses
via the TLB. The SUSEG segment is an analogy of the USEG segment in
user mode. Every memory access outside the SUSEG and SSEG memory
ranges in supervisor mode causes the Address Error exception.
Finally, in kernel mode, the following five segments are available:
* KUSEG, with the virtual address range of [0x00000000, 0x80000000)
* KSEG0, with the virtual address range of [0x80000000, 0xA0000000)
* KSEG1, with the virtual address range of [0xA0000000, 0xC0000000)
* KSSEG, with the virtual address range of [0xC0000000, 0xE0000000)
* KSEG3, with the virtual address range of [0xE0000000, 0xFFFFFFFF]
The KSSEG segment is alternatively labeled as KSEG2.
The virtual addresses from the KUSEG, KSSEG and KSEG3 segments are
mapped to physical addresses via the TLB. The KUSEG segment is an
analogy of the USEG segment in user mode and the KSSEG is an analogy
of the SSEG segment in supervisor mode.
The virtual addresses from the KSEG0 and KSEG1 segments are mapped to
physical addresses using a hard-wired identity mapping by subtracting
the base address of the segment, i.e. both the virtual addresses
0x80000000 and 0xA0000000 are mapped to the same physical address
0x00000000. In other words, the virtual address ranges of the KSEG0
and KSEG1 segments are mapped to the physical address range of
[0x00000000, 0x20000000).
On the actual MIPS R4000 CPU the memory accesses in the KSEG1 segment
bypass the CPU cache.
General Recommendations for the Implementation -------------------------
The following recommendations capture the usual criteria of quality of
source code that is generally expected in critical system-level
software. While respecting these recommendations is slightly less
binding than the functional requirements of the assignment, severely
violating them might still lead to rejection of your implementation.
- Avoid using non-trivial hard-wired numerical constants in the source
code. Use properly named reusable macros.
- Use empty lines and block comments as visual delimiters to
consistently demark logical parts of the source code.
- Use consistent horizontal spacing to improve the readability and
comprehension of the source code. This includes both spaces in
expressions and proper indentation.
- Avoid creating overly long functions, functions with an excessive
level of block nesting and functions that implement an excessive
number of distinct logical operations. The function name should
adequately capture the summary of the function logical operation.
- Avoid creating source files that mix logically unrelated concerns or
functionality. Avoid placing source files into unrelated
directories.
- Use properly named macros or inline functions as replacements for
complex logical and arithmetic expressions.
- Use a consistent coding style (similar constructs should use similar
means). Match the coding style of the new code with the coding style
of the existing code.
- Use English for identifiers and comments. Use a consistent way of
naming things and a consistent way of commenting.
Task Assignment --------------------------------------------------------
Implement the kernel frame allocator. The purpose of the frame
allocator is the bookkeeping of frames (physical pages), i.e. managing
which parts of the physical memory are used and which parts are
available for allocation.
The size and alignment of the frames should be chosen so that the
frames could be easily mapped to virtual pages using the virtual
memory management mechanisms of the MIPS R4000 CPU (i.e. a frame size
of 4 KiB and a natural alignment is a sensible choice).
Implement a data structure for the bookkeeping of the frames. The data
structure should provide reasonable time and space complexity of the
most common operations (i.e. testing whether a consecutive sequence of
frames is used or available, updating the state of a consecutive
sequence of frames and looking up a consecutive sequence of available
frames). It is possible to provide a source reimplementation of the
binary implementation of the bitmap data structure from Kalisto
(kernel/adt/bitmap.{obj|h}), but it is not necessary to keep this API
and it is even possible to provide an original implementation of a
completely different data structure.
The implementation of the frame allocator can take the liberty of
using the following simplifying assumptions:
* There is only a single continuous block of usable physical memory
starting at the physical address 0x00000000.
* The size of the continuous block of usable physical memory is a
multiple of 4 KiB.
* The entire continuous block of usable physical memory is accessible
via the KSEG0 and KSEG1 segments of the virtual address space (i.e.
it is smaller than 512 MiB).
The frame allocator is required to implement the following API:
* void frame_init(void)
This function initializes the data structures of the frame
allocator. It is called from the bsp_main() function of the kernel
that initializes the kernel on the bootstrap CPU. One of the
suggested operations of this function is to scan the physical memory
to determine the usable frames. The _kernel_end symbol might be
helpful in avoiding the code and static data of the kernel.
* int frame_alloc(uintptr_t *paddr, const size_t cnt,
const vm_flags_t flags)
This function looks up a consecutive sequence available frames with
the length of @cnt and marks them as used. If the lookup is
successful, the function returns EOK. If @cnt equals to 0 or if the
lookup is unsuccessful, the function returns ENOMEM.
Depending on the bit flags in the @flags argument, the function
either looks for any suitable continuous block of frames and returns
the starting physical address of such block in the @paddr output
argument (if @flags contains the VF_VA_AUTO flag), or it merely
checks whether there is a suitable continuous block of frames at the
physical address specified by the caller in the @paddr argument (if
@flags contains the VF_VA_USER flag). If the user-defined value in
@paddr is not properly aligned, the function return EINVAL.
Other possible flags in @flags (VF_AT_KSEG0, VF_AT_KSEG1, etc.) can
be ignored as they are defined for future extensions.
A physical frame is considered available only if it is indeed
possible to use the frame for storing arbitrary data by the caller,
without corrupting any other essential data. Thus the code and
static data of the kernel, memory used internally by the frame
allocator, as well as frames allocated by previous calls of
frame_alloc() and not released yet are not considered available.
* int frame_free(const uintptr_t paddr, const size_t cnt)
This function checks whether the continuous block of frames starting
at the physical address @paddr and with the length of @cnt frames is
marked as used by previous call(s) of frame_alloc(). If this is the
case, then this function releases the block of frames (marks them as
available) and returns EOK.
If @cnt equals to 0, if @paddr is not properly aligned or if any of
the frames defined by @paddr and @cnt was not previously allocated
by a call of frame_alloc(), then this function returns EINVAL. It is
thus not possible to release frames containing the kernel code or
static data, memory used internally by the frame allocator, etc.
It is permitted to use a single call of frame_alloc() to allocate
a block of frames and later use one or multiple calls of
frame_free() to release disjoint sub-blocks of the original block.
It is also permitted to call frame_alloc() multiple times in a way
to allocate a larger continuous super-block of frames and later call
frame_free() to release the entire super-block (or any sub-block of
this super-block).
Unit Tests -------------------------------------------------------------
The unit tests that validate the functionality of the implementation
can be found in the kernel/tests/mm subtree of the source tree of
Kalisto 0.9.12. The infrastructure for running and evaluating the
tests can be executed using the tests-mm.sh shell script. Your
implementation must successfully pass all the supplied tests in a
non-trivial way (i.e. the frame allocator must actually allocate some
memory, it must not leak memory, the tests must finish in a reasonable
time, etc.). Modification of the internal logic of the tests is
forbidden.
The amount of configured physical memory can be randomly altered
(in a way respecting the simplifying assumptions of this assignment)
in order to stress-test your implementation.
Delete the original binary implementation of the frame allocator
(kernel/mm/falloc.obj) and possibly the original binary implementation
of the bitmap data structure (kernel/adt/bitmap.obj) from the source
tree of Kalisto to make sure that the tests validate your original
implementation.
To integrate your implementation with the tests, add necessary
#include directives to the kernel/api.h header file to make sure
all required declarations are available for the tests.
Recommended Literature -------------------------------------------------
[1] Operating Systems Course study material, Chapter 3. Memory
Management, http://d3s.mff.cuni.cz/~ceres/sch/osy/text/ch03.html
[2] Wikipedia: Memory management,
https://en.wikipedia.org/wiki/Memory_management
[3] OSDev Wiki: Page Frame Allocation,
http://wiki.osdev.org/Page_Frame_Allocation
More information about the NSWI004
mailing list