[OSy] Assignment of the 1st semestral task

Martin Decky decky at d3s.mff.cuni.cz
Thu Oct 27 11:04:43 CEST 2016


Dear colleagues,

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 on October 31st or 
November 7th. 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 10th 2016 (meaning that you should deliver your 
implementation no later than this day).

Please send your implementation via email to the following email address:

   nswi004 at d3s.mff.cuni.cz

You should send your implementation as an archive (zip, tar.bz2, etc.) 
in the attachment of the email. Please make sure to include everything 
necessary to run your implementation, to run the required unit tests and 
to evaluate your source code.

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

Martin Decky
-------------- next part --------------
========================================================================
                        Operating Systems Course
                             Semestral Task

                     Topic no. 1: Memory Management
                           Extended Assignment
========================================================================
Date of assignment:  October  27th 2016
Submission deadline: November 10th 2016
------------------------------------------------------------------------

  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.10 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.10 is available for
  download from the following URL:

    http://d3s.mff.cuni.cz/osy/download/kalisto-0.9.10.tar.bz2

  If the assignment does not define an aspect of the required
  implementation specifically or precisely, 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, 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_ini(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(void **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 void *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.10. 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