它山之石，可以攻玉--从内核中学到了什么（获奖名单已公布-2014-4-21）

JackNorton

内核中在进程管理采用红黑树数据结构。
红黑树对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。红黑树应用在关联数组、字典的实现上。需要的空间比散列表小。任何键值对应，需要随机存储和键有序的情况都可以用。

Godbach

回复 91# JackNorton

感谢分享


   

uudiin

MARK之，前来围观

Godbach

回复 93# uudiin

别光 MARK，多多分享一下。


   

我只想混口饭吃

那个源码那边有？
还有那边有在探讨？
新手:wink:

uxyzp

“分享一下曾经解决了燃眉之急的某个内核新特性”

有这么巧？

andloani

1. 内核的哪些数据结构以及 API 被用到或者移植到了和内核没有直接关系的工作中
内核代码很精练高效，很多都被我借鉴到自己写的用户空间的程序中，红黑树，链表，加密算法，还有模仿container_of宏对自己的结构体进行操作。

2. 分享一下曾经解决了燃眉之急的某个内核新特性
曾经需要将某驱动程序的固件在机器启动后从用户空间放到内核空间中，开始自己搞了一整套暴露/sys接口，通过ioctl，mmap把内核空间暴露给用户空间，然后用户空间再将固件写入内核空间。。。。但是当时还是有问题没解决，而且感觉这个干很**内核的原则。结果后来无意发现其实03年起内核就引入了request_firmware这个特性/Documentation/firmware_class/readme，晕，原来内核有一整套完整的东西，比我自己山寨的那套好多了，果断用之完成任务，心里也踏实了。

3. 介绍一下个人曾经研究过的某个内核特性
研究的比较透的排队自旋锁(FIFO Ticket Spinlock)，这是Linux  2.6.25 版本中引入的一种新型自旋锁，解决了自旋锁的公平问题。当时是为了解决一个双核平台出现的死锁问题，当时我心中的自旋锁就是非0则1的锁而已。后来仔细分析dump和看代码之后，才发现原来内核的自旋锁已经是排队锁了。把自旋锁的汇编一步步搞清楚之后，觉得代码确实精妙，原来我以为的自旋锁自旋的时候cpu就会忙等，其实汇编上还专门使用了休眠指令，在自旋的时候cpu就进入休眠以节省功耗。搞清楚排队自旋锁的原理之后就好分析了，最后发现是在一个核加锁之后，另外一个核来了中断，并在那个中断中调用spin_lock_init将锁状态**，导致后续函数无法得到排队锁而被锁死。关于排队自旋锁，有兴趣的可以了解http://www.ibm.com/developerworks/cn/linux/l-cn-spinlock/

Godbach

回复 97# andloani

感谢分享。

   

Godbach

回复 96# uxyzp

也可以是那种本来内核就有的特性或者机制，折腾了很久才发现。有那种众里寻他千百度，蓦然回首，那人却在灯火阑珊处的赶脚。

   

andloani

回复 99# Godbach


    没错，我经常这样，自己苦苦搞一大套，搞到出问题的时候，再从源码中细细搜索，就会发现原来内核早就提供整套方法了。