CSE 422S: Studio 11

Kernel Memory Management


"This is not to say that, from a programmer's point of view, kernel memory allocations are difficult -- just different."

—Robert Love, Linux Kernel Development, 3rd Ed., Chapter 12, pp. 231

The Linux kernel offers several approaches to memory management, including a variety of memory allocation and deallocation facilities for use in kernel space, which offer different trade-offs between memory utilization and performance, as well as different guarantees on physical contiguity. In today's studio you will explore physical memory allocation via the page allocator, and will modify the contents of these pages via the kernel's virtual memory mapping.

In this studio, you will:

  1. Allocate and deallocate memory for different numbers of objects, using the kernel-level page allocator.
  2. Use address translation structures to manipulate the memory allocated via the kernel-level page allocator.

Please complete the required exercises below, as well as any optional enrichment exercises that you wish to complete. We encourage you to please work in groups of 2 or 3 people on each studio (and the groups are allowed to change from studio to studio) though if you would prefer to complete any studio by yourself that is allowed.

As you work through these exercises, please record your answers, and when you finish them each and every person who worked on them should please log into Canvas, select this course in this semester, and then upload a file containing them and also upload any other files the assignment asks for, and submit those files for this studio assignment (there should be a separate submission from each person who worked together on them).

Make sure that the name of each person who worked on these exercises is listed in the first answer, and make sure you number each of your responses so it is easy to match your responses with each exercise.


Required Exercises

  1. As the answer to the first exercise, list the names of the people who worked together on this studio.

  2. Download the following existing kernel module framework and Makefile onto the Linux lab machine where you have built your kernel modules for previous studios. Modify the Makefile to point to the location of the Linux source tree in your directories on that machine.

    The module takes a single unsigned integer parameter, which can be specified as an argument to insmod:

    sudo insmod kernel_memory.ko nr_structs=some value

    The value defaults to 2,000 if no value is provided for it. See the discussion of module parameters on pp. 346 in LKD, chapter 17 for more information. The module's initialization function also creates a single kernel thread that simply outputs a message to the system log with the value of the module parameter.

    Compile your module (don't forget to say module add raspberry), choose any positive value for nr_structs and load the module on your Raspberry Pi and check that the message appears in the system log. Note that this initial compilation will likely have a warning due to a function that you're not using now but will later in this studio - for now you can ignore that warning since we'll be using the function later.

    Now, inside your module, declare a struct type that contains an array of 8 unsigned integers, as in:

    #define ARR_SIZE 8
    typedef struct datatype_t {
        unsigned int array[ARR_SIZE];
    } datatype;

    In your module's thread function, print a second message to the system log that prints:

    Recompile your module and load it on your Raspberry Pi, and as the answer to this exercise, show 'dmesg' traces that print out these values.

  3. Recall the discussion from today's LKD reading (Ch. 12) on kernel-level page allocation. The core page allocation routine, as discussed on LKD pp. 235, is:

    struct page * alloc_pages(gfp_t gfp_mask, unsigned int order);

    This routine returns a pointer to an array of 2^{order} pages of physical memory. As discussed in the text, the kernel does not allow you to allocate arbitrary numbers of contiguous pages, but restricts you to allocations based on a construct called the order, which is the base 2 logarithm of the number of pages you wish to allocate. So, if you want to allocate 16 pages, the order of the allocation would be log2(16)=4.

    Inside your kernel thread function, you are going to allocate memory that can hold the the user-configurable number (nr_structs) of datatype structs. To do so, you will need to use the alloc_pages function (passing GFP_KERNEL as the first argument), and so you must calculate the following information:

    1. The kernel page size (use the PAGE_SIZE kernel macro)
    2. The number of struct elements that will fit in one page
    3. Based on this calculation, the number of pages you need to allocate to hold nr_structs (recall how integer division works -- you will need to use the modulo operator)
    4. Based on this calculation, the order that you should pass to the page allocator

    Note that the module already implements a function my_get_order that takes a single integer argument, nr_pages, and returns the order that must be set to the base 2 logarithm of the next power of 2 equal to or above nr_pages. You do not need to modify this function, but should understand how it works. Consider the following points:

    Once you understand how this function operates, modify your module to include three new static unsigned int variables, nr_pages, order, and nr_structs_per_page that your kernel thread function should calculate based on the user-specified nr_structs. Modify your kernel thread to print out the value of these three variables.

    Recompile your module and load it on your Raspberry Pi, and as the answer to this exercise, explain what the function my_get_order does, and show the relevant output in 'dmesg' output when the module is loaded with 1000, 2000, and 4000 as nr_structs

  4. Now, we are going to use the the alloc_pages function to allocate enough memory pages to contain the number of structs given in the module parameter - i.e., the smallest power of 2 that would be sufficient based on your calculation of the number of objects per page in the previous exercise.

    Recall that the return value from alloc_pages is a pointer to an array of struct page, which is of size 2^{order} total pages. We are now going to iterate through this memory and use address translation and pointer arithmetic to initialize the contents of memory with values in the array field of the datatype type. First, declare another global static variable static struct page * pages;, and in the thread function set pages to the return value of alloc_pages. Make sure this function succeeds by checking the return value for NULL.

    Because code must always access memory via its virtual address, and we currently only have struct page * to identify the memory, we must perform the following operations before accessing the memory:

    You will need to use the following translation functions/macros to accomplish this:

    Once you have a pointer via __va(), you are ready to access the memory that you allocated. For example, to access the first datatype struct in first page of the allocated memory, declare the following pointer variable in your module:

    static struct datatype_t * dt;

    and then say:

    dt = (struct datatype_t *)__va(....);

    At this point it's a good idea to build your module, and fix any warnings or errors before proceeding.

    Now, we are going to have your module's thread function iterate through each struct in each physical memory page and set each integer value to a specific number, according to the following pseudo-code:

    for (i = 0; i < nr_pages; i++) {
        unsigned long cur_page = physical address of the allocated memory + the offset to the ith page
        for (j = 0; j < nr_structs_per_page; j++) {
            unsigned long cur_struct = cur_page + offset to jth struct
            datatype_t * this_struct = convert physical address in cur_struct to a virtual address
            for (k = 0; k < ARR_SIZE; k++) {
                this_struct->array[k] = i*nr_structs_per_page*ARR_SIZE + j*ARR_SIZE + k;
            }
        }
    }

    Finally, also modify the inner k loop to print out the value of every element for which both j=0 and k=0. Compile and then load and unload your module on your Raspberry Pi with the value of 200 and as the answer to this exercise please show the values printed in dmesg.

  5. First, remove the print statements from the body of the kernel thread once you have captured the output for the previous exercise.

    The final step of this studio is to perform the same operations in the 3-dimensional nested loop above, but in the module teardown function. After invoking kthread_stop() to break the kernel thread out of its schedule() loop, perform the same address translation steps as in the thread function. In the body of the inner k loop, simply ensure that each value matches its expected value with a check like:

    if (this_struct->array[k] != (i*nr_structs_per_page*ARR_SIZE + j*ARR_SIZE + k)) {
        print error message
    }

    Now, after the loop, invoke __free_pages(struct page *, unsigned int order); to free the pages allocated by the kernel thread. If all values match their expected values, print out a success message.

    As the answer to this exercise, run your program with values of 1,000, 10,000, and 50,000, and show the output in 'dmesg', which should just be statements showing the values of global variables and a success statement on module unload.

Things to turn in


Page updated Monday, August 10, 2020, by Chris Gill