原创 Linux内核栈溢出（stack overflow）问题

最近一段时间在设计和开发一个Linux内核模块，进入到最后的正确性测试与稳定性测试阶段。在这个阶段发现了一个非常有意思的问题，堆栈溢出（stack overflow）。Linux内核堆栈溢出之后直接导致了系统kernel Panic。由于导致stack overflow的原因是递归调用导致的，所以，最后通过调试串口导出的kernel panic信息很快就定位问题所在了，否则这样的问题还真是很难调试和发现。通过这次bug，我们应该记住的是：Linux内核stack资源是有限的，而递归调用将大量消耗stack资源，因此在内核编程中尽量少用递归算法，否则将会导致出乎意料的一些问题。依次类推，为了减少stack资源的消耗，程序的局部变量定义的不要太大，否则也将会消耗大量stack资源，从而导致内核程序的不稳定。

<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

为了解决递归调用导致的问题，我将递归算法改写成了非递归算法，解决了stack overflow的问题。在此介绍一下递归算法改写成非递归算法的一些思想。在项目实现过程中，需要对IO请求进行按顺序排队，因此采用了效率较高并且实现简单的快速排序算法，该算法是一种分治算法，即将排序队列进行切分，分解成一系列的小问题进行求解，针对这种问题，很容易采用递归的办法进行实现，伪代码描述如下：

/* qs_sort实现从小到大的排序 */

Struct bio qs_sort(struct bio_list *list_head, struct bio *bio_tail) {

       Struct bio_list *less_list, *large_list;

       Struct bio *middle_bio;

       /* 递归调用结束点，小问题求解完毕，直接返回最后一个元素 */

If (!list_head) {

              Return bio_tail;

       }

/* 对队列进行切分，选择一个middle_bio，并且按照middle_bio将其切分成less_list队列和large_list队列 */

       Split_list(list_head, less_list, large_list, &middle_bio);

       /* 采用递归的方法实现大队列的排序操作 */

       Middle_bio->bi_next = qs_sort(large_list, bio_tail);

/* 采用递归的方法实现小队列的排序操作 */

       Return qs_sort(less_list, middle_bio);

}

有上述可见，采用函数递归的方法实现简单，但是将会牺牲（栈）存储空间，为此，需要将其改写成非递归的实现方法，非递归的实现算法可以点击此处下载（https://static.assets-stash.eet-china.com/album/old-resources/2009/3/21/ddece665-46d3-43e5-92bb-49627325b66a.rar，欢迎提出意见）。改写的思想是将递归所采用的存储栈空间动态分配。递归算法本质上利用堆栈存储了切分的小问题，因此，可以采用系统内存动态分配存储空间，自己维护小问题堆栈。那么可以做到不利用函数堆栈空间，避免了栈空间的大量消耗。

总之，在内核程序实现过程中，一定要注意栈空间的使用，特别像递归这样的方法尽量少用，否则将可能会对产品产生致命的打击。