A Geek's Page

我们知道，当无符号数上溢时，它会安安静静地绕回，因此，当比较两个无符号数时，不得不考虑绕回的问题。很可能绝大多数情况下不会出现溢出的情况，但是一旦溢出而处理不当就会导致系统进入非预期状态。不幸的是，Linux内核中的kfifo并没有恰当地处理这一问题。

struct kfifo定义在include/linux/kfifo.h中，其成员如下：

struct kfifo {
        unsigned char *buffer;
        unsigned int size;
        unsigned int in;
        unsigned int out;
        spinlock_t *lock;
};

   118  unsigned int __kfifo_put(struct kfifo *fifo,
   119                           unsigned char *buffer, unsigned int len)
   120  {
   121          unsigned int l;
   122
   123          len = min(len, fifo->size - fifo->in + fifo->out);
   ...
   130          smp_mb();
   131
   132          /* first put the data starting from fifo->in to buffer end */
   133          l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
   134          memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);   
   135
   136          /* then put the rest (if any) at the beginning of the buffer */
   137          memcpy(fifo->buffer, buffer + l, len - l);
   ...
   144          smp_wmb();
   145
   146          fifo->in += len;
   147
   148          return len;
   149  }
   ...
   164  unsigned int __kfifo_get(struct kfifo *fifo,
   165                           unsigned char *buffer, unsigned int len)
   166  {
   167          unsigned int l;
   168
   169          len = min(len, fifo->in - fifo->out);
   ...
   176          smp_rmb();
   177
   178          /* first get the data from fifo->out until the end of the buffer */
   179          l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
   180          memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
   181
   182          /* then get the rest (if any) from the beginning of the buffer */
   183          memcpy(buffer + l, fifo->buffer, len - l);
   ...
   190          smp_mb();
   191
   192          fifo->out += len;
   193
   194          return len;
   195  }

下面一个粗糙的内核模块和用户程序可以展示这个bug。内核模块如下：

     1  #include <linux/kernel.h>
     2  #include <linux/init.h>
     3  #include <linux/module.h>
     4  #include <linux/fs.h>
     5  #include <asm/uaccess.h>
     6  #include <linux/err.h>
     7  #include <linux/gfp.h>
     8  #include <linux/spinlock.h>
     9  #include <linux/kfifo.h>
    10  #include <linux/string.h>
    11
    12  #define LFS_MAGIC 0x19860913
    13  #define NFILES  2
    14  #define TEST_BUF_LEN    64
    15
    16  static struct kfifo *fifo;
    17  static spinlock_t lock;
    18  static char *buf;
    19
    20  static int lfs_open_file(struct inode *inode, struct file *filp)
    21  {
    22          if (inode->i_ino > NFILES)
    23                  return -ENODEV;
    24          return 0;
    25  }
    26
    27  static ssize_t lfs_read_file(struct file *filp, char *buffer,
    28                               size_t count, loff_t * offset)
    29  {
    30          int len;
    31
    32          len = kfifo_get(fifo, buf, count);
    33          if (*offset > len)
    34                  return 0;
    35          if (count > len - *offset)
    36                  count = len - *offset;
    37
    38          if (copy_to_user(buffer, buf + *offset, count))
    39                  return -EFAULT;
    40          *offset += count;
    41          return count;
    42  }
    43
    44  static ssize_t lfs_write_file(struct file *filp, const char *buffer,
    45                                size_t count, loff_t * offset)
    46  {
    47          if (*offset != 0)
    48                  *offset = 0;
    49
    50          if (count >= TEST_BUF_LEN)
    51                  count = TEST_BUF_LEN;
    52
    53          if (copy_from_user(buf, buffer, count))
    54                  return -EFAULT;
    55
    56          return (ssize_t) kfifo_put(fifo, (char *)buffer, count);
    57  }
    58
    59  static int my_atoi(const char *name)
    60  {
    61          int val = 0;
    62
    63          for (;; name++) {
    64                  switch (*name) {
    65                  case '0'...'9':
    66                          val = 10 * val + (*name - '0');
    67                          break;
    68                  default:
    69                          return val;
    70                  }
    71          }
    72  }
    73
    74  static int lfs_open_file2(struct inode *inode, struct file *filp)
    75  {
    76          if (inode->i_ino > NFILES)
    77                  return -ENODEV;
    78          filp->private_data = fifo;
    79          return 0;
    80  }
    81
    82  static ssize_t lfs_read_file2(struct file *filp, char *buffer,
    83                                size_t count, loff_t * offset)
    84  {
    85          int len;
    86          struct kfifo *myfifo = (struct kfifo *)filp->private_data;
    87
    88          len =
    89              snprintf(buf, TEST_BUF_LEN, "in=%u out=%u\n", myfifo->in,
    90                       myfifo->out);
    91          if (*offset > len)
    92                  return 0;
    93          if (count > len - *offset)
    94                  count = len - *offset;
    95
    96          if (copy_to_user(buffer, buf + *offset, count))
    97                  return -EFAULT;
    98          *offset += count;
    99          return count;
   100  }
   101
   102  static ssize_t lfs_write_file2(struct file *filp, const char *buffer,
   103                                 size_t count, loff_t * offset)
   104  {
   105          char *p = buf;
   106          struct kfifo *myfifo = (struct kfifo *)filp->private_data;
   107
   108          if (*offset != 0)
   109                  return -EINVAL;
   110
   111          if (count >= TEST_BUF_LEN)
   112                  return -EINVAL;
   113          memset(buf, 0, TEST_BUF_LEN);
   114          if (copy_from_user(buf, buffer, count))
   115                  return -EFAULT;
   116          p = strchr(buf, ' ');
   117          if (!p)
   118                  return -EINVAL;
   119          *p++ = '\0';
   120          myfifo->in = my_atoi(buf);
   121          myfifo->out = my_atoi(p);
   122          return count;
   123  }
   124
   125  static struct file_operations lfs_file_ops = {
   126          .open = lfs_open_file,
   127          .read = lfs_read_file,
   128          .write = lfs_write_file,
   129  };
   130
   131  static struct file_operations lfs_file2_ops = {
   132          .open = lfs_open_file2,
   133          .read = lfs_read_file2,
   134          .write = lfs_write_file2,
   135  };
   136
   137  struct tree_descr myfiles[] = {
   138          {NULL, NULL, 0},
   139          {.name = "kfifo",
   140           .ops = &lfs_file_ops,
   141           .mode = S_IWUSR | S_IRUGO},
   142          {.name = "debug",
   143           .ops = &lfs_file2_ops,
   144           .mode = S_IWUSR | S_IRUGO},
   145          {"", NULL, 0}
   146  };
   147
   148  static int lfs_fill_super(struct super_block *sb, void *data, int silent)
   149  {
   150          return simple_fill_super(sb, LFS_MAGIC, myfiles);
   151  }
   152
   153  static int lfs_get_super(struct file_system_type *fst,
   154                           int flags, const char *devname, void *data,
   155                           struct vfsmount *mnt)
   156  {
   157          return get_sb_single(fst, flags, data, lfs_fill_super, mnt);
   158  }
   159
   160  static struct file_system_type lfs_type = {
   161          .owner = THIS_MODULE,
   162          .name = "demofs",
   163          .get_sb = lfs_get_super,
   164          .kill_sb = kill_litter_super,
   165  };
   166
   167  static int __init lfs_init(void)
   168  {
   169          spin_lock_init(&lock);
   170          fifo = kfifo_alloc(TEST_BUF_LEN, GFP_KERNEL, &lock);
   171          if (IS_ERR(fifo)) {
   172                  kfifo_free(fifo);
   173                  return -ENOMEM;
   174          }
   175          /*
   176           * We just want the overflow comes soon.
   177           * You can, of course, let fifo->out and fifo->out
   178           * to be 0. And we can let them increase by 'fifo->size'
   179           * in the user space quietly. Sooner or later, they will
   180           * overflow again like this.
   181           */
   182          fifo->in = fifo->out = 0xffffffff - 0x20;
   183          buf = kmalloc(TEST_BUF_LEN, GFP_KERNEL);
   184          if (!buf) {
   185                  kfifo_free(fifo);
   186                  return -ENOMEM;
   187          }
   188          return register_filesystem(&lfs_type);
   189  }
   190
   191  static void __exit lfs_exit(void)
   192  {
   193          unregister_filesystem(&lfs_type);
   194          kfifo_free(fifo);
   195          kfree(buf);
   196  }
   197
   198  module_init(lfs_init);
   199  module_exit(lfs_exit);
   200
   201  MODULE_LICENSE("GPL");
   202  MODULE_VERSION("1.0");
   203  MODULE_AUTHOR("WANG Cong <xiyou.wangcong@gmail.com>");
   204  MODULE_DESCRIPTION("Show the bug of unsigned integer overflow in kfifo.");
   205  MODULE_SUPPORTED_DEVICE("libfs filesystem");

     1  #include <sys/types.h>
     2  #include <sys/stat.h>
     3  #include <unistd.h>
     4  #include <fcntl.h>
     5
     6  /*
     7   * Ensure that you name this file 'bugshow.c'
     8   * and put it in the same dir with 'bugshow.sh'.
     9   */
    10  int main(void)
    11  {
    12          int fd;
    13          int i;
    14          char buf[256];
    15
    16          if((fd = open("/mnt/libfs/kfifo", O_RDWR)) == -1)
    17                  return -1;
    18          for(i=0;i< 256;i++)
    19                  buf='0';
    20          /*
    21           * I won't check the return value of write.
    22           * And that's the reason why I don't use 'echo'.
    23           */
    24          write(fd, buf, 256);
    25          return 0;
    26  }
    27

--------------------------------------------------------------------------

     1  #! /bin/bash
     2  #bugshow.sh
     3  #Author: WANG Cong, XIPT. <xiyou.wangcong@gmail.com>
     4  #Usage: ./bugshow.sh install your_module_name.ko
     5  #    OR ./bugshow.sh uninstall your_module_name
     6
     7  if [ $# != "2" ]; then
     8          echo "Usage: ./bugshow.sh install your_module_name.ko"
     9          echo "OR ./bugshow.sh uninstall your_module_name"
    10          exit -1
    11  fi
    12  action="$1"
    13  if [ "$action" = "install" ]; then
    14          module=${!#}
    15          /sbin/insmod $module
    16          mkdir -p /mnt/libfs
    17          mount -t demofs none /mnt/libfs
    18          if find ./ -name bugshow.c
    19          then
    20                  gcc -Wall -o bugshow bugshow.c
    21          else
    22                  echo "Can't find bugshow.c!"
    23                  exit -2
    24          fi
    25          ./bugshow
    26          cat /mnt/libfs/debug
    27          ./bugshow
    28          cat /mnt/libfs/debug
    29  elif [ "$action" = "uninstall" ]; then
    30          module=${!#}
    31          umount none
    32          rmdir /mnt/libfs
    33          /sbin/rmmod $module
    34  else
    35          echo "Bad usage!"
    36          exit -3
    37  fi
    38  exit 0

一个简单的补丁如下：

--- kernel/kfifo.c.orig 2007-02-07 19:42:51.000000000 +0800
+++ kernel/kfifo.c      2007-02-07 19:43:31.000000000 +0800
@@ -24,6 +24,7 @@
 #include <linux/slab.h>
 #include <linux/err.h>
 #include <linux/kfifo.h>
+#include <linux/compiler.h>

 /**
  * kfifo_init - allocates a new FIFO using a preallocated buffer
@@ -120,6 +121,12 @@ unsigned int __kfifo_put(struct kfifo *f
 {
        unsigned int l;

+       /*If only fifo->in overflows, let both overflow!*/
+       if (unlikely(fifo->in < fifo->out)) {
+               fifo->out += fifo->size;
+               fifo->in  += fifo->size;
+       }
+
        len = min(len, fifo->size - fifo->in + fifo->out);

        /*
@@ -166,6 +173,12 @@ unsigned int __kfifo_get(struct kfifo *f
 {
        unsigned int l;

+       /*If only fifo->in overflows, let both overflow!*/
+       if (unlikely(fifo->in < fifo->out)) {
+               fifo->out += fifo->size;
+               fifo->in  += fifo->size;
+       }
+
        len = min(len, fifo->in - fifo->out);

        /*

Linux内核中大量使用了队列，这里仅列举它在进程管理中的几处应用。

状态为TASK_RUNNING的进程都会被放入运行队列（runqueue）中，这是通过task_struct（定义在include/linux/sched.h）中的run_list成员来链接的。不过，为了让内核每次都能选取优先级最合适的进程，Linux为每个优先级构建了一个queue！这是通过struct prio_array来实现的，struct prio_array的定义（在kernel/sched.c）大致如下：

struct prio_array {
int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
};

状态为TASK_STOPPED，EXIT_ZOMBIE或EXIT_DEAD的进程不会被放入专门的队列中，它们直接通过pid或者通过父进程的孩子队列来访问。

TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE状态的进程会被放入等待队列。不同的是，每个等待事件都会有一个等待队列，该队列中的进程等待同一事件的完成（不要惊慌！“事件”一个动态的过程，不好通过具体的结构来定义一个“事件”。这里等待一个事件就是查看某个条件是否为真，比如某个标志变量是否为真。）。wait_queue_head_t的定义（include/linux/wait.h）如下：

typedef struct _ _wait_queue_head {
        spinlock_t lock;
        struct list_head task_list;
    }wait_queue_head_t;

typedef struct _ _wait_queue {
        unsigned int flags;
        struct task_struct * task;
        wait_queue_func_t func;
        struct list_head task_list;
    }wait_queue_t;

唤醒的接口虽然只有wake_up*()，但它内部也分成好几种。带“interruptible”的唤醒函数只会唤醒状态是TASK_INTERRUPTIBLE的进程，而不带的则会唤醒TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE的进程；所有唤醒函数都会把等待同一事件的nonexclusive进程全部唤醒，或者把其中一个exclusive的进程唤醒；而带“nr”的则会唤醒指定个数的exclusive的进程，带“all”的会把全部exclusive进程唤醒。带“sync”会忽略优先级的检查，高优先级的进程可能会被延迟。最后，持有自旋锁时只能调用wait_up_locked()。