udevd: implement a more efficient queue file format

Directory lookups show up in profiling. The queue files are responsible
for a large proportion of file-related system calls in udev coldplug.

Instead of creating a file for each event, append their details to a
log file.  The file is periodically rebuilt (garbage-collected) to
prevent it from growing indefinitely.

This single queue file replaces both the queue directory and the
uevent_seqnum file. On desktop systems the file tends not to grow
beyond one page. So it should also save a small amount of memory in
tmpfs.

Tests on a running EeePC indicate average savings of 5% *udevd* cpu time
as measured by oprofile. __link_path_walk is reduced from 1.5% to
1.3%. It is not completely clear where the rest of the gains come from.

In tests running ~400 events, the queue file is rebuilt about 5 times.

Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>

1 files changed, 215 insertions, 95 deletions

diff --git a/udev/lib/libudev-queue.c b/udev/lib/libudev-queue.c
index 8dce6c314d..cf1ddf3a07 100644
--- a/udev/lib/libudev-queue.c
+++ b/udev/lib/libudev-queue.c
@@ -2,6 +2,7 @@
  * libudev - interface to udev device information
  *
  * Copyright (C) 2008 Kay Sievers <kay.sievers@vrfy.org>
+ * Copyright (C) 2009 Alan Jenkins <alan-jenkins@tuffmail.co.uk>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -17,6 +18,7 @@
 #include <string.h>
 #include <dirent.h>
 #include <fcntl.h>
+#include <limits.h>
 #include <sys/stat.h>
 
 #include "libudev.h"
@@ -25,7 +27,6 @@
 struct udev_queue {
 	struct udev *udev;
 	int refcount;
-	unsigned long long int last_seen_udev_seqnum;
 	struct udev_list_node queue_list;
 	struct udev_list_node failed_list;
 };
@@ -74,7 +75,7 @@ struct udev *udev_queue_get_udev(struct udev_queue *udev_queue)
 	return udev_queue->udev;
 }
 
-unsigned long long int udev_queue_get_kernel_seqnum(struct udev_queue *udev_queue)
+unsigned long long int udev_get_kernel_seqnum(struct udev *udev)
 {
 	char filename[UTIL_PATH_SIZE];
 	unsigned long long int seqnum;
@@ -82,9 +83,7 @@ unsigned long long int udev_queue_get_kernel_seqnum(struct udev_queue *udev_queu
 	char buf[32];
 	ssize_t len;
 
-	if (udev_queue == NULL)
-		return -EINVAL;
-	util_strscpyl(filename, sizeof(filename), udev_get_sys_path(udev_queue->udev), "/kernel/uevent_seqnum", NULL);
+	util_strscpyl(filename, sizeof(filename), udev_get_sys_path(udev), "/kernel/uevent_seqnum", NULL);
 	fd = open(filename, O_RDONLY);
 	if (fd < 0)
 		return 0;
@@ -94,130 +93,271 @@ unsigned long long int udev_queue_get_kernel_seqnum(struct udev_queue *udev_queu
 		return 0;
 	buf[len-1] = '\0';
 	seqnum = strtoull(buf, NULL, 10);
-	dbg(udev_queue->udev, "seqnum=%llu\n", seqnum);
 	return seqnum;
 }
 
-unsigned long long int udev_queue_get_udev_seqnum(struct udev_queue *udev_queue)
+unsigned long long int udev_queue_get_kernel_seqnum(struct udev_queue *udev_queue)
 {
-	char filename[UTIL_PATH_SIZE];
 	unsigned long long int seqnum;
-	int fd;
-	char buf[32];
-	ssize_t len;
 
 	if (udev_queue == NULL)
 		return -EINVAL;
-	util_strscpyl(filename, sizeof(filename), udev_get_dev_path(udev_queue->udev), "/.udev/uevent_seqnum", NULL);
-	fd = open(filename, O_RDONLY);
-	if (fd < 0)
-		return 0;
-	len = read(fd, buf, sizeof(buf));
-	close(fd);
-	if (len <= 2)
-		return 0;
-	buf[len-1] = '\0';
-	seqnum = strtoull(buf, NULL, 10);
+
+	seqnum = udev_get_kernel_seqnum(udev_queue->udev);
 	dbg(udev_queue->udev, "seqnum=%llu\n", seqnum);
-	udev_queue->last_seen_udev_seqnum = seqnum;
 	return seqnum;
 }
 
-int udev_queue_get_udev_is_active(struct udev_queue *udev_queue)
+int udev_queue_read_seqnum(FILE *queue_file, unsigned long long int *seqnum)
+{
+	if (fread(seqnum, sizeof(unsigned long long int), 1, queue_file) != 1)
+		return -1;
+
+	return 0;
+}
+
+ssize_t udev_queue_skip_devpath(FILE *queue_file)
+{
+	unsigned short int len;
+
+	if (fread(&len, sizeof(unsigned short int), 1, queue_file) == 1) {
+		char devpath[len];
+
+		/* use fread to skip, fseek might drop buffered data */
+		if (fread(devpath, 1, len, queue_file) == len)
+			return len;
+	}
+
+	return -1;
+}
+
+ssize_t udev_queue_read_devpath(FILE *queue_file, char *devpath, size_t size)
+{
+	unsigned short int read_bytes = 0;
+	unsigned short int len;
+
+	if (fread(&len, sizeof(unsigned short int), 1, queue_file) != 1)
+		return -1;
+
+	read_bytes = (len < size - 1) ? len : size - 1;
+	if (fread(devpath, 1, read_bytes, queue_file) != read_bytes)
+		return -1;
+	devpath[read_bytes] = '\0';
+
+	/* if devpath was too long, skip unread characters */
+	if (read_bytes != len) {
+		unsigned short int skip_bytes = len - read_bytes;
+		char buf[skip_bytes];
+
+		if (fread(buf, 1, skip_bytes, queue_file) != skip_bytes)
+			return -1;
+	}
+
+	return read_bytes;
+}
+
+static FILE *open_queue_file(struct udev_queue *udev_queue, unsigned long long int *seqnum_start)
 {
 	char filename[UTIL_PATH_SIZE];
-	struct stat statbuf;
+	FILE *queue_file;
 
-	if (udev_queue == NULL)
+	util_strscpyl(filename, sizeof(filename), udev_get_dev_path(udev_queue->udev), "/.udev/queue.bin", NULL);
+	queue_file = fopen(filename, "r");
+	if (queue_file == NULL)
+		return NULL;
+
+	if (udev_queue_read_seqnum(queue_file, seqnum_start) < 0) {
+		err(udev_queue->udev, "corrupt queue file\n");
+		fclose(queue_file);
+		return NULL;
+	}
+
+	return queue_file;
+}
+
+
+unsigned long long int udev_queue_get_udev_seqnum(struct udev_queue *udev_queue)
+{
+	unsigned long long int seqnum_udev;
+	FILE *queue_file;
+
+	queue_file = open_queue_file(udev_queue, &seqnum_udev);
+	if (queue_file == NULL)
 		return 0;
-	util_strscpyl(filename, sizeof(filename), udev_get_dev_path(udev_queue->udev), "/.udev/uevent_seqnum", NULL);
-	if (stat(filename, &statbuf) == 0)
-		return 1;
-	return 0;
+
+	while (1) {
+		unsigned long long int seqnum;
+		ssize_t devpath_len;
+
+		if (udev_queue_read_seqnum(queue_file, &seqnum) < 0)
+			break;
+		devpath_len = udev_queue_skip_devpath(queue_file);
+		if (devpath_len < 0)
+			break;
+		if (devpath_len > 0)
+			seqnum_udev = seqnum;
+	}
+
+	fclose(queue_file);
+	return seqnum_udev;
+}
+
+int udev_queue_get_udev_is_active(struct udev_queue *udev_queue)
+{
+	unsigned long long int seqnum_start;
+	FILE *queue_file;
+
+	queue_file = open_queue_file(udev_queue, &seqnum_start);
+	if (queue_file == NULL)
+		return 0;
+
+	fclose(queue_file);
+	return 1;
 }
 
 int udev_queue_get_queue_is_empty(struct udev_queue *udev_queue)
 {
-	char queuename[UTIL_PATH_SIZE];
-	struct stat statbuf;
 	unsigned long long int seqnum_kernel;
+	unsigned long long int seqnum_udev = 0;
+	int queued = 0;
+	int is_empty = 0;
+	FILE *queue_file;
 
 	if (udev_queue == NULL)
 		return -EINVAL;
-	util_strscpyl(queuename, sizeof(queuename), udev_get_dev_path(udev_queue->udev), "/.udev/queue", NULL);
-	if (stat(queuename, &statbuf) == 0) {
+	queue_file = open_queue_file(udev_queue, &seqnum_udev);
+	if (queue_file == NULL)
+		return 1;
+
+	while (1) {
+		unsigned long long int seqnum;
+		ssize_t devpath_len;
+
+		if (udev_queue_read_seqnum(queue_file, &seqnum) < 0)
+			break;
+		devpath_len = udev_queue_skip_devpath(queue_file);
+		if (devpath_len < 0)
+			break;
+
+		if (devpath_len > 0) {
+			queued++;
+			seqnum_udev = seqnum;
+		} else {
+			queued--;
+		}
+	}
+
+	if (queued > 0) {
 		dbg(udev_queue->udev, "queue is not empty\n");
-		return 0;
+		goto out;
 	}
+
 	seqnum_kernel = udev_queue_get_kernel_seqnum(udev_queue);
-	if (seqnum_kernel <= udev_queue->last_seen_udev_seqnum) {
-		dbg(udev_queue->udev, "queue is empty\n");
-		return 1;
-	}
-	/* update udev seqnum, and check if udev is still running */
-	if (udev_queue_get_udev_seqnum(udev_queue) == 0)
-		if (!udev_queue_get_udev_is_active(udev_queue))
-			return 1;
-	if (seqnum_kernel <= udev_queue->last_seen_udev_seqnum) {
-		dbg(udev_queue->udev, "queue is empty\n");
-		return 1;
+	if (seqnum_udev < seqnum_kernel) {
+		dbg(udev_queue->udev, "queue is empty but kernel events still pending [%llu]<->[%llu]\n",
+					seqnum_kernel, seqnum_udev);
+		goto out;
 	}
-	dbg(udev_queue->udev, "queue is empty, but kernel events still pending [%llu]<->[%llu]\n",
-	     seqnum_kernel, udev_queue->last_seen_udev_seqnum);
-	return 0;
+
+	dbg(udev_queue->udev, "queue is empty\n");
+	is_empty = 1;
+
+out:
+	fclose(queue_file);
+	return is_empty;
 }
 
-int udev_queue_get_seqnum_is_finished(struct udev_queue *udev_queue, unsigned long long int seqnum)
+int udev_queue_get_seqnum_sequence_is_finished(struct udev_queue *udev_queue,
+					       unsigned long long int start, unsigned long long int end)
 {
-	char filename[UTIL_PATH_SIZE];
-	struct stat statbuf;
+	unsigned long long int seqnum = 0;
+	ssize_t devpath_len;
+	int unfinished;
+	FILE *queue_file;
 
 	if (udev_queue == NULL)
 		return -EINVAL;
-	/* did it reach the queue? */
-	if (seqnum > udev_queue->last_seen_udev_seqnum)
-		if (seqnum > udev_queue_get_udev_seqnum(udev_queue))
-			return 0;
-	/* is it still in the queue? */
-	snprintf(filename, sizeof(filename), "%s/.udev/queue/%llu",
-		 udev_get_dev_path(udev_queue->udev), seqnum);
-	if (lstat(filename, &statbuf) == 0)
+	queue_file = open_queue_file(udev_queue, &seqnum);
+	if (queue_file == NULL)
+		return 1;
+	if (start < seqnum)
+		start = seqnum;
+	if (start > end)
+		return 1;
+	if (end - start > INT_MAX - 1)
+		return -EOVERFLOW;
+	unfinished = (end - start) + 1;
+
+	while (unfinished > 0) {
+		if (udev_queue_read_seqnum(queue_file, &seqnum) < 0)
+			break;
+		devpath_len = udev_queue_skip_devpath(queue_file);
+		if (devpath_len < 0)
+			break;
+
+		if (devpath_len == 0) {
+			if (seqnum >= start && seqnum <= end)
+				unfinished--;
+		}
+	}
+	fclose(queue_file);
+
+	return (unfinished == 0);
+}
+
+int udev_queue_get_seqnum_is_finished(struct udev_queue *udev_queue, unsigned long long int seqnum)
+{
+	if (!udev_queue_get_seqnum_sequence_is_finished(udev_queue, seqnum, seqnum))
 		return 0;
+
 	dbg(udev_queue->udev, "seqnum: %llu finished\n", seqnum);
 	return 1;
 }
 
 struct udev_list_entry *udev_queue_get_queued_list_entry(struct udev_queue *udev_queue)
 {
-	char path[UTIL_PATH_SIZE];
-	DIR *dir;
-	struct dirent *dent;
+	unsigned long long int seqnum;
+	FILE *queue_file;
 
 	if (udev_queue == NULL)
 		return NULL;
 	udev_list_cleanup_entries(udev_queue->udev, &udev_queue->queue_list);
-	util_strscpyl(path, sizeof(path), udev_get_dev_path(udev_queue->udev), "/.udev/queue", NULL);
-	dir = opendir(path);
-	if (dir == NULL)
+
+	queue_file = open_queue_file(udev_queue, &seqnum);
+	if (queue_file == NULL)
 		return NULL;
-	for (dent = readdir(dir); dent != NULL; dent = readdir(dir)) {
+
+	while (1) {
 		char syspath[UTIL_PATH_SIZE];
 		char *s;
 		size_t l;
 		ssize_t len;
+		char seqnum_str[32];
+		struct udev_list_entry *list_entry;
+
+		if (udev_queue_read_seqnum(queue_file, &seqnum) < 0)
+			break;
+		snprintf(seqnum_str, sizeof(seqnum_str), "%llu", seqnum);
 
-		if (dent->d_name[0] == '.')
-			continue;
 		s = syspath;
 		l = util_strpcpyl(&s, sizeof(syspath), udev_get_sys_path(udev_queue->udev), NULL);
-		len = readlinkat(dirfd(dir), dent->d_name, s, l);
-		if (len < 0 || (size_t)len >= l)
-			continue;
-		s[len] = '\0';
-		dbg(udev_queue->udev, "found '%s' [%s]\n", syspath, dent->d_name);
-		udev_list_entry_add(udev_queue->udev, &udev_queue->queue_list, syspath, dent->d_name, 0, 0);
+		len = udev_queue_read_devpath(queue_file, s, l);
+		if (len < 0)
+			break;
+
+		if (len > 0) {
+			udev_list_entry_add(udev_queue->udev, &udev_queue->queue_list, syspath, seqnum_str, 0, 0);
+		} else {
+			udev_list_entry_foreach(list_entry, udev_list_get_entry(&udev_queue->queue_list)) {
+				if (strcmp(seqnum_str, udev_list_entry_get_value(list_entry)) == 0) {
+					udev_list_entry_delete(list_entry);
+					break;
+				}
+			}
+		}
 	}
-	closedir(dir);
+	fclose(queue_file);
+
 	return udev_list_get_entry(&udev_queue->queue_list);
 }
 
@@ -259,23 +399,3 @@ struct udev_list_entry *udev_queue_get_failed_list_entry(struct udev_queue *udev
 	closedir(dir);
 	return udev_list_get_entry(&udev_queue->failed_list);
 }
-
-int udev_queue_export_udev_seqnum(struct udev_queue *udev_queue, unsigned long long int seqnum)
-{
-	return -1;
-}
-
-int udev_queue_export_device_queued(struct udev_queue *udev_queue, struct udev_device *udev_device)
-{
-	return -1;
-}
-
-int udev_queue_export_device_finished(struct udev_queue *udev_queue, struct udev_device *udev_device)
-{
-	return -1;
-}
-
-int udev_queue_export_device_failed(struct udev_queue *udev_queue, struct udev_device *udev_device)
-{
-	return -1;
-}