Linux kernel series: HIGHMEM

This is the second post in the Linux kernel series. The first part of the series was about memblock. This week, the topic is HIGHMEM.

What is HIGHMEM?

The Linux kernel virtualizes its memory. Virtual memory addresses, which can be used by programs, are mapped to physical memory addresses. When the size of the physical memory exceeds the (maximum) size of the virtual memory, it is not possible for the kernel to map every physical address to a virtual address. So the kernel uses temporary mappings when it wants to access part of the physical memory that is not mapped to a permanent virtual memory address. The part of physical memory that does not have a permanent mapping to a virtual address is called high memory (HIGHMEM).[1]

HIGHMEM is often needed in 32 bit systems. A 32 bit address can represent at most 232 = 4,294,967,296 different addresses, which is approximately 4 GB (or exactly 4 GiB). But many systems have more than 4 GB of physical memory.

The available virtual memory space has to be divided between kernel space and user space. A common split is 3 : 1 user space : kernel space, which would mean 3 GB for user space and 1 GB for kernel space on a 32 bit system. The part of kernel space that has a direct mapping to a permanent physical memory is called LOWMEM. LOWMEM is contiguously mapped in physical memory.[2]

Creating Temporary Maps

There are several different functions for creating temporary virtual maps.[2]

vmap() : used to map multiple physical pages into a contiguous virtual address space for a long duration
kmap() : used to map a single physical page for a short duration. Prone to deadlocks when nested, and not recommended in new code
kmap_atomic() : used to map a single physical page for a very short duration. It performs well because it is restricted to the CPU that issued it, but the issuing task must stay on the same CPU until it finishes.
kmap_local_page() : recently developed as a replacement for kmap(). It creates a mapping that is restricted to local use by a single thread of execution. This function is preferred over the other functions and should be used when possible.[3]

References

  1. High Memory Handling — The Linux Kernel documentation
  2. Memory Mapping — The Linux Kernel documentation
  3. LKML Mailing List

Linux kernel series: memblock

This post is the first in a series in which I discuss the basics of a component or concept in the Linux kernel. The goal is to explain it in such a way that a beginner C or C++ programmer unfamiliar with the Linux kernel can comprehend it. There will be at least 2 posts in this series, including this one.

This week, the topic is memblock.

What is memblock?

When programming in kernel space, you cannot use the C standard library memory allocation functions available in user space, such as malloc, free, calloc, realloc, or reallocarray.[1] There are kernel space equivalents, such as kmalloc or kzalloc, kfree, kcalloc, krealloc_array, krealloc,[2] and more. However, these memory allocators are set up during the booting process. In the period of time before these allocators are available, the system still needs to allocate memory. During that period of time, a specialized allocator called memblock is used to allocate memory.[3]

memblock views the system memory as a collection of contiguous regions. memblock is made up of memblock types, which are themselves made up of multiple memory regions. There are several structures and functions for working with memblock.[4]

Structures

struct memblock

The struct memblock wraps the metadata for the memory and reserved memblock types, along with current_limit, the physical address of the current allocation limit, and bottom_up, the allocation direction. The allocation limit limits allocations to memory that is currently accessible and can be set with memblock_set_current_limit(phys_addr_t limit). The memblock structure is statically initialized at build time.

[5]
struct memblock {
	bool bottom_up;
	phys_addr_t current_limit;
	struct memblock_type memory;
	struct memblock_type reserved;
};

struct memblock_type

An array of several memory regions of the same type can be represented with struct memblock_type. This struct defines an array of memory regions regions of type name with cnt number of regions. The total size of the array is max, and the size of all the regions is total_size.

[5]
struct memblock_type {
	unsigned long cnt;
	unsigned long max;
	phys_addr_t total_size;
	struct memblock_region *regions;
	char *name;
};

The memory region types are memory, reserved, and physmem.

  • memory is the physical memory available to the kernel.
  • reserved refers to the regions that were actually allocated.
  • physmem is the total physical memory available during boot regardless of whether the kernel can access it. It is not available on some architectures.

struct memblock_region

The struct memblock_region represents a memory region with base address base, size size, memory region attributes flags, and NUMA node id nid. NUMA is a system with non-uniform memory access.

[5]
struct memblock_region {
	phys_addr_t base;
	phys_addr_t size;
	enum memblock_flags flags;
#ifdef CONFIG_NUMA
	int nid;
#endif
};

The memory region attributes are defined in enum memblock_flags.

[5]
enum memblock_flags {
	MEMBLOCK_NONE		= 0x0,	/* No special request */
	MEMBLOCK_HOTPLUG	= 0x1,	/* hotpluggable region */
	MEMBLOCK_MIRROR		= 0x2,	/* mirrored region */
	MEMBLOCK_NOMAP		= 0x4,	/* don't add to kernel direct mapping */
	MEMBLOCK_DRIVER_MANAGED = 0x8,	/* always detected via a driver */
};

Functions

memblock is initialized in setup_arch() and taken down in mem_init().

memblock has many useful APIs. These APIs include functions for adding and removing memory regions, and allocating and freeing memory, among many other functions.

Adding and removing

These functions add or remove a memblock region with the given base address and size. They return an int indicating whether the operation succeeded. The memblock_add_node() version adds the region within a NUMA node and includes parameters for the node id and memblock flags.

memblock_add(base, size)memblock_add_node(base, size, nid, flags)
memblock_remove(base, size)

Allocating

These functions allocate a memory block and return the physical address of the memory.

memblock_phys_alloc(size, align)
memblock_phys_alloc_range(size, align, start, end)
memblock_phys_alloc_try_nid(size, align, nid)

These functions allocate a memory block and return the virtual address of the memory.

memblock_alloc(size, align)
memblock_alloc_from(size, align, min_addr)
memblock_alloc_low(size, align)
memblock_alloc_node(size, align, nid)

Freeing

The functions memblock_free() and memblock_phys_free() free a boot memory block that was previously allocated; it is not released to the buddy allocator (which handles allocation after boot process completes). The *ptr parameter in memblock_free() is the starting address of the boot memory block. The functions memblock_free_all() and memblock_free_late() free pages to the buddy allocator.

memblock_free(*ptr, size)
memblock_phys_free(base, size)
memblock_free_all(void)
memblock_free_late(base, size)

References

  1. malloc(3) — Linux manual page
  2. Memory Management APIs — The Linux Kernel documentation
  3. Boot time memory management — The Linux Kernel documentation
  4. Boot time memory management — The Linux Kernel documentation: Functions and structures
  5. Code snippet from linux/memblock.h

Building an 8080 Emulator: Planning

My Capstone project this term is Build an Emulator and Run Space Invaders ROM. I will be working with a team of three other students. I am excited about working on this project because I am interested in low-level programming and old-school video games. Most of the code will be written in C (my favorite programming language!), but 8080 assembly code will also be used.

The program will take a ROM file as input. Currently, we are planning to target the Space Invaders ROM, but we may test with other ROM files if time allows. Since my group includes both Linux and Windows users, the program will be compatible with Linux and Windows. As an extension, we may develop for compatibility with other platforms, such as mobile.

Building the Disassembler

The first step will be to build a disassembler that will read hexadecimal data from the ROM file and print out the corresponding 8080 assembly instruction. There are 256 instructions, corresponding to opcodes 0x00 through 0xff. Thus, the implementation will likely involve a really long switch statement. For example, this snippet from emulator 101:

	switch (*code) {    
	case 0x00: 
		printf("NOP"); break;    
	case 0x01: 
		printf("LXI    B,#$%02x%02x", code[2], code[1]);
		opbytes=3; break;    

Memory Map

The Intel 8080 CPU has 16 address pins, so it uses 16 bit addresses (0000 through ffff). The memory map for Space Invaders tells us what each address is used for.

0000-1FFF 8K ROM
2000-23FF 1K RAM
2400-3FFF 7K Video RAM
4000- RAM mirror

Implementing Opcodes

The next step will be to implement the instructions. We will create data structures to store info about the current state of the registers and the values of the FLAGS. The Intel 8080 CPU has seven 8-bit registers (A, B, C, D, E, H, and L) as well as the 16-bit registers for the stack pointer (SP), program counter (PC), and status register (FLAGS).

The program will modify the state (stored in the data structures) according to what effect that instruction would actually have on the registers in the 8080.

Emulating the Rest of the Hardware

We will need to emulate the rest of the hardware in the Space Invaders machine to actually see and play the game. This includes interrupts, graphics, buttons, and sounds. We will also need to emulate the speed of the 8080 processor, which has a CPU clock rate of 2 Mhz.

From Windows-only user to Linux kernel programmer

Until 2014, I was a Windows user who liked the idea of Linux but believed that it was too complicated for me to install and use. I didn’t consider myself a programmer or particularly tech-savvy. Today, I contributed my fourth clean-up patch to the Linux kernel. Additionally, I am less than three months away from graduating with a BS in Computer Science, and I am very confident in my technical abilities.

Finding my passion

My first degree was a BS in Chemical Engineering from the University of Texas at Austin. After I graduated, I began a doctoral program in Chemical Engineering at the University of California at Davis. I dropped out after the first quarter when I realized what I had suspected during my undergraduate degree: that I was not very passionate about the subject.

I then embarked on a search for my “passion”. I tried many different things that didn’t quite work out. Then, I decided to try web development and Android app development. I took some courses on Udemy and checked out programming books from the library. When I started learning to program, it immediately clicked. Somehow I just knew that Computer Science was that long sought-after “passion”.

Embracing Linux

In 2014, I met my current partner, who convinced me that Linux was awesome and installed Ubuntu on my six-year-old Dell laptop. I eventually learned how to install Linux on my own (and bought a new computer!). Ironically, at UT, I had dated a Linux-obsessed Computer Science major, who may have offered to do this but should have been more pushy about it!

After I learned more about programming and Linux, I wanted to contribute to open source projects, but I was having trouble getting started. I would read through the documentation for open source projects but then feel too intimidated to get involved.

One day, I was looking at the New contributors task list for a Wikimedia project, and I noticed that someone had posted a comment asking if a particular task could be used for Outreachy. I hadn’t heard of that before. When I looked into it, I realized that it was the perfect opportunity for me.

Outreachy

Outreachy is an internship program in which interns work on open source and open science projects. Outreachy seeks to increase diversity in open source communities:

Outreachy provides internships to people subject to systemic bias and impacted by underrepresentation in the technical industry where they are living.

https://www.outreachy.org/

The internship is remote and lasts three months. Interns work 30 hours per week and are paid a $7,000 stipend. Interns also work with a mentor. Unlike most internships, applicants aren’t required to be enrolled in school. So, I could do it after I graduate.

Contributing

I applied, and my initial application was approved! Now I am in the contribution period, in which applicants make contributions to one or more projects. I was immediately drawn to the Linux kernel projects. The set up was a bit extensive and included building the kernel from source, but it was much more approachable than trying to do it on my own. Even if I am not selected for an internship, I will be grateful that I was able to participate in the contribution period.