[PATCH 2/2] udevd: Avoid repeated scans for goto targets (udev_iter_find_label)

[PATCH 2/2] udevd: Avoid repeated scans for goto targets (udev_iter_find_label)

[Alan Jenkins]

The scans are now performed up-front at parse-time, instead of being
repeated for each event at run-time.

Cachegrind reports a 5% reduction in cpu cycles
(excluding the time spent in-kernel).

diff --git a/udev/udev_rules.c b/udev/udev_rules.c
index d4dcb06..9c37571 100644
--- a/udev/udev_rules.c
+++ b/udev/udev_rules.c
@@ -1529,7 +1529,7 @@ int udev_rules_get_name(struct udev_rules *rules, struct udevice *udevice)
 
 			if (rule->goto_label.operation != KEY_OP_UNSET) {
 				dbg(udevice->udev, "moving forward to label '%s'\n", key_val(rule, &rule->goto_label));
-				udev_rules_iter_label(&iter, key_val(rule, &rule->goto_label));
+				udev_rules_iter_goto(&iter, rule->goto_rule_off);
 			}
 		}
 	}
@@ -1609,7 +1609,7 @@ int udev_rules_get_run(struct udev_rules *rules, struct udevice *udevice)
 
 			if (rule->goto_label.operation != KEY_OP_UNSET) {
 				dbg(udevice->udev, "moving forward to label '%s'\n", key_val(rule, &rule->goto_label));
-				udev_rules_iter_label(&iter, key_val(rule, &rule->goto_label));
+				udev_rules_iter_goto(&iter, rule->goto_rule_off);
 			}
 		}
 	}
diff --git a/udev/udev_rules.h b/udev/udev_rules.h
index 02685e1..af96b81 100644
--- a/udev/udev_rules.h
+++ b/udev/udev_rules.h
@@ -84,6 +84,7 @@ struct udev_rule {
 	struct key wait_for;
 	struct key label;
 	struct key goto_label;
+	size_t goto_rule_off;
 
 	struct key name;
 	struct key symlink;
@@ -122,7 +123,7 @@ extern void udev_rules_cleanup(struct udev_rules *rules);
 
 extern void udev_rules_iter_init(struct udev_rules_iter *iter, struct udev_rules *rules);
 extern struct udev_rule *udev_rules_iter_next(struct udev_rules_iter *iter);
-extern struct udev_rule *udev_rules_iter_label(struct udev_rules_iter *iter, const char *label);
+extern struct udev_rule *udev_rules_iter_goto(struct udev_rules_iter *iter, size_t rule_off);
 
 extern int udev_rules_get_name(struct udev_rules *rules, struct udevice *udev);
 extern int udev_rules_get_run(struct udev_rules *rules, struct udevice *udev);
diff --git a/udev/udev_rules_parse.c b/udev/udev_rules_parse.c
index 229096c..5a76889 100644
--- a/udev/udev_rules_parse.c
+++ b/udev/udev_rules_parse.c
@@ -58,29 +58,40 @@ struct udev_rule *udev_rules_iter_next(struct udev_rules_iter *iter)
 	return rule;
 }
 
-struct udev_rule *udev_rules_iter_label(struct udev_rules_iter *iter, const char *label)
+struct udev_rule *udev_rules_iter_goto(struct udev_rules_iter *iter, size_t rule_off)
+{
+	struct udev_rules *rules = iter->rules;
+	struct udev_rule *rule;
+
+	dbg(rules->udev "current=%zi\n", iter->current);
+	iter->current = rule_off;
+	rule = (struct udev_rule *) (rules->buf + iter->current);
+
+	return rule;
+}
+
+static size_t find_label(const struct udev_rules_iter *iter, const char *label)
 {
 	struct udev_rule *rule;
 	struct udev_rules *rules = iter->rules;
-	size_t start = iter->current;
+	size_t current = iter->current;
 
 next:
-	dbg(rules->udev, "current=%zi\n", iter->current);
-	if (iter->current >= rules->bufsize) {
+	dbg(rules->udev, "current=%zi\n", current);
+	if (current >= rules->bufsize) {
 		err(rules->udev, "LABEL='%s' not found, GOTO will be ignored\n", label);
-		iter->current = start;
-		return NULL;
+		return iter->current;
 	}
-	rule = (struct udev_rule *) (rules->buf + iter->current);
+	rule = (struct udev_rule *) (rules->buf + current);
 
 	if (strcmp(&rule->buf[rule->label.val_off], label) != 0) {
 		dbg(rules->udev, "moving forward, looking for label '%s'\n", label);
-		iter->current += sizeof(struct udev_rule) + rule->bufsize;
+		current += sizeof(struct udev_rule) + rule->bufsize;
 		goto next;
 	}
 
 	dbg(rules->udev, "found label '%s'\n", label);
-	return rule;
+	return current;
 }
 
 static int get_key(struct udev_rules *rules, char **line, char **key, enum key_operation *operation, char **value)
@@ -674,6 +685,11 @@ static int parse_file(struct udev_rules *rules, const char *filename)
 	size_t cur;
 	size_t count;
 	int retval = 0;
+	size_t start;
+	struct udev_rule *rule;
+	struct udev_rules_iter iter;
+
+	start = rules->bufsize;
 
 	if (file_map(filename, &buf, &bufsize) != 0) {
 		err(rules->udev, "can't open '%s' as rules file: %s\n", filename, strerror(errno));
@@ -722,6 +738,22 @@ static int parse_file(struct udev_rules *rules, const char *filename)
 		add_to_rules(rules, line, filename, lineno);
 	}
 
+	/* Compute all goto targets within this file */
+	udev_rules_iter_init(&iter, rules);
+	udev_rules_iter_goto(&iter, start);
+	while((rule = udev_rules_iter_next(&iter))) {
+		if (rule->goto_label.operation != KEY_OP_UNSET) {
+			char *goto_label = &rule->buf[rule->goto_label.val_off];
+
+			dbg(rules->udev, "resolving goto label '%s'", goto_label);
+			rule->goto_rule_off = find_label(&iter, goto_label);
+			if (rule->goto_rule_off = iter.current) {
+				err(rules->udev, "goto nonexistent label '%s' in '%s'",
+				    goto_label, filename);
+			}
+		}
+	}
+
 	file_unmap(buf, bufsize);
 	return retval;
 }

Re: [PATCH 2/2] udevd: Avoid repeated scans for goto targets (udev_iter_find_label)

[Kay Sievers]

On Sun, Sep 28, 2008 at 13:02, Alan Jenkins <alan-jenkins@tuffmail.co.uk> wrote:
> The scans are now performed up-front at parse-time, instead of being
> repeated for each event at run-time.
>
> Cachegrind reports a 5% reduction in cpu cycles
> (excluding the time spent in-kernel).

Both patches applied.

Thanks,
Kay