Sort module list for /proc/modules seq file reads

Hi Andrew,

Here is the updated version of the module list sort for coherent seq file reads. It includes, in the comments, a byte-by-byte test case that shows the race it solves. It has been updated since the last post to make sure the byte-by-byte read works correctly by using "pos" instead of m->private as position indicator.

Only /proc/modules is provided as a user, but it should eventually be used by other kernel parts, such as kallsyms, to make sure they protect themselves from list modification while they iterate on them.

It applies to 2.6.23-rc3-mm1.

Mathieu

Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Add support for sorted list in seq_file. It aims at changing the way /proc/modules and kallsyms iterates on the module list to remove a race between module unload and module/symbol listing.

The list is sorted by ascending list_head pointer address.

Changelog:

When reading the data by small chunks (i.e. byte by byte), the index (ppos) is incremented by seq_read() directly and no "next" callback is called when going to the next module.

Therefore, use ppos instead of m->private to deal with the fact that this index is incremented directly to pass to the next module in seq_read() after the buffer has been emptied.

---
 fs/seq_file.c            |   47 +++++++++++++++++++++++++++++++++++++++++++++++
 include/linux/seq_file.h |   20 ++++++++++++++++++++
 2 files changed, 67 insertions(+)

Index: linux-2.6-lttng/fs/seq_file.c
===================================================================
@@ -510,3 +510,50 @@ struct list_head *seq_list_next(void *v,
 }
 
 EXPORT_SYMBOL(seq_list_next);
+
+struct list_head *seq_sorted_list_start(struct list_head *head, loff_t *ppos)
+{
+	struct list_head *lh;
+
+	list_for_each(lh, head)
+		if ((unsigned long)lh >= *ppos) {
+			*ppos = (unsigned long)lh;
+			return lh;
+		}
+	return NULL;
+}
+
+EXPORT_SYMBOL(seq_sorted_list_start);
+
+struct list_head *seq_sorted_list_start_head(struct list_head *head,
+		loff_t *ppos)
+{
+	struct list_head *lh;
+
+	if (!*ppos) {
+		*ppos = (unsigned long)head;
+		return head;
+	}
+	list_for_each(lh, head)
+		if ((unsigned long)lh >= *ppos) {
+			*ppos = (long)lh->prev;
+			return lh->prev;
+		}
+	return NULL;
+}
+
+EXPORT_SYMBOL(seq_sorted_list_start_head);
+
+struct list_head *seq_sorted_list_next(void *p, struct list_head *head,
+		loff_t *ppos)
+{
+	struct list_head *lh;
+	void *next;
+
+	lh = ((struct list_head *)p)->next;
+	next = (lh == head) ? NULL : lh;
+	*ppos = next ? (unsigned long)next : -1UL;
+	return next;
+}
+
+EXPORT_SYMBOL(seq_sorted_list_next);

Index: linux-2.6-lttng/include/linux/seq_file.h
===================================================================
@@ -63,5 +63,25 @@ extern struct list_head *seq_list_start_
 extern struct list_head *seq_list_next(void *v, struct list_head *head,
 		loff_t *ppos);
 
+/*
+ * Helpers for iteration over a list sorted by ascending head pointer address.
+ * To be used in contexts where preemption cannot be disabled to insure to
+ * continue iteration on a modified list starting at the same location where it
+ * stopped, or at a following location. It insures that the lost information
+ * will only be in elements added/removed from the list between iterations.
+ * void *pos is only used to get the next list element and may not be a valid
+ * list_head anymore when given to seq_sorted_list_start() or
+ * seq_sorted_list_start_head().
+ */
+extern struct list_head *seq_sorted_list_start(struct list_head *head,
+		loff_t *ppos);
+extern struct list_head *seq_sorted_list_start_head(struct list_head *head,
+		loff_t *ppos);
+/*
+ * next must be called with an existing p node
+ */
+extern struct list_head *seq_sorted_list_next(void *p, struct list_head *head,
+		loff_t *ppos);
+
 #endif
 #endif

Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

A race that appears both in /proc/modules and in kallsyms: if, between the seq file reads, the process is put to sleep and at this moment a module is or removed from the module list, the listing will skip an amount of modules/symbols corresponding to the amount of elements present in the unloaded module, but at the current position in the list if the iteration is located after the removed module.

The cleanest way I found to deal with this problem is to sort the module list. We can then keep the old struct module * as the old iterator, knowing the it may be removed between the seq file reads, but we only use it as "get next". If it is not present in the module list, the next pointer will be used.

By doing this, removing a given module will now only fuzz the output related to this specific module, not any random module anymore. Since modprobe uses /proc/modules, it might be important to make sure multiple concurrent running modprobes won't interfere with each other.

Small test program for this:

#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

#define BUFSIZE 1024

int main()

{
	int fd = open("/proc/modules", O_RDONLY);
	char buf[BUFSIZE];
	ssize_t size;

	do {
		size = read(fd, buf, 1);
		printf("%c", buf[0]);
		usleep(100000);
	} while(size > 0);

	close(fd);
	return 0;
}

Actual test (kernel 2.6.23-rc3):

dijkstra:~# lsmod
Module                  Size  Used by
pl2303                 18564  0
usbserial              29032  1 pl2303
ppdev                   7844  0
sky2                   37476  0
skge                   36368  0
rtc                    10104  0
snd_hda_intel         265628  0

(here, while we are printing the 2nd line, I rmmod pl2303)

compudj@dijkstra:~/test$ ./module
pl2303 18564 0 - Live 0xf886e000
usbserial 29032 1 pl2303, Live 0xf8865000
sky2 37476 0 - Live 0xf884f000
skge 36368 0 - Live 0xf8838000
rtc 10104 0 - Live 0xf8825000

We see the the 2nd line is garbage.

Now, with my patch applied:
(here, while we are printing the rtc module, I rmmod rtc)
nd_hda_intel 268708 0 - Live 0xf8820000 ltt_control 2372 0 - Live 0xf8866000
rtc 10392 0 - Live 0xf886d000
skge 36768 0 - Live 0xf8871000
ltt_statedump 8516 0 - Live 0xf887b000

We see that since the rtc line was already in the buffer, it has been printed completely.

(here, while we are printing the skge module, I rmmod rtc)
snd_hda_intel 268708 0 - Live 0xf8820000 ltt_control 2372 0 - Live 0xf8866000
rtc 10392 0 - Live 0xf886d000
skge 36768 0 - Live 0xf8871000
ltt_statedump 8516 0 - Live 0xf887b000
sky2 38420 0 - Live 0xf88cd000

We see that the iteration continued at the same position even though the rtc module, located in earlier addresses, was removed.

Changelog:

When reading the data by small chunks (i.e. byte by byte), the index (ppos) is incremented by seq_read() directly and no "next" callback is called when going to the next module.

Therefore, use ppos instead of m->private to deal with the fact that this index is incremented directly to pass to the next module in seq_read() after the buffer has been emptied.

Before fix, it prints the first module indefinitely. The patch fixes this.

---
 kernel/module.c |   26 +++++++++++++++++++++-----
 1 file changed, 21 insertions(+), 5 deletions(-)

Index: linux-2.6-lttng/kernel/module.c
===================================================================
@@ -63,8 +63,10 @@ extern int module_sysfs_initialized;
 /* If this is set, the section belongs in the init part of the module */
 #define INIT_OFFSET_MASK (1UL << (BITS_PER_LONG-1))
 
-/* List of modules, protected by module_mutex or preempt_disable
- * (add/delete uses stop_machine). */
+/*
+ * List of modules, protected by module_mutex or preempt_disable
+ * (add/delete uses stop_machine). Sorted by ascending list node address.
+ */
 DEFINE_MUTEX(module_mutex);
 LIST_HEAD(modules);
 static DECLARE_MUTEX(notify_mutex);

@@ -2130,10 +2132,24 @@ nomodsectinfo:
 /*
  * link the module with the whole machine is stopped with interrupts off
  * - this defends against kallsyms not taking locks
+ * We sort the modules by struct module pointer address to permit correct
+ * iteration over modules of, at least, kallsyms for preemptible operations,
+ * such as read(). Sorting by struct module pointer address is equivalent to
+ * sort by list node address.
  */
 static int __link_module(void *_mod)
 {
-	struct module *mod = _mod;
+	struct module *mod = _mod, *iter;
+
+	list_for_each_entry_reverse(iter, &modules, list) {
+		BUG_ON(iter == mod);	/* Should never be in the list twice */
+		if (iter < mod) {
+			/* We belong to the location right after iter. */
+			list_add(&mod->list, &iter->list);
+			return 0;
+		}
+	}
+	/* We should be added at the head of the list */
 	list_add(&mod->list, &modules);
 	return 0;
 }

@@ -2398,12 +2414,12 @@ unsigned long module_kallsyms_lookup_nam
 static void *m_start(struct seq_file *m, loff_t *pos)
 {
 	mutex_lock(&module_mutex);
-	return seq_list_start(&modules, *pos);
+	return seq_sorted_list_start(&modules, pos);
 }
 
 static void *m_next(struct seq_file *m, void *p, loff_t *pos)
 {
-	return seq_list_next(p, &modules, pos);
+	return seq_sorted_list_next(p, &modules, pos);
 }
 
 static void m_stop(struct seq_file *m, void *p)

Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68