Linux内核文档索引

Posted 2014-10-24 00:10 +0800 by ZhangJie ‐ 206 min read

迁移自 hitzhangjie/Study 项目下的内容，本文是看内核源码时对文档的一个阅读、内容总结。

============================================================================= Fri Sep 18 12:23:06 CST 2014 #

Documentation/

[1] zorro.txt zorro bus ii\iiioZorro II is the name of the general purpose expansion bus used by the Amiga 2000 computer. The bus is mainly a buffered extension of the Motorola 68000 bus, with support for bus mastering DMA. The expansion slots use a 100-pin connector and the card form factor is the same as the IBM PC. Zorro II cards implement the Autoconfig protocol for automatic address space assignment (designed before, yet similar to, Plug and Play on the PC). Zorro II was succeeded by Zorro III.

[2] xz.txt XZ is a general purpose data compression format with high compression ratio and relatively fast decompression. The primary compression algorithm (filter) is LZMA2. Additional filters can be used to improve 0010 compression ratio even further. E.g. Branch/Call/Jump (BCJ) filters 0011 improve compression ratio of executable data.

[3] workqueue.txt There are many cases where an asynchronous process execution context is needed and the workqueue (wq) API is the most commonly used mechanism for such cases. When such an asynchronous execution context is needed, a work item describing which function to execute is put on a queue. An independent thread serves as the asynchronous execution context. The queue is called workqueue and the thread is called worker.

[4] volatile-considered-harmful.txt C programmers have often taken volatile to mean that the variable could be changed outside of the current thread of execution; as a result, they are sometimes tempted to use it in kernel code when shared data structures are being used. In other words, they have been known to treat volatile types kernel code is almost never correct; this document describes why.

[5] video-output.txt The output sysfs class driver provides an abstract video output layer that can be used to hook platform specific methods to enable/disable video output device through common sysfs interface.

[6] vgaarbiter.txt Graphic devices are accessed through ranges in I/O or memory space. While most modern devices allow relocation of such ranges, some “Legacy” VGA devices implemented on PCI will typically have the same “hard-decoded” addresses as they did on ISA. For more details see “PCI Bus Binding to IEEE Std 1275-1994 Standard for Boot (Initialization Configuration) Firmware Revision 2.1” Section 7, Legacy Devices.

[7] unshare.txt This document describes the new system call, unshare. The document provides an overview of the feature, why it is needed, how it can be used, its interface specification, design, implementation and how it can be tested.

[8] unicode.txt kernel code has been rewritten to use Unicode to map characters to fonts. By downloading a single Unicode-to-font table, both the eight-bit character sets and UTF-8 mode are changed to use the font as indicated.

[9] unaligned memory access Linux runs on a wide variety of architectures which have varying behaviour when it comes to memory access. This document presents some details about unaligned accesses, why you need to write code that doesn’t cause them, and how to write such code!

=============================================================================

Fri Sep 19 10:59:56 CST 2014 #

[10] sysrq.txt It is a ‘magical’ key combo you can hit which the kernel will respond to regardless of whatever else it is doing, unless it is completely locked up. Here is the list of possible values in /proc/sys/kernel/sysrq: 0 - disable sysrq completely 1 - enable all functions of sysrq >1 - bitmask of allowed sysrq functions (see below for detailed function description): 2 - enable control of console logging level 4 - enable control of keyboard (SAK, unraw) 8 - enable debugging dumps of processes etc. 16 - enable sync command 32 - enable remount read-only 64 - enable signalling of processes (term, kill, oom-kill) 128 - allow reboot/poweroff 256 - allow nicing of all RT tasks

You can set the value in the file by the following command: echo “number” >/proc/sys/kernel/sysrq

Note that the value of /proc/sys/kernel/sysrq influences only the invocation via a keyboard. Invocation of any operation via /proc/sysrq-trigger is always allowed (by a user with admin privileges).

Regarding to how to make invoke the sysrq commands, please refer to the kernel documentation, there’s some differences between different architectures including x86, spark and others. some keyboards may generate different keycode sequences, remapping may be required, too.

[11] sysfs-rules.txt kernel-exported sysfs exports internal kernel implementation details and depends on internal kernel structures and layout. It is agreed upon by the kernel developers that the Linux kernel does not provide a stable internal API. Therefore, there are aspects of the sysfs interface that may not be stable across kernel releases.

To minimize the risk of breaking users of sysfs, which are in most cases low-level userspace applications, with a new kernel release, the users of sysfs must follow some rules to use an as-abstract-as-possible way to access this filesystem. The current udev and HAL programs already implement this and users are encouraged to plug, if possible, into the abstractions these programs provide instead of accessing sysfs directly.

But if you really do want or need to access sysfs directly, please follow the following rules and then your programs should work with future versions of the sysfs interface.

[12] svga.txt This small document describes the “Video Mode Selection” feature which allows the use of various special video modes supported by the video BIOS. Due to usage of the BIOS, the selection is limited to boot time (before the kernel decompression starts) and works only on 80X86 machines.

[13] stable_kernel_rules.txt Everything you ever wanted to know about Linux -stable releases.

Rules on what kind of patches are accepted, and which ones are not, into the “-stable” tree:

• It must be obviously correct and tested.
• It cannot be bigger than 100 lines, with context.
• It must fix only one thing.
• It must fix a real bug that bothers people (not a, “This could be a problem…” type thing).
• It must fix a problem that causes a build error (but not for things marked CONFIG_BROKEN), an oops, a hang, data corruption, a real security issue, or some “oh, that’s not good” issue. In short, something critical.
• Serious issues as reported by a user of a distribution kernel may also be considered if they fix a notable performance or interactivity issue. As these fixes are not as obvious and have a higher risk of a subtle regression they should only be submitted by a distribution kernel maintainer and include an addendum linking to a bugzilla entry if it exists and additional information on the user-visible impact.
• New device IDs and quirks are also accepted.
• No “theoretical race condition” issues, unless an explanation of how the race can be exploited is also provided.
• It cannot contain any “trivial” fixes in it (spelling changes, whitespace cleanups, etc).
• It must follow the Documentation/SubmittingPatches rules.
• It or an equivalent fix must already exist in Linus' tree (upstream).

Procedure for submitting patches to the -stable tree:

• Send the patch, after verifying that it follows the above rules, to stable@vger.kernel.org. You must note the upstream commit ID in the changelog of your submission.

• To have the patch automatically included in the stable tree, add the tag Cc: stable@vger.kernel.org in the sign-off area. Once the patch is merged it will be applied to the stable tree without anything else needing to be done by the author or subsystem maintainer.

• If the patch requires other patches as prerequisites which can be cherry-picked than this can be specified in the following format in the sign-off area:

  Cc: stable@vger.kernel.org # 3.3.x: a1f84a3: sched: Check for idle Cc: stable@vger.kernel.org # 3.3.x: 1b9508f: sched: Rate-limit newidle Cc: stable@vger.kernel.org # 3.3.x: fd21073: sched: Fix affinity logic Cc: stable@vger.kernel.org # 3.3.x Signed-off-by: Ingo Molnar mingo@elte.hu

  The tag sequence has the meaning of: git cherry-pick a1f84a3 git cherry-pick 1b9508f git cherry-pick fd21073 git cherry-pick

• The sender will receive an ACK when the patch has been accepted into the queue, or a NAK if the patch is rejected. This response might take a few days, according to the developer’s schedules.

• If accepted, the patch will be added to the -stable queue, for review by other developers and by the relevant subsystem maintainer.

• Security patches should not be sent to this alias, but instead to the documented security@kernel.org address.

Review cycle:

• When the -stable maintainers decide for a review cycle, the patches will be sent to the review committee, and the maintainer of the affected area of the patch (unless the submitter is the maintainer of the area) and CC: to the linux-kernel mailing list.
• The review committee has 48 hours in which to ACK or NAK the patch.
• If the patch is rejected by a member of the committee, or linux-kernel members object to the patch, bringing up issues that the maintainers and members did not realize, the patch will be dropped from the queue.
• At the end of the review cycle, the ACKed patches will be added to the latest -stable release, and a new -stable release will happen.
• Security patches will be accepted into the -stable tree directly from the security kernel team, and not go through the normal review cycle. Contact the kernel security team for more details on this procedure.

[14] stable_api_nonsense.txt This is being written to try to explain why Linux does not have a binary kernel interface, nor does it have a stable kernel interface. Please realize that this article describes the in kernel interfaces, not the kernel to userspace interfaces. The kernel to userspace interface is the one that application programs use, the syscall interface. That interface is very stable over time, and will not break. I have old programs that were built on a pre 0.9something kernel that still work just fine on the latest 2.6 kernel release. That interface is the one that users and application programmers can count on being stable.

there are two main topics here, binary kernel interfaces and stable kernel source interfaces. They both depend on each other, but we will discuss the binary stuff first to get it out of the way.

Binary Kernel Interface ##

Assuming that we had a stable kernel source interface for the kernel, a binary interface would naturally happen too, right? Wrong. Please consider the following facts about the Linux kernel:

• Depending on the version of the C compiler you use, different kernel data structures will contain different alignment of structures, and possibly include different functions in different ways (putting functions inline or not.) The individual function organization isn’t that important, but the different data structure padding is very important.
• Depending on what kernel build options you select, a wide range of different things can be assumed by the kernel:
  • different structures can contain different fields
  • Some functions may not be implemented at all, (i.e. some locks compile away to nothing for non-SMP builds.)
  • Memory within the kernel can be aligned in different ways, depending on the build options.
  • Linux runs on a wide range of different processor architectures. There is no way that binary drivers from one architecture will run on another architecture properly.

Now a number of these issues can be addressed by simply compiling your module for the exact specific kernel configuration, using the same exact C compiler that the kernel was built with. This is sufficient if you want to provide a module for a specific release version of a specific Linux distribution. But multiply that single build by the number of different Linux distributions and the number of different supported releases of the Linux distribution and you quickly have a nightmare of different build options on different releases. Also realize that each Linux distribution release contains a number of different kernels, all tuned to different hardware types (different processor types and different options), so for even a single release you will need to create multiple versions of your module.

Trust me, you will go insane over time if you try to support this kind of release, I learned this the hard way a long time ago…

Stable Kernel Source Interfaces ##

This is a much more “volatile” topic if you talk to people who try to keep a Linux kernel driver that is not in the main kernel tree up to date over time.

Linux kernel development is continuous and at a rapid pace, never stopping to slow down. As such, the kernel developers find bugs in current interfaces, or figure out a better way to do things. If they do that, they then fix the current interfaces to work better. When they do so, function names may change, structures may grow or shrink, and function parameters may be reworked. If this happens, all of the instances of where this interface is used within the kernel are fixed up at the same time, ensuring that everything continues to work properly.

As a specific examples of this, the in-kernel USB interfaces have undergone at least three different reworks over the lifetime of this subsystem. These reworks were done to address a number of different issues:

• A change from a synchronous model of data streams to an asynchronous one. This reduced the complexity of a number of drivers and increased the throughput of all USB drivers such that we are now running almost all USB devices at their maximum speed possible.

• A change was made in the way data packets were allocated from the USB core by USB drivers so that all drivers now needed to provide more information to the USB core to fix a number of documented deadlocks.

This is in stark contrast to a number of closed source operating systems which have had to maintain their older USB interfaces over time. This provides the ability for new developers to accidentally use the old interfaces and do things in improper ways, causing the stability of the operating system to suffer.

In both of these instances, all developers agreed that these were important changes that needed to be made, and they were made, with relatively little pain. If Linux had to ensure that it will preserve a stable source interface, a new interface would have been created, and the older, broken one would have had to be maintained over time, leading to extra work for the USB developers. Since all Linux USB developers do their work on their own time, asking programmers to do extra work for no gain, for free, is not a possibility.

Security issues are also very important for Linux. When a security issue is found, it is fixed in a very short amount of time. A number of times this has caused internal kernel interfaces to be reworked to prevent the security problem from occurring. When this happens, all drivers that use the interfaces were also fixed at the same time, ensuring that the security problem was fixed and could not come back at some future time accidentally. If the internal interfaces were not allowed to change, fixing this kind of security problem and insuring that it could not happen again would not be possible.

Kernel interfaces are cleaned up over time. If there is no one using a current interface, it is deleted. This ensures that the kernel remains as small as possible, and that all potential interfaces are tested as well as they can be (unused interfaces are pretty much impossible to test for validity.)

[15] spinlocks.txt

自旋锁，这里自旋的意思值得是线程在一个while循环中不停地检查期望的条件是否得到 了满足，如果没有得到满足就等待一段时间，然后继续检查，知道满足之后才会执行后续 的处理。 说白了，自旋就是忙等，我们在以前学习组成原理的时候，了解到cpu与设备的通信方式 主要有3种，分别是程序查询方式（忙等）、中断请求、DMA。其中程序查询方式会中断 cpu的执行，原地踏步，影响cpu的执行效率，可能想到这的时候会认为自旋锁也是这样的 一种锁，这很自然，类比嘛，但是其中有些差别。 我们前面提及的程序查询方式是cpu与硬件设备进行通信的方式，与我们这里操作系统内 部的自旋锁还稍微有些差别，不过，确实是，自旋锁这种排它性锁对系统整体性能可能影 响是比较大的，所以我们在内核中不会用它来长时间阻塞一个线程，而是用它来短暂的阻 塞一个线程，例如将其用于进程调度、线程调度，这个时候，自旋锁在内核中还是非常高 效的。

另外，实现自旋锁还是比较复杂的，因为要保证能够正确处理可能存在的竟态条件，需要 考虑cpu架构，以及针对这种架构的特殊的汇编指令，例如原子的test、set指令来实现对 自旋锁的加锁、解锁、测试，这在高级语言中是无法做到的。 如果cpu架构中没有原子的这种test、set操作的话，则需要通过某种算法来实现类似的原 子操作。 这样看来，自旋锁是与cpu有关的，好了，现在先不多说了，在看第3个例子的时候，提到 non-irq版本的自旋锁进入临界区后，如果有相同的cpu上有中断到达，并且中断处理函数 中请求相同的自旋锁时，会引发死锁，当讲到这的时候，我们将详细描述自旋锁的实现细 节。

其实自旋锁效率高不高，还是要看应用的场景，好了下面介绍一下内核中3种常用的自旋 锁。

Lesson 1: Spin locks

The most basic primitive for locking is spinlock.

static DEFINE_SPINLOCK(xxx_lock);
 
    unsigned long flags;

    spin_lock_irqsave(&xxx_lock, flags);
    ... critical section here ..
    spin_unlock_irqrestore(&xxx_lock, flags);

这里的自旋锁会屏蔽后期到达的中断请求，屏蔽并不是表示忽略，而是将到达的中断
请求暂时保存起来，即irqsave，等临界区代码执行完毕时，再将咱存的中断请求恢
复，即irqrestore。

The above is always safe. It will disable interrupts locally, but the spinlock itself will guarantee the global lock, so it will guarantee that there is only one thread-of-control within the region(s) protected by that lock. This works well even under UP also, so the code does not need to worry about UP vs SMP issues: the spinlocks work correctly under both.

UP: Uniprocessor，单处理器； SMP: Symmetric Multiprocessor，对称多处理器； spin_lock_irqsave/spin_lock_irqrestore会禁止中断，这种方式使得自旋锁在UP、SMP 两种情况下均适用。

NOTE! Implications of spin_locks for memory are further described in:

Documentation/memory-barriers.txt
   (5) LOCK operations.
   (6) UNLOCK operations.

The above is usually pretty simple (you usually need and want only one spinlock for most things - using more than one spinlock can make things a lot more complex and even slower and is usually worth it only for sequences that you know need to be split up: avoid it at all cost if you aren’t sure).

This is really the only really hard part about spinlocks: once you start using spinlocks they tend to expand to areas you might not have noticed before, because you have to make sure the spinlocks correctly protect the shared data structures everywhere they are used. The spinlocks are most easily added to places that are completely independent of other code (for example, internal driver data structures that nobody else ever touches).

NOTE! The spin-lock is safe only when you also use the lock itself to do locking across CPU’s, which implies that EVERYTHING that touches a shared variable has to agree about the spinlock they want to use.

Lesson 2: reader-writer spinlocks.

If your data accesses have a very natural pattern where you usually tend to mostly read from the shared variables, the reader-writer locks (rw_lock) versions of the spinlocks are sometimes useful. They allow multiple readers to be in the same critical region at once, but if somebody wants to change the variables it has to get an exclusive write lock.

NOTE! reader-writer locks require more atomic memory operations than simple spinlocks. Unless the reader critical section is long, you are better off just using spinlocks.

其实这里考虑的还是细粒度加锁，以便提高并行、并发能力。 禁用中断的自旋锁版本是最简单的自旋锁版本，但是它由于是排它性锁，所以对并行性影 响较大； 而自旋锁的另一个版本，读写锁，在读者较多的情况下，能够适当提高并行性，提升系统 性能，但是这种情况下，最好临界区比较长，如果临界区比较短的情况下，并行性能的提 升也不会很明显，这个时候最好使用简单版本的自旋锁。

The routines look the same as above:

rwlock_t xxx_lock = __RW_LOCK_UNLOCKED(xxx_lock);
 
     unsigned long flags;
 
     read_lock_irqsave(&xxx_lock, flags);
     .. critical section that only reads the info ...
     read_unlock_irqrestore(&xxx_lock, flags);
 
     write_lock_irqsave(&xxx_lock, flags);
     .. read and write exclusive access to the info ...
     write_unlock_irqrestore(&xxx_lock, flags);

The above kind of lock may be useful for complex data structures like linked lists, especially searching for entries without changing the list itself. The read lock allows many concurrent readers. Anything that changes the list will have to get the write lock.

NOTE! RCU is better for list traversal, but requires careful attention to design detail (see Documentation/RCU/listRCU.txt).

Also, you cannot “upgrade” a read-lock to a write-lock, so if you at any time need to do any changes (even if you don’t do it every time), you have to get the write-lock at the very beginning.

NOTE! We are working hard to remove reader-writer spinlocks in most cases, so please don’t add a new one without consensus. (Instead, see Documentation/RCU/rcu.txt for complete information.)

Lesson 3: spinlocks revisited.

The single spin-lock primitives above are by no means the only ones. They are the most safe ones, and the ones that work under all circumstances, but partly because they are safe they are also fairly slow. They are slower than they’d need to be, because they do have to disable interrupts (which is just a single instruction on a x86, but it’s an expensive one - and on other architectures it can be worse).

这里说的因为前两个版本安全，所以它们慢，这么说的原因，是因为，它们加锁的方式限 制了并行度的提高，以牺牲其他线程的运行来保证安全，这影响了整体的运行效率。

If you have a case where you have to protect a data structure across several CPU’s and you want to use spinlocks you can potentially use cheaper versions of the spinlocks. IF you know that the spinlocks are never used in interrupt handlers, you can use the non-irq versions:

non-irq版本的自旋锁指的是，没有屏蔽中断的自旋锁，当线程进入临界区时，如果这个 时候有中断到达，该中断信号将会被中断处理函数处理，而不是像自旋锁中最简单的那个 版本一样将之irqsave\irqrestore。

    spin_lock(&lock);
    ...
    spin_unlock(&lock);

(and the equivalent read-write versions too, of course). The spinlock will guarantee the same kind of exclusive access, and it will be much faster. This is useful if you know that the data in question is only ever manipulated from a “process context”, ie no interrupts involved.

The reasons you mustn’t use these versions if you have interrupts that play with the spinlock is that you can get deadlocks:

    spin_lock(&lock);
    ...
            <- interrupt comes in:
                    spin_lock(&lock);

    如果在处理器1上加了自旋锁，在进入临界区之后，如果在相同的处理器上有中
    断请求，并且处理函数中也请求对相同的自旋锁进行加锁，此时就会发生死锁;
    如果该中断是在不同的处理器上的话，则不会引发死锁。

    为什么会这样呢，前面讲述各个版本的自旋锁之前，我们提到了自旋锁的实现与
    具体的cpu架构以及特殊的汇编指令有关，好的，现在我们讲一下x86架构下，一
    个non-irq版本的自旋锁的实现（详细信息参看wiki）：

    ; Intel syntax
     
    locked:        ; The lock variable. 1 = locked, 0 = unlocked.
         dd      0
    spin_lock:
         mov     eax, 1          ; Set the EAX register to 1.

         xchg    eax, [locked]   ; Atomically swap the EAX register with
                                 ; the lock variable.
                                 ; This will always store 1 to the lock, leaving
                                 ; the previous value in the EAX register.
         test    eax, eax        ; Test EAX with itself. Among other things, this will
                                 ; set the processor's Zero Flag if EAX is 0.
                                 ; If EAX is 0, then the lock was unlocked and
                                 ; we just locked it.
                                 ; Otherwise, EAX is 1 and we didn't acquire the lock.  
         jnz     spin_lock       ; Jump back to the MOV instruction if the Zero Flag is
                                 ;  not set; the lock was previously locked, and so
                                 ; we need to spin until it becomes unlocked.
         ret                     ; The lock has been acquired, return to the calling 
                                 ;  function.
    spin_unlock:
         mov     eax, 0          ; Set the EAX register to 0.
         xchg    eax, [locked]   ; Atomically swap the EAX register with
                                 ;  the lock variable.
         ret                     ; The lock has been released.

where [an interrupt] tries to lock an already locked variable. This is ok if [the other interrupt] happens on another CPU, but it is not ok if the interrupt happens on the same CPU that already holds the lock, because the lock will obviously never be released (because the interrupt is waiting for the lock, and the lock-holder is interrupted by the interrupt and will not continue until the interrupt has been processed).

这段话很重要，我翻译翻译！ 在翻译之前，需要指明，文档中有几个地方写的不是很好 ，比如 the other interrupt，其实这个the other interrupt指的就是前面的an interrupt，不指出来理解起来就是误解。

首先non-irq版本的自旋锁不会屏蔽中断，有中断到达的时候，仍然会对其进行中断处理 ，这一点要明确。

【当某个中断试图锁定一个已经被锁定的变量时，如果这个中断是在另一个cpu上到达， 那么这种情况下是可行的：

在当前cpu1上一个线程已经锁定了该变量（non-irq锁），这个时候中断到达到达
cpu2，然后cpu2进入中断的中断处理函数，处理函数中请求对该变量再次加锁，这个
时候，cpu不会允许该加锁，参考上面x86中spinlock的实现，当前[locked]中值为1
，xchg之后，eax为1，test eax,eax，标志寄存器Z为1，jnz spin_lock继续自旋，
可见此时加锁没有成功，中断会继续自旋直到加锁成功。

如果要加锁成功，就要等到cpu1上的持有锁的线程释放锁，只要它释放了锁，cpu2上
的执行中断处理函数的线程就能够成功对其、进行加锁，二者不会构成死锁。

所以说这种情形下，是可行的！

】

【当某个中断试图锁定一个已经被锁定的变量时，如果这个中断与当前中断在相同的cpu上 到达，那么这种情况下是不可行的：

在当前cpu上一个线程已经锁定了该变量（non-irq锁），这个时候中断到达，然后进
入中断的中断处理函数，处理函数中请求对该变量再次加锁，这个时候，cpu不会允
许该加锁，参考上面x86中spinlock的实现，当前[locked]中值为1，xchg之后，eax
为1，test eax,eax，标志寄存器Z为1，jnz spin_lock继续自旋，可见此时加锁没有
成功，中断1会继续自旋直到加锁成功，但是，只有持有该锁的当前线程被中断了，
释放锁的代码不可能被执行，也就是说中断处理函数中会一直阻塞不会返回。中断处
理函数请求加锁，而当前线程作为锁的持有者，又不释放锁，从而造成死锁。

所以说这种情形下，是不可行的！

】

(This is also the reason why the irq-versions of the spinlocks only need to disable the local interrupts - it’s ok to use spinlocks in interrupts on other CPU’s, because an interrupt on another CPU doesn’t interrupt the CPU that holds the lock, so the lock-holder can continue and eventually releases the lock).

Note that you can be clever with read-write locks and interrupts. For example, if you know that the interrupt only ever gets a read-lock, then you can use a non-irq version of read locks everywhere - because they don’t block on each other (and thus there is no dead-lock wrt interrupts. But when you do the write-lock, you have to use the irq-safe version.

For an example of being clever with rw-locks, see the “waitqueue_lock” handling in kernel/sched.c - nothing ever changes a wait-queue from within an interrupt, they only read the queue in order to know whom to wake up. So read-locks are safe (which is good: they are very common indeed), while write-locks need to protect themselves against interrupts.

Reference information:

For dynamic initialization, use spin_lock_init() or rwlock_init() as appropriate:

spinlock_t xxx_lock; rwlock_t xxx_rw_lock;

static int __init xxx_init(void) { spin_lock_init(&xxx_lock); rwlock_init(&xxx_rw_lock); … }

module_init(xxx_init);

For static initialization, use DEFINE_SPINLOCK() / DEFINE_RWLOCK() or __SPIN_LOCK_UNLOCKED() / __RW_LOCK_UNLOCKED() as appropriate.

[16] sparse.txt Using sparse for typechecking

[17] sgi-viws.txt

The SGI Visual Workstations (models 320 and 540) are based around the Cobalt, Lithium, and Arsenic ASICs. The Cobalt ASIC is the main system ASIC which interfaces the 1-4 IA32 cpus, the memory system, and the I/O system in the Lithium ASIC. The Cobalt ASIC also contains the 3D gfx rendering engine which renders to main system memory – part of which is used as the frame buffer which is DMA’ed to a video connector using the Arsenic ASIC. A PIIX4 chip and NS87307 are used to provide legacy device support (IDE, serial, floppy, and parallel).

The Visual Workstation chipset largely conforms to the PC architecture with some notable exceptions such as interrupt handling.

[18] sgi-ioc4.txt

The SGI IOC4 PCI device is a bit of a strange beast, so some notes on it are in order.

First, even though the IOC4 performs multiple functions, such as an IDE controller, a serial controller, a PS/2 keyboard/mouse controller, and an external interrupt mechanism, it’s not implemented as a multifunction device. The consequence of this from a software standpoint is that all these functions share a single IRQ, and they can’t all register to own the same PCI device ID. To make matters a bit worse, some of the register blocks (and even registers themselves) present in IOC4 are mixed-purpose between these several functions, meaning that there’s no clear “owning” device driver.

The solution is to organize the IOC4 driver into several independent drivers, “ioc4”, “sgiioc4”, and “ioc4_serial”. Note that there is no PS/2 controller driver as this functionality has never been wired up on a shipping IO card.

[19] serial-console.txt

Linux Serial Console

To use a serial port as console you need to compile the support into your kernel - by default it is not compiled in. For PC style serial ports it’s the config option next to “Standard/generic (dumb) serial support”. You must compile serial support into the kernel and not as a module.

It is possible to specify multiple devices for console output. You can define a new kernel command line option to select which device(s) to use for console output.

The format of this option is:

console=device,options

device: tty0 for the foreground virtual console ttyX for any other virtual console ttySx for a serial port lp0 for the first parallel port ttyUSB0 for the first USB serial device

options: depend on the driver. For the serial port this defines the baudrate/parity/bits/flow control of the port, in the format BBBBPNF, where BBBB is the speed, P is parity (n/o/e), N is number of bits, and F is flow control (‘r’ for RTS). Default is 9600n8. The maximum baudrate is 115200.

You can specify multiple console= options on the kernel command line. Output will appear on all of them. The last device will be used when you open /dev/console. So, for example:

console=ttyS1,9600 console=tty0

defines that opening /dev/console will get you the current foreground virtual console, and kernel messages will appear on both the VGA console and the 2nd serial port (ttyS1 or COM2) at 9600 baud.

Note that you can only define one console per device type (serial, video).

If no console device is specified, the first device found capable of acting as a system console will be used. At this time, the system first looks for a VGA card and then for a serial port. So if you don’t have a VGA card in your system the first serial port will automatically become the console.

You will need to create a new device to use /dev/console. The official /dev/console is now character device 5,1.

(You can also use a network device as a console. See Documentation/networking/netconsole.txt for information on that.)

Here’s an example that will use /dev/ttyS1 (COM2) as the console. Replace the sample values as needed.

1. Create /dev/console (real console) and /dev/tty0 (master virtual console):

cd /dev rm -f console tty0 mknod -m 622 console c 5 1 mknod -m 622 tty0 c 4 0

2. LILO can also take input from a serial device. This is a very useful option. To tell LILO to use the serial port: In lilo.conf (global section):

serial = 1,9600n8 (ttyS1, 9600 bd, no parity, 8 bits)

3. Adjust to kernel flags for the new kernel, again in lilo.conf (kernel section)

append = “console=ttyS1,9600”

4. Make sure a getty runs on the serial port so that you can login to it once the system is done booting. This is done by adding a line like this to /etc/inittab (exact syntax depends on your getty):

S1:23:respawn:/sbin/getty -L ttyS1 9600 vt100

5. Init and /etc/ioctl.save

Sysvinit remembers its stty settings in a file in /etc, called `/etc/ioctl.save'. REMOVE THIS FILE before using the serial console for the first time, because otherwise init will probably set the baudrate to 38400 (baudrate of the virtual console).

6. /dev/console and X Programs that want to do something with the virtual console usually open /dev/console. If you have created the new /dev/console device, and your console is NOT the virtual console some programs will fail. Those are programs that want to access the VT interface, and use /dev/console instead of /dev/tty0. Some of those programs are:

Xfree86, svgalib, gpm, SVGATextMode

It should be fixed in modern versions of these programs though.

Note that if you boot without a console= option (or with console=/dev/tty0), /dev/console is the same as /dev/tty0. In that case everything will still work.

[20] rtc.txt

Real Time Clock (RTC) Drivers for Linux

[21] rt-mutex.txt

RT-mutex subsystem with PI support

这个地方PI指的是Priority Inheritance。

RT-mutexes with priority inheritance are used to support PI-futexes, which enable pthread_mutex_t priority inheritance attributes (PTHREAD_PRIO_INHERIT). [See Documentation/pi-futex.txt for more details about PI-futexes.]

This technology was developed in the -rt tree and streamlined for pthread_mutex support.

Basic principles: ##

RT-mutexes extend the semantics of simple mutexes by the priority inheritance protocol. RT-mutexes通过优先级继承协议，扩展了简单mutex的语义。

A low priority owner of a rt-mutex inherits the priority of a higher priority waiter until the rt-mutex is released. If the temporarily boosted owner blocks on a rt-mutex itself it propagates the priority boosting to the owner of the other rt_mutex it gets blocked on. The priority boosting is immediately removed once the rt_mutex has been unlocked.

rt-mutex的一个低优先级持有者，可以继承等待该rt-mutex的一个高优先级任务的优先级 ，低优先级持有者获取了高优先级任务的优先级之后，在内核任务调度时会获取更多的机 会，能够尽快执行完任务，更早地释放rt-mutex，从而让高优先级任务不用因为等待低优 先级任务释放锁而浪费太多时间。在低优先级任务释放锁之后，将恢复到以前的低优先级 。

假如一个获取了rt-mutex（记为m1）的低优先级任务继承了一个等待该锁的高优先级任务 的优先级，此时如果该低优先级任务还希望获取另一个rt-mutex（记为m2），那么该低优 先级会将继承到的高优先级任务的优先级传递给锁m2的持有者。如果m2的持有者因为获取 高优先级提前完成了任务并释放锁，那么m1的持有者也会提前获得锁m2并尽快完成任务， 并释放锁m1、m2，从而使得高优先级任务尽快获得锁m1.这样看来，rt-mutex优先级的继 承，对系统整体性能来说会是一大改进。

This approach allows us to shorten the block of high-prio tasks on mutexes which protect shared resources. Priority inheritance is not a magic bullet for poorly designed applications, but it allows well-designed applications to use userspace locks in critical parts of an high priority thread, without losing determinism.

The enqueueing of the waiters into the rtmutex waiter list is done in priority order. For same priorities FIFO order is chosen. For each rtmutex, only the top priority waiter is enqueued into the owner’s priority waiters list. This list too queues in priority order. Whenever the top priority waiter of a task changes (for example it timed out or got a signal), the priority of the owner task is readjusted. [The priority enqueueing is handled by “plists”, see

等待rt-mutex的任务按照优先级顺序进入该rt-mutex的等待队列。如果任务是相同的优先 级，则按照先请求先进入队列的原则。对于每一个rt-mutex，只有优先级最高的处于等待 状态的任务会被选择进入锁持有者的优先级等待者队列中，并且这个队列也是按照优先级 进行排序。不管什么时候，这个任务的优先级等待队列的最高优先级的任务发生改变，这 个任务的优先级都会被进行重新调整。

include/linux/plist.h for more details.]

RT-mutexes are optimized for fastpath operations and have no internal locking overhead when locking an uncontended mutex or unlocking a mutex without waiters. The optimized fastpath operations require cmpxchg support. [If that is not available then the rt-mutex internal spinlock is used]

The state of the rt-mutex is tracked via the owner field of the rt-mutex structure:

rt_mutex->owner holds the task_struct pointer of the owner. Bit 0 and 1 are used to keep track of the “owner is pending” and “rtmutex has waiters” state.

owner bit1 bit0 NULL 0 0 mutex is free (fast acquire possible) NULL 0 1 invalid state NULL 1 0 Transitional state* NULL 1 1 invalid state taskpointer 0 0 mutex is held (fast release possible) taskpointer 0 1 task is pending owner taskpointer 1 0 mutex is held and has waiters taskpointer 1 1 task is pending owner and mutex has waiters

Pending-ownership handling is a performance optimization: pending-ownership is assigned to the first (highest priority) waiter of the mutex, when the mutex is released. The thread is woken up and once it starts executing it can acquire the mutex. Until the mutex is taken by it (bit 0 is cleared) a competing higher priority thread can “steal” the mutex which puts the woken up thread back on the waiters list.

The pending-ownership optimization is especially important for the uninterrupted workflow of high-prio tasks which repeatedly takes/releases locks that have lower-prio waiters. Without this optimization the higher-prio thread would ping-pong to the lower-prio task [because at unlock time we always assign a new owner].

(*) The “mutex has waiters” bit gets set to take the lock. If the lock doesn’t already have an owner, this bit is quickly cleared if there are no waiters. So this is a transitional state to synchronize with looking at the owner field of the mutex and the mutex owner releasing the lock.

[22] rt-mutex-design.txt

RT-mutex implementation design ##

This document tries to describe the design of the rtmutex.c implementation. It doesn’t describe the reasons why rtmutex.c exists. For that please see Documentation/rt-mutex.txt. Although this document does explain problems that happen without this code, but that is in the concept to understand what the code actually is doing.

这个文档解释rtmutex的具体设计，关于为什么要实现rtmutex，请参考前面21这部分。

The goal of this document is to help others understand the priority inheritance (PI) algorithm that is used, as well as reasons for the decisions that were made to implement PI in the manner that was done.

这个文档的目的是为了帮助别人理解使用的优先级继承算法，以及实现该算法过程中采用 的某些相关决策的原因。

Unbounded Priority Inversion ##

Priority inversion is when a lower priority process executes while a higher priority process wants to run. This happens for several reasons, and most of the time it can’t be helped. Anytime a high priority process wants to use a resource that a lower priority process has (a mutex for example), the high priority process must wait until the lower priority process is done with the resource. This is a priority inversion. What we want to prevent is something called unbounded priority inversion. That is when the high priority process is prevented from running by a lower priority process for an undetermined amount of time.

理解优先级反转，优先级反转指的是，当一个低优先级进程执行的时候，同时有一个高优 先级进程也希望执行。这在很多情况下都会发生，并且大多数情况下是无法被干预的。某 个时候，如果一个高优先级进车功能希望使用一个低优先级进程拥有的资源，例如一个锁 ，高优先级进程不得不等待到低优先级进程释放这个资源，然后才能获取到该资源，并继 续执行。本来高优先级的进程应该先于低优先级进程执行，但是这里，却因为等待低优先 级进程释放资源而等待，并且等待的时间是无法确定的，这种情况我们称之为优先级反转 。 我们希望能够阻止不受限制的优先级反转，即，当一个高优先级进程被一个低优先级进程 阻塞，并且阻塞时间不缺定，我们需要阻止或者尽量避免这种情况。

The classic example of unbounded priority inversion is were you have three processes, let’s call them processes A, B, and C, where A is the highest priority process, C is the lowest, and B is in between. A tries to grab a lock that C owns and must wait and lets C run to release the lock. But in the meantime, B executes, and since B is of a higher priority than C, it preempts C, but by doing so, it is in fact preempting A which is a higher priority process. Now there’s no way of knowing how long A will be sleeping waiting for C to release the lock, because for all we know, B is a CPU hog and will never give C a chance to release the lock. This is called unbounded priority inversion.

举个不受限制的优先级反转的例子，假定有3个进程A、B、C，优先级依次降低，现在A希 望获取一个锁，这个锁被C持有，因此A需要等待到C执行到释放锁后才能继续向下执行， 假定在C释放锁之前，B开始执行，由于B优先级比C高，有可能B会抢占CPU而先于C执行， 假定B占用的CPU时间比较长，例如B是一个while(1)循环，它不会给C机会区释放锁，因此 间接地阻止了最高优先级进程A的执行，并且A继续等待的事件会很长甚至是永久，这被称 之为不受限制的优先级反转。

Here’s a little ASCII art to show the problem.

grab lock L1 (owned by C)
      |
 A ---+
         C preempted by B
           |
 C    +----+
 
 B         +-------->
                 B now keeps A from running.

Priority Inheritance (PI) ##

There are several ways to solve this issue, but other ways are out of scope for this document. Here we only discuss PI.

有很多方法来解决不受限制的优先级反转问题，但是这里值讨论优先级继承PI这种方法。

PI is where a process inherits the priority of another process if the other process blocks on a lock owned by the current process. To make this easier to understand, let’s use the previous example, with processes A, B, and C again.

This time, when A blocks on the lock owned by C, C would inherit the priority of A. So now if B becomes runnable, it would not preempt C, since C now has the high priority of A. As soon as C releases the lock, it loses its inherited priority, and A then can continue with the resource that C had.

以上个例子为例，引入PI，这次，当A等待C释放锁而阻塞时，C会继承A的优先级。所以如 果B运行的时候，它不会抢占C的CPU，因为C已经继承了A的优先级，A的优先级是最高的。 一旦C释放了锁之后，它就会失去从A继承来的优先级，A然后就会获得C释放的锁并继续执 行。

Terminology ##

Here I explain some terminology that is used in this document to help describe the design that is used to implement PI.

PI chain - The PI chain is an ordered series of locks and processes that cause processes to inherit priorities from a previous process that is blocked on one of its locks. This is described in more detail later in this document.

       优先级继承链。

mutex - In this document, to differentiate from locks that implement PI and spin locks that are used in the PI code, from now on the PI locks will be called a mutex.

       在这篇文档中，为了区分实现了优先级继承的锁，和实现该锁的代码中用到
       的普通的自旋锁，从现在开始，实现了优先级继承的锁，将被称为mutex。

lock - In this document from now on, I will use the term lock when referring to spin locks that are used to protect parts of the PI algorithm. These locks disable preemption for UP (when CONFIG_PREEMPT is enabled) and on SMP prevents multiple CPUs from entering critical sections simultaneously.

       在这篇文档中，将使用lock指代自旋锁。

spin lock - Same as lock above.

        自旋锁，与我们上面提到的lock，在描述PI锁的时候，将表示相同的概念。

waiter - A waiter is a struct that is stored on the stack of a blocked process. Since the scope of the waiter is within the code for a process being blocked on the mutex, it is fine to allocate the waiter on the process’s stack (local variable). This structure holds a pointer to the task, as well as the mutex that the task is blocked on. It also has the plist node structures to place the task in the waiter_list of a mutex as well as the pi_list of a mutex owner task (described below).

       waiter is sometimes used in reference to the task that is waiting
       on a mutex. This is the same as waiter->task.

waiters - A list of processes that are blocked on a mutex.

top waiter - The highest priority process waiting on a specific mutex.

top pi waiter - The highest priority process waiting on one of the mutexes that a specific process owns.

Note: task and process are used interchangeably in this document, mostly to differentiate between two processes that are being described together.

PI chain ##

The PI chain is a list of processes and mutexes that may cause priority inheritance to take place. Multiple chains may converge, but a chain would never diverge, since a process can’t be blocked on more than one mutex at a time.

Example:

Process: A, B, C, D, E Mutexes: L1, L2, L3, L4

A owns: L1
        B blocked on L1
        B owns L2
               C blocked on L2
               C owns L3
                      D blocked on L3
                      D owns L4
                             E blocked on L4

The chain would be:

E->L4->D->L3->C->L2->B->L1->A

To show where two chains merge, we could add another process F and another mutex L5 where B owns L5 and F is blocked on mutex L5.

The chain for F would be:

F->L5->B->L1->A

Since a process may own more than one mutex, but never be blocked on more than one, the chains merge.

Here we show both chains:

E->L4->D->L3->C->L2-+
                    |
                    +->B->L1->A
                    |
              F->L5-+

For PI to work, the processes at the right end of these chains (or we may also call it the Top of the chain) must be equal to or higher in priority than the processes to the left or below in the chain.

Also since a mutex may have more than one process blocked on it, we can have multiple chains merge at mutexes. If we add another process G that is blocked on mutex L2:

G->L2->B->L1->A

And once again, to show how this can grow I will show the merging chains again.

E->L4->D->L3->C-+
                +->L2-+
                |     |
              G-+     +->B->L1->A
                      |
                F->L5-+

Plist ##

Before I go further and talk about how the PI chain is stored through lists on both mutexes and processes, I’ll explain the plist. This is similar to the struct list_head functionality that is already in the kernel. The implementation of plist is out of scope for this document, but it is very important to understand what it does.

There are a few differences between plist and list, the most important one being that plist is a priority sorted linked list. This means that the priorities of the plist are sorted, such that it takes O(1) to retrieve the highest priority item in the list. Obviously this is useful to store processes based on their priorities.

Another difference, which is important for implementation, is that, unlike list, the head of the list is a different element than the nodes of a list. So the head of the list is declared as struct plist_head and nodes that will be added to the list are declared as struct plist_node.

Mutex Waiter List ##

Every mutex keeps track of all the waiters that are blocked on itself. The mutex has a plist to store these waiters by priority. This list is protected by a spin lock that is located in the struct of the mutex. This lock is called wait_lock. Since the modification of the waiter list is never done in interrupt context, the wait_lock can be taken without disabling interrupts.

Task PI List ##

To keep track of the PI chains, each process has its own PI list. This is a list of all top waiters of the mutexes that are owned by the process. Note that this list only holds the top waiters and not all waiters that are blocked on mutexes owned by the process.

The top of the task’s PI list is always the highest priority task that is waiting on a mutex that is owned by the task. So if the task has inherited a priority, it will always be the priority of the task that is at the top of this list.

This list is stored in the task structure of a process as a plist called pi_list. This list is protected by a spin lock also in the task structure, called pi_lock. This lock may also be taken in interrupt context, so when locking the pi_lock, interrupts must be disabled.

Depth of the PI Chain ##

The maximum depth of the PI chain is not dynamic, and could actually be defined. But is very complex to figure it out, since it depends on all the nesting of mutexes. Let’s look at the example where we have 3 mutexes, L1, L2, and L3, and four separate functions func1, func2, func3 and func4. The following shows a locking order of L1->L2->L3, but may not actually be directly nested that way.

void func1(void) { mutex_lock(L1);

/* do anything */

mutex_unlock(L1);

}

void func2(void) { mutex_lock(L1); mutex_lock(L2);

/* do something */

mutex_unlock(L2);
mutex_unlock(L1);

}

void func3(void) { mutex_lock(L2); mutex_lock(L3);

/* do something else */

mutex_unlock(L3);
mutex_unlock(L2);

}

void func4(void) { mutex_lock(L3);

/* do something again */

mutex_unlock(L3);

}

Now we add 4 processes that run each of these functions separately. Processes A, B, C, and D which run functions func1, func2, func3 and func4 respectively, and such that D runs first and A last. With D being preempted in func4 in the “do something again” area, we have a locking that follows:

D owns L3 C blocked on L3 C owns L2 B blocked on L2 B owns L1 A blocked on L1

And thus we have the chain A->L1->B->L2->C->L3->D.

This gives us a PI depth of 4 (four processes), but looking at any of the functions individually, it seems as though they only have at most a locking depth of two. So, although the locking depth is defined at compile time, it still is very difficult to find the possibilities of that depth.

Now since mutexes can be defined by user-land applications, we don’t want a DOS type of application that nests large amounts of mutexes to create a large PI chain, and have the code holding spin locks while looking at a large amount of data. So to prevent this, the implementation not only implements a maximum lock depth, but also only holds at most two different locks at a time, as it walks the PI chain. More about this below.

Mutex owner and flags ##

The mutex structure contains a pointer to the owner of the mutex. If the mutex is not owned, this owner is set to NULL. Since all architectures have the task structure on at least a four byte alignment (and if this is not true, the rtmutex.c code will be broken!), this allows for the two least significant bits to be used as flags. This part is also described in Documentation/rt-mutex.txt, but will also be briefly described here.

Bit 0 is used as the “Pending Owner” flag. This is described later. Bit 1 is used as the “Has Waiters” flags. This is also described later in more detail, but is set whenever there are waiters on a mutex.

cmpxchg Tricks ##

Some architectures implement an atomic cmpxchg (Compare and Exchange). This is used (when applicable) to keep the fast path of grabbing and releasing mutexes short.

cmpxchg is basically the following function performed atomically:

unsigned long _cmpxchg(unsigned long *A, unsigned long *B, unsigned long *C) { unsigned long T = *A; if (*A == *B) { *A = *C; } return T; } #define cmpxchg(a,b,c) _cmpxchg(&a,&b,&c)

This is really nice to have, since it allows you to only update a variable if the variable is what you expect it to be. You know if it succeeded if the return value (the old value of A) is equal to B.

The macro rt_mutex_cmpxchg is used to try to lock and unlock mutexes. If the architecture does not support CMPXCHG, then this macro is simply set to fail every time. But if CMPXCHG is supported, then this will help out extremely to keep the fast path short.

The use of rt_mutex_cmpxchg with the flags in the owner field help optimize the system for architectures that support it. This will also be explained later in this document.

Priority adjustments ##

The implementation of the PI code in rtmutex.c has several places that a process must adjust its priority. With the help of the pi_list of a process this is rather easy to know what needs to be adjusted.

The functions implementing the task adjustments are rt_mutex_adjust_prio, __rt_mutex_adjust_prio (same as the former, but expects the task pi_lock to already be taken), rt_mutex_getprio, and rt_mutex_setprio.

rt_mutex_getprio and rt_mutex_setprio are only used in __rt_mutex_adjust_prio.

rt_mutex_getprio returns the priority that the task should have. Either the task’s own normal priority, or if a process of a higher priority is waiting on a mutex owned by the task, then that higher priority should be returned. Since the pi_list of a task holds an order by priority list of all the top waiters of all the mutexes that the task owns, rt_mutex_getprio simply needs to compare the top pi waiter to its own normal priority, and return the higher priority back.

(Note: if looking at the code, you will notice that the lower number of prio is returned. This is because the prio field in the task structure is an inverse order of the actual priority. So a “prio” of 5 is of higher priority than a “prio” of 10.)

__rt_mutex_adjust_prio examines the result of rt_mutex_getprio, and if the result does not equal the task’s current priority, then rt_mutex_setprio is called to adjust the priority of the task to the new priority. Note that rt_mutex_setprio is defined in kernel/sched.c to implement the actual change in priority.

It is interesting to note that __rt_mutex_adjust_prio can either increase or decrease the priority of the task. In the case that a higher priority process has just blocked on a mutex owned by the task, __rt_mutex_adjust_prio would increase/boost the task’s priority. But if a higher priority task were for some reason to leave the mutex (timeout or signal), this same function would decrease/unboost the priority of the task. That is because the pi_list always contains the highest priority task that is waiting on a mutex owned by the task, so we only need to compare the priority of that top pi waiter to the normal priority of the given task.

High level overview of the PI chain walk ##

The PI chain walk is implemented by the function rt_mutex_adjust_prio_chain.

The implementation has gone through several iterations, and has ended up with what we believe is the best. It walks the PI chain by only grabbing at most two locks at a time, and is very efficient.

The rt_mutex_adjust_prio_chain can be used either to boost or lower process priorities.

rt_mutex_adjust_prio_chain is called with a task to be checked for PI (de)boosting (the owner of a mutex that a process is blocking on), a flag to check for deadlocking, the mutex that the task owns, and a pointer to a waiter that is the process’s waiter struct that is blocked on the mutex (although this parameter may be NULL for deboosting).

For this explanation, I will not mention deadlock detection. This explanation will try to stay at a high level.

When this function is called, there are no locks held. That also means that the state of the owner and lock can change when entered into this function.

Before this function is called, the task has already had rt_mutex_adjust_prio performed on it. This means that the task is set to the priority that it should be at, but the plist nodes of the task’s waiter have not been updated with the new priorities, and that this task may not be in the proper locations in the pi_lists and wait_lists that the task is blocked on. This function solves all that.

A loop is entered, where task is the owner to be checked for PI changes that was passed by parameter (for the first iteration). The pi_lock of this task is taken to prevent any more changes to the pi_list of the task. This also prevents new tasks from completing the blocking on a mutex that is owned by this task.

If the task is not blocked on a mutex then the loop is exited. We are at the top of the PI chain.

A check is now done to see if the original waiter (the process that is blocked on the current mutex) is the top pi waiter of the task. That is, is this waiter on the top of the task’s pi_list. If it is not, it either means that there is another process higher in priority that is blocked on one of the mutexes that the task owns, or that the waiter has just woken up via a signal or timeout and has left the PI chain. In either case, the loop is exited, since we don’t need to do any more changes to the priority of the current task, or any task that owns a mutex that this current task is waiting on. A priority chain walk is only needed when a new top pi waiter is made to a task.

The next check sees if the task’s waiter plist node has the priority equal to the priority the task is set at. If they are equal, then we are done with the loop. Remember that the function started with the priority of the task adjusted, but the plist nodes that hold the task in other processes pi_lists have not been adjusted.

Next, we look at the mutex that the task is blocked on. The mutex’s wait_lock is taken. This is done by a spin_trylock, because the locking order of the pi_lock and wait_lock goes in the opposite direction. If we fail to grab the lock, the pi_lock is released, and we restart the loop.

Now that we have both the pi_lock of the task as well as the wait_lock of the mutex the task is blocked on, we update the task’s waiter’s plist node that is located on the mutex’s wait_list.

Now we release the pi_lock of the task.

Next the owner of the mutex has its pi_lock taken, so we can update the task’s entry in the owner’s pi_list. If the task is the highest priority process on the mutex’s wait_list, then we remove the previous top waiter from the owner’s pi_list, and replace it with the task.

Note: It is possible that the task was the current top waiter on the mutex, in which case the task is not yet on the pi_list of the waiter. This is OK, since plist_del does nothing if the plist node is not on any list.

If the task was not the top waiter of the mutex, but it was before we did the priority updates, that means we are deboosting/lowering the task. In this case, the task is removed from the pi_list of the owner, and the new top waiter is added.

Lastly, we unlock both the pi_lock of the task, as well as the mutex’s wait_lock, and continue the loop again. On the next iteration of the loop, the previous owner of the mutex will be the task that will be processed.

Note: One might think that the owner of this mutex might have changed since we just grab the mutex’s wait_lock. And one could be right. The important thing to remember is that the owner could not have become the task that is being processed in the PI chain, since we have taken that task’s pi_lock at the beginning of the loop. So as long as there is an owner of this mutex that is not the same process as the tasked being worked on, we are OK.

Looking closely at the code, one might be confused. The check for the end of the PI chain is when the task isn’t blocked on anything or the task’s waiter structure “task” element is NULL. This check is protected only by the task’s pi_lock. But the code to unlock the mutex sets the task’s waiter structure “task” element to NULL with only the protection of the mutex’s wait_lock, which was not taken yet. Isn’t this a race condition if the task becomes the new owner?

The answer is No! The trick is the spin_trylock of the mutex’s wait_lock. If we fail that lock, we release the pi_lock of the task and continue the loop, doing the end of PI chain check again.

In the code to release the lock, the wait_lock of the mutex is held the entire time, and it is not let go when we grab the pi_lock of the new owner of the mutex. So if the switch of a new owner were to happen after the check for end of the PI chain and the grabbing of the wait_lock, the unlocking code would spin on the new owner’s pi_lock but never give up the wait_lock. So the PI chain loop is guaranteed to fail the spin_trylock on the wait_lock, release the pi_lock, and try again.

If you don’t quite understand the above, that’s OK. You don’t have to, unless you really want to make a proof out of it ;)

Pending Owners and Lock stealing ##

One of the flags in the owner field of the mutex structure is “Pending Owner”. What this means is that an owner was chosen by the process releasing the mutex, but that owner has yet to wake up and actually take the mutex.

Why is this important? Why can’t we just give the mutex to another process and be done with it?

The PI code is to help with real-time processes, and to let the highest priority process run as long as possible with little latencies and delays. If a high priority process owns a mutex that a lower priority process is blocked on, when the mutex is released it would be given to the lower priority process. What if the higher priority process wants to take that mutex again. The high priority process would fail to take that mutex that it just gave up and it would need to boost the lower priority process to run with full latency of that critical section (since the low priority process just entered it).

There’s no reason a high priority process that gives up a mutex should be penalized if it tries to take that mutex again. If the new owner of the mutex has not woken up yet, there’s no reason that the higher priority process could not take that mutex away.

To solve this, we introduced Pending Ownership and Lock Stealing. When a new process is given a mutex that it was blocked on, it is only given pending ownership. This means that it’s the new owner, unless a higher priority process comes in and tries to grab that mutex. If a higher priority process does come along and wants that mutex, we let the higher priority process “steal” the mutex from the pending owner (only if it is still pending) and continue with the mutex.

Taking of a mutex (The walk through) ##

OK, now let’s take a look at the detailed walk through of what happens when taking a mutex.

The first thing that is tried is the fast taking of the mutex. This is done when we have CMPXCHG enabled (otherwise the fast taking automatically fails). Only when the owner field of the mutex is NULL can the lock be taken with the CMPXCHG and nothing else needs to be done.

If there is contention on the lock, whether it is owned or pending owner we go about the slow path (rt_mutex_slowlock).

The slow path function is where the task’s waiter structure is created on the stack. This is because the waiter structure is only needed for the scope of this function. The waiter structure holds the nodes to store the task on the wait_list of the mutex, and if need be, the pi_list of the owner.

The wait_lock of the mutex is taken since the slow path of unlocking the mutex also takes this lock.

We then call try_to_take_rt_mutex. This is where the architecture that does not implement CMPXCHG would always grab the lock (if there’s no contention).

try_to_take_rt_mutex is used every time the task tries to grab a mutex in the slow path. The first thing that is done here is an atomic setting of the “Has Waiters” flag of the mutex’s owner field. Yes, this could really be false, because if the mutex has no owner, there are no waiters and the current task also won’t have any waiters. But we don’t have the lock yet, so we assume we are going to be a waiter. The reason for this is to play nice for those architectures that do have CMPXCHG. By setting this flag now, the owner of the mutex can’t release the mutex without going into the slow unlock path, and it would then need to grab the wait_lock, which this code currently holds. So setting the “Has Waiters” flag forces the owner to synchronize with this code.

Now that we know that we can’t have any races with the owner releasing the mutex, we check to see if we can take the ownership. This is done if the mutex doesn’t have a owner, or if we can steal the mutex from a pending owner. Let’s look at the situations we have here.

1. Has owner that is pending

The mutex has a owner, but it hasn’t woken up and the mutex flag “Pending Owner” is set. The first check is to see if the owner isn’t the current task. This is because this function is also used for the pending owner to grab the mutex. When a pending owner wakes up, it checks to see if it can take the mutex, and this is done if the owner is already set to itself. If so, we succeed and leave the function, clearing the “Pending Owner” bit.

If the pending owner is not current, we check to see if the current priority is higher than the pending owner. If not, we fail the function and return.

There’s also something special about a pending owner. That is a pending owner is never blocked on a mutex. So there is no PI chain to worry about. It also means that if the mutex doesn’t have any waiters, there’s no accounting needed to update the pending owner’s pi_list, since we only worry about processes blocked on the current mutex.

If there are waiters on this mutex, and we just stole the ownership, we need to take the top waiter, remove it from the pi_list of the pending owner, and add it to the current pi_list. Note that at this moment, the pending owner is no longer on the list of waiters. This is fine, since the pending owner would add itself back when it realizes that it had the ownership stolen from itself. When the pending owner tries to grab the mutex, it will fail in try_to_take_rt_mutex if the owner field points to another process.

2. No owner

If there is no owner (or we successfully stole the lock), we set the owner of the mutex to current, and set the flag of “Has Waiters” if the current mutex actually has waiters, or we clear the flag if it doesn’t. See, it was OK that we set that flag early, since now it is cleared.

3. Failed to grab ownership

The most interesting case is when we fail to take ownership. This means that there exists an owner, or there’s a pending owner with equal or higher priority than the current task.

We’ll continue on the failed case.

If the mutex has a timeout, we set up a timer to go off to break us out of this mutex if we failed to get it after a specified amount of time.

Now we enter a loop that will continue to try to take ownership of the mutex, or fail from a timeout or signal.

Once again we try to take the mutex. This will usually fail the first time in the loop, since it had just failed to get the mutex. But the second time in the loop, this would likely succeed, since the task would likely be the pending owner.

If the mutex is TASK_INTERRUPTIBLE a check for signals and timeout is done here.

The waiter structure has a “task” field that points to the task that is blocked on the mutex. This field can be NULL the first time it goes through the loop or if the task is a pending owner and had its mutex stolen. If the “task” field is NULL then we need to set up the accounting for it.

Task blocks on mutex ##

The accounting of a mutex and process is done with the waiter structure of the process. The “task” field is set to the process, and the “lock” field to the mutex. The plist nodes are initialized to the processes current priority.

Since the wait_lock was taken at the entry of the slow lock, we can safely add the waiter to the wait_list. If the current process is the highest priority process currently waiting on this mutex, then we remove the previous top waiter process (if it exists) from the pi_list of the owner, and add the current process to that list. Since the pi_list of the owner has changed, we call rt_mutex_adjust_prio on the owner to see if the owner should adjust its priority accordingly.

If the owner is also blocked on a lock, and had its pi_list changed (or deadlock checking is on), we unlock the wait_lock of the mutex and go ahead and run rt_mutex_adjust_prio_chain on the owner, as described earlier.

Now all locks are released, and if the current process is still blocked on a mutex (waiter “task” field is not NULL), then we go to sleep (call schedule).

Waking up in the loop ##

The schedule can then wake up for a few reasons.

1. we were given pending ownership of the mutex.
2. we received a signal and was TASK_INTERRUPTIBLE
3. we had a timeout and was TASK_INTERRUPTIBLE

In any of these cases, we continue the loop and once again try to grab the ownership of the mutex. If we succeed, we exit the loop, otherwise we continue and on signal and timeout, will exit the loop, or if we had the mutex stolen we just simply add ourselves back on the lists and go back to sleep.

Note: For various reasons, because of timeout and signals, the steal mutex algorithm needs to be careful. This is because the current process is still on the wait_list. And because of dynamic changing of priorities, especially on SCHED_OTHER tasks, the current process can be the highest priority task on the wait_list.

Failed to get mutex on Timeout or Signal ##

If a timeout or signal occurred, the waiter’s “task” field would not be NULL and the task needs to be taken off the wait_list of the mutex and perhaps pi_list of the owner. If this process was a high priority process, then the rt_mutex_adjust_prio_chain needs to be executed again on the owner, but this time it will be lowering the priorities.

Unlocking the Mutex ##

The unlocking of a mutex also has a fast path for those architectures with CMPXCHG. Since the taking of a mutex on contention always sets the “Has Waiters” flag of the mutex’s owner, we use this to know if we need to take the slow path when unlocking the mutex. If the mutex doesn’t have any waiters, the owner field of the mutex would equal the current process and the mutex can be unlocked by just replacing the owner field with NULL.

If the owner field has the “Has Waiters” bit set (or CMPXCHG is not available), the slow unlock path is taken.

The first thing done in the slow unlock path is to take the wait_lock of the mutex. This synchronizes the locking and unlocking of the mutex.

A check is made to see if the mutex has waiters or not. On architectures that do not have CMPXCHG, this is the location that the owner of the mutex will determine if a waiter needs to be awoken or not. On architectures that do have CMPXCHG, that check is done in the fast path, but it is still needed in the slow path too. If a waiter of a mutex woke up because of a signal or timeout between the time the owner failed the fast path CMPXCHG check and the grabbing of the wait_lock, the mutex may not have any waiters, thus the owner still needs to make this check. If there are no waiters then the mutex owner field is set to NULL, the wait_lock is released and nothing more is needed.

If there are waiters, then we need to wake one up and give that waiter pending ownership.

On the wake up code, the pi_lock of the current owner is taken. The top waiter of the lock is found and removed from the wait_list of the mutex as well as the pi_list of the current owner. The task field of the new pending owner’s waiter structure is set to NULL, and the owner field of the mutex is set to the new owner with the “Pending Owner” bit set, as well as the “Has Waiters” bit if there still are other processes blocked on the mutex.

The pi_lock of the previous owner is released, and the new pending owner’s pi_lock is taken. Remember that this is the trick to prevent the race condition in rt_mutex_adjust_prio_chain from adding itself as a waiter on the mutex.

We now clear the “pi_blocked_on” field of the new pending owner, and if the mutex still has waiters pending, we add the new top waiter to the pi_list of the pending owner.

Finally we unlock the pi_lock of the pending owner and wake it up.

[23] robust-futexes.txt

Background ##

what are robust futexes? To answer that, we first need to understand what futexes are: normal futexes are special types of locks that in the noncontended case can be acquired/released from userspace without having to enter the kernel.

A futex is in essence a user-space address, e.g. a 32-bit lock variable field. If userspace notices contention (the lock is already owned and someone else wants to grab it too) then the lock is marked with a value that says “there’s a waiter pending”, and the sys_futex(FUTEX_WAIT) syscall is used to wait for the other guy to release it. The kernel creates a ‘futex queue’ internally, so that it can later on match up the waiter with the waker - without them having to know about each other. When the owner thread releases the futex, it notices (via the variable value) that there were waiter(s) pending, and does the sys_futex(FUTEX_WAKE) syscall to wake them up. Once all waiters have taken and released the lock, the futex is again back to ‘uncontended’ state, and there’s no in-kernel state associated with it. The kernel completely forgets that there ever was a futex at that address. This method makes futexes very lightweight and scalable.

“Robustness” is about dealing with crashes while holding a lock: if a process exits prematurely while holding a pthread_mutex_t lock that is also shared with some other process (e.g. yum segfaults while holding a pthread_mutex_t, or yum is kill -9-ed), then waiters for that lock need to be notified that the last owner of the lock exited in some irregular way.

To solve such types of problems, “robust mutex” userspace APIs were created: pthread_mutex_lock() returns an error value if the owner exits prematurely - and the new owner can decide whether the data protected by the lock can be recovered safely.

There is a big conceptual problem with futex based mutexes though: it is the kernel that destroys the owner task (e.g. due to a SEGFAULT), but the kernel cannot help with the cleanup: if there is no ‘futex queue’ (and in most cases there is none, futexes being fast lightweight locks) then the kernel has no information to clean up after the held lock! Userspace has no chance to clean up after the lock either - userspace is the one that crashes, so it has no opportunity to clean up. Catch-22.

In practice, when e.g. yum is kill -9-ed (or segfaults), a system reboot is needed to release that futex based lock. This is one of the leading bugreports against yum.

To solve this problem, the traditional approach was to extend the vma (virtual memory area descriptor) concept to have a notion of ‘pending robust futexes attached to this area’. This approach requires 3 new syscall variants to sys_futex(): FUTEX_REGISTER, FUTEX_DEREGISTER and FUTEX_RECOVER. At do_exit() time, all vmas are searched to see whether they have a robust_head set. This approach has two fundamental problems left:

• it has quite complex locking and race scenarios. The vma-based approach had been pending for years, but they are still not completely reliable.

• they have to scan every vma at sys_exit() time, per thread!

The second disadvantage is a real killer: pthread_exit() takes around 1 microsecond on Linux, but with thousands (or tens of thousands) of vmas every pthread_exit() takes a millisecond or more, also totally destroying the CPU’s L1 and L2 caches!

This is very much noticeable even for normal process sys_exit_group() calls: the kernel has to do the vma scanning unconditionally! (this is because the kernel has no knowledge about how many robust futexes there are to be cleaned up, because a robust futex might have been registered in another task, and the futex variable might have been simply mmap()-ed into this process’s address space).

This huge overhead forced the creation of CONFIG_FUTEX_ROBUST so that normal kernels can turn it off, but worse than that: the overhead makes robust futexes impractical for any type of generic Linux distribution.

So something had to be done.

New approach to robust futexes ##

At the heart of this new approach there is a per-thread private list of robust locks that userspace is holding (maintained by glibc) - which userspace list is registered with the kernel via a new syscall [this registration happens at most once per thread lifetime]. At do_exit() time, the kernel checks this user-space list: are there any robust futex locks to be cleaned up?

In the common case, at do_exit() time, there is no list registered, so the cost of robust futexes is just a simple current->robust_list != NULL comparison. If the thread has registered a list, then normally the list is empty. If the thread/process crashed or terminated in some incorrect way then the list might be non-empty: in this case the kernel carefully walks the list [not trusting it], and marks all locks that are owned by this thread with the FUTEX_OWNER_DIED bit, and wakes up one waiter (if any).

The list is guaranteed to be private and per-thread at do_exit() time, so it can be accessed by the kernel in a lockless way.

There is one race possible though: since adding to and removing from the list is done after the futex is acquired by glibc, there is a few instructions window for the thread (or process) to die there, leaving the futex hung. To protect against this possibility, userspace (glibc) also maintains a simple per-thread ‘list_op_pending’ field, to allow the kernel to clean up if the thread dies after acquiring the lock, but just before it could have added itself to the list. Glibc sets this list_op_pending field before it tries to acquire the futex, and clears it after the list-add (or list-remove) has finished.

That’s all that is needed - all the rest of robust-futex cleanup is done in userspace [just like with the previous patches].

Ulrich Drepper has implemented the necessary glibc support for this new mechanism, which fully enables robust mutexes.

Key differences of this userspace-list based approach, compared to the vma based method:

• it’s much, much faster: at thread exit time, there’s no need to loop over every vma (!), which the VM-based method has to do. Only a very simple ‘is the list empty’ op is done.

• no VM changes are needed - ‘struct address_space’ is left alone.

• no registration of individual locks is needed: robust mutexes dont need any extra per-lock syscalls. Robust mutexes thus become a very lightweight primitive - so they dont force the application designer to do a hard choice between performance and robustness - robust mutexes are just as fast.

• no per-lock kernel allocation happens.

• no resource limits are needed.

• no kernel-space recovery call (FUTEX_RECOVER) is needed.

• the implementation and the locking is “obvious”, and there are no interactions with the VM.

Performance ##

I have benchmarked the time needed for the kernel to process a list of 1 million (!) held locks, using the new method [on a 2GHz CPU]:

• with FUTEX_WAIT set [contended mutex]: 130 msecs
• without FUTEX_WAIT set [uncontended mutex]: 30 msecs

I have also measured an approach where glibc does the lock notification [which it currently does for !pshared robust mutexes], and that took 256 msecs - clearly slower, due to the 1 million FUTEX_WAKE syscalls userspace had to do.

(1 million held locks are unheard of - we expect at most a handful of locks to be held at a time. Nevertheless it’s nice to know that this approach scales nicely.)

Implementation details ##

The patch adds two new syscalls: one to register the userspace list, and one to query the registered list pointer:

asmlinkage long sys_set_robust_list(struct robust_list_head __user *head, size_t len);

asmlinkage long sys_get_robust_list(int pid, struct robust_list_head __user **head_ptr, size_t __user *len_ptr);

List registration is very fast: the pointer is simply stored in current->robust_list. [Note that in the future, if robust futexes become widespread, we could extend sys_clone() to register a robust-list head for new threads, without the need of another syscall.]

So there is virtually zero overhead for tasks not using robust futexes, and even for robust futex users, there is only one extra syscall per thread lifetime, and the cleanup operation, if it happens, is fast and straightforward. The kernel doesn’t have any internal distinction between robust and normal futexes.

If a futex is found to be held at exit time, the kernel sets the following bit of the futex word:

#define FUTEX_OWNER_DIED 0x40000000

and wakes up the next futex waiter (if any). User-space does the rest of the cleanup.

Otherwise, robust futexes are acquired by glibc by putting the TID into the futex field atomically. Waiters set the FUTEX_WAITERS bit:

#define FUTEX_WAITERS 0x80000000

and the remaining bits are for the TID.

Testing, architecture support ##

i’ve tested the new syscalls on x86 and x86_64, and have made sure the parsing of the userspace list is robust [ ;-) ] even if the list is deliberately corrupted.

i386 and x86_64 syscalls are wired up at the moment, and Ulrich has tested the new glibc code (on x86_64 and i386), and it works for his robust-mutex testcases.

All other architectures should build just fine too - but they wont have the new syscalls yet.

Architectures need to implement the new futex_atomic_cmpxchg_inatomic() inline function before writing up the syscalls (that function returns -ENOSYS right now).

[24] robust-futex-ABI.txt

The robust futex ABI robust futex #

Robust_futexes provide a mechanism that is used in addition to normal futexes, for kernel assist of cleanup of held locks on task exit.

robust futex除了提供futex的功能之外，它还提供了一种机制，在任务结束时用于辅助 内核对任务持有的锁进行清理。

The interesting data as to what futexes a thread is holding is kept on a linked list in user space, where it can be updated efficiently as locks are taken and dropped, without kernel intervention. The only additional kernel intervention required for robust_futexes above and beyond what is required for futexes is:

我们关心的数据是线程持有的futexes，这些树需被保存在用户空间的一个链表中，当被 加锁或者锁被释放时，这个链表中的数据可以被高效地更新，这一过程不许要内核的干预 。针对我们上面提到的robust_futexes，内核对它的唯一干预以及它相对于futexes添加 的功能包括：

1. a one time call, per thread, to tell the kernel where its list of held robust_futexes begins, and
2. internal kernel code at exit, to handle any listed locks held by the exiting thread.

The existing normal futexes already provide a “Fast Userspace Locking” mechanism, which handles uncontested locking without needing a system call, and handles contested locking by maintaining a list of waiting threads in the kernel. Options on the sys_futex(2) system call support waiting on a particular futex, and waking up the next waiter on a particular futex.

For robust_futexes to work, the user code (typically in a library such as glibc linked with the application) has to manage and place the necessary list elements exactly as the kernel expects them. If it fails to do so, then improperly listed locks will not be cleaned up on exit, probably causing deadlock or other such failure of the other threads waiting on the same locks.

A thread that anticipates possibly using robust_futexes should first issue the system call:

asmlinkage long sys_set_robust_list(struct robust_list_head __user *head, size_t len);

The pointer ‘head’ points to a structure in the threads address space consisting of three words. Each word is 32 bits on 32 bit arch’s, or 64 bits on 64 bit arch’s, and local byte order. Each thread should have its own thread private ‘head’.

If a thread is running in 32 bit compatibility mode on a 64 native arch kernel, then it can actually have two such structures - one using 32 bit words for 32 bit compatibility mode, and one using 64 bit words for 64 bit native mode. The kernel, if it is a 64 bit kernel supporting 32 bit compatibility mode, will attempt to process both lists on each task exit, if the corresponding sys_set_robust_list() call has been made to setup that list.

The first word in the memory structure at ‘head’ contains a pointer to a single linked list of ‘lock entries’, one per lock, as described below. If the list is empty, the pointer will point to itself, ‘head’. The last ‘lock entry’ points back to the ‘head’.

The second word, called ‘offset’, specifies the offset from the address of the associated ‘lock entry’, plus or minus, of what will be called the ‘lock word’, from that ‘lock entry’. The ‘lock word’ is always a 32 bit word, unlike the other words above. The ‘lock word’ holds 3 flag bits in the upper 3 bits, and the thread id (TID) of the thread holding the lock in the bottom 29 bits. See further below for a description of the flag bits.

The third word, called ‘list_op_pending’, contains transient copy of the address of the ‘lock entry’, during list insertion and removal, and is needed to correctly resolve races should a thread exit while in the middle of a locking or unlocking operation.

Each ‘lock entry’ on the single linked list starting at ‘head’ consists of just a single word, pointing to the next ‘lock entry’, or back to ‘head’ if there are no more entries. In addition, nearby to each ‘lock entry’, at an offset from the ‘lock entry’ specified by the ‘offset’ word, is one ‘lock word’.

The ‘lock word’ is always 32 bits, and is intended to be the same 32 bit lock variable used by the futex mechanism, in conjunction with robust_futexes. The kernel will only be able to wakeup the next thread waiting for a lock on a threads exit if that next thread used the futex mechanism to register the address of that ‘lock word’ with the kernel.

For each futex lock currently held by a thread, if it wants this robust_futex support for exit cleanup of that lock, it should have one ‘lock entry’ on this list, with its associated ‘lock word’ at the specified ‘offset’. Should a thread die while holding any such locks, the kernel will walk this list, mark any such locks with a bit indicating their holder died, and wakeup the next thread waiting for that lock using the futex mechanism.

When a thread has invoked the above system call to indicate it anticipates using robust_futexes, the kernel stores the passed in ‘head’ pointer for that task. The task may retrieve that value later on by using the system call:

asmlinkage long sys_get_robust_list(int pid, struct robust_list_head __user **head_ptr, size_t __user *len_ptr);

It is anticipated that threads will use robust_futexes embedded in larger, user level locking structures, one per lock. The kernel robust_futex mechanism doesn’t care what else is in that structure, so long as the ‘offset’ to the ‘lock word’ is the same for all robust_futexes used by that thread. The thread should link those locks it currently holds using the ‘lock entry’ pointers. It may also have other links between the locks, such as the reverse side of a double linked list, but that doesn’t matter to the kernel.

By keeping its locks linked this way, on a list starting with a ‘head’ pointer known to the kernel, the kernel can provide to a thread the essential service available for robust_futexes, which is to help clean up locks held at the time of (a perhaps unexpectedly) exit.

Actual locking and unlocking, during normal operations, is handled entirely by user level code in the contending threads, and by the existing futex mechanism to wait for, and wakeup, locks. The kernels only essential involvement in robust_futexes is to remember where the list ‘head’ is, and to walk the list on thread exit, handling locks still held by the departing thread, as described below.

There may exist thousands of futex lock structures in a threads shared memory, on various data structures, at a given point in time. Only those lock structures for locks currently held by that thread should be on that thread’s robust_futex linked lock list a given time.

A given futex lock structure in a user shared memory region may be held at different times by any of the threads with access to that region. The thread currently holding such a lock, if any, is marked with the threads TID in the lower 29 bits of the ‘lock word’.

When adding or removing a lock from its list of held locks, in order for the kernel to correctly handle lock cleanup regardless of when the task exits (perhaps it gets an unexpected signal 9 in the middle of manipulating this list), the user code must observe the following protocol on ‘lock entry’ insertion and removal:

On insertion:

1. set the ‘list_op_pending’ word to the address of the ‘lock entry’ to be inserted,
2. acquire the futex lock,
3. add the lock entry, with its thread id (TID) in the bottom 29 bits of the ‘lock word’, to the linked list starting at ‘head’, and
4. clear the ‘list_op_pending’ word.

On removal:

1. set the ‘list_op_pending’ word to the address of the ‘lock entry’ to be removed,
2. remove the lock entry for this lock from the ‘head’ list,
3. release the futex lock, and
4. clear the ‘lock_op_pending’ word.

On exit, the kernel will consider the address stored in ‘list_op_pending’ and the address of each ‘lock word’ found by walking the list starting at ‘head’. For each such address, if the bottom 29 bits of the ‘lock word’ at offset ‘offset’ from that address equals the exiting threads TID, then the kernel will do two things:

1. if bit 31 (0x80000000) is set in that word, then attempt a futex wakeup on that address, which will waken the next thread that has used to the futex mechanism to wait on that address, and
2. atomically set bit 30 (0x40000000) in the ‘lock word’.

In the above, bit 31 was set by futex waiters on that lock to indicate they were waiting, and bit 30 is set by the kernel to indicate that the lock owner died holding the lock.

The kernel exit code will silently stop scanning the list further if at any point:

1. the ‘head’ pointer or an subsequent linked list pointer is not a valid address of a user space word
2. the calculated location of the ‘lock word’ (address plus ‘offset’) is not the valid address of a 32 bit user space word
3. if the list contains more than 1 million (subject to future kernel configuration changes) elements.

When the kernel sees a list entry whose ‘lock word’ doesn’t have the current threads TID in the lower 29 bits, it does nothing with that entry, and goes on to the next entry.

Bit 29 (0x20000000) of the ‘lock word’ is reserved for future use.

============================================================================= Sat Sep 20 00:25:48 CST 2014 #

[25] rfkill.txt

rfkill - RF kill switch support

The rfkill subsystem provides a generic interface to disabling any radio transmitter in the system. When a transmitter is blocked, it shall not radiate any power.

The subsystem also provides the ability to react on button presses and disable all transmitters of a certain type (or all). This is intended for situations where transmitters need to be turned off, for example on aircraft.

The rfkill subsystem has a concept of “hard” and “soft” block, which differ little in their meaning (block == transmitters off) but rather in whether they can be changed or not:

• hard block: read-only radio block that cannot be overriden by software
• soft block: writable radio block (need not be readable) that is set by the system software.

[26] rbtree.txt

What are red-black trees, and what are they for? ##

Red-black trees are a type of self-balancing binary search tree, used for storing sortable key/value data pairs. This differs from radix trees (which are used to efficiently store sparse arrays and thus use long integer indexes to insert/access/delete nodes) and hash tables (which are not kept sorted to be easily traversed in order, and must be tuned for a specific size and hash function where rbtrees scale gracefully storing arbitrary keys).

Red-black trees are similar to AVL trees, but provide faster real-time bounded worst case performance for insertion and deletion (at most two rotations and three rotations, respectively, to balance the tree), with slightly slower (but still O(log n)) lookup time.

To quote Linux Weekly News:

There are a number of red-black trees in use in the kernel. The deadline and CFQ I/O schedulers employ rbtrees to track requests; the packet CD/DVD driver does the same. The high-resolution timer code uses an rbtree to organize outstanding timer requests. The ext3 filesystem tracks directory entries in a red-black tree. Virtual memory areas (VMAs) are tracked with red-black trees, as are epoll file descriptors, cryptographic keys, and network packets in the “hierarchical token bucket” scheduler.

[27] ramoops.txt

Ramoops is an oops/panic logger that writes its logs to RAM before the system crashes. It works by logging oopses and panics in a circular buffer. Ramoops needs a system with persistent RAM so that the content of that area can survive after a restart.

[28] prio_tree.txt

[29] printk-formats.txt

[30] preempt-locking.txt

[31] pnp.txt

Plug and Play provides a means of detecting and setting resources for legacy or otherwise unconfigurable devices. The Linux Plug and Play Layer provides these services to compatible drivers.

[32] pinctrl.txt

[33] pi-futex.txt

类似与rt-mutex的实现。

[34] parport.txt [35] parport-lowlevel.txt

The `parport' code provides parallel-port support under Linux. This includes the ability to share one port between multiple device drivers.

[36] padata.txt

Padata is a mechanism by which the kernel can farm work out to be done in parallel on multiple CPUs while retaining the ordering of tasks. It was developed for use with the IPsec code, which needs to be able to perform encryption and decryption on large numbers of packets without reordering those packets. The crypto developers made a point of writing padata in a sufficiently general fashion that it could be put to other uses as well.

[37] oops-tracing.txt

[38] 00-INDEX

This is a brief list of all the files in ./linux/Documentation and what they contain. If you add a documentation file, please list it here in alphabetical order as well, or risk being hunted down like a rabid dog. Please try and keep the descriptions small enough to fit on one line.

[39] Changes

This document is designed to provide a list of the minimum levels of software necessary to run the 3.0 kernels.

============================================================================= Sat Sep 20 10:03:48 CST 2014 #

[40] CodingStyle.txt

            Linux kernel coding style

This is a short document describing the preferred coding style for the linux kernel. Coding style is very personal, and I won’t force my views on anybody, but this is what goes for anything that I have to be able to maintain, and I’d prefer it for most other things too. Please at least consider the points made here.

First off, I’d suggest printing out a copy of the GNU coding standards, and NOT read it. Burn them, it’s a great symbolic gesture.

Anyway, here goes:

            Chapter 1: Indentation

Tabs are 8 characters, and thus indentations are also 8 characters. There are heretic movements that try to make indentations 4 (or even 2!) characters deep, and that is akin to trying to define the value of PI to be 3.

Rationale: The whole idea behind indentation is to clearly define where a block of control starts and ends. Especially when you’ve been looking at your screen for 20 straight hours, you’ll find it a lot easier to see how the indentation works if you have large indentations.

Now, some people will claim that having 8-character indentations makes the code move too far to the right, and makes it hard to read on a 80-character terminal screen. The answer to that is that if you need more than 3 levels of indentation, you’re screwed anyway, and should fix your program.

In short, 8-char indents make things easier to read, and have the added benefit of warning you when you’re nesting your functions too deep. Heed that warning.

The preferred way to ease multiple indentation levels in a switch statement is to align the “switch” and its subordinate “case” labels in the same column instead of “double-indenting” the “case” labels. E.g.:

    switch (suffix) {
    case 'G':
    case 'g':
            mem <<= 30;
            break;
    case 'M':
    case 'm':
            mem <<= 20;
            break;
    case 'K':
    case 'k':
            mem <<= 10;
            /* fall through */
    default:
            break;
    }

Don’t put multiple statements on a single line unless you have something to hide:

    if (condition) do_this;
      do_something_everytime;

Don’t put multiple assignments on a single line either. Kernel coding style is super simple. Avoid tricky expressions.

Outside of comments, documentation and except in Kconfig, spaces are never used for indentation, and the above example is deliberately broken.

Get a decent editor and don’t leave whitespace at the end of lines.

            Chapter 2: Breaking long lines and strings

Coding style is all about readability and maintainability using commonly available tools.

The limit on the length of lines is 80 columns and this is a strongly preferred limit.

Statements longer than 80 columns will be broken into sensible chunks, unless exceeding 80 columns significantly increases readability and does not hide information. Descendants are always substantially shorter than the parent and are placed substantially to the right. The same applies to function headers with a long argument list. However, never break user-visible strings such as printk messages, because that breaks the ability to grep for them.

            Chapter 3: Placing Braces and Spaces

The other issue that always comes up in C styling is the placement of braces. Unlike the indent size, there are few technical reasons to choose one placement strategy over the other, but the preferred way, as shown to us by the prophets Kernighan and Ritchie, is to put the opening brace last on the line, and put the closing brace first, thusly:

    if (x is true) {
            we do y
    }

This applies to all non-function statement blocks (if, switch, for, while, do). E.g.:

    switch (action) {
    case KOBJ_ADD:
            return "add";
    case KOBJ_REMOVE:
            return "remove";
    case KOBJ_CHANGE:
            return "change";
    default:
            return NULL;
    }

However, there is one special case, namely functions: they have the opening brace at the beginning of the next line, thus:

    int function(int x)
    {
            body of function
    }

Heretic people all over the world have claimed that this inconsistency is … well … inconsistent, but all right-thinking people know that (a) K&R are right and (b) K&R are right. Besides, functions are special anyway (you can’t nest them in C).

Note that the closing brace is empty on a line of its own, except in the cases where it is followed by a continuation of the same statement, ie a “while” in a do-statement or an “else” in an if-statement, like this:

    do {
            body of do-loop
    } while (condition);

and

    if (x == y) {
            ..
    } else if (x > y) {
            ...
    } else {
            ....
    }

Rationale: K&R.

Also, note that this brace-placement also minimizes the number of empty (or almost empty) lines, without any loss of readability. Thus, as the supply of new-lines on your screen is not a renewable resource (think 25-line terminal screens here), you have more empty lines to put comments on.

Do not unnecessarily use braces where a single statement will do.

if (condition) action();

and

if (condition) do_this(); else do_that();

This does not apply if only one branch of a conditional statement is a single statement; in the latter case use braces in both branches:

if (condition) { do_this(); do_that(); } else { otherwise(); }

            3.1:  Spaces

Linux kernel style for use of spaces depends (mostly) on function-versus-keyword usage. Use a space after (most) keywords. The notable exceptions are sizeof, typeof, alignof, and attribute, which look somewhat like functions (and are usually used with parentheses in Linux, although they are not required in the language, as in: “sizeof info” after “struct fileinfo info;” is declared).

So use a space after these keywords: if, switch, case, for, do, while but not with sizeof, typeof, alignof, or attribute. E.g., s = sizeof(struct file);

Do not add spaces around (inside) parenthesized expressions. This example is bad:

    s = sizeof( struct file );

When declaring pointer data or a function that returns a pointer type, the preferred use of ‘*’ is adjacent to the data name or function name and not adjacent to the type name. Examples:

    char *linux_banner;
    unsigned long long memparse(char *ptr, char **retptr);
    char *match_strdup(substring_t *s);

Use one space around (on each side of) most binary and ternary operators, such as any of these:

    =  +  -  <  >  *  /  %  |  &  ^  <=  >=  ==  !=  ?  :

but no space after unary operators: & * + - ~ ! sizeof typeof alignof attribute defined

no space before the postfix increment & decrement unary operators: ++ –

no space after the prefix increment & decrement unary operators: ++ –

and no space around the ‘.’ and “->” structure member operators.

Do not leave trailing whitespace at the ends of lines. Some editors with “smart” indentation will insert whitespace at the beginning of new lines as appropriate, so you can start typing the next line of code right away. However, some such editors do not remove the whitespace if you end up not putting a line of code there, such as if you leave a blank line. As a result, you end up with lines containing trailing whitespace.

Git will warn you about patches that introduce trailing whitespace, and can optionally strip the trailing whitespace for you; however, if applying a series of patches, this may make later patches in the series fail by changing their context lines.

            Chapter 4: Naming

C is a Spartan language, and so should your naming be. Unlike Modula-2 and Pascal programmers, C programmers do not use cute names like ThisVariableIsATemporaryCounter. A C programmer would call that variable “tmp”, which is much easier to write, and not the least more difficult to understand.

HOWEVER, while mixed-case names are frowned upon, descriptive names for global variables are a must. To call a global function “foo” is a shooting offense.

GLOBAL variables (to be used only if you really need them) need to have descriptive names, as do global functions. If you have a function that counts the number of active users, you should call that “count_active_users()” or similar, you should not call it “cntusr()”.

Encoding the type of a function into the name (so-called Hungarian notation) is brain damaged - the compiler knows the types anyway and can check those, and it only confuses the programmer. No wonder MicroSoft makes buggy programs.

LOCAL variable names should be short, and to the point. If you have some random integer loop counter, it should probably be called “i”. Calling it “loop_counter” is non-productive, if there is no chance of it being mis-understood. Similarly, “tmp” can be just about any type of variable that is used to hold a temporary value.

If you are afraid to mix up your local variable names, you have another problem, which is called the function-growth-hormone-imbalance syndrome. See chapter 6 (Functions).

            Chapter 5: Typedefs

Please don’t use things like “vps_t”.

It’s a mistake to use typedef for structures and pointers. When you see a

    vps_t a;

in the source, what does it mean?

In contrast, if it says

    struct virtual_container *a;

you can actually tell what “a” is.

Lots of people think that typedefs “help readability”. Not so. They are useful only for:

(a) totally opaque objects (where the typedef is actively used to hide what the object is).

 Example: "pte_t" etc. opaque objects that you can only access using
 the proper accessor functions.

 NOTE! Opaqueness and "accessor functions" are not good in themselves.
 The reason we have them for things like pte_t etc. is that there
 really is absolutely _zero_ portably accessible information there.

(b) Clear integer types, where the abstraction helps avoid confusion whether it is “int” or “long”.

 u8/u16/u32 are perfectly fine typedefs, although they fit into
 category (d) better than here.

 NOTE! Again - there needs to be a _reason_ for this. If something is
 "unsigned long", then there's no reason to do

    typedef unsigned long myflags_t;

 but if there is a clear reason for why it under certain circumstances
 might be an "unsigned int" and under other configurations might be
 "unsigned long", then by all means go ahead and use a typedef.

(c) when you use sparse to literally create a new type for type-checking.

(d) New types which are identical to standard C99 types, in certain exceptional circumstances.

 Although it would only take a short amount of time for the eyes and
 brain to become accustomed to the standard types like 'uint32_t',
 some people object to their use anyway.

 Therefore, the Linux-specific 'u8/u16/u32/u64' types and their
 signed equivalents which are identical to standard types are
 permitted -- although they are not mandatory in new code of your
 own.

 When editing existing code which already uses one or the other set
 of types, you should conform to the existing choices in that code.

(e) Types safe for use in userspace.

 In certain structures which are visible to userspace, we cannot
 require C99 types and cannot use the 'u32' form above. Thus, we
 use __u32 and similar types in all structures which are shared
 with userspace.

Maybe there are other cases too, but the rule should basically be to NEVER EVER use a typedef unless you can clearly match one of those rules.

In general, a pointer, or a struct that has elements that can reasonably be directly accessed should never be a typedef.

            Chapter 6: Functions

Functions should be short and sweet, and do just one thing. They should fit on one or two screenfuls of text (the ISO/ANSI screen size is 80x24, as we all know), and do one thing and do that well.

The maximum length of a function is inversely proportional to the complexity and indentation level of that function. So, if you have a conceptually simple function that is just one long (but simple) case-statement, where you have to do lots of small things for a lot of different cases, it’s OK to have a longer function.

However, if you have a complex function, and you suspect that a less-than-gifted first-year high-school student might not even understand what the function is all about, you should adhere to the maximum limits all the more closely. Use helper functions with descriptive names (you can ask the compiler to in-line them if you think it’s performance-critical, and it will probably do a better job of it than you would have done).

Another measure of the function is the number of local variables. They shouldn’t exceed 5-10, or you’re doing something wrong. Re-think the function, and split it into smaller pieces. A human brain can generally easily keep track of about 7 different things, anything more and it gets confused. You know you’re brilliant, but maybe you’d like to understand what you did 2 weeks from now.

In source files, separate functions with one blank line. If the function is exported, the EXPORT* macro for it should follow immediately after the closing function brace line. E.g.:

int system_is_up(void) { return system_state == SYSTEM_RUNNING; } EXPORT_SYMBOL(system_is_up);

In function prototypes, include parameter names with their data types. Although this is not required by the C language, it is preferred in Linux because it is a simple way to add valuable information for the reader.

            Chapter 7: Centralized exiting of functions

Albeit deprecated by some people, the equivalent of the goto statement is used frequently by compilers in form of the unconditional jump instruction.

The goto statement comes in handy when a function exits from multiple locations and some common work such as cleanup has to be done.

The rationale is:

• unconditional statements are easier to understand and follow
• nesting is reduced
• errors by not updating individual exit points when making modifications are prevented
• saves the compiler work to optimize redundant code away ;)

int fun(int a) { int result = 0; char *buffer = kmalloc(SIZE);

    if (buffer == NULL)
            return -ENOMEM;

    if (condition1) {
            while (loop1) {
                    ...
            }
            result = 1;
            goto out;
    }
    ...

out: kfree(buffer); return result; }

            Chapter 8: Commenting

Comments are good, but there is also a danger of over-commenting. NEVER try to explain HOW your code works in a comment: it’s much better to write the code so that the working is obvious, and it’s a waste of time to explain badly written code.

Generally, you want your comments to tell WHAT your code does, not HOW. Also, try to avoid putting comments inside a function body: if the function is so complex that you need to separately comment parts of it, you should probably go back to chapter 6 for a while. You can make small comments to note or warn about something particularly clever (or ugly), but try to avoid excess. Instead, put the comments at the head of the function, telling people what it does, and possibly WHY it does it.

When commenting the kernel API functions, please use the kernel-doc format. See the files Documentation/kernel-doc-nano-HOWTO.txt and scripts/kernel-doc for details.

Linux style for comments is the C89 “/* … */” style. Don’t use C99-style “// …” comments.

The preferred style for long (multi-line) comments is:

    /*
     * This is the preferred style for multi-line
     * comments in the Linux kernel source code.
     * Please use it consistently.
     *
     * Description:  A column of asterisks on the left side,
     * with beginning and ending almost-blank lines.
     */

It’s also important to comment data, whether they are basic types or derived types. To this end, use just one data declaration per line (no commas for multiple data declarations). This leaves you room for a small comment on each item, explaining its use.

            Chapter 9: You've made a mess of it

That’s OK, we all do. You’ve probably been told by your long-time Unix user helper that “GNU emacs” automatically formats the C sources for you, and you’ve noticed that yes, it does do that, but the defaults it uses are less than desirable (in fact, they are worse than random typing - an infinite number of monkeys typing into GNU emacs would never make a good program).

So, you can either get rid of GNU emacs, or change it to use saner values. To do the latter, you can stick the following in your .emacs file:

(defun c-lineup-arglist-tabs-only (ignored) “Line up argument lists by tabs, not spaces” (let* ((anchor (c-langelem-pos c-syntactic-element)) (column (c-langelem-2nd-pos c-syntactic-element)) (offset (- (1+ column) anchor)) (steps (floor offset c-basic-offset))) (* (max steps 1) c-basic-offset)))

(add-hook ‘c-mode-common-hook (lambda () ;; Add kernel style (c-add-style “linux-tabs-only” ‘(“linux” (c-offsets-alist (arglist-cont-nonempty c-lineup-gcc-asm-reg c-lineup-arglist-tabs-only))))))

(add-hook ‘c-mode-hook (lambda () (let ((filename (buffer-file-name))) ;; Enable kernel mode for the appropriate files (when (and filename (string-match (expand-file-name “~/src/linux-trees”) filename)) (setq indent-tabs-mode t) (c-set-style “linux-tabs-only”)))))

This will make emacs go better with the kernel coding style for C files below ~/src/linux-trees.

But even if you fail in getting emacs to do sane formatting, not everything is lost: use “indent”.

Now, again, GNU indent has the same brain-dead settings that GNU emacs has, which is why you need to give it a few command line options. However, that’s not too bad, because even the makers of GNU indent recognize the authority of K&R (the GNU people aren’t evil, they are just severely misguided in this matter), so you just give indent the options “-kr -i8” (stands for “K&R, 8 character indents”), or use “scripts/Lindent”, which indents in the latest style.

“indent” has a lot of options, and especially when it comes to comment re-formatting you may want to take a look at the man page. But remember: “indent” is not a fix for bad programming.

            Chapter 10: Kconfig configuration files

For all of the Kconfig* configuration files throughout the source tree, the indentation is somewhat different. Lines under a “config” definition are indented with one tab, while help text is indented an additional two spaces. Example:

config AUDIT bool “Auditing support” depends on NET help Enable auditing infrastructure that can be used with another kernel subsystem, such as SELinux (which requires this for logging of avc messages output). Does not do system-call auditing without CONFIG_AUDITSYSCALL.

Features that might still be considered unstable should be defined as dependent on “EXPERIMENTAL”:

config SLUB depends on EXPERIMENTAL && !ARCH_USES_SLAB_PAGE_STRUCT bool “SLUB (Unqueued Allocator)” …

while seriously dangerous features (such as write support for certain filesystems) should advertise this prominently in their prompt string:

config ADFS_FS_RW bool “ADFS write support (DANGEROUS)” depends on ADFS_FS …

For full documentation on the configuration files, see the file Documentation/kbuild/kconfig-language.txt.

            Chapter 11: Data structures

Data structures that have visibility outside the single-threaded environment they are created and destroyed in should always have reference counts. In the kernel, garbage collection doesn’t exist (and outside the kernel garbage collection is slow and inefficient), which means that you absolutely have to reference count all your uses.

Reference counting means that you can avoid locking, and allows multiple users to have access to the data structure in parallel - and not having to worry about the structure suddenly going away from under them just because they slept or did something else for a while.

Note that locking is not a replacement for reference counting. Locking is used to keep data structures coherent, while reference counting is a memory management technique. Usually both are needed, and they are not to be confused with each other.

Many data structures can indeed have two levels of reference counting, when there are users of different “classes”. The subclass count counts the number of subclass users, and decrements the global count just once when the subclass count goes to zero.

Examples of this kind of “multi-level-reference-counting” can be found in memory management (“struct mm_struct”: mm_users and mm_count), and in filesystem code (“struct super_block”: s_count and s_active).

Remember: if another thread can find your data structure, and you don’t have a reference count on it, you almost certainly have a bug.

            Chapter 12: Macros, Enums and RTL

Names of macros defining constants and labels in enums are capitalized.

#define CONSTANT 0x12345

Enums are preferred when defining several related constants.

CAPITALIZED macro names are appreciated but macros resembling functions may be named in lower case.

Generally, inline functions are preferable to macros resembling functions.

Macros with multiple statements should be enclosed in a do - while block:

#define macrofun(a, b, c)
do {
if (a == 5)
do_this(b, c);
} while (0)

Things to avoid when using macros:

1. macros that affect control flow:

#define FOO(x)
do {
if (blah(x) < 0)
return -EBUGGERED;
} while(0)

is a very bad idea. It looks like a function call but exits the “calling” function; don’t break the internal parsers of those who will read the code.

2. macros that depend on having a local variable with a magic name:

#define FOO(val) bar(index, val)

might look like a good thing, but it’s confusing as hell when one reads the code and it’s prone to breakage from seemingly innocent changes.

3. macros with arguments that are used as l-values: FOO(x) = y; will bite you if somebody e.g. turns FOO into an inline function.

4. forgetting about precedence: macros defining constants using expressions must enclose the expression in parentheses. Beware of similar issues with macros using parameters.

#define CONSTANT 0x4000 #define CONSTEXP (CONSTANT | 3)

The cpp manual deals with macros exhaustively. The gcc internals manual also covers RTL which is used frequently with assembly language in the kernel.

            Chapter 13: Printing kernel messages

Kernel developers like to be seen as literate. Do mind the spelling of kernel messages to make a good impression. Do not use crippled words like “dont”; use “do not” or “don’t” instead. Make the messages concise, clear, and unambiguous.

Kernel messages do not have to be terminated with a period.

Printing numbers in parentheses (%d) adds no value and should be avoided.

There are a number of driver model diagnostic macros in <linux/device.h> which you should use to make sure messages are matched to the right device and driver, and are tagged with the right level: dev_err(), dev_warn(), dev_info(), and so forth. For messages that aren’t associated with a particular device, <linux/printk.h> defines pr_debug() and pr_info().

Coming up with good debugging messages can be quite a challenge; and once you have them, they can be a huge help for remote troubleshooting. Such messages should be compiled out when the DEBUG symbol is not defined (that is, by default they are not included). When you use dev_dbg() or pr_debug(), that’s automatic. Many subsystems have Kconfig options to turn on -DDEBUG. A related convention uses VERBOSE_DEBUG to add dev_vdbg() messages to the ones already enabled by DEBUG.

            Chapter 14: Allocating memory

The kernel provides the following general purpose memory allocators: kmalloc(), kzalloc(), kcalloc(), vmalloc(), and vzalloc(). Please refer to the API documentation for further information about them.

The preferred form for passing a size of a struct is the following:

    p = kmalloc(sizeof(*p), ...);

The alternative form where struct name is spelled out hurts readability and introduces an opportunity for a bug when the pointer variable type is changed but the corresponding sizeof that is passed to a memory allocator is not.

Casting the return value which is a void pointer is redundant. The conversion from void pointer to any other pointer type is guaranteed by the C programming language.

            Chapter 15: The inline disease

There appears to be a common misperception that gcc has a magic “make me faster” speedup option called “inline”. While the use of inlines can be appropriate (for example as a means of replacing macros, see Chapter 12), it very often is not. Abundant use of the inline keyword leads to a much bigger kernel, which in turn slows the system as a whole down, due to a bigger icache footprint for the CPU and simply because there is less memory available for the pagecache. Just think about it; a pagecache miss causes a disk seek, which easily takes 5 milliseconds. There are a LOT of cpu cycles that can go into these 5 milliseconds.

A reasonable rule of thumb is to not put inline at functions that have more than 3 lines of code in them. An exception to this rule are the cases where a parameter is known to be a compiletime constant, and as a result of this constantness you know the compiler will be able to optimize most of your function away at compile time. For a good example of this later case, see the kmalloc() inline function.

Often people argue that adding inline to functions that are static and used only once is always a win since there is no space tradeoff. While this is technically correct, gcc is capable of inlining these automatically without help, and the maintenance issue of removing the inline when a second user appears outweighs the potential value of the hint that tells gcc to do something it would have done anyway.

            Chapter 16: Function return values and names

Functions can return values of many different kinds, and one of the most common is a value indicating whether the function succeeded or failed. Such a value can be represented as an error-code integer (-Exxx = failure, 0 = success) or a “succeeded” boolean (0 = failure, non-zero = success).

Mixing up these two sorts of representations is a fertile source of difficult-to-find bugs. If the C language included a strong distinction between integers and booleans then the compiler would find these mistakes for us… but it doesn’t. To help prevent such bugs, always follow this convention:

    If the name of a function is an action or an imperative command,
    the function should return an error-code integer.  If the name
    is a predicate, the function should return a "succeeded" boolean.

For example, “add work” is a command, and the add_work() function returns 0 for success or -EBUSY for failure. In the same way, “PCI device present” is a predicate, and the pci_dev_present() function returns 1 if it succeeds in finding a matching device or 0 if it doesn’t.

All EXPORTed functions must respect this convention, and so should all public functions. Private (static) functions need not, but it is recommended that they do.

Functions whose return value is the actual result of a computation, rather than an indication of whether the computation succeeded, are not subject to this rule. Generally they indicate failure by returning some out-of-range result. Typical examples would be functions that return pointers; they use NULL or the ERR_PTR mechanism to report failure.

            Chapter 17:  Don't re-invent the kernel macros

The header file include/linux/kernel.h contains a number of macros that you should use, rather than explicitly coding some variant of them yourself. For example, if you need to calculate the length of an array, take advantage of the macro

#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))

Similarly, if you need to calculate the size of some structure member, use

#define FIELD_SIZEOF(t, f) (sizeof(((t*)0)->f))

There are also min() and max() macros that do strict type checking if you need them. Feel free to peruse that header file to see what else is already defined that you shouldn’t reproduce in your code.

            Chapter 18:  Editor modelines and other cruft

Some editors can interpret configuration information embedded in source files, indicated with special markers. For example, emacs interprets lines marked like this:

-- mode: c --

Or like this:

/* Local Variables: compile-command: “gcc -DMAGIC_DEBUG_FLAG foo.c” End: */

Vim interprets markers that look like this:

Do not include any of these in source files. People have their own personal editor configurations, and your source files should not override them. This includes markers for indentation and mode configuration. People may use their own custom mode, or may have some other magic method for making indentation work correctly.

[41] BUG-HUNTING.txt

这篇文档讲述了如何定位内核中的bug，常用的方式包括通过git-bisect进行搜索，以及 通过常规的旧有方式进行搜索定位，下面对其进行简要描述。

Finding using git-bisect ##

Using the provided tools with git makes finding bugs easy provided the bug is reproducible.

Steps to do it:

• start using git for the kernel source
• read the man page for git-bisect
• have fun

Finding it the old way ##

[Sat Mar 2 10:32:33 PST 1996 KERNEL_BUG-HOWTO lm@sgi.com (Larry McVoy)]

This is how to track down a bug if you know nothing about kernel hacking. It’s a brute force approach but it works pretty well.

You need:

    . A reproducible bug - it has to happen predictably (sorry)
    . All the kernel tar files from a revision that worked to the
      revision that doesn't

You will then do:

    . Rebuild a revision that you believe works, install, and verify that.
    . Do a binary search over the kernels to figure out which one
      introduced the bug.  I.e., suppose 1.3.28 didn't have the bug, but
      you know that 1.3.69 does.  Pick a kernel in the middle and build
      that, like 1.3.50.  Build & test; if it works, pick the mid point
      between .50 and .69, else the mid point between .28 and .50.
    . You'll narrow it down to the kernel that introduced the bug.  You
      can probably do better than this but it gets tricky.

    . Narrow it down to a subdirectory

      - Copy kernel that works into "test".  Let's say that 3.62 works,
        but 3.63 doesn't.  So you diff -r those two kernels and come
        up with a list of directories that changed.  For each of those
        directories:

            Copy the non-working directory next to the working directory
            as "dir.63".
            One directory at time, try moving the working directory to
            "dir.62" and mv dir.63 dir"time, try

                    mv dir dir.62
                    mv dir.63 dir
                    find dir -name '*.[oa]' -print | xargs rm -f

            And then rebuild and retest.  Assuming that all related
            changes were contained in the sub directory, this should
            isolate the change to a directory.

            Problems: changes in header files may have occurred; I've
            found in my case that they were self explanatory - you may
            or may not want to give up when that happens.

    . Narrow it down to a file

      - You can apply the same technique to each file in the directory,
        hoping that the changes in that file are self contained.

    . Narrow it down to a routine

      - You can take the old file and the new file and manually create
        a merged file that has

            #ifdef VER62
            routine()
            {
                    ...
            }
            #else
            routine()
            {
                    ...
            }
            #endif

        And then walk through that file, one routine at a time and
        prefix it with

            #define VER62
            /* both routines here */
            #undef VER62

        Then recompile, retest, move the ifdefs until you find the one
        that makes the difference.

Finally, you take all the info that you have, kernel revisions, bug description, the extent to which you have narrowed it down, and pass that off to whomever you believe is the maintainer of that section. A post to linux.dev.kernel isn’t such a bad idea if you’ve done some work to narrow it down.

If you get it down to a routine, you’ll probably get a fix in 24 hours.

My apologies to Linus and the other kernel hackers for describing this brute force approach, it’s hardly what a kernel hacker would do. However, it does work and it lets non-hackers help fix bugs. And it is cool because Linux snapshots will let you do this - something that you can’t do with vendor supplied releases.

还讲述了如何修复内核bug的方式。

Fixing the bug #

Nobody is going to tell you how to fix bugs. Seriously. You need to work it out. But below are some hints on how to use the tools.

To debug a kernel, use objdump and look for the hex offset from the crash output to find the valid line of code/assembler. Without debug symbols, you will see the assembler code for the routine shown, but if your kernel has debug symbols the C code will also be available. (Debug symbols can be enabled in the kernel hacking menu of the menu configuration.) For example:

objdump -r -S -l --disassemble net/dccp/ipv4.o

NB.: you need to be at the top level of the kernel tree for this to pick up your C files.

If you don’t have access to the code you can also debug on some crash dumps e.g. crash dump output as shown by Dave Miller.

EIP is at ip_queue_xmit+0x14/0x4c0 … Code: 44 24 04 e8 6f 05 00 00 e9 e8 fe ff ff 8d 76 00 8d bc 27 00 00 00 00 55 57 56 53 81 ec bc 00 00 00 8b ac 24 d0 00 00 00 8b 5d 08 <8b> 83 3c 01 00 00 89 44 24 14 8b 45 28 85 c0 89 44 24 18 0f 85

Put the bytes into a “foo.s” file like this:

      .text
      .globl foo

foo: .byte …. /* bytes from Code: part of OOPS dump */

Compile it with “gcc -c -o foo.o foo.s” then look at the output of “objdump –disassemble foo.o”.

Output:

ip_queue_xmit: push %ebp push %edi push %esi push %ebx sub $0xbc, %esp mov 0xd0(%esp), %ebp ! %ebp = arg0 (skb) mov 0x8(%ebp), %ebx ! %ebx = skb->sk mov 0x13c(%ebx), %eax ! %eax = inet_sk(sk)->opt

In addition, you can use GDB to figure out the exact file and line number of the OOPS from the vmlinux file. If you have CONFIG_DEBUG_INFO enabled, you can simply copy the EIP value from the OOPS:

EIP: 0060:[] Not tainted VLI

And use GDB to translate that to human-readable form:

gdb vmlinux (gdb) l *0xc021e50e

If you don’t have CONFIG_DEBUG_INFO enabled, you use the function offset from the OOPS:

EIP is at vt_ioctl+0xda8/0x1482

And recompile the kernel with CONFIG_DEBUG_INFO enabled:

make vmlinux gdb vmlinux (gdb) p vt_ioctl (gdb) l *(0x

1: If you use a facility then #include the file that defines/declares
   that facility.  Don't depend on other header files pulling in ones
   that you use.

2: Builds cleanly with applicable or modified CONFIG options =y, =m, and
   =n.  No gcc warnings/errors, no linker warnings/errors.

2b: Passes allnoconfig, allmodconfig

2c: Builds successfully when using O=builddir

3: Builds on multiple CPU architectures by using local cross-compile tools
   or some other build farm.

4: ppc64 is a good architecture for cross-compilation checking because it
   tends to use `unsigned long' for 64-bit quantities.

5: Check your patch for general style as detailed in
   Documentation/CodingStyle.  Check for trivial violations with the
   patch style checker prior to submission (scripts/checkpatch.pl).
   You should be able to justify all violations that remain in
   your patch.

6: Any new or modified CONFIG options don't muck up the config menu.

7: All new Kconfig options have help text.

8: Has been carefully reviewed with respect to relevant Kconfig
   combinations.  This is very hard to get right with testing -- brainpower
   pays off here.

9: Check cleanly with sparse.

10: Use 'make checkstack' and 'make namespacecheck' and fix any problems
    that they find.  Note: checkstack does not point out problems explicitly,
             but any one function that uses more than 512 bytes on the stack is a
             candidate for change.
         
11: Include kernel-doc to document global kernel APIs.  (Not required for
                     static functions, but OK there also.) Use 'make htmldocs' or 'make mandocs' to check the kernel-doc and fix any issues.
         
12: Has been tested with CONFIG_PREEMPT, CONFIG_DEBUG_PREEMPT,
             CONFIG_DEBUG_SLAB, CONFIG_DEBUG_PAGEALLOC, CONFIG_DEBUG_MUTEXES,
             CONFIG_DEBUG_SPINLOCK, CONFIG_DEBUG_ATOMIC_SLEEP, CONFIG_PROVE_RCU
             and CONFIG_DEBUG_OBJECTS_RCU_HEAD all simultaneously enabled.
         
13: Has been build- and runtime tested with and without CONFIG_SMP and
             CONFIG_PREEMPT.
         
14: If the patch affects IO/Disk, etc: has been tested with and without
             CONFIG_LBDAF.
         
15: All codepaths have been exercised with all lockdep features enabled.
         
16: All new /proc entries are documented under Documentation/
         
17: All new kernel boot parameters are documented in
             Documentation/kernel-parameters.txt.
         
18: All new module parameters are documented with MODULE_PARM_DESC()
    
19: All new userspace interfaces are documented in Documentation/ABI/.
        See Documentation/ABI/README for more information.
        Patches that change userspace interfaces should be CCed to
        linux-api@vger.kernel.org.
    
20: Check that it all passes `make headers_check'.
    
21: Has been checked with injection of at least slab and page-allocation
        failures.  See Documentation/fault-injection/.
    
        If the new code is substantial, addition of subsystem-specific fault
        injection might be appropriate.
    
22: Newly-added code has been compiled with `gcc -W' (use "make
		EXTRA_CFLAGS=-W").  This will generate lots of noise, but is good for finding 		bugs like "warning: comparison between signed and unsigned".
    
23: Tested after it has been merged into the -mm patchset to make sure
        that it still works with all of the other queued patches and various
        changes in the VM, VFS, and other subsystems.
    
24: All memory barriers {e.g., barrier(), rmb(), wmb()} need a comment in the
        source code that explains the logic of what they are doing and why.
    
25: If any ioctl's are added by the patch, then also update
        Documentation/ioctl/ioctl-number.txt.
    
26: If your modified source code depends on or uses any of the kernel
        APIs or features that are related to the following kconfig symbols,
        then test multiple builds with the related kconfig symbols disabled
        and/or =m (if that option is available) [not all of these at the
        same time, just various/random combinations of them]:
    
        CONFIG_SMP, CONFIG_SYSFS, CONFIG_PROC_FS, CONFIG_INPUT, CONFIG_PCI,
        CONFIG_BLOCK, CONFIG_PM, CONFIG_HOTPLUG, CONFIG_MAGIC_SYSRQ,
        CONFIG_NET, CONFIG_INET=n (but latter with CONFIG_NET=y)

SRCTREE= linux-2.6
MYFILE=  drivers/net/mydriver.c
 
cd $SRCTREE
cp $MYFILE $MYFILE.orig
vi $MYFILE      # make your change
cd ..
diff -up $SRCTREE/$MYFILE{.orig,} > /tmp/patch

MYSRC= /devel/linux-2.6
 
tar xvfz linux-2.6.12.tar.gz
mv linux-2.6.12 linux-2.6.12-vanilla
diff -uprN -X linux-2.6.12-vanilla/Documentation/dontdiff \
linux-2.6.12-vanilla $MYSRC > /tmp/patch

    Developer's Certificate of Origin 1.1

    By making a contribution to this project, I certify that:

    (a) The contribution was created in whole or in part by me and I have
        the right to submit it under the open source license indicated in
        the file; or

    (b) The contribution is based upon previous work that, to the best of
        my knowledge, is covered under an appropriate open source license
        and I have the right under that license to submit that work with
        modifications, whether created in whole or in part by me, under
        the same open source license (unless I am permitted to submit
                under a different license), as indicated in the file; or

    (c) The contribution was provided directly to me by some other person
        who certified (a), (b) or (c) and I have not modified it.

    (d) I understand and agree that this project and the contribution are
        public and that a record of the contribution (including all
        personal information I submit with it, including my sign-off) is
        maintained indefinitely and may be redistributed consistent with
        this project or the open source license(s) involved.

then you just add a line saying
        Signed-off-by: Random J Developer <random@developer.example.org>

    Signed-off-by: Random J Developer <random@developer.example.org>
    [lucky@maintainer.example.org: struct foo moved from foo.c to foo.h]
    Signed-off-by: Lucky K Maintainer <lucky@maintainer.example.org>

Date:   Tue May 13 19:10:30 +0000

    SCSI: libiscsi regression in 2.6.25: fix nop timer handling

    commit 4cf1043593db6a337f10e006c23c69e5fc93e722 upstream

Date:   Tue May 13 22:12:27 +0200

    wireless, airo: waitbusy() won't delay

    [backport of 2.6 commit b7acbdfbd1f277c1eb23f344f899cfa4cd0bf36a]

    Reviewer's statement of oversight

    By offering my Reviewed-by: tag, I state that:

     (a) I have carried out a technical review of this patch to
         evaluate its appropriateness and readiness for inclusion into
         the mainline kernel.

     (b) Any problems, concerns, or questions relating to the patch
         have been communicated back to the submitter.  I am satisfied
         with the submitter's response to my comments.

     (c) While there may be things that could be improved with this
         submission, I believe that it is, at this time, (1) a
         worthwhile modification to the kernel, and (2) free of known
         issues which would argue against its inclusion.

     (d) While I have reviewed the patch and believe it to be sound, I
         do not (unless explicitly stated elsewhere) make any
         warranties or guarantees that it will achieve its stated
         purpose or function properly in any given situation.

Subject: [PATCH 001/123] subsystem: summary phrase

Subject: [patch 2/5] ext2: improve scalability of bitmap searching
Subject: [PATCHv2 001/207] x86: fix eflags tracking

    From: Original Author <author@example.com>

    "Please pull from

            git://jdelvare.pck.nerim.net/jdelvare-2.6 i2c-for-linus

     to get these changes:"

    dev = alloc_etherdev (sizeof(struct funky_private));
    if (!dev)
            return -ENODEV;
    #ifdef CONFIG_NET_FUNKINESS
    init_funky_net(dev);
    #endif

 - CPU untranslated.  This is the "physical" address.  Physical address 
   0 is what the CPU sees when it drives zeroes on the memory bus.

 - CPU translated address. This is the "virtual" address, and is 
   completely internal to the CPU itself with the CPU doing the appropriate
   translations into "CPU untranslated". 

 - bus address. This is the address of memory as seen by OTHER devices, 
   not the CPU. Now, in theory there could be many different bus 
   addresses, with each device seeing memory in some device-specific way, but
   happily most hardware designers aren't actually actively trying to make
   things any more complex than necessary, so you can assume that all 
   external hardware sees the memory the same way. 

0-2 GB          "real memory"
2 GB-3 GB       "system IO" (inb/out and similar accesses on x86)
3 GB-4 GB       "IO memory" (shared memory over the IO bus)

 physical address:      0
 virtual address:       0xC0000000
 bus address:           0x80000000

 一些方便使用的函数，用于获取、设置2^x的容量的环形缓冲区中的信息。

 内存访问限制，用于保证环形缓冲区中数据对象的生产者和消费者不能共享锁。

    http://sourceforge.net/projects/gkernel/

Note that changing the root directory does not involve unmounting it.  It
is therefore possible to leave processes running on initrd during that
procedure. Also note that file systems mounted under initrd continue to be
accessible.

struct uio_map {
    struct kobject kobj;
    struct uio_mem *mem;
};

container_of(pointer, type, member)

struct uio_map *u_map = container_of(kp, struct uio_map, kobj);

struct uio_map {
    struct kobject kobj;
    struct uio_mem *mem;
};

#define to_map(map) container_of(map, struct uio_map, kobj)

struct uio_map *map = to_map(kobj);

void kobject_init(struct kobject *kobj, struct kobj_type *ktype);

int kobject_add(struct kobject *kobj, struct kobject *parent, const char *fmt, ...);

int kobject_rename(struct kobject *kobj, const char *new_name);

const char *kobject_name(const struct kobject * kobj);

int kobject_init_and_add(struct kobject *kobj, struct kobj_type *ktype,
                         struct kobject *parent, const char *fmt, ...);

int kobject_uevent(struct kobject *kobj, enum kobject_action action);

struct kobject *kobject_get(struct kobject *kobj);
void kobject_put(struct kobject *kobj);

struct kobject *kobject_create_and_add(char *name, struct kobject *parent);

int sysfs_create_file(struct kobject *kobj, struct attribute *attr);
    or
int sysfs_create_group(struct kobject *kobj, struct attribute_group *grp);

kobject *kp = 
    kobject_init(tt->kobj);            // init中初始化后kobj引用计数1
                                    // init返回指向kobj的指针，引用计数为2
kobject_put(tt->kobj);                // kobj引用计数--后，为1
如果是这样的话，那就不存在问题了。

void my_object_release(struct kobject *kobj)
{
        struct my_object *mine = container_of(kobj, struct my_object, kobj);

        /* Perform any additional cleanup on this object, then... */
        kfree(mine);
}

struct kobj_type {
        void (*release)(struct kobject *);
        const struct sysfs_ops *sysfs_ops;
        struct attribute    **default_attrs;
};

从这个结构体定义中，我们看到它包括一个成员release，这是一个函数指针，即我
们前面提到的为每个kobject提供的release函数。
前面提及必须为每个kobject指定release函数，而release方法包含在ktype结构体里
面，这样我们就可以理解前面提及的“每个kobject都必须指定一个ktype”这个知识点
了。

    IA
     |

 struct my_data *data;

 data = kmalloc(sizeof(*data), GFP_KERNEL);
 if (!data)
        return -ENOMEM;
 kref_init(&data->refcount);

    kref_get(&data->refcount);
    task = kthread_run(more_data_handling, data, "more_data_handling");
    if (task == ERR_PTR(-ENOMEM)) {
            rv = -ENOMEM;
            goto out;
    }

    .
    . do stuff with data here
    .

    task = kthread_run(more_data_handling, data, "more_data_handling");
    if (task == ERR_PTR(-ENOMEM)) {
            rv = -ENOMEM;
            goto out;
    } else
            /* BAD BAD BAD - get is after the handoff */
            kref_get(&data->refcount);

    /* Silly extra get and put */
    kref_get(&obj->ref);
    enqueue(obj);
    kref_put(&obj->ref, obj_cleanup);

    enqueue(obj);
    /* We are done with obj, so we pass our refcount off
       to the queue.  DON'T TOUCH obj AFTER HERE! */

    list_del(&entry->link);
    kfree(entry);