Kernel Structure and Infrastructure David Ferry, Chris Gill,

Kernel Structure and Infrastructure David Ferry, Chris Gill,

Kernel Structure and Infrastructure David Ferry, Chris Gill, Brian Kocoloski CSE 422S - Operating Systems Organization Washington University in St. Louis St. Louis, MO 63130 1 Kernel vs. Application Coding What are some of the differences? CSE 422S Operating Systems Organization 2 Kernel vs. Application Coding

What are some of the differences? What happens when a user space program executes: printf(Hello world\n); int * array = malloc(sizeof(int) * 10); CSE 422S Operating Systems Organization 3 Kernel vs. Application Coding What are some of the differences? What happens when a user space program executes: printf(Hello world\n); int * array = malloc(sizeof(int) * 10);

About how large would you expect a hello world program to be? CSE 422S Operating Systems Organization 4 Kernel vs. Application Coding Two major differences: The core kernel has no standard libraries The core kernel must be a monolithic, statically linked library No standard libraries: No libc (malloc, pthreads, string handling, etc.) Partly because of chicken/egg situation Also, standard libraries can be too slow

No dynamic loading of shared libraries for the core kernel CSE 422S Operating Systems Organization 5 Two Big Problems 1. A totally static kernel would be enormous About 20 million lines of code in 2015 Most of this is hardware drivers that are never used on any given platform 2. Programmers rely on library functions for efficiency and correctness E.g., things like data structures, sleeping routines, etc. What libraries to use? (hint: not glibc) Kernel code has to be entirely self-contained

Also, chicken+egg problem, as glibc functions may in turn invoke the kernel via system calls CSE 422S Operating Systems Organization 6 First Solution: Loadable Kernel Modules Kernel modules are kernel code that can be loaded dynamically: Can be loaded/unloaded whenever Runs in kernel mode Can access exported kernel variables and functions Can export variables and functions to kernel or other modules

CSE 422S Operating Systems Organization 7 Why Kernel Modules Linux is a monolithic kernel. All functionality is compiled into the same static binary that is loaded into memory on boot. Without modules, the entire kernel would need to be loaded into memory to boot a node. Problems? Waste of memory (embedded systems) Slower boot time Larger trusted computing base (TCB), more room for bugs CSE 422S Operating Systems Organization

8 What are Kernel Modules used for? What pieces of code do we think might not be needed on every system that the kernel boots on? 1. Device Drivers 2. Architecture-specific code Lines of code (just .c files) for: 1. Device Drivers: 1,583,159 2. Everything else: 1,003,777 (Includes all of the architectures that were not using!) CSE 422S Operating Systems Organization 9

What are Kernel Modules used for? Beyond space savings, what else might modules be useful for? 1. Out-of-tree functionality that is not accepted into mainline kernel 2. Allowing users to load custom functionality at runtime 3. Configuring/patching a running system without requiring a reboot 4. Your lab assignments in this class CSE 422S Operating Systems Organization 10

Second Solution: Kernel Libraries Kernel libraries re-implement a lot of the functionality programmers expect in user space Are statically compiled into the kernel Automatically available just by including relevant header Built to be kernel-safe (sleeping, waiting, locking, etc. is done properly) Features: Utilities: kmalloc, kthreads, string parsing, etc. Containers: hash tables, binary trees etc. Algorithms: sorting, compression Mostly found under /lib and /include/linux CSE 422S Operating Systems Organization

11 Kernel Libraries Mostly found under /lib and /include/linux Many kernel libraries have clear analogues to user space libraries: - malloc/free vs kmalloc/kfree - pthread_create vs kthread_create - sleep/usleep/nanosleep (user) vs msleep (kernel) Some, however, are a bit different: - e.g., linked list implementation CSE 422S Operating Systems Organization 12

Example: Linked Lists (LKD pg. 88) struct fox { unsigned long tail_length; unsigned long weight; bool is_fantastic; }; If you wanted a list of structs of type struct_fox: struct fox { unsigned long tail_length; unsigned long weight; bool is_fantastic; struct fox * prev; struct fox * next; }; struct fox {

unsigned long tail_length; unsigned long weight; bool is_fantastic; struct list_head list_node; }; CSE 422S Operating Systems Organization 13 Case 1: Manually Linked Together struct fox { unsigned long tail_length; unsigned long weight; bool is_fantastic; struct fox * prev; struct fox * next;

}; struct fox { unsigned long tail_length; unsigned long weight; bool is_fantastic; struct fox * prev; struct fox * next; }; struct fox { unsigned long tail_length; unsigned long weight; bool is_fantastic; struct fox * prev; struct fox * next; };

struct fox { unsigned long tail_length; unsigned long weight; bool is_fantastic; struct fox * prev; struct fox * next; }; Disadvantage: need to roll your own code for each list you create Duplicate code throughout the kernel Introduce bugs Lose optimizations (placement within cache lines, etc.) CSE 422S Operating Systems Organization 14 Case 2: Embedding Fox in

list_head A list-able struct must contain struct list_head struct list_head { struct list_head *next; struct list_head *prev; }; If you wanted a list of structs of type data: struct fox{ unsigned long tail_length; unsigned long weight; bool is_fantastic; struct list_head list_node; }; CSE 422S Operating Systems Organization 15

Source: https://notes.shichao.io/lkd/ch3/ CSE 422S Operating Systems Organization 16 Example: Linked Lists Initializing a list dynamically: struct fox *new_fox; new_fox = kmalloc(sizeof(struct fox), GFP_KERNEL); new_fox->tail_length = 40; new_fox->weight = 6; new_fox->is_fantastic = false; INIT_LIST_HEAD(&(new_fox->list_node)); Or statically at compile time: static LIST_HEAD(fox_list_head); CSE 422S Operating Systems Organization

17 Example: Linked Lists Q: list_node.next, list_node.prev point to other list_head. So, how do I get access to the struct fox * embedded within? struct fox { unsigned long tail_length; unsigned long weight; bool is_fantastic; struct list_head list_node; }; list_node.prev struct list_head { struct list_head * prev;

struct list_head * next; }; list_node.next struct list_head { struct list_head * prev; struct list_head * next; }; CSE 422S Operating Systems Organization 18 Example: Linked Lists Casting out from list_node to containing structure: struct fox * fox;

struct list_head * node; fox = list_entry(node, struct fox, list_node); /* list_entry( arg 1: Pointer to list_head structure, arg 2: Type of outer containing structure, arg 3: Struct member of list_head within containing structure ) */ CSE 422S Operating Systems Organization 19 Example: Linked Lists Functions may take pointers to list nodes or pointers to the

list head: Adding: struct data *new_data; list_add(&new_data->list, &data_list_head); Deleting: list_del(&new_data->list); kfree(new_data); //if dynamic CSE 422S Operating Systems Organization 20 Example: Linked Lists Iterating: struct list_head ptr; list_for_each(ptr, data_list_head){ //ptr points to each list structure }

struct data *data_ptr; list_for_each_entry(d_ptr, data_list_head, list){ //d_ptr points to each data structure } Also: list_for_each_entry_reverse() list_for_each_entry_safe() //for modifying list elements CSE 422S Operating Systems Organization 21 Example: Linked Lists See also: /include/linux/list.h /include/linux/types.h Moral of the story:

Always search for functionality before writing it yourself. CSE 422S Operating Systems Organization 22 Module Implementation Must define: An initialization function called on load An exit function called on unload The init function must be self contained! Must unwind actions if initialization cannot complete successfully E.g. if you kmalloc() space but dont free it, that physical memory is now lost (until system restart)

You can also pass parameters to modules at load time. CSE 422S Operating Systems Organization 23 Loading and Unloading Modules Modern approach uses modprobe utility Checks dependences, other important features Optional enrichment exercise today uses it Today we will use insmod and rmmod Must use sudo to invoke these on your Rpi ERROR: could not insert module jiffies_module.ko: Operation not permitted

Cannot unload a module thats not loaded ERROR: Module jiffies_module is not currently loaded Cannot load a module thats already there ERROR: could not insert module simple_module.ko: File exists CSE 422S Operating Systems Organization 24

Recently Viewed Presentations

  • BONE MARKINGS - Mayfield High School

    BONE MARKINGS - Mayfield High School

    What are the 2 main types of bone markings BONE MARKINGS Every bump, groove, and hole has a name on your bones Bone Markings Two types of bone markings: Projections (aka processes) that grow out from the bone Depressions (cavities)...
  • GAS LAWS BOYLES LAW BACKGROUND (FOR NOTES) 1

    GAS LAWS BOYLES LAW BACKGROUND (FOR NOTES) 1

    Robert Boyle was among the first to note the relationship between pressure and volume of a gas. ... Fill the Erlenmeyer flask with about 15 mL of water and then place it on the hot plate. Turn the hot plate...
  • Diapositive 1 - Université Laval

    Diapositive 1 - Université Laval

    CREÉ Plan d'action 2009-2010 Cellule Secrétariat Cellule secrétariat Composition Secrétariat général Secrétariat exécutif Membres Missions Représentation de la CREÉ Partenariat et coopération internationale Recrutement des étudiants internationaux Coordination et suivi des plans d'action Animation des rencontres Financement Secrétaire général Ndugumbo...
  • Joint Research Centre - Europa

    Joint Research Centre - Europa

    GSTB (optional) Business is actively involved in local social community projects. Business participates in visitor payback schemes with the proceeds going to local 'green' projects, or has a collection box for green related charities. It should be noted that the...
  • Valentine L/O: to explore a realistic interpretation of love

    Valentine L/O: to explore a realistic interpretation of love

    ValentineL/O: to explore a realistic interpretation of love. Answer these questions in pairs by annotating your copy of the poem: What is the poem about? How is the presentation of love explored? What is Duffy saying and why? Identify and...
  • Animal Kingdom: Birds

    Animal Kingdom: Birds

    6 Characteristics of Birds Endothermic (warm blooded) Vertebrates (Hollow Bones!) 4 Chamber Heart All Have Feathers All Lay Eggs Have Scales on Feet and Legs How do birds fly? The top has less "air pressure" and this produces an UPWARD...
  • PSLE Results 2010 - MOE

    PSLE Results 2010 - MOE

    PSLE Results 2013 Rivervale Primary School Secondary School Option Exercise Administration Administrative Matters 1) Sec 1 Option Compulsory Choices up to 6 schools On-line at home 24hr Amendments - only once allowed by the System School assistance at the General...
  • What is Advocacy? - Social Care Wales | Social Care Wales

    What is Advocacy? - Social Care Wales | Social Care Wales

    Possible extension - ask individuals to demonstrate a mode of listening in pairs/groups or to the whole group. Active . listening. is a way of "listening for meaning" in which the listener checks with the speaker to see that a...