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>

8 files changed, 724 insertions, 255 deletions

diff --git a/udev/Makefile.am b/udev/Makefile.am
index fa8279dd61..6cd2f23dc3 100644
--- a/udev/Makefile.am
+++ b/udev/Makefile.am
@@ -30,6 +30,7 @@ common_files = \
 	lib/libudev-monitor.c \
 	lib/libudev-enumerate.c \
 	lib/libudev-queue.c \
+	lib/libudev-queue-export.c \
 	lib/libudev-ctrl.c
 
 if USE_SELINUX
diff --git a/udev/lib/exported_symbols b/udev/lib/exported_symbols
index 24a6595462..8e7749e488 100644
--- a/udev/lib/exported_symbols
+++ b/udev/lib/exported_symbols
@@ -68,5 +68,6 @@ udev_queue_get_udev_seqnum
 udev_queue_get_udev_is_active
 udev_queue_get_queue_is_empty
 udev_queue_get_seqnum_is_finished
+udev_queue_get_seqnum_sequence_is_finished
 udev_queue_get_queued_list_entry
 udev_queue_get_failed_list_entry
diff --git a/udev/lib/libudev-private.h b/udev/lib/libudev-private.h
index 9ec5e1aae2..3eb3d7957f 100644
--- a/udev/lib/libudev-private.h
+++ b/udev/lib/libudev-private.h
@@ -150,10 +150,18 @@ void udev_list_entry_set_flag(struct udev_list_entry *list_entry, int flag);
 	     entry = tmp, tmp = udev_list_entry_get_next(tmp))
 
 /* libudev-queue */
-int udev_queue_export_udev_seqnum(struct udev_queue *udev_queue, unsigned long long int seqnum);
-int udev_queue_export_device_queued(struct udev_queue *udev_queue, struct udev_device *udev_device);
-int udev_queue_export_device_finished(struct udev_queue *udev_queue, struct udev_device *udev_device);
-int udev_queue_export_device_failed(struct udev_queue *udev_queue, struct udev_device *udev_device);
+unsigned long long int udev_get_kernel_seqnum(struct udev *udev);
+int udev_queue_read_seqnum(FILE *queue_file, unsigned long long int *seqnum);
+ssize_t udev_queue_read_devpath(FILE *queue_file, char *devpath, size_t size);
+ssize_t udev_queue_skip_devpath(FILE *queue_file);
+
+/* libudev-queue-export */
+struct udev_queue_export *udev_queue_export_new(struct udev *udev);
+void udev_queue_export_unref(struct udev_queue_export *udev_queue_export);
+void udev_queue_export_cleanup(struct udev_queue_export *udev_queue_export);
+int udev_queue_export_device_queued(struct udev_queue_export *udev_queue_export, struct udev_device *udev_device);
+int udev_queue_export_device_finished(struct udev_queue_export *udev_queue_export, struct udev_device *udev_device);
+int udev_queue_export_device_failed(struct udev_queue_export *udev_queue_export, struct udev_device *udev_device);
 
 /* libudev-utils */
 #define UTIL_PATH_SIZE				1024
diff --git a/udev/lib/libudev-queue-export.c b/udev/lib/libudev-queue-export.c
new file mode 100644
index 0000000000..ddb1974dbe
--- /dev/null
+++ b/udev/lib/libudev-queue-export.c
@@ -0,0 +1,473 @@
+/*
+ * 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
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ */
+
+/*
+ * DISCLAIMER - The file format mentioned here is private to udev/libudev,
+ *              and may be changed without notice.
+ *
+ *
+ * The udev event queue is exported as a binary log file.
+ * Each log record consists of a sequence number followed by the device path.
+ *
+ * When a new event is queued, its details are appended to the log.
+ * When the event finishes, a second record is appended to the log
+ * with the same sequence number but a null devpath.
+ *
+ * Example:
+ *	{1, "/devices/virtual/mem/null" },
+ *	{2, "/devices/virtual/mem/zero" },
+ *	{1, "" },
+ * Event 2 is still queued, but event 1 has been finished
+ *
+ * The queue does not grow indefinitely.  It is periodically re-created
+ * to remove finished events.  Atomic rename() makes this transparent to readers.
+ *
+ *
+ * The queue file starts with a single sequence number which specifies the
+ * minimum sequence number in the log that follows.  Any events prior to this
+ * sequence number have already finished.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <dirent.h>
+#include <limits.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <assert.h>
+
+#include "udev.h"
+
+static int rebuild_queue_file(struct udev_queue_export *udev_queue_export);
+
+struct udev_queue_export {
+	struct udev *udev;
+	int failed_count;	/* number of failed events exported */
+	int queued_count;	/* number of unfinished events exported in queue file */
+	FILE *queue_file;
+	unsigned long long int seqnum_max;	/* earliest sequence number in queue file */
+	unsigned long long int seqnum_min;	/* latest sequence number in queue file */
+	int waste_bytes;			/* queue file bytes wasted on finished events */
+};
+
+struct udev_queue_export *udev_queue_export_new(struct udev *udev)
+{
+	struct udev_queue_export *udev_queue_export;
+	unsigned long long int initial_seqnum;
+
+	if (udev == NULL)
+		return NULL;
+
+	udev_queue_export = calloc(1, sizeof(struct udev_queue_export));
+	if (udev_queue_export == NULL)
+		return NULL;
+	udev_queue_export->udev = udev;
+
+	initial_seqnum = udev_get_kernel_seqnum(udev);
+	udev_queue_export->seqnum_min = initial_seqnum;
+	udev_queue_export->seqnum_max = initial_seqnum;
+
+	udev_queue_export_cleanup(udev_queue_export);
+	if (rebuild_queue_file(udev_queue_export) != 0) {
+		free(udev_queue_export);
+		return NULL;
+	}
+
+	return udev_queue_export;
+}
+
+void udev_queue_export_unref(struct udev_queue_export *udev_queue_export)
+{
+	if (udev_queue_export == NULL)
+		return;
+	if (udev_queue_export->queue_file != NULL)
+		fclose(udev_queue_export->queue_file);
+	free(udev_queue_export);
+}
+
+void udev_queue_export_cleanup(struct udev_queue_export *udev_queue_export)
+{
+	char filename[UTIL_PATH_SIZE];
+
+	util_strscpyl(filename, sizeof(filename), udev_get_dev_path(udev_queue_export->udev), "/.udev/queue.tmp", NULL);
+	unlink(filename);
+
+	util_strscpyl(filename, sizeof(filename), udev_get_dev_path(udev_queue_export->udev), "/.udev/queue.bin", NULL);
+	unlink(filename);
+}
+
+
+static int skip_to(FILE *file, long offset)
+{
+	long old_offset;
+
+	/* fseek may drop buffered data, avoid it for small seeks */
+	old_offset = ftell(file);
+	if (offset > old_offset && old_offset - offset <= BUFSIZ) {
+		size_t skip_bytes = old_offset - offset;
+		char buf[skip_bytes];
+
+		if (fread(buf, skip_bytes, 1, file) != skip_bytes)
+			return -1;
+	}
+
+	return fseek(file, offset, SEEK_SET);
+}
+
+struct queue_devpaths {
+	unsigned int devpaths_first;	/* index of first queued event */
+	unsigned int devpaths_size;
+	long devpaths[];		/* seqnum -> offset of devpath in queue file (or 0) */
+};
+
+/*
+ * Returns a table mapping seqnum to devpath file offset for currently queued events.
+ * devpaths[i] represents the event with seqnum = i + udev_queue_export->seqnum_min.
+ */
+static struct queue_devpaths *build_index(struct udev_queue_export *udev_queue_export)
+{
+	struct queue_devpaths *devpaths;
+	unsigned long long int range;
+	long devpath_offset;
+	ssize_t devpath_len;
+	unsigned long long int seqnum;
+	unsigned long long int n;
+	unsigned int i;
+
+	/* seek to the first event in the file */
+	rewind(udev_queue_export->queue_file);
+	udev_queue_read_seqnum(udev_queue_export->queue_file, &seqnum);
+
+	/* allocate the table */
+	range = udev_queue_export->seqnum_min - udev_queue_export->seqnum_max;
+	if (range - 1 > INT_MAX) {
+		err(udev_queue_export->udev, "queue file overflow\n");
+		return NULL;
+	}
+	devpaths = calloc(1, sizeof(struct queue_devpaths) + (range + 1) * sizeof(long));
+	if (index == NULL)
+		return NULL;
+	devpaths->devpaths_size = range + 1;
+
+	/* read all records and populate the table */
+	while(1) {
+		if (udev_queue_read_seqnum(udev_queue_export->queue_file, &seqnum) < 0)
+			break;
+		n = seqnum - udev_queue_export->seqnum_max;
+		if (n >= devpaths->devpaths_size)
+			goto read_error;
+
+		devpath_offset = ftell(udev_queue_export->queue_file);
+		devpath_len = udev_queue_skip_devpath(udev_queue_export->queue_file);
+		if (devpath_len < 0)
+			goto read_error;
+
+		if (devpath_len > 0)
+			devpaths->devpaths[n] = devpath_offset;
+		else
+			devpaths->devpaths[n] = 0;
+	}
+
+	/* find first queued event */
+	for (i = 0; i < devpaths->devpaths_size; i++) {
+		if (devpaths->devpaths[i] != 0)
+			break;
+	}
+	devpaths->devpaths_first = i;
+
+	return devpaths;
+
+read_error:
+	err(udev_queue_export->udev, "queue file corrupted\n");
+	free(devpaths);
+	return NULL;
+}
+
+static int rebuild_queue_file(struct udev_queue_export *udev_queue_export)
+{
+	unsigned long long int seqnum;
+	struct queue_devpaths *devpaths = NULL;
+	char filename[UTIL_PATH_SIZE];
+	char filename_tmp[UTIL_PATH_SIZE];
+	FILE *new_queue_file = NULL;
+	unsigned int i;
+
+	/* read old queue file */
+	if (udev_queue_export->queue_file != NULL) {
+		dbg(udev_queue_export->udev, "compacting queue file, freeing %d bytes\n",
+						udev_queue_export->waste_bytes);
+
+		devpaths = build_index(udev_queue_export);
+		if (devpaths != NULL)
+			udev_queue_export->seqnum_max += devpaths->devpaths_first;
+	}
+	if (devpaths == NULL) {
+		dbg(udev_queue_export->udev, "creating empty queue file\n");
+		udev_queue_export->queued_count = 0;
+		udev_queue_export->seqnum_max = udev_queue_export->seqnum_min;
+	}
+
+	/* create new queue file */
+	util_strscpyl(filename_tmp, sizeof(filename_tmp), udev_get_dev_path(udev_queue_export->udev), "/.udev/queue.tmp", NULL);
+	new_queue_file = fopen(filename_tmp, "w+");
+	if (new_queue_file == NULL)
+		goto error;
+	seqnum = udev_queue_export->seqnum_max;
+	fwrite(&seqnum, 1, sizeof(unsigned long long int), new_queue_file);
+
+	/* copy unfinished events only to the new file */
+	if (devpaths != NULL) {
+		for (i = devpaths->devpaths_first; i < devpaths->devpaths_size; i++) {
+			char devpath[UTIL_PATH_SIZE];
+			int err;
+			unsigned short devpath_len;
+
+			if (devpaths->devpaths[i] != 0)
+			{
+				skip_to(udev_queue_export->queue_file, devpaths->devpaths[i]);
+				err = udev_queue_read_devpath(udev_queue_export->queue_file, devpath, sizeof(devpath));
+				devpath_len = err;
+
+				fwrite(&seqnum, sizeof(unsigned long long int), 1, new_queue_file);
+				fwrite(&devpath_len, sizeof(unsigned short), 1, new_queue_file);
+				fwrite(devpath, 1, devpath_len, new_queue_file);
+			}
+			seqnum++;
+		}
+		free(devpaths);
+		devpaths = NULL;
+	}
+	fflush(new_queue_file);
+	if (ferror(new_queue_file))
+		goto error;
+
+	/* rename the new file on top of the old one */
+	util_strscpyl(filename, sizeof(filename), udev_get_dev_path(udev_queue_export->udev), "/.udev/queue.bin", NULL);
+	if (rename(filename_tmp, filename) != 0)
+		goto error;
+
+	if (udev_queue_export->queue_file != NULL)
+		fclose(udev_queue_export->queue_file);
+	udev_queue_export->queue_file = new_queue_file;
+	udev_queue_export->waste_bytes = 0;
+
+	return 0;
+
+error:
+	err(udev_queue_export->udev, "failed to create queue file: %m\n");
+	udev_queue_export_cleanup(udev_queue_export);
+
+	if (udev_queue_export->queue_file != NULL) {
+		fclose(udev_queue_export->queue_file);
+		udev_queue_export->queue_file = NULL;
+	}
+	if (new_queue_file != NULL)
+		fclose(new_queue_file);
+
+	if (devpaths != NULL)
+		free(devpaths);
+	udev_queue_export->queued_count = 0;
+	udev_queue_export->waste_bytes = 0;
+	udev_queue_export->seqnum_max = udev_queue_export->seqnum_min;
+
+	return -1;
+}
+
+static int write_queue_record(struct udev_queue_export *udev_queue_export,
+			      unsigned long long int seqnum, const char *devpath, size_t devpath_len)
+{
+	unsigned short len;
+
+	if (udev_queue_export->queue_file == NULL) {
+		dbg(udev_queue_export->udev, "can't record event: queue file not available\n");
+		return -1;
+	}
+
+	if (fwrite(&seqnum, sizeof(unsigned long long int), 1, udev_queue_export->queue_file) != 1)
+		goto write_error;
+
+	len = (devpath_len < USHRT_MAX) ? devpath_len : USHRT_MAX;
+	if (fwrite(&len, sizeof(unsigned short), 1, udev_queue_export->queue_file) != 1)
+		goto write_error;
+	if (fwrite(devpath, 1, len, udev_queue_export->queue_file) != len)
+		goto write_error;
+
+	/* *must* flush output; caller may fork */
+	if (fflush(udev_queue_export->queue_file) != 0)
+		goto write_error;
+
+	return 0;
+
+write_error:
+	/* if we failed half way through writing a record to a file,
+	   we should not try to write any further records to it. */
+	err(udev_queue_export->udev, "error writing to queue file: %m\n");
+	fclose(udev_queue_export->queue_file);
+	udev_queue_export->queue_file = NULL;
+
+	return -1;
+}
+
+
+enum device_state {
+	DEVICE_QUEUED,
+	DEVICE_FINISHED,
+	DEVICE_FAILED,
+};
+
+static inline size_t queue_record_size(size_t devpath_len)
+{
+	return sizeof(unsigned long long int) + sizeof(unsigned short int) + devpath_len;
+}
+
+static int update_queue(struct udev_queue_export *udev_queue_export,
+			 struct udev_device *udev_device, enum device_state state)
+{
+	unsigned long long int seqnum = udev_device_get_seqnum(udev_device);
+	const char *devpath = NULL;
+	size_t devpath_len = 0;
+	int bytes;
+	int err;
+
+	if (state == DEVICE_QUEUED) {
+		devpath = udev_device_get_devpath(udev_device);
+		devpath_len = strlen(devpath);
+	}
+
+	/* recover from an earlier failed rebuild */
+	if (udev_queue_export->queue_file == NULL) {
+		if (rebuild_queue_file(udev_queue_export) != 0)
+			return -1;
+	}
+
+	/* when the queue files grow too large, they must be garbage collected and rebuilt */
+	bytes = ftell(udev_queue_export->queue_file) + queue_record_size(devpath_len);
+
+	/* if we're removing the last event from the queue, that's the best time to rebuild it */
+	if (state != DEVICE_QUEUED && udev_queue_export->queued_count == 1 && bytes > 2048) {
+		/* because we don't need to read the old queue file */
+		fclose(udev_queue_export->queue_file);
+		udev_queue_export->queue_file = NULL;
+		rebuild_queue_file(udev_queue_export);
+		return 0;
+	}
+
+	/* try to rebuild the queue files before they grow larger than one page. */
+	if ((udev_queue_export->waste_bytes > bytes / 2) && bytes > 4096)
+		rebuild_queue_file(udev_queue_export);
+
+	/* don't record a finished event, if we already dropped the event in a failed rebuild */
+	if (seqnum < udev_queue_export->seqnum_max)
+		return 0;
+
+	/* now write to the queue */
+	if (state == DEVICE_QUEUED) {
+		udev_queue_export->queued_count++;
+		udev_queue_export->seqnum_min = seqnum;
+	} else {
+		udev_queue_export->waste_bytes += queue_record_size(devpath_len) + queue_record_size(0);
+		udev_queue_export->queued_count--;
+	}
+	err = write_queue_record(udev_queue_export, seqnum, devpath, devpath_len);
+
+	/* try to handle ENOSPC */
+	if (err != 0 && udev_queue_export->queued_count == 0) {
+		udev_queue_export_cleanup(udev_queue_export);
+		err = rebuild_queue_file(udev_queue_export);
+	}
+
+	return err;
+}
+
+static void update_failed(struct udev_queue_export *udev_queue_export,
+			  struct udev_device *udev_device, enum device_state state)
+{
+	struct udev *udev = udev_device_get_udev(udev_device);
+	char filename[UTIL_PATH_SIZE];
+	char *s;
+	size_t l;
+
+	if (state != DEVICE_FAILED && udev_queue_export->failed_count == 0)
+		return;
+
+	/* location of failed file */
+	s = filename;
+	l = util_strpcpyl(&s, sizeof(filename), udev_get_dev_path(udev_queue_export->udev), "/.udev/failed/", NULL);
+	util_path_encode(udev_device_get_devpath(udev_device), s, l);
+
+	switch (state) {
+	case DEVICE_FAILED:
+		/* record event in the failed directory */
+		if (udev_queue_export->failed_count == 0)
+			util_create_path(udev, filename);
+		udev_queue_export->failed_count++;
+
+		udev_selinux_setfscreatecon(udev, filename, S_IFLNK);
+		symlink(udev_device_get_devpath(udev_device), filename);
+		udev_selinux_resetfscreatecon(udev);
+		break;
+
+	case DEVICE_QUEUED:
+		/* delete failed file */
+		if (unlink(filename) == 0) {
+			util_delete_path(udev, filename);
+			udev_queue_export->failed_count--;
+		}
+		break;
+
+	case DEVICE_FINISHED:
+		if (udev_device_get_devpath_old(udev_device) != NULL) {
+			/* "move" event - rename failed file to current name, do not delete failed */
+			char filename_old[UTIL_PATH_SIZE];
+
+			s = filename_old;
+			l = util_strpcpyl(&s, sizeof(filename_old), udev_get_dev_path(udev_queue_export->udev), "/.udev/failed/", NULL);
+			util_path_encode(udev_device_get_devpath_old(udev_device), s, l);
+
+			if (rename(filename_old, filename) == 0)
+				info(udev, "renamed devpath, moved failed state of '%s' to %s'\n",
+				     udev_device_get_devpath_old(udev_device), udev_device_get_devpath(udev_device));
+		}
+		break;
+	}
+
+	return;
+}
+
+static int update(struct udev_queue_export *udev_queue_export,
+		  struct udev_device *udev_device, enum device_state state)
+{
+	update_failed(udev_queue_export, udev_device, state);
+
+	if (update_queue(udev_queue_export, udev_device, state) != 0)
+		return -1;
+
+	return 0;
+}
+
+int udev_queue_export_device_queued(struct udev_queue_export *udev_queue_export, struct udev_device *udev_device)
+{
+	return update(udev_queue_export, udev_device, DEVICE_QUEUED);
+}
+
+int udev_queue_export_device_finished(struct udev_queue_export *udev_queue_export, struct udev_device *udev_device)
+{
+	return update(udev_queue_export, udev_device, DEVICE_FINISHED);
+}
+
+int udev_queue_export_device_failed(struct udev_queue_export *udev_queue_export, struct udev_device *udev_device)
+{
+	return update(udev_queue_export, udev_device, DEVICE_FAILED);
+}
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;
-}
diff --git a/udev/lib/libudev.h b/udev/lib/libudev.h
index 9346eb4ddd..9b51ea3300 100644
--- a/udev/lib/libudev.h
+++ b/udev/lib/libudev.h
@@ -115,6 +115,8 @@ unsigned long long int udev_queue_get_udev_seqnum(struct udev_queue *udev_queue)
 int udev_queue_get_udev_is_active(struct udev_queue *udev_queue);
 int udev_queue_get_queue_is_empty(struct udev_queue *udev_queue);
 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);
 struct udev_list_entry *udev_queue_get_queued_list_entry(struct udev_queue *udev_queue);
 struct udev_list_entry *udev_queue_get_failed_list_entry(struct udev_queue *udev_queue);
 #endif
diff --git a/udev/udevadm-settle.c b/udev/udevadm-settle.c
index 52d9c0b244..f1052aa148 100644
--- a/udev/udevadm-settle.c
+++ b/udev/udevadm-settle.c
@@ -173,24 +173,16 @@ int udevadm_settle(struct udev *udev, int argc, char *argv[])
 	}
 
 	while (!is_timeout) {
-		/* exit if queue is empty */
-		if (udev_queue_get_queue_is_empty(udev_queue))
-			break;
-
-		/* if asked for, wait for a specific sequence of events */
 		if (start > 0) {
-			unsigned long long seq;
-			int finished;
-
-			finished = 0;
-			for (seq = start; seq <= end; seq++) {
-				finished  = udev_queue_get_seqnum_is_finished(udev_queue, seq);
-				if (!finished)
-					break;
-			}
-			if (finished)
+			/* if asked for, wait for a specific sequence of events */
+			if (udev_queue_get_seqnum_sequence_is_finished(udev_queue, start, end) == 1)
+				break;
+		} else {
+			/* exit if queue is empty */
+			if (udev_queue_get_queue_is_empty(udev_queue))
 				break;
 		}
+
 		usleep(1000 * 1000 / LOOP_PER_SECOND);
 	}
 
diff --git a/udev/udevd.c b/udev/udevd.c
index 23d594f556..5ee61d2e23 100644
--- a/udev/udevd.c
+++ b/udev/udevd.c
@@ -65,6 +65,7 @@ static void reap_sigchilds(void);
 
 static int debug_trace;
 static struct udev_rules *rules;
+static struct udev_queue_export *udev_queue_export;
 static struct udev_ctrl *udev_ctrl;
 static struct udev_monitor *kernel_monitor;
 static volatile sig_atomic_t sigchilds_waiting;
@@ -78,12 +79,6 @@ static int max_childs;
 static int childs;
 static struct udev_list_node event_list;
 
-enum event_state {
-	EVENT_QUEUED,
-	EVENT_FINISHED,
-	EVENT_FAILED,
-};
-
 static struct udev_event *node_to_event(struct udev_list_node *node)
 {
 	char *event;
@@ -93,76 +88,15 @@ static struct udev_event *node_to_event(struct udev_list_node *node)
 	return (struct udev_event *)event;
 }
 
-static void export_event_state(struct udev_event *event, enum event_state state)
-{
-	char filename[UTIL_PATH_SIZE];
-	char filename_failed[UTIL_PATH_SIZE];
-	char *s;
-	size_t l;
-
-	/* location of queue file */
-	snprintf(filename, sizeof(filename), "%s/.udev/queue/%llu",
-		 udev_get_dev_path(event->udev), udev_device_get_seqnum(event->dev));
-
-	/* location of failed file */
-	s = filename_failed;
-	l = util_strpcpyl(&s, sizeof(filename_failed), udev_get_dev_path(event->udev), "/.udev/failed/", NULL);
-	util_path_encode(udev_device_get_devpath(event->dev), s, l);
-
-	switch (state) {
-	case EVENT_QUEUED:
-		if(unlink(filename_failed) == 0)
-			util_delete_path(event->udev, filename_failed);
-		util_create_path(event->udev, filename);
-		udev_selinux_setfscreatecon(event->udev, filename, S_IFLNK);
-		symlink(udev_device_get_devpath(event->dev), filename);
-		udev_selinux_resetfscreatecon(event->udev);
-		break;
-	case EVENT_FINISHED:
-		if (udev_device_get_devpath_old(event->dev) != NULL) {
-			/* "move" event - rename failed file to current name, do not delete failed */
-			char filename_failed_old[UTIL_PATH_SIZE];
-
-			s = filename_failed_old;
-			l = util_strpcpyl(&s, sizeof(filename_failed_old), udev_get_dev_path(event->udev), "/.udev/failed/", NULL);
-			util_path_encode(udev_device_get_devpath_old(event->dev), s, l);
-			if (rename(filename_failed_old, filename_failed) == 0)
-				info(event->udev, "renamed devpath, moved failed state of '%s' to %s'\n",
-				     udev_device_get_devpath_old(event->dev), udev_device_get_devpath(event->dev));
-		} else {
-			if (unlink(filename_failed) == 0)
-				util_delete_path(event->udev, filename_failed);
-		}
-
-		unlink(filename);
-
-		/* clean up possibly empty queue directory */
-		if (udev_list_is_empty(&event_list))
-			util_delete_path(event->udev, filename);
-		break;
-	case EVENT_FAILED:
-		/* move failed event to the failed directory */
-		util_create_path(event->udev, filename_failed);
-		rename(filename, filename_failed);
-
-		/* clean up possibly empty queue directory */
-		if (udev_list_is_empty(&event_list))
-			util_delete_path(event->udev, filename);
-		break;
-	}
-
-	return;
-}
-
 static void event_queue_delete(struct udev_event *event)
 {
 	udev_list_node_remove(&event->node);
 
 	/* mark as failed, if "add" event returns non-zero */
 	if (event->exitstatus && strcmp(udev_device_get_action(event->dev), "add") == 0)
-		export_event_state(event, EVENT_FAILED);
+		udev_queue_export_device_failed(udev_queue_export, event->dev);
 	else
-		export_event_state(event, EVENT_FINISHED);
+		udev_queue_export_device_finished(udev_queue_export, event->dev);
 
 	udev_device_unref(event->dev);
 	udev_event_unref(event);
@@ -201,6 +135,7 @@ static void event_fork(struct udev_event *event)
 	switch (pid) {
 	case 0:
 		/* child */
+		udev_queue_export_unref(udev_queue_export);
 		udev_ctrl_unref(udev_ctrl);
 		logging_close();
 		logging_init("udevd-event");
@@ -267,27 +202,12 @@ static void event_fork(struct udev_event *event)
 
 static void event_queue_insert(struct udev_event *event)
 {
-	char filename[UTIL_PATH_SIZE];
-	int fd;
-
 	event->queue_time = time(NULL);
 
-	export_event_state(event, EVENT_QUEUED);
+	udev_queue_export_device_queued(udev_queue_export, event->dev);
 	info(event->udev, "seq %llu queued, '%s' '%s'\n", udev_device_get_seqnum(event->dev),
 	     udev_device_get_action(event->dev), udev_device_get_subsystem(event->dev));
 
-	util_strscpyl(filename, sizeof(filename), udev_get_dev_path(event->udev), "/.udev/uevent_seqnum", NULL);
-	fd = open(filename, O_WRONLY|O_TRUNC|O_CREAT, 0644);
-	if (fd >= 0) {
-		char str[32];
-		int len;
-
-		len = sprintf(str, "%llu\n", udev_device_get_seqnum(event->dev));
-		write(fd, str, len);
-		close(fd);
-	}
-
-
 	udev_list_node_append(&event->node, &event_list);
 	run_exec_q = 1;
 
@@ -637,59 +557,6 @@ static void reap_sigchilds(void)
 	}
 }
 
-static void cleanup_queue_dir(struct udev *udev)
-{
-	char dirname[UTIL_PATH_SIZE];
-	char filename[UTIL_PATH_SIZE];
-	DIR *dir;
-
-	util_strscpyl(filename, sizeof(filename), udev_get_dev_path(udev), "/.udev/uevent_seqnum", NULL);
-	unlink(filename);
-
-	util_strscpyl(dirname, sizeof(dirname), udev_get_dev_path(udev), "/.udev/queue", NULL);
-	dir = opendir(dirname);
-	if (dir != NULL) {
-		while (1) {
-			struct dirent *dent;
-
-			dent = readdir(dir);
-			if (dent == NULL || dent->d_name[0] == '\0')
-				break;
-			if (dent->d_name[0] == '.')
-				continue;
-			unlinkat(dirfd(dir), dent->d_name, 0);
-		}
-		closedir(dir);
-		rmdir(dirname);
-	}
-}
-
-static void export_initial_seqnum(struct udev *udev)
-{
-	char filename[UTIL_PATH_SIZE];
-	int fd;
-	char seqnum[32];
-	ssize_t len = 0;
-
-	util_strscpyl(filename, sizeof(filename), udev_get_sys_path(udev), "/kernel/uevent_seqnum", NULL);
-	fd = open(filename, O_RDONLY);
-	if (fd >= 0) {
-		len = read(fd, seqnum, sizeof(seqnum)-1);
-		close(fd);
-	}
-	if (len <= 0) {
-		strcpy(seqnum, "0\n");
-		len = 3;
-	}
-	util_strscpyl(filename, sizeof(filename), udev_get_dev_path(udev), "/.udev/uevent_seqnum", NULL);
-	util_create_path(udev, filename);
-	fd = open(filename, O_WRONLY|O_TRUNC|O_CREAT, 0644);
-	if (fd >= 0) {
-		write(fd, seqnum, len);
-		close(fd);
-	}
-}
-
 static void startup_log(struct udev *udev)
 {
 	FILE *f;
@@ -837,8 +704,11 @@ int main(int argc, char *argv[])
 		goto exit;
 	}
 	udev_list_init(&event_list);
-	cleanup_queue_dir(udev);
-	export_initial_seqnum(udev);
+	udev_queue_export = udev_queue_export_new(udev);
+	if (udev_queue_export == NULL) {
+		err(udev, "error creating queue file\n");
+		goto exit;
+	}
 
 	if (daemonize) {
 		pid_t pid;
@@ -1027,9 +897,11 @@ handle_signals:
 			settle_pid = 0;
 		}
 	}
-	cleanup_queue_dir(udev);
+	udev_queue_export_cleanup(udev_queue_export);
 	rc = 0;
 exit:
+
+	udev_queue_export_unref(udev_queue_export);
 	udev_rules_unref(rules);
 	udev_ctrl_unref(udev_ctrl);
 	if (inotify_fd >= 0)