remaper

Kernel locking

- rusty Unreliable Guide To Locking

简单来说，就两个要点：

1. 跨上下文要避免抢占
2. 上锁过程是否可以睡眠

http://blog.pipul.org/2012/11/锁/

Linux kernel design patterns

1. http://lwn.net/Articles/336224/
2. http://lwn.net/Articles/336255/
3. http://lwn.net/Articles/336262/

The Secret to 10 Million Concurrent Connections -The Kernel is the Problem, Not the Solution

-The Secret to 10 Million Concurrent Connections -The Kernel is the Problem, Not the Solution

Now that we have the C10K concurrent connection problem licked, how do we level up and support 10 million concurrent connections? Impossible you say. Nope, systems right now are delivering 10 million concurrent connections using techniques that are as radical as they may be unfamiliar.

To learn how it’s done we turn to Robert Graham, CEO of Errata Security, and his absolutely fantastic talk at Shmoocon 2013 called C10M Defending The Internet At Scale.

Robert has a brilliant way of framing the problem that I’ve never heard of before. He starts with a little bit of history, relating how Unix wasn’t originally designed to be a general server OS, it was designed to be a control system for a telephone network. It was the telephone network that actually transported the data so there was a clean separation between the control plane and the data plane. The problem is we now use Unix servers as part of the data plane, which we shouldn’t do at all. If we were designing a kernel for handling one application per server we would design it very differently than for a multi-user kernel.

Which is why he says the key is to understand:

• The kernel isn’t the solution. The kernel is the problem.

Which means:

• Don’t let the kernel do all the heavy lifting. Take packet handling, memory management, and processor scheduling out of the kernel and put it into the application, where it can be done efficiently. Let Linux handle the control plane and let the the application handle the data plane.

The result will be a system that can handle 10 million concurrent connections with 200 clock cycles for packet handling and 1400 hundred clock cycles for application logic. As a main memory access costs 300 clock cycles it’s key to design in way that minimizes code and cache misses.

With a data plane oriented system you can process 10 million packets per second. With a control plane oriented system you only get 1 million packets per second.

If this seems extreme keep in mind the old saying: scalability is specialization. To do something great you can’t outsource performance to the OS. You have to do it yourself.

Now, let’s learn how Robert creates a system capable of handling 10 million concurrent connections...

C10K Problem - So Last Decade

A decade ago engineers tackled the C10K scalability problems that prevented servers from handling more than 10,000 concurrent connections. This problem was solved by fixing OS kernels and moving away from threaded servers like Apache to event-driven servers like Nginx and Node. This process has taken a decade as people have been moving away from Apache to scalable servers. In the last few years we’ve seen faster adoption of scalable servers.

The Apache Problem

• The Apache problem is the more connections the worse the performance.
• Key insight: performance and scalability or orthogonal concepts. They don’t mean the same thing. When people talk about scale they often are talking about performance, but there’s a difference between scale and performance. As we’ll see with Apache.
• With short term connections that last a few seconds, say a quick transaction, if you are executing a 1000 TPS then you’ll only have about a 1000 concurrent connections to the server.
• Change the length of the transactions to 10 seconds, now at 1000 TPS you’ll have 10K connections open. Apache’s performance drops off a cliff though which opens you to DoS attacks. Just do a lot of downloads and Apache falls over.
• If you are handling 5,000 connections per second and you want to handle 10K, what do you do? Let’s say you upgrade hardware and double it the processor speed. What happens? You get double the performance but you don’t get double the scale. The scale may only go to 6K connections per second. Same thing happens if you keep on doubling. 16x the performance is great but you still haven’t got to 10K connections. Performance is not the same as scalability.
• The problem was Apache would fork a CGI process and then kill it. This didn’t scale.
• Why? Servers could not handle 10K concurrent connections because of O(n^2) algorithms used in the kernel.
  • Two basic problems in the kernel:
    • Connection = thread/process. As a packet came in it would walk down all 10K processes in the kernel to figure out which thread should handle the packet
    • Connections = select/poll (single thread). Same scalability problem. Each packet had to walk a list of sockets.
  • Solution: fix the kernel to make lookups in constant time
    • Threads now constant time context switch regardless of number of threads.
    • Came with a new scalable epoll()/IOCompletionPort constant time socket lookup.
• Thread scheduling still didn’t scale so servers scaled using epoll with sockets which led to the asynchronous programming model embodied in Node and Nginx. This shifted software to a different performance graph. Even with a slower server when you add more connections the performance doesn’t drop off a cliff. At 10K connections a laptop is even faster than a 16 core server.

The C10M Problem - The Next Decade

In the very near future servers will need to handle millions of concurrent connections. With IPV6 the number of potential connections from each server is in the millions so we need to go to the next level of scalability.

• Examples of applications that will need this sort of scalability: IDS/IPS because they connection to a server backbone. Other examples: DNS root server, TOR node, Nmap of Internet, video streaming, banking, Carrier NAT, Voip PBX, load balancer, web cache, firewall, email receive, spam filtering.
• Often people who see Internet scale problems are appliances rather than servers because they are selling hardware + software. You buy the device and insert it into your datacenter. These devices may contain an Intel motherboard or Network processors and specialized chips for encryption, packet inspection, etc.
• X86 prices on Newegg as of Feb 2013 - $5K for 40gpbs, 32-cores, 256gigs RAM. The servers can do more than 10K connections. If they can’t it’s because you’ve made bad choices with software. It’s not the underlying hardware that’s the issues. This hardware can easily scale to 10 million concurrent connections.

What the 10M Concurrent Connection Challenge means:

1. 10 million concurrent connections
2. 1 million connections/second - sustained rate at about 10 seconds a connections
3. 10 gigabits/second connection - fast connections to the Internet.
4. 10 million packets/second - expect current servers to handle 50K packets per second, this is going to a higher level. Servers used to be able to handle 100K interrupts per second and every packet caused interrupts.
5. 10 microsecond latency - scalable servers might handle the scale but latency would spike.
6. 10 microsecond jitter - limit the maximum latency
7. 10 coherent CPU cores - software should scale to larger numbers of cores. Typically software only scales easily to four cores. Servers can scale to many more cores so software needs to be rewritten to support larger core machines.

We’ve Learned Unix Not Network Programming

• A generation of programmers has learned network programming by reading Unix Networking Programming by W. Richard Stevens. The problem is the book is about Unix, not just network programming. It tells you to let Unix do all the heavy lifting and you just write a small little server on top of Unix. But the kernel doesn’t scale. The solution is to move outside the kernel and do all the heavy lifting yourself.
• An example of the impact of this is to consider Apache’s thread per connection model. What this means is the thread scheduler determines which read() to call next depending on which data arrives. You are using the thread scheduling system as the packet scheduling system. (I really like this, never thought of it that way before).
• What Nginx says it don’t use thread scheduling as the packet scheduler. Do the packet scheduling yourself. Use select to find the socket, we know it has data so we can read immediately and it won’t block, and then process the data.
• Lesson: Let Unix handle the network stack, but you handle everything from that point on.

How do you write software that scales?

How do change your software to make it scale? A lot of or rules of thumb are false about how much hardware can handle. We need to know what the performance capabilities actually are.

To go to the next level the problems we need to solve are:

1. packet scalability
2. multi-core scalability
3. memory scalability

Packet Scaling - Write Your Own Custom Driver to Bypass the Stack

• The problem with packets is they go through the Unix kernel. The network stack is complicated and slow. The path of packets to your application needs to be more direct. Don’t let the OS handle the packets.
• The way to do this is to write your own driver. All the driver does is send the packet to your application instead of through the stack. You can find drivers: PF_RING, Netmap, Intel DPDK (data plane development kit). The Intel is closed source, but there’s a lot of support around it.
• How fast? Intel has a benchmark where the process 80 million packets per second (200 clock cycles per packet) on a fairly lightweight server. This is through user mode too. The packet makes its way up through to user mode and then down again to go out. Linux doesn’t do more than a million packets per second when getting UDP packets up to user mode and out again. Performance is 80-1 of a customer driver to a Linux.
• For the 10 million packets per second goal if 200 clock cycles are used in getting the packet that leaves 1400 clocks cycles to implement functionally like a DNS/IDS.
• With PF_RING you get raw packets so you have to do your TCP stack. People are doing user mode stacks. For Intel there is an available TCP stack that offers really scalable performance.

Multi-Core Scalability

Multi-core scalability is not the same thing as multi-threading scalability. We’re all familiar with the idea processors are not getting faster, but we are getting more of them.

Most code doesn’t scale past 4 cores. As we add more cores it’s not just that performance levels off, we can get slower and slower as we add more cores. That’s because software is written badly. We want software as we add more cores to scale nearly linearly. Want to get faster as we add more cores.

Multi-threading coding is not multi-core coding

• Multi-threading:
  • More than one thread per CPU core
  • Locks to coordinate threads (done via system calls)
  • Each thread a different task
• Multi-core:
  • One thread per CPU core
  • When two threads/cores access the same data they can’t stop and wait for each other
  • All threads part of the same task
• Our problem is how to spread an application across many cores.
• Locks in Unix are implemented in the kernel. What happens at 4 cores using locks is that most software starts waiting for other threads to give up a lock. So the kernel starts eating up more performance than you gain from having more CPUs.
• What we need is an architecture that is more like a freeway than an intersection controlled by a stop light. We want no waiting where everyone continues at their own pace with as little overhead as possible.
• Solutions:
  • Keep data structures per core. Then on aggregation read all the counters.
  • Atomics. Instructions supported by the CPU that can called from C. Guaranteed to be atomic, never conflict. Expensive, so don’t want to use for everything.
  • Lock-free data structures. Accessible by threads that never stop and wait for each other. Don’t do it yourself. It’s very complex to work across different architectures.
  • Threading model. Pipelined vs worker thread model. It’s not just synchronization that’s the problem, but how your threads are architected.
  • Processor affinity. Tell the OS to use the first two cores. Then set where your threads run on which cores. You can also do the same thing with interrupts. So you own these CPUs and Linux doesn’t.

Memory Scalability

• The problem is if you have 20gigs of RAM and let’s say you use 2k per connection, then if you only have 20meg L3 cache, none of that data will be in cache. It costs 300 clock cycles to go out to main memory, at which time the CPU isn’t doing anything.
• Think about this with our 1400 clock cycle budge per packet. Remember 200 clocks/pkt overhead. We only have 4 cache misses per packet and that's a problem.
• Co-locate Data
  • Don’t scribble data all over memory via pointers. Each time you follow a pointer it will be a cache miss: [hash pointer] -> [Task Control Block] -> [Socket] -> [App]. That’s four cache misses.
  • Keep all the data together in one chunk of memory: [TCB | Socket | App]. Prereserve memory by preallocating all the blocks. This reduces cache misses from 4 to 1.
• Paging
  • The paging table for 32gigs require 64MB of paging tables which doesn’t fit in cache. So you have two caches misses, one for the paging table and one for what it points to. This is detail we can’t ignore for scalable software.
  • Solutions: compress data; use cache efficient structures instead of binary search tree that has a lot of memory accesses
  • NUMA architectures double the main memory access time. Memory may not be on a local socket but is on another socket.
• Memory pools
  • Preallocate all memory all at once on startup.
  • Allocate on a per object, per thread, and per socket basis.
• Hyper-threading
  • Network processors can run up to 4 threads per processor, Intel only has 2.
  • This masks the latency, for example, from memory accesses because when one thread waits the other goes at full speed.
• Hugepages
  • Reduces page table size. Reserve memory from the start and then your application manages the memory.

Summary

• NIC
  • Problem: going through the kernel doesn’t work well.
  • Solution: take the adapter away from the OS by using your own driver and manage them yourself
• CPU
  • Problem: if you use traditional kernel methods to coordinate your application it doesn’t work well.
  • Solution: Give Linux the first two CPUs and you application manages the remaining CPUs. No interrupts will happen on those CPUs that you don’t allow.
• Memory
  • Problem: Takes special care to make work well.
  • Solution: At system startup allocate most of the memory in hugepages that you manage.

The control plane is left to Linux, for the data plane, nothing. The data plane runs in application code. It never interacts with the kernel. There’s no thread scheduling, no system calls, no interrupts, nothing.

Yet, what you have is code running on Linux that you can debug normally, it’s not some sort of weird hardware system that you need custom engineer for. You get the performance of custom hardware that you would expect for your data plane, but with your familiar programming and development environment.

Related Articles

• Read on Hacker News or Reddit
• Is It Time To Get Rid Of The Linux OS Model In The Cloud?
• Machine VM + Cloud API - Rewriting The Cloud From Scratch
• Exokernel
• Blog on C10M
• Multi-core scaling: it’s not multi-threaded with some good comment action.
• Intel® DPDK: Data Plane Development Kit

Control Groups

Redhat在关于cgroup方面的一份非常详细的文档

1. Red Hat Enterprise Linux 6 Resource Management Guide

what is the real necessary change

看内核patchs的时候，经常会看到一些清理代码的patch，理由是unnecessary，比如这个：

[PATCH] vfs: no need to check about IS_IMMUTABLE in do_fallocate

From: Ashish Sangwan <a.sangwan <at> samsung.com>

In do_fallocate, first there is check for FMODE_WRITE and after that
there is second check for IS_IMMUTABLE.
A file cannot be opened in write mode if the corresponding inode is
immutable, hence the second check is not required.

Signed-off-by: Ashish Sangwan <a.sangwan <at> samsung.com>
Signed-off-by: Namjae Jeon <namjae.jeon <at> samsung.com>
---
 fs/open.c |    3 ---
 1 files changed, 0 insertions(+), 3 deletions(-)

diff --git a/fs/open.c b/fs/open.c
index 8c74100..939e402 100644
--- a/fs/open.c
+++ b/fs/open.c
 <at>  <at>  -245,9 +245,6  <at>  <at>
 	int do_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
 	if (mode & FALLOC_FL_PUNCH_HOLE && IS_APPEND(inode))
 		return -EPERM;

-	if (IS_IMMUTABLE(inode))
-		return -EPERM;
-
 	/*
 	 * Revalidate the write permissions, in case security policy has
 	 * changed since the files were opened.

事实上看起来这处代码是多余的。不过我更偏向的想法是，基础函数或者通常一下比较通用的代码，要尽可能的具备语义自描述的特性，就是说，它不需要理解外界的环境是什么样的，只对输入做符合规格的检查。

比如这里的do_fallocate()函数，正常情况下，能以write模式打开的文件，它的inode肯定不是IS_IMMUTABLE，所以这个patch里把这个不必要的一步去掉了。

但是反过来考虑一下，如果将来某天，我们可能为了满足某种特别的需求，即使文件的inode是IS_IMMUTABLE的，也可以以write模式打开，但是实现这个功能代码的作者，未必会想到此处可能会引发BUG，而且这种地方还不少。

Linux Kernel Procfs Guide

- J.A.K.Mouw@its.tudelft.nl  Linux Kernel Procfs Guide

1. Introduction

The /proc file system (procfs) is a special file system in the linux kernel. It’s a virtual file system: it is not associated with a block device but exists only in memory. The files in the procfs are there to allow userland programs access to certain information from the kernel (like process information in /proc/[0-9]+/), but also for debug purposes (like /proc/ksyms). This guide describes the use of the procfs file system from within the Linux kernel. It starts by introducing all relevant functions to manage the files within the file system.
After that it shows how to communicate with userland, and some tips and tricks will be pointed out. Finally a complete example will be shown. Note that the files in /proc/sys are sysctl files: they don’t belong to procfs and are governed by a completely different API described in the Kernel API book.

2. Managing procfs entries

This chapter describes the functions that various kernel components use to populate the procfs with files, symlinks, device nodes, and directories. A minor note before we start: if you want to use any of the procfs functions, be sure to include the correct header file! This should be one of the first lines in your code:

#include <linux/proc_fs.h>

2.1. Creating a regular file

struct proc_dir_entry* create_proc_entry(const char* name, mode_t mode,
 struct proc_dir_entry* parent);

This function creates a regular file with the name name, file mode mode in the directory parent. To create a file in the root of the procfs, use NULL as parent parameter. When successful, the function will return a pointer to the freshly created struct proc_dir_entry; otherwise it will return NULL. Chapter 3 describes how to do something useful with regular files. Note that it is specifically supported that you can pass a path that spans multiple directories. For example create_proc_entry("drivers/via0/info") will create the via0 directory if necessary, with standard 0755 permissions. If you only want to be able to read the file, the function create_proc_read_entry described in Section 4.1 may be used to create and initialise the procfs entry in one single call.

2.2. Creating a symlink

struct proc_dir_entry* proc_symlink(const char* name, struct proc_dir_entry* parent,
 const char* dest);

This creates a symlink in the procfs directory parent that points from name to dest. This translates in userland to ln -s dest name.

2.3. Creating a device

struct proc_dir_entry* proc_mknod(const char* name, mode_t mode,
 struct proc_dir_entry* parent, kdev_t rdev);

Creates a device file name with mode mode in the procfs directory parent. The device file will work on the device rdev, which can be generated by using the MKDEV macro from linux/kdev_t.h. The mode parameter must contain S_IFBLK or S_IFCHR to create a device node. Compare with userland mknod --mode=mode name rdev.

2.4. Creating a directory

struct proc_dir_entry* proc_mkdir(const char* name, struct proc_dir_entry* parent);

Create a directory name in the procfs directory parent.

2.5. Removing an entry

void remove_proc_entry(const char* name, struct proc_dir_entry* parent);

Removes the entry name in the directory parent from the procfs. Entries are removed by their name, not by the struct proc_dir_entry returned by the various create functions. Note that this function doesn’t recursively remove entries. Be sure to free the data entry from the struct proc_dir_entry before remove_proc_entry is called (that is: if there was some data allocated, of course). See Section 3.3 for more information on using the data entry.

3. Communicating with userland

Instead of reading (or writing) information directly from kernel memory, procfs works with call back functions for files: functions that are called when a specific file is being read or written. Such functions have to be initialised after the procfs file is created by setting the read_proc and/or write_proc fields in the struct proc_dir_entry* that the function create_proc_entry returned:

struct proc_dir_entry* entry;
entry->read_proc = read_proc_foo;
entry->write_proc = write_proc_foo;

If you only want to use a the read_proc, the function create_proc_read_entry described in Section 4.1 may be used to create and initialise the procfs entry in one single call.

3.1. Reading data

The read function is a call back function that allows userland processes to read data from the kernel. The read function should have the following format:

int read_func(char* page, char** start, off_t off, int count,
int* eof, void* data);

The read function should write its information into the page. For proper use, the function should start writing at an offset of off in page and write at most count bytes, but because most read functions are quite simple and only return a small amount of information, these two parameters are usually ignored (it breaks pagers like more and less, but cat still works). If the off and count parameters are properly used, eof should be used to signal that the end of the file has been reached by writing 1 to the memory location eof points to.

The parameter start doesn’t seem to be used anywhere in the kernel. The data parameter can be used to create a single call back function for several files, see Section 3.3. The read_func function must return the number of bytes written into the page. Chapter 5 shows how to use a read call back function.

3.2. Writing data

The write call back function allows a userland process to write data to the kernel, so it has some kind of control over the kernel. The write function should have the following format:

int write_func(struct file* file, const char* buffer, unsigned
long count, void* data);

The write function should read count bytes at maximum from the buffer. Note that the buffer doesn’t live in the kernel’s memory space, so it should first be copied to kernel space with copy_from_user. The file parameter is usually ignored. Section 3.3 shows how to use the data parameter. Again, Chapter 5 shows how to use this call back function.

3.3. A single call back for many files

When a large number of almost identical files is used, it’s quite inconvenient to use a separate call back function for each file. A better approach is to have a single call back function that distinguishes between the files by using the data field in struct
proc_dir_entry. First of all, the data field has to be initialised:

struct proc_dir_entry* entry;
struct my_file_data *file_data;
file_data = kmalloc(sizeof(struct my_file_data), GFP_KERNEL);
entry->data = file_data;

The data field is a void *, so it can be initialised with anything. Now that the data field is set, the read_proc and write_proc can use it to distinguish between files because they get it passed into their data parameter:

int foo_read_func(char *page, char **start, off_t off,
int count, int *eof, void *data)
{
	int len;
	if(data == file_data) {
		/* special case for this file */
	} else {
		/* normal processing */
	}
	return len;
}

Be sure to free the data data field when removing the procfs entry.

4. Tips and tricks

4.1. Convenience functions

struct proc_dir_entry* create_proc_read_entry(const char* name,
mode_t mode, struct proc_dir_entry* parent, read_proc_t*
read_proc, void* data);

This function creates a regular file in exactly the same way as create_proc_entry from Section 2.1 does, but also allows to set the read function read_proc in one call. This function can set the data as well, like explained in Section 3.3.

4.2. Modules

If procfs is being used from within a module, be sure to set the owner field in the struct proc_dir_entry to THIS_MODULE.

struct proc_dir_entry* entry;
entry->owner = THIS_MODULE;

4.3. Mode and ownership

Sometimes it is useful to change the mode and/or ownership of a procfs entry. Here is an example that shows how to achieve that:

struct proc_dir_entry* entry;
entry->mode = S_IWUSR |S_IRUSR | S_IRGRP | S_IROTH;
entry->uid = 0;entry->gid = 100;