Forward march Kernel!

So anyway, I spent this boxing day weekend holiday doing that. Leading up to this, I’d casually flirt with the idea and would browse my “Essential Linux Device Drivers” book and then Amazon for resources on the Linux kernel. Leading up to this, I’d been beginning to do a little bit here and a little bit there – the stuff that I could still do productively and not have to invest mountains of time into that is. for example I had recently I installed Fedora 25 onto my laptop and dual booted that sucker – I can tell you that Windows 10 on my laptop is not happy I can tell you!

I’d downloaded a free kindle book which was around how to implement loadable kernel modules and it was badly written(I mean it was bad – it was but an author who had poor English skills but thankfully the C code made up for that…anyway) and well I thought It’d be time(when i eventually start) to get a good book on Linux kernel development and that I’d use that to interleave with the device driver book I had – which I might add I feelt like it needed more kernel know-how than I currently had. So I bought Robert Love’s Linux Kernel Development(Developer’s library) and started to read that one my tablet. Oh yeah, I’ve got a Windows 10 tablet also – its a Samsung. My Windows 10 on my laptop is even more nervous about that…

Its a great book and its useful and descriptive and I’ve learned a lot and more importantly I’ve really enjoyed reading it. Its a kindle book. I can take notes with it and being on my tablet makes its really neat and portable. That said, I’ve been reading on my laptop too – which is also portable. Oh its also worth noting that I had to recompile my fedora 25 kernel because I could not load modules into it. As it happens this is because I didn’t install kernel-devel-headers packages but i didn’t know that so i just recompiled the whole kernel and modules loaded fine. When I say modules, I mean my “hello kernel” module. Device drivers are usually implemented as modules. Its far safer writing kernel code in a module, I’ve Oops’ed a few times and its just the module that goes ‘bye-bye’ and the rest of my Linux is fine. Come to think about it – probably should be doing this stuff in a VM but what they hell – I’ll probably do that eventually because once my loadable module crashes – I can’t unload it or re-load it. A VM is a very good idea.

So far I’ve read about process creation, kernel data structures, system calls, interrupts and interrupt handlers(my favourite), bottom halves, timers and synchronization. That was really fun. I also had a brief look at some of the string routines in the source. Was happy to note that they also use variables names like s1 and s2 because i think its more concise and with context you know its “string1” and “string2”. I’d just implemented a basic word counting routine myself in my library. These routines in the kernel were more impressive i can tell you!

Having come from a will to implement a device driver, two main things that I learnt that was interesting. First, hardware speaks to the processor via interrupt lines – it sends an electronic signal up these interrupt lines(via a bus to the interrupt controller chip on the board) which then interrupts the processor and the processor then interrupts the kernel and runs one of the registered interrupt handlers. So this is what a device driver will aim to do: register an interrupt handler for a device, when that device generates interrupts on that interrupt line(which we’re registered on) – we’ll handle the interrupt -interpret what it means, interact with the device and basically deal with the hardware in a defined manner – normally according to a specification- all in the interrupt handler which is in ‘interrupt context’.

One of the most interesting things is that we’d be interrupt context which is different to  process context(kernel dealing with a process/task either from userspace or in the kernel) where the interrupt handler needs to acknowledge the request, do some fast work to niteract with the hardware like copy data to/from it into kernel and schedule heavier, less time-critical work to be done later – via ‘bottom halves’(mechanism for deferring work outside of the interrupt context). Usually to deal with a interrupt, you’d disable any possible other interrupts on that interrupt line, deal with it and get out fast! So my guess is that I’ll be needing yo register an interrupt handler from my device driver – implemented via the loadable module. Very cool.

Bottom halves are like background threads –and indeed that are implemented in the kernel as such(eg softirqd). You put your work into a botton half – tasklet or softirq or work queue and let the kernel execute it sometime in the future. Nice thing about this is that they run in process context(kernel mode) and are preemptable whereas interrupt mode is not. This means we can sleep in bottom halves. Interrupt handlers can’t sleep.

Speaking about executing work later and having our tasks be put to sleep raised the issue of shared data and locking. You can busy-spin via spinlocks in interrupt context because you can’t sleep there but using semphores, mutexes and read-writer and seqlocks locks allow you to sleep so you must use them where you can sleep(bottom halves) –  if you were pre-empted, that’d be ok to hold a sleepable lock. Still because you can be interrupted while in a bottom half or have multiple bottom halves(softirqs) running concurrently – they could tred on each other’s data – so exclusive access to locks was discussed. Also very interesting.

I found that discussion on memory barriers and atomic_t type a bit boring but they are useful for ensuring no premature loading/storing of registered are optimised by the processor or compiler in the former case and that setting and incrementing certain types are just that – atomic. I guess I’ll be more interested in them when i need to use their functionality.

I’d used a kernel linked list before by borrowing some guys code online which he had ripped it out of the kernel and I implemented it into my C library, before replacing it with my own implementation(because I can not because its better – it isn’t). Anyway linux kernel lined list are powerful (and oh they work) but its kinda wierd to use. So it wasn’t a complete surprise to have it make sense to me on first explanation. These are cantered around structures called list_head nodes that link together – but they themselves don’t have the node data…but can move backward and forward and you can obtain the node data by using a container_of() function on the node…and it magically finds that node data. Actually to be more accurate you need to embedd one of these list_head structures in your data structure. and then just using a container_of(list_head) will get your data – so it can figure out what structure its apart of - these kernel developers are pretty smart.

Some more interesting facts:

1. The kernel can be in interrupt context or process context(executing user or kernel task)
2. The kernel is pre-emptive and thus it can ask any of its own internal processes/tasks to sleep and they will. Same with user space processes.
3. To leave user mode, the user mode code has to generate a software interrupt, which the processor then switches to kernel mode and when we pass some parameters to the processor from user mode, those parameters contain the system call that will be run in kernel mode. Results are brought back in the inverse fashion – kernel puts results in processor registers and asks for a context switch and we’re back in user mode!
4. Spin locks can be used in interrupt context – no other lock type is permitted because they will probably sleep
5. You cannot sleep in interrupt context.
6. Bottom halves are like background threads in an application(the kernel)
7. The kernel has a fixed stack size but you can still call kmalloc() in it and kfree()
8. The system timer interrupts the kernel periodically and consistently and calculates the time a process has been running for the scheduler  -who’ll use this info to determine if the process currently running should be put to sleep in favour of a higher priority one.
9. You can call kernel system calls – syscalls directly without the need of a C-library to do it for you
10. Work queues, tasklets and softirqs use the kernel’s background threads to run – they can be pre-empted(put to sleep or yield to the processor so efficient if needing to block as other work can be done)
11. There is a ird datastructure that will allow the fast mapping of new UIDs to object pointers. This is useful so you can give a user mode process a UID number (it generates one) and when it gives it back to you, the ird structure can efficiently give you back the pointer corresponding to that UID, probably a tracked kernel structure that has some relevance to the UID that user is asking you about – basically a map data structure.
12. You can copy to and from userspace and kernel space. This is usually done with in the syscall. Got to ensure that the passed parameters from user space are appropriate as they can be a security risk and can bring down the kernel say if we try and deference a pointer provided by the user mode app and its NULL.
13. Kernel mode can access user mode address space
14. Each process has a task_struct in the kernel.
15. Each process has its own address space, referenced by the mm member on the task_struct.
16. fork() returns twice – once in the parent and once in the child.
17. fork() is processed by the clone() syscall when is responsible for copying a subset of parent’s data for the child process.(including setting up a new address space)
18. exec() loads a executable image into the address space and starts the process up (puts the process state into RUNNABLE)

So what does my module do currently? Nothing useful. But: it

1. Utilises the kernel source to link into kernel provided data structures and routines.
2. Creates a linked-list
3. Creates a queue.
4. Allocates kernel memory dynamically
5. Prints to the kernel buffer.
6. Makes no sense but it compiles, loads into the kernel and it outputs just fine via dmesg.
7. It was a lot of fun.

#include <linux/init.h>
#include <linux/module.h>
#include <linux/list.h>
#include <linux/slab.h>
#include <linux/kfifo.h>

MODULE_LICENSE("GPL");

struct fox {
	unsigned int	tail_length;
	unsigned int	weight;
	bool		is_fantastic;
	struct list_head list;
};

static int hello_init(void)
{
	LIST_HEAD(fox_list);
	struct fox *red_fox;
	
	printk(KERN_INFO "Hello kernel!");

	// dynamically create a list
	red_fox = kmalloc(sizeof(*red_fox), GFP_KERNEL);
	red_fox->tail_length = 40;
	red_fox->is_fantastic = true;
	
	INIT_LIST_HEAD(&red_fox->list);
	
	//statically create a list
	struct fox blue_fox = {.
		tail_length = 20,
		.weight = 30,
		.is_fantastic = true,
		.list = LIST_HEAD_INIT(blue_fox.list),
	};
	
	// Add entries to a static list fox_list
	list_add(&red_fox->list, &fox_list);
	list_add(&blue_fox.list, &fox_list);

	// search through the fox list for each item in the list
	struct fox *each;
	list_for_each_entry(each, &fox_list, list) {
		//refer to each item in the list - merely refernces to the data
		printk(KERN_INFO "Foun entry %d", each->tail_length);
	}

	// create a queue

	struct kfifo fifo;
	int ret;
	// set it up
	ret = kfifo_alloc(&fifo, PAGE_SIZE, GFP_KERNEL);
	if(ret) return ret;

	// push our two foxes into it
	int rc = kfifo_in(&fifo, &red_fox, sizeof(struct fox*));
	if( rc == sizeof(struct fox*))
		printk("fox structure copied fully");
	rc = kfifo_in(&fifo, &blue_fox, sizeof(struct fox*));
	if( rc == sizeof(struct fox*))
		printk("fox structure copied fully");
	printk("size of the fifo is %d", kfifo_size(&fifo));
	
	// put the contents in temp(the contents is just the pointer to the fox objects) 
	struct fox* temp;
	ret = kfifo_out(&fifo, &temp, sizeof(struct fox*));
	if(ret != sizeof(struct fox*)){
		printk(KERN_ALERT "bad juju");
		goto free;
	}
	printk(KERN_INFO "Dequed entry was %d", temp->tail_length);
free:
	kfifo_free(&fifo);
	kfree(red_fox);
	return 0;
}

static void hello_exit(void)
{
	printk(KERN_INFO "Goodbye kernel!");
}

module_init(hello_init);
module_exit(hello_exit);

So lots still to learn and do. My ultimate goal is to create a electronic device(yeah breadboard, solder etc) – hook it up to the computer and make the computer control or interact with it – obviously via a device driver which I will write. Here to the future!