chiark / gitweb /
replace in-memory rules array with match/action token list
authorKay Sievers <kay.sievers@vrfy.org>
Wed, 22 Oct 2008 22:13:59 +0000 (00:13 +0200)
committerKay Sievers <kay.sievers@vrfy.org>
Wed, 22 Oct 2008 22:13:59 +0000 (00:13 +0200)
The in-memory rule array of a common desktop distro install took:
  1151088 bytes
with the token list:
  109232 bytes tokens (6827 * 16 bytes), 71302 bytes buffer

TODO
test/udev-test.pl
udev/udev-event.c
udev/udev-node.c
udev/udev-rules.c
udev/udev.h
udev/udev.xml

diff --git a/TODO b/TODO
index 7cbe916..fd9b2be 100644 (file)
--- a/TODO
+++ b/TODO
@@ -1,5 +1,5 @@
+  o use node for tmpnode, if it already exists
   o add DVB variables to kernel, and drop shell script rule
-  o rework rules to a match-action list, instead of a rules array
   o DEVTYPE for disks is set by the kernel, they will be removed from
     the default rules
   o "udevadm control" commands will only accept the --<command> syntax
index 243e961..9725aff 100755 (executable)
@@ -470,8 +470,8 @@ EOF
                devpath         => "/devices/virtual/tty/console",
                exp_name        => "foo" ,
                rules           => <<EOF
-ATTRS{dev}=="5:1", NAME="foo"
 KERNEL=="console", NAME="TTY"
+ATTRS{dev}=="5:1", NAME="foo"
 EOF
        },
        {
@@ -546,8 +546,8 @@ EOF
 SUBSYSTEMS=="scsi", KERNELS=="*:1", NAME="no-match"
 SUBSYSTEMS=="scsi", KERNELS=="*:0:1", NAME="no-match"
 SUBSYSTEMS=="scsi", KERNELS=="*:0:0:1", NAME="no-match"
+SUBSYSTEMS=="scsi", KERNEL=="0:0:0:0", NAME="before"
 SUBSYSTEMS=="scsi", KERNELS=="*", NAME="scsi-0:0:0:0"
-SUBSYSTEMS=="scsi", KERNELS=="0:0:0:0", NAME="bad"
 EOF
        },
        {
@@ -556,8 +556,8 @@ EOF
                devpath         => "/devices/pci0000:00/0000:00:1f.2/host0/target0:0:0/0:0:0:0/block/sda",
                exp_name        => "scsi-0:0:0:0",
                rules           => <<EOF
+SUBSYSTEMS=="scsi", KERNELS=="0:0:0:0", NAME="before"
 SUBSYSTEMS=="scsi", KERNELS=="*:0", NAME="scsi-0:0:0:0"
-SUBSYSTEMS=="scsi", KERNELS=="0:0:0:0", NAME="bad"
 EOF
        },
        {
@@ -566,8 +566,8 @@ EOF
                devpath         => "/devices/pci0000:00/0000:00:1f.2/host0/target0:0:0/0:0:0:0/block/sda",
                exp_name        => "scsi-0:0:0:0",
                rules           => <<EOF
+SUBSYSTEMS=="scsi", KERNELS=="0:0:0:0", NAME="before"
 SUBSYSTEMS=="scsi", KERNELS=="*:0:0:0", NAME="scsi-0:0:0:0"
-SUBSYSTEMS=="scsi", KERNELS=="0:0:0:0", NAME="bad"
 EOF
        },
        {
@@ -1154,8 +1154,8 @@ EOF
                exp_name        => "match",
                rules           => <<EOF
 SUBSYSTEMS=="scsi", KERNEL!="sda1", NAME="matches-but-is-negated"
+SUBSYSTEMS=="scsi", KERNEL=="sda1", NAME="before"
 SUBSYSTEMS=="scsi", KERNEL!="xsda1", NAME="match"
-SUBSYSTEMS=="scsi", KERNEL=="sda1", NAME="wrong"
 EOF
        },
        {
@@ -1165,8 +1165,8 @@ EOF
                exp_name        => "not-anything",
                rules           => <<EOF
 SUBSYSTEMS=="scsi", SUBSYSTEM=="block", KERNEL!="sda1", NAME="matches-but-is-negated"
+SUBSYSTEMS=="scsi", KERNEL=="sda1", NAME="before"
 SUBSYSTEMS=="scsi", SUBSYSTEM!="anything", NAME="not-anything"
-SUBSYSTEMS=="scsi", KERNEL=="sda1", NAME="wrong"
 EOF
        },
        {
@@ -1175,8 +1175,8 @@ EOF
                devpath         => "/devices/pci0000:00/0000:00:1f.2/host0/target0:0:0/0:0:0:0/block/sda/sda1",
                exp_name        => "nonzero-program",
                rules           => <<EOF
+SUBSYSTEMS=="scsi", KERNEL=="sda1", NAME="before"
 KERNEL=="sda1", PROGRAM!="/bin/false", NAME="nonzero-program"
-SUBSYSTEMS=="scsi", KERNEL=="sda1", NAME="wrong"
 EOF
        },
        {
@@ -1185,8 +1185,8 @@ EOF
                devpath         => "/devices/pci0000:00/0000:00:1f.2/host0/target0:0:0/0:0:0:0/block/sda/sda1",
                exp_name        => "true",
                rules           => <<EOF
+SUBSYSTEMS=="scsi", KERNEL=="sda1", NAME="before"
 KERNEL   ==   "sda1"     ,    NAME   =    "true"
-SUBSYSTEMS=="scsi", KERNEL=="sda1", NAME="wrong"
 EOF
        },
        {
@@ -1209,8 +1209,8 @@ EOF
                rules           => <<EOF
 ENV{ENV_KEY_TEST}="test"
 SUBSYSTEMS=="scsi", KERNEL=="sda1", ENV{ENV_KEY_TEST}=="go", NAME="wrong"
-SUBSYSTEMS=="scsi", KERNEL=="sda1", ENV{ENV_KEY_TEST}=="yes", ENV{ACTION}=="add", ENV{DEVPATH}=="/devices/pci0000:00/0000:00:1f.2/host0/target0:0:0/0:0:0:0/block/sda/sdax1", NAME="no"
-SUBSYSTEMS=="scsi", KERNEL=="sda1", ENV{ENV_KEY_TEST}=="test", ENV{ACTION}=="add", ENV{DEVPATH}=="/devices/pci0000:00/0000:00:1f.2/host0/target0:0:0/0:0:0:0/block/sda/sda1", NAME="true"
+SUBSYSTEMS=="scsi", KERNEL=="sda1", ENV{ENV_KEY_TEST}=="yes", ENV{ACTION}=="add", ENV{DEVPATH}=="*/block/sda/sdax1", NAME="no"
+SUBSYSTEMS=="scsi", KERNEL=="sda1", ENV{ENV_KEY_TEST}=="test", ENV{ACTION}=="add", ENV{DEVPATH}=="*/block/sda/sda1", NAME="true"
 SUBSYSTEMS=="scsi", KERNEL=="sda1", ENV{ENV_KEY_TEST}=="bad", NAME="bad"
 EOF
        },
@@ -1222,8 +1222,8 @@ EOF
                rules           => <<EOF
 SUBSYSTEMS=="scsi", KERNEL=="sda1", ENV{ASSIGN}="true"
 SUBSYSTEMS=="scsi", KERNEL=="sda1", ENV{ASSIGN}=="yes", NAME="no"
+SUBSYSTEMS=="scsi", KERNEL=="sda1", NAME="before"
 SUBSYSTEMS=="scsi", KERNEL=="sda1", ENV{ASSIGN}=="true", NAME="true"
-SUBSYSTEMS=="scsi", KERNEL=="sda1", NAME="bad"
 EOF
        },
        {
@@ -1234,9 +1234,9 @@ EOF
                rules           => <<EOF
 SUBSYSTEMS=="scsi", KERNEL=="sda1", ENV{ASSIGN}="true"
 SUBSYSTEMS=="scsi", KERNEL=="sda1", ENV{ASSIGN}="absolutely-\$env{ASSIGN}"
+SUBSYSTEMS=="scsi", KERNEL=="sda1", NAME="before"
 SUBSYSTEMS=="scsi", KERNEL=="sda1", ENV{ASSIGN}=="yes", NAME="no"
 SUBSYSTEMS=="scsi", KERNEL=="sda1", ENV{ASSIGN}=="absolutely-true", NAME="true"
-SUBSYSTEMS=="scsi", KERNEL=="sda1", NAME="bad"
 EOF
        },
        {
@@ -1248,8 +1248,8 @@ EOF
 SUBSYSTEM=="block", KERNEL=="*[0-9]", ENV{PARTITION}="true", ENV{MAINDEVICE}="false"
 SUBSYSTEM=="block", KERNEL=="*[!0-9]", ENV{PARTITION}="false", ENV{MAINDEVICE}="true"
 ENV{MAINDEVICE}=="true", NAME="disk"
+SUBSYSTEM=="block", NAME="before"
 ENV{PARTITION}=="true", NAME="part"
-SUBSYSTEM=="block", NAME="bad"
 EOF
        },
        {
@@ -1280,12 +1280,12 @@ SUBSYSTEMS=="scsi", KERNEL=="sda1", PROGRAM=="/bin/echo -e \\xef\\xe8garbage", R
 EOF
        },
        {
-               desc            => "read sysfs value from device down in the chain",
+               desc            => "read sysfs value from parent device",
                subsys          => "block",
                devpath         => "/devices/pci0000:00/0000:00:1d.7/usb5/5-2/5-2:1.0/tty/ttyACM0",
                exp_name        => "serial-354172020305000",
                rules           => <<EOF
-KERNEL=="ttyACM*", NAME="serial-%s{serial}"
+KERNEL=="ttyACM*", ATTRS{serial}=="?*", NAME="serial-%s{serial}"
 EOF
        },
        {
@@ -1311,13 +1311,13 @@ ACTION=="add", KERNEL=="sda", NAME="ok"
 EOF
        },
        {
-               desc            => "apply NAME only once",
+               desc            => "apply NAME final",
                subsys          => "block",
                devpath         => "/devices/pci0000:00/0000:00:1f.2/host0/target0:0:0/0:0:0:0/block/sda",
                exp_name        => "link",
                exp_target      => "ok",
                rules           => <<EOF
-KERNEL=="sda", NAME="ok"
+KERNEL=="sda", NAME:="ok"
 KERNEL=="sda", NAME="not-ok"
 KERNEL=="sda", SYMLINK+="link"
 EOF
@@ -1344,8 +1344,8 @@ EOF
                exp_rem_error   => "yes",
                option          => "clean",
                rules           => <<EOF
-KERNEL=="sda", NAME="ok", RUN+="/bin/sh -c 'ln -s `basename \$\$DEVNAME` %r/testsymlink'"
 KERNEL=="sda", NAME="not-ok"
+KERNEL=="sda", NAME="ok", RUN+="/bin/sh -c 'ln -s `basename \$\$DEVNAME` %r/testsymlink'"
 EOF
        },
        {
@@ -1410,12 +1410,12 @@ EOF
                desc            => "test empty NAME",
                subsys          => "tty",
                devpath         => "/devices/pci0000:00/0000:00:1d.7/usb5/5-2/5-2:1.0/tty/ttyACM0",
-               exp_name        => "node",
+               exp_name        => "<none>",
                not_exp_name    => "wrong",
                exp_add_error   => "yes",
                rules           => <<EOF
-KERNEL=="ttyACM[0-9]*", NAME=""
 KERNEL=="ttyACM[0-9]*", NAME="wrong"
+KERNEL=="ttyACM[0-9]*", NAME=""
 EOF
        },
        {
@@ -1424,9 +1424,9 @@ EOF
                devpath         => "/devices/pci0000:00/0000:00:1d.7/usb5/5-2/5-2:1.0/tty/ttyACM0",
                exp_name        => "right",
                rules           => <<EOF
-KERNEL=="ttyACM[0-9]*", NAME="right"
 KERNEL=="ttyACM[0-9]*", NAME=""
 KERNEL=="ttyACM[0-9]*", NAME="wrong"
+KERNEL=="ttyACM[0-9]*", NAME="right"
 EOF
        },
        {
@@ -1435,8 +1435,8 @@ EOF
                devpath         => "/devices/pci0000:00/0000:00:1d.7/usb5/5-2/5-2:1.0/tty/ttyACM0",
                exp_name        => "right",
                rules           => <<EOF
+KERNEL=="ttyACM*", NAME="before"
 KERNEL=="ttyACM*|nothing", NAME="right"
-KERNEL=="ttyACM*", NAME="wrong"
 EOF
        },
        {
@@ -1446,8 +1446,8 @@ EOF
                exp_name        => "right",
                rules           => <<EOF
 KERNEL=="dontknow*|*nothing", NAME="nomatch"
+KERNEL=="ttyACM*", NAME="before"
 KERNEL=="dontknow*|ttyACM*|nothing*", NAME="right"
-KERNEL=="ttyACM*", NAME="wrong"
 EOF
        },
        {
@@ -1479,9 +1479,10 @@ EOF
                rules           => <<EOF
 KERNEL=="sda1", GOTO="TEST"
 KERNEL=="sda1", NAME="wrong"
+KERNEL=="sda1", GOTO="BAD"
 KERNEL=="sda1", NAME="", LABEL="NO"
 KERNEL=="sda1", NAME="right", LABEL="TEST"
-KERNEL=="sda1", NAME="wrong2"
+KERNEL=="sda1", LABEL="BAD"
 EOF
        },
        {
@@ -1615,6 +1616,7 @@ EOF
                exp_name        => "sda",
                exp_perms       => "0:0:0400",
                rules           => <<EOF
+KERNEL=="sda", MODE="666"
 KERNEL=="sda", PROGRAM=="/bin/echo 0 0 0400", OWNER="%c{1}", GROUP="%c{2}", MODE="%c{3}"
 EOF
        },
@@ -1623,8 +1625,9 @@ EOF
                subsys          => "block",
                devpath         => "/devices/pci0000:00/0000:00:1f.2/host0/target0:0:0/0:0:0:0/block/sda",
                exp_name        => "sda",
-               exp_perms       => "0:0:0400",
+               exp_perms       => "0:0:0660",
                rules           => <<EOF
+KERNEL=="sda", MODE="440"
 KERNEL=="sda", PROGRAM=="/bin/echo 0 0 0400letsdoabuffferoverflow0123456789012345789012345678901234567890", OWNER="%c{1}", GROUP="%c{2}", MODE="%c{3}"
 EOF
        },
index 05bb022..b41dcd0 100644 (file)
@@ -37,14 +37,10 @@ struct udev_event *udev_event_new(struct udev_device *dev)
        event = calloc(1, sizeof(struct udev_event));
        if (event == NULL)
                return NULL;
-
        event->dev = dev;
        event->udev = udev_device_get_udev(dev);
        udev_list_init(&event->run_list);
        event->mode = 0660;
-       util_strlcpy(event->owner, "0", sizeof(event->owner));
-       util_strlcpy(event->group, "0", sizeof(event->group));
-
        dbg(event->udev, "allocated event %p\n", event);
        return event;
 }
@@ -95,69 +91,6 @@ static int get_format_len(struct udev *udev, char **str)
        return -1;
 }
 
-/* handle "[<SUBSYSTEM>/<KERNEL>]<attribute>" format */
-int udev_event_apply_subsys_kernel(struct udev_event *udev_event, const char *string,
-                                  char *result, size_t maxsize, int read_value)
-{
-       char temp[UTIL_PATH_SIZE];
-       char *subsys;
-       char *sysname;
-       char *attr;
-       struct udev_device *dev;
-
-       if (string == NULL)
-               string = result;
-       if (string[0] != '[')
-               return -1;
-
-       util_strlcpy(temp, string, sizeof(temp));
-
-       subsys = &temp[1];
-
-       sysname = strchr(subsys, '/');
-       if (sysname == NULL)
-               return -1;
-       sysname[0] = '\0';
-       sysname = &sysname[1];
-
-       attr = strchr(sysname, ']');
-       if (attr == NULL)
-               return -1;
-       attr[0] = '\0';
-       attr = &attr[1];
-       if (attr[0] == '/')
-               attr = &attr[1];
-       if (attr[0] == '\0')
-               attr = NULL;
-
-       if (read_value && attr == NULL)
-               return -1;
-
-       dev = udev_device_new_from_subsystem_sysname(udev_event->udev, subsys, sysname);
-       if (dev == NULL)
-               return -1;
-
-       if (read_value) {
-               const char *val;
-
-               val = udev_device_get_sysattr_value(dev, attr);
-               if (val != NULL)
-                       util_strlcpy(result, val, maxsize);
-               else
-                       result[0] = '\0';
-               info(udev_event->udev, "value '[%s/%s]%s' is '%s'\n", subsys, sysname, attr, result);
-       } else {
-               util_strlcpy(result, udev_device_get_syspath(dev), maxsize);
-               if (attr != NULL) {
-                       util_strlcat(result, "/", maxsize);
-                       util_strlcat(result, attr, maxsize);
-               }
-               info(udev_event->udev, "path '[%s/%s]%s' is '%s'\n", subsys, sysname, attr, result);
-       }
-       udev_device_unref(dev);
-       return 0;
-}
-
 void udev_event_apply_format(struct udev_event *event, char *string, size_t maxsize)
 {
        struct udev_device *dev = event->dev;
@@ -349,36 +282,23 @@ found:
                        if (attr == NULL)
                                err(event->udev, "missing file parameter for attr\n");
                        else {
+                               const char *val;
                                char value[UTIL_NAME_SIZE] = "";
                                size_t size;
 
-                               udev_event_apply_subsys_kernel(event, attr, value, sizeof(value), 1);
+                               util_resolve_subsys_kernel(event->udev, attr, value, sizeof(value), 1);
+
+                               val = udev_device_get_sysattr_value(event->dev, attr);
+                               if (val != NULL)
+                                       util_strlcpy(value, val, sizeof(value));
 
                                /* try the current device, other matches may have selected */
                                if (value[0] == '\0' && event->dev_parent != NULL && event->dev_parent != event->dev) {
-                                       const char *val;
-
                                        val = udev_device_get_sysattr_value(event->dev_parent, attr);
                                        if (val != NULL)
                                                util_strlcpy(value, val, sizeof(value));
                                }
 
-                               /* look at all devices along the chain of parents */
-                               if (value[0] == '\0') {
-                                       struct udev_device *dev_parent = dev;
-                                       const char *val;
-
-                                       do {
-                                               dbg(event->udev, "looking at '%s'\n", udev_device_get_syspath(dev_parent));
-                                               val = udev_device_get_sysattr_value(dev_parent, attr);
-                                               if (val != NULL) {
-                                                       util_strlcpy(value, val, sizeof(value));
-                                                       break;
-                                               }
-                                               dev_parent = udev_device_get_parent(dev_parent);
-                                       } while (dev_parent != NULL);
-                               }
-
                                if (value[0]=='\0')
                                        break;
 
@@ -590,17 +510,29 @@ int udev_event_execute_rules(struct udev_event *event, struct udev_rules *rules)
 
                dbg(event->udev, "device node add '%s'\n", udev_device_get_devpath(dev));
 
-               udev_rules_get_name(rules, event);
+               udev_rules_apply_to_event(rules, event);
+               if (event->tmp_node[0] != '\0') {
+                       dbg(event->udev, "removing temporary device node\n");
+                       util_unlink_secure(event->udev, event->tmp_node);
+                       event->tmp_node[0] = '\0';
+               }
+
                if (event->ignore_device) {
                        info(event->udev, "device event will be ignored\n");
                        goto exit;
                }
 
-               if (event->name[0] == '\0') {
+               if (event->name_ignore) {
                        info(event->udev, "device node creation supressed\n");
                        goto exit;
                }
 
+               if (event->name[0] == '\0') {
+                       info(event->udev, "no node name set, will use kernel name '%s'\n",
+                            udev_device_get_sysname(event->dev));
+                       util_strlcpy(event->name, udev_device_get_sysname(event->dev), sizeof(event->name));
+               }
+
                /* set device node name */
                util_strlcpy(filename, udev_get_dev_path(event->udev), sizeof(filename));
                util_strlcat(filename, "/", sizeof(filename));
@@ -610,15 +542,17 @@ int udev_event_execute_rules(struct udev_event *event, struct udev_rules *rules)
                /* read current database entry; cleanup, if it is known device */
                dev_old = udev_device_new_from_syspath(event->udev, udev_device_get_syspath(dev));
                if (dev_old != NULL) {
-                       info(event->udev, "device '%s' already in database, updating\n",
-                            udev_device_get_devpath(dev));
-                       udev_node_update_old_links(dev, dev_old, event->test);
+                       if (udev_device_get_devnode(dev_old) != NULL) {
+                               info(event->udev, "device node '%s' already in database, updating\n",
+                                    udev_device_get_devnode(dev_old));
+                               udev_node_update_old_links(dev, dev_old, event->test);
+                       }
                        udev_device_unref(dev_old);
                }
 
                udev_device_update_db(dev);
 
-               err = udev_node_add(dev, event->mode, event->owner, event->group, event->test);
+               err = udev_node_add(dev, event->mode, event->uid, event->gid, event->test);
                if (err != 0)
                        goto exit;
 
@@ -629,7 +563,7 @@ int udev_event_execute_rules(struct udev_event *event, struct udev_rules *rules)
        if (strcmp(udev_device_get_subsystem(dev), "net") == 0 && strcmp(udev_device_get_action(dev), "add") == 0) {
                dbg(event->udev, "netif add '%s'\n", udev_device_get_devpath(dev));
 
-               udev_rules_get_name(rules, event);
+               udev_rules_apply_to_event(rules, event);
                if (event->ignore_device) {
                        info(event->udev, "device event will be ignored\n");
                        goto exit;
@@ -684,7 +618,7 @@ int udev_event_execute_rules(struct udev_event *event, struct udev_rules *rules)
                        udev_device_set_devnode(dev, devnode);
                }
 
-               udev_rules_get_run(rules, event);
+               udev_rules_apply_to_event(rules, event);
                if (event->ignore_device) {
                        info(event->udev, "device event will be ignored\n");
                        goto exit;
@@ -700,7 +634,7 @@ int udev_event_execute_rules(struct udev_event *event, struct udev_rules *rules)
        }
 
        /* default devices */
-       udev_rules_get_run(rules, event);
+       udev_rules_apply_to_event(rules, event);
        if (event->ignore_device)
                info(event->udev, "device event will be ignored\n");
 exit:
index 03b8d61..b39100d 100644 (file)
@@ -390,49 +390,20 @@ void udev_node_update_old_links(struct udev_device *dev, struct udev_device *dev
        }
 }
 
-int udev_node_add(struct udev_device *dev, mode_t mode, const char *owner, const char *group, int test)
+int udev_node_add(struct udev_device *dev, mode_t mode, uid_t uid, gid_t gid, int test)
 {
        struct udev *udev = udev_device_get_udev(dev);
-       uid_t uid;
-       gid_t gid;
        int i;
        int num;
        struct udev_list_entry *list_entry;
        int err = 0;
 
-       util_create_path(udev, udev_device_get_devnode(dev));
-
-       if (strcmp(owner, "root") == 0)
-               uid = 0;
-       else {
-               char *endptr;
-               unsigned long id;
-
-               id = strtoul(owner, &endptr, 10);
-               if (endptr[0] == '\0')
-                       uid = (uid_t) id;
-               else
-                       uid = util_lookup_user(udev, owner);
-       }
-
-       if (strcmp(group, "root") == 0)
-               gid = 0;
-       else {
-               char *endptr;
-               unsigned long id;
-
-               id = strtoul(group, &endptr, 10);
-               if (endptr[0] == '\0')
-                       gid = (gid_t) id;
-               else
-                       gid = util_lookup_group(udev, group);
-       }
-
        info(udev, "creating device node '%s', devnum=%d:%d, mode=%#o, uid=%d, gid=%d\n",
             udev_device_get_devnode(dev),
             major(udev_device_get_devnum(dev)), minor(udev_device_get_devnum(dev)),
             mode, uid, gid);
 
+       util_create_path(udev, udev_device_get_devnode(dev));
        if (!test)
                if (udev_node_mknod(dev, NULL, makedev(0,0), mode, uid, gid) != 0) {
                        err = -1;
index 32eed78..b456c3d 100644 (file)
@@ -1,6 +1,5 @@
 /*
- * Copyright (C) 2003 Greg Kroah-Hartman <greg@kroah.com>
- * Copyright (C) 2003-2008 Kay Sievers <kay.sievers@vrfy.org>
+ * Copyright (C) 2008 Kay Sievers <kay.sievers@vrfy.org>
  *
  * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
 
 #include "udev.h"
 
-struct udev_rules {
-       struct udev *udev;
-       char *buf;
-       size_t bufsize;
-       int resolve_names;
-};
-
-struct udev_rules_iter {
-       struct udev_rules *rules;
-       size_t current;
-};
+#define PREALLOC_TOKEN                 2048
+#define PREALLOC_STRBUF                        32 * 1024
 
 enum key_operation {
        KEY_OP_UNSET,
@@ -50,144 +40,216 @@ enum key_operation {
        KEY_OP_ASSIGN_FINAL,
 };
 
-struct key {
-       enum key_operation operation;
-       size_t val_off;
+static const char *operation_str[] = {
+       [KEY_OP_MATCH] =        "match",
+       [KEY_OP_NOMATCH] =      "nomatch",
+       [KEY_OP_ADD] =          "add",
+       [KEY_OP_ASSIGN] =       "assign",
+       [KEY_OP_ASSIGN_FINAL] = "assign-final",
 };
 
-struct key_pair {
-       struct key key;
-       size_t key_name_off;
+enum token_type {
+       TK_UNDEF,
+       TK_RULE,
+
+       TK_M_WAITFOR,                   /* val */
+       TK_M_ACTION,                    /* val */
+       TK_M_DEVPATH,                   /* val */
+       TK_M_KERNEL,                    /* val */
+       TK_M_DEVLINK,                   /* val */
+       TK_M_NAME,                      /* val */
+       TK_M_ENV,                       /* val, attr */
+       TK_M_SUBSYSTEM,                 /* val */
+       TK_M_DRIVER,                    /* val */
+       TK_M_ATTR,                      /* val, attr */
+
+       TK_M_KERNELS,                   /* val */
+       TK_M_SUBSYSTEMS,                /* val */
+       TK_M_DRIVERS,                   /* val */
+       TK_M_ATTRS,                     /* val, attr */
+       TK_PARENTS_MAX,
+
+       TK_M_TEST,                      /* val, mode_t */
+       TK_M_PROGRAM,                   /* val */
+       TK_M_IMPORT_FILE,               /* val */
+       TK_M_IMPORT_PROG,               /* val */
+       TK_M_IMPORT_PARENT,             /* val */
+       TK_M_RESULT,                    /* val */
+
+       TK_A_IGNORE_DEVICE,
+       TK_A_STRING_ESCAPE_NONE,
+       TK_A_STRING_ESCAPE_REPLACE,
+       TK_A_NUM_FAKE_PART,             /* int */
+       TK_A_DEVLINK_PRIO,              /* int */
+       TK_A_OWNER,                     /* val */
+       TK_A_GROUP,                     /* val */
+       TK_A_MODE,                      /* val */
+       TK_A_OWNER_ID,                  /* uid_t */
+       TK_A_GROUP_ID,                  /* gid_t */
+       TK_A_MODE_ID,                   /* mode_t */
+       TK_A_ENV,                       /* val, attr */
+       TK_A_NAME,                      /* val */
+       TK_A_DEVLINK,                   /* val */
+       TK_A_EVENT_TIMEOUT,             /* int */
+       TK_A_IGNORE_REMOVE,
+       TK_A_ATTR,                      /* val, attr */
+       TK_A_RUN,                       /* val, bool */
+       TK_A_GOTO,                      /* size_t */
+       TK_A_LAST_RULE,
+
+       TK_END,
 };
 
-#define PAIRS_MAX              5
-struct key_pairs {
-       int count;
-       struct key_pair keys[PAIRS_MAX];
+static const char *token_str[] = {
+       [TK_UNDEF] =                    "UNDEF",
+       [TK_RULE] =                     "RULE",
+
+       [TK_M_WAITFOR] =                "M WAITFOR",
+       [TK_M_ACTION] =                 "M ACTION",
+       [TK_M_DEVPATH] =                "M DEVPATH",
+       [TK_M_KERNEL] =                 "M KERNEL",
+       [TK_M_DEVLINK] =                "M DEVLINK",
+       [TK_M_NAME] =                   "M NAME",
+       [TK_M_ENV] =                    "M ENV",
+       [TK_M_SUBSYSTEM] =              "M SUBSYSTEM",
+       [TK_M_DRIVER] =                 "M DRIVER",
+       [TK_M_ATTR] =                   "M ATTR",
+
+       [TK_M_KERNELS] =                "M KERNELS",
+       [TK_M_SUBSYSTEMS] =             "M SUBSYSTEMS",
+       [TK_M_DRIVERS] =                "M DRIVERS",
+       [TK_M_ATTRS] =                  "M ATTRS",
+       [TK_PARENTS_MAX] =              "PARENTS_MAX",
+
+       [TK_M_TEST] =                   "M TEST",
+       [TK_M_PROGRAM] =                "M PROGRAM",
+       [TK_M_IMPORT_FILE] =            "M IMPORT_FILE",
+       [TK_M_IMPORT_PROG] =            "M IMPORT_PROG",
+       [TK_M_IMPORT_PARENT] =          "M MPORT_PARENT",
+       [TK_M_RESULT] =                 "M RESULT",
+
+       [TK_A_IGNORE_DEVICE] =          "A IGNORE_DEVICE",
+       [TK_A_STRING_ESCAPE_NONE] =     "A STRING_ESCAPE_NONE",
+       [TK_A_STRING_ESCAPE_REPLACE] =  "A STRING_ESCAPE_REPLACE",
+       [TK_A_NUM_FAKE_PART] =          "A NUM_FAKE_PART",
+       [TK_A_DEVLINK_PRIO] =           "A DEVLINK_PRIO",
+       [TK_A_OWNER] =                  "A OWNER",
+       [TK_A_GROUP] =                  "A GROUP",
+       [TK_A_MODE] =                   "A MODE",
+       [TK_A_OWNER_ID] =               "A OWNER_ID",
+       [TK_A_GROUP_ID] =               "A GROUP_ID",
+       [TK_A_MODE_ID] =                "A MODE_ID",
+       [TK_A_ENV] =                    "A ENV",
+       [TK_A_NAME] =                   "A NAME",
+       [TK_A_DEVLINK] =                "A DEVLINK",
+       [TK_A_EVENT_TIMEOUT] =          "A EVENT_TIMEOUT",
+       [TK_A_IGNORE_REMOVE] =          "A IGNORE_REMOVE",
+       [TK_A_ATTR] =                   "A ATTR",
+       [TK_A_RUN] =                    "A RUN",
+       [TK_A_GOTO] =                   "A GOTO",
+       [TK_A_LAST_RULE] =              "A LAST_RULE",
+
+       [TK_END] =                      "END",
 };
 
-enum import_type {
-       IMPORT_UNSET,
-       IMPORT_PROGRAM,
-       IMPORT_FILE,
-       IMPORT_PARENT,
+struct token {
+       enum token_type type;
+       union {
+               struct {
+                       unsigned int next_rule;
+                       unsigned int label_off;
+                       unsigned int filename_off;
+               } rule;
+               struct {
+                       enum key_operation op;
+                       unsigned int value_off;
+                       union {
+                               unsigned int attr_off;
+                               int ignore_error;
+                               int i;
+                               unsigned int rule_goto;
+                               mode_t  mode;
+                               uid_t uid;
+                               gid_t gid;
+                               int num_fake_part;
+                               int devlink_prio;
+                               int event_timeout;
+                       };
+               } key;
+       };
 };
 
-enum escape_type {
-       ESCAPE_UNSET,
-       ESCAPE_NONE,
-       ESCAPE_REPLACE,
+#define MAX_TK         64
+struct rule_tmp {
+       struct udev_rules *rules;
+       struct token rule;
+       struct token token[MAX_TK];
+       unsigned int token_cur;
 };
 
-struct udev_rule {
-       struct key action;
-       struct key devpath;
-       struct key kernel;
-       struct key subsystem;
-       struct key driver;
-       struct key_pairs attr;
-
-       struct key kernels;
-       struct key subsystems;
-       struct key drivers;
-       struct key_pairs attrs;
-
-       struct key_pairs env;
-       struct key program;
-       struct key result;
-       struct key import;
-       enum import_type import_type;
-       struct key test;
-       mode_t test_mode_mask;
-       struct key run;
-       struct key wait_for;
-       struct key label;
-       struct key goto_label;
-       size_t goto_rule_off;
-
-       struct key name;
-       struct key symlink;
-       struct key symlink_match;
-       struct key owner;
-       struct key group;
-       struct key mode;
-       enum escape_type string_escape;
-
-       unsigned int link_priority;
-       int event_timeout;
-       unsigned int partitions;
-       unsigned int last_rule:1,
-                    run_ignore_error:1,
-                    ignore_device:1,
-                    ignore_remove:1;
-
-       size_t bufsize;
-       char buf[];
+struct udev_rules {
+       struct udev *udev;
+       int resolve_names;
+       struct token *tokens;
+       unsigned int token_cur;
+       unsigned int token_max;
+       char *buf;
+       size_t buf_cur;
+       size_t buf_max;
+       unsigned int buf_count;
 };
 
-static void udev_rules_iter_init(struct udev_rules_iter *iter, struct udev_rules *rules)
+/* we could lookup and return existing strings, or tails of strings */
+static int add_string(struct udev_rules *rules, const char *str)
 {
-       dbg(rules->udev, "bufsize=%zi\n", rules->bufsize);
-       iter->rules = rules;
-       iter->current = 0;
-}
+       size_t len = strlen(str)+1;
+       int off;
 
-static struct udev_rule *udev_rules_iter_next(struct udev_rules_iter *iter)
-{
-       struct udev_rules *rules;
-       struct udev_rule *rule;
+       if (rules->buf_cur + len+1 >= rules->buf_max) {
+               char *buf;
+               unsigned int add;
 
-       rules = iter->rules;
-       if (!rules)
-               return NULL;
+               /* double the buffer size */
+               add = rules->buf_max;
+               if (add < len)
+                       add = len;
 
-       dbg(rules->udev, "current=%zi\n", iter->current);
-       if (iter->current >= rules->bufsize) {
-               dbg(rules->udev, "no more rules\n");
-               return NULL;
+               buf = realloc(rules->buf, rules->buf_max + add);
+               if (buf == NULL)
+                       return -1;
+               info(rules->udev, "extend buffer from %zu to %zu\n", rules->buf_max, rules->buf_max + add);
+               rules->buf = buf;
+               rules->buf_max += add;
        }
-
-       /* get next rule */
-       rule = (struct udev_rule *) (rules->buf + iter->current);
-       iter->current += sizeof(struct udev_rule) + rule->bufsize;
-
-       return rule;
+       off = rules->buf_cur;
+       memcpy(&rules->buf[rules->buf_cur], str, len);
+       rules->buf_cur += len;
+       rules->buf_count++;
+       return off;
 }
 
-static struct udev_rule *udev_rules_iter_goto(struct udev_rules_iter *iter, size_t rule_off)
+static int add_token(struct udev_rules *rules, struct token *token)
 {
-       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;
-}
+       if (rules->token_cur+1 >= rules->token_max) {
+               struct token *tokens;
+               unsigned int add;
 
-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 current = iter->current;
-
-next:
-       dbg(rules->udev, "current=%zi\n", current);
-       if (current >= rules->bufsize) {
-               dbg(rules->udev, "LABEL='%s' not found\n", label);
-               return 0;
-       }
-       rule = (struct udev_rule *) (rules->buf + current);
+               /* double the buffer size */
+               add = rules->token_max;
+               if (add < 1)
+                       add = 1;
 
-       if (strcmp(&rule->buf[rule->label.val_off], label) != 0) {
-               dbg(rules->udev, "moving forward, looking for label '%s'\n", label);
-               current += sizeof(struct udev_rule) + rule->bufsize;
-               goto next;
+               tokens = realloc(rules->tokens, (rules->token_max + add ) * sizeof(struct token));
+               if (tokens == NULL)
+                       return -1;
+               info(rules->udev, "extend tokens from %u to %u\n", rules->token_max, rules->token_max + add);
+               rules->tokens = tokens;
+               rules->token_max += add;
        }
-
-       dbg(rules->udev, "found label '%s'\n", label);
-       return current;
+       memcpy(&rules->tokens[rules->token_cur], token, sizeof(struct token));
+       rules->token_cur++;
+       return 0;
 }
 
 static int import_property_from_string(struct udev_device *dev, char *line)
@@ -267,7 +329,7 @@ static int import_property_from_string(struct udev_device *dev, char *line)
        return 0;
 }
 
-static int import_file_into_env(struct udev_device *dev, const char *filename)
+static int import_file_into_properties(struct udev_device *dev, const char *filename)
 {
        FILE *f;
        char line[UTIL_LINE_SIZE];
@@ -281,7 +343,7 @@ static int import_file_into_env(struct udev_device *dev, const char *filename)
        return 0;
 }
 
-static int import_program_into_env(struct udev_device *dev, const char *program)
+static int import_program_into_properties(struct udev_device *dev, const char *program)
 {
        struct udev *udev = udev_device_get_udev(dev);
        char **envp;
@@ -308,7 +370,7 @@ static int import_program_into_env(struct udev_device *dev, const char *program)
        return 0;
 }
 
-static int import_parent_into_env(struct udev_device *dev, const char *filter)
+static int import_parent_into_properties(struct udev_device *dev, const char *filter)
 {
        struct udev *udev = udev_device_get_udev(dev);
        struct udev_device *dev_parent;
@@ -336,8 +398,9 @@ static int import_parent_into_env(struct udev_device *dev, const char *filter)
 }
 
 #define WAIT_LOOP_PER_SECOND           50
-static int wait_for_file(struct udev_event *event, const char *file, int timeout)
+static int wait_for_file(struct udev_device *dev, const char *file, int timeout)
 {
+       struct udev *udev = udev_device_get_udev(dev);
        char filepath[UTIL_PATH_SIZE];
        char devicepath[UTIL_PATH_SIZE] = "";
        struct stat stats;
@@ -345,8 +408,8 @@ static int wait_for_file(struct udev_event *event, const char *file, int timeout
 
        /* a relative path is a device attribute */
        if (file[0] != '/') {
-               util_strlcpy(devicepath, udev_get_sys_path(event->udev), sizeof(devicepath));
-               util_strlcat(devicepath, udev_device_get_devpath(event->dev), sizeof(devicepath));
+               util_strlcpy(devicepath, udev_get_sys_path(udev), sizeof(devicepath));
+               util_strlcat(devicepath, udev_device_get_devpath(dev), sizeof(devicepath));
 
                util_strlcpy(filepath, devicepath, sizeof(filepath));
                util_strlcat(filepath, "/", sizeof(filepath));
@@ -354,22 +417,22 @@ static int wait_for_file(struct udev_event *event, const char *file, int timeout
                file = filepath;
        }
 
-       dbg(event->udev, "will wait %i sec for '%s'\n", timeout, file);
+       dbg(udev, "will wait %i sec for '%s'\n", timeout, file);
        while (--loop) {
                /* lookup file */
                if (stat(file, &stats) == 0) {
-                       info(event->udev, "file '%s' appeared after %i loops\n", file, (timeout * WAIT_LOOP_PER_SECOND) - loop-1);
+                       info(udev, "file '%s' appeared after %i loops\n", file, (timeout * WAIT_LOOP_PER_SECOND) - loop-1);
                        return 0;
                }
                /* make sure, the device did not disappear in the meantime */
                if (devicepath[0] != '\0' && stat(devicepath, &stats) != 0) {
-                       info(event->udev, "device disappeared while waiting for '%s'\n", file);
+                       info(udev, "device disappeared while waiting for '%s'\n", file);
                        return -2;
                }
-               info(event->udev, "wait for '%s' for %i mseconds\n", file, 1000 / WAIT_LOOP_PER_SECOND);
+               info(udev, "wait for '%s' for %i mseconds\n", file, 1000 / WAIT_LOOP_PER_SECOND);
                usleep(1000 * 1000 / WAIT_LOOP_PER_SECOND);
        }
-       info(event->udev, "waiting for '%s' failed\n", file);
+       info(udev, "waiting for '%s' failed\n", file);
        return -1;
 }
 
@@ -411,883 +474,407 @@ static int attr_subst_subdir(char *attr, size_t len)
        return found;
 }
 
-static char *key_val(struct udev_rule *rule, struct key *key)
-{
-       return rule->buf + key->val_off;
-}
-
-static char *key_pair_name(struct udev_rule *rule, struct key_pair *pair)
-{
-       return rule->buf + pair->key_name_off;
-}
-
-static int match_key(struct udev *udev, const char *key_name, struct udev_rule *rule, struct key *key, const char *val)
+static int get_key(struct udev *udev, char **line, char **key, enum key_operation *op, char **value)
 {
-       char value[UTIL_PATH_SIZE];
-       char *key_value;
-       char *pos;
-       int match = 0;
+       char *linepos;
+       char *temp;
 
-       if (key->operation != KEY_OP_MATCH &&
-           key->operation != KEY_OP_NOMATCH)
-               return 0;
+       linepos = *line;
+       if (linepos == NULL && linepos[0] == '\0')
+               return -1;
 
-       if (val == NULL)
-               val = "";
+       /* skip whitespace */
+       while (isspace(linepos[0]) || linepos[0] == ',')
+               linepos++;
 
-       /* look for a matching string, parts are separated by '|' */
-       util_strlcpy(value, rule->buf + key->val_off, sizeof(value));
-       key_value = value;
-       dbg(udev, "key %s value='%s'\n", key_name, key_value);
-       while (key_value != NULL) {
-               pos = strchr(key_value, '|');
-               if (pos != NULL) {
-                       pos[0] = '\0';
-                       pos = &pos[1];
-               }
+       /* get the key */
+       if (linepos[0] == '\0')
+               return -1;
+       *key = linepos;
 
-               dbg(udev, "match %s '%s' <-> '%s'\n", key_name, key_value, val);
-               match = (fnmatch(key_value, val, 0) == 0);
-               if (match)
+       while (1) {
+               linepos++;
+               if (linepos[0] == '\0')
+                       return -1;
+               if (isspace(linepos[0]))
                        break;
-
-               key_value = pos;
-       }
-
-       if (match && (key->operation == KEY_OP_MATCH)) {
-               dbg(udev, "%s is true (matching value)\n", key_name);
-               return 0;
-       }
-       if (!match && (key->operation == KEY_OP_NOMATCH)) {
-               dbg(udev, "%s is true (non-matching value)\n", key_name);
-               return 0;
-       }
-       return -1;
-}
-
-/* match a single rule against a given device and possibly its parent devices */
-static int match_rule(struct udev_event *event, struct udev_rule *rule)
-{
-       struct udev_device *dev = event->dev;
-       int i;
-
-       if (match_key(event->udev, "ACTION", rule, &rule->action, udev_device_get_action(dev)))
-               goto nomatch;
-
-       if (match_key(event->udev, "KERNEL", rule, &rule->kernel, udev_device_get_sysname(dev)))
-               goto nomatch;
-
-       if (match_key(event->udev, "SUBSYSTEM", rule, &rule->subsystem, udev_device_get_subsystem(dev)))
-               goto nomatch;
-
-       if (match_key(event->udev, "DEVPATH", rule, &rule->devpath, udev_device_get_devpath(dev)))
-               goto nomatch;
-
-       if (match_key(event->udev, "DRIVER", rule, &rule->driver, udev_device_get_driver(dev)))
-               goto nomatch;
-
-       /* match NAME against a value assigned by an earlier rule */
-       if (match_key(event->udev, "NAME", rule, &rule->name, event->name))
-               goto nomatch;
-
-       /* match against current list of symlinks */
-       if (rule->symlink_match.operation == KEY_OP_MATCH ||
-           rule->symlink_match.operation == KEY_OP_NOMATCH) {
-               size_t devlen = strlen(udev_get_dev_path(event->udev))+1;
-               struct udev_list_entry *list_entry;
-               int match = 0;
-
-               udev_list_entry_foreach(list_entry, udev_device_get_devlinks_list_entry(dev)) {
-                       const char *devlink;
-
-                       devlink =  &udev_list_entry_get_name(list_entry)[devlen];
-                       if (match_key(event->udev, "SYMLINK", rule, &rule->symlink_match, devlink) == 0) {
-                               match = 1;
+               if (linepos[0] == '=')
+                       break;
+               if ((linepos[0] == '+') || (linepos[0] == '!') || (linepos[0] == ':'))
+                       if (linepos[1] == '=')
                                break;
-                       }
-               }
-               if (!match)
-                       goto nomatch;
-       }
-
-       for (i = 0; i < rule->env.count; i++) {
-               struct key_pair *pair = &rule->env.keys[i];
-
-               /* we only check for matches, assignments will be handled later */
-               if (pair->key.operation == KEY_OP_MATCH ||
-                   pair->key.operation == KEY_OP_NOMATCH) {
-                       struct udev_list_entry *list_entry;
-                       const char *key_name = key_pair_name(rule, pair);
-                       const char *value;
-
-                       list_entry = udev_device_get_properties_list_entry(event->dev);
-                       list_entry = udev_list_entry_get_by_name(list_entry, key_name);
-                       value = udev_list_entry_get_value(list_entry);
-                       if (value == NULL) {
-                               dbg(event->udev, "ENV{%s} is not set, treat as empty\n", key_name);
-                               value = "";
-                       }
-                       if (match_key(event->udev, "ENV", rule, &pair->key, value))
-                               goto nomatch;
-               }
-       }
-
-       if (rule->test.operation == KEY_OP_MATCH ||
-           rule->test.operation == KEY_OP_NOMATCH) {
-               char filename[UTIL_PATH_SIZE];
-               struct stat statbuf;
-               int match;
-
-               util_strlcpy(filename, key_val(rule, &rule->test), sizeof(filename));
-               udev_event_apply_format(event, filename, sizeof(filename));
-               if (udev_event_apply_subsys_kernel(event, NULL, filename, sizeof(filename), 0) != 0)
-                       if (filename[0] != '/') {
-                               char tmp[UTIL_PATH_SIZE];
-
-                               util_strlcpy(tmp, udev_device_get_syspath(dev), sizeof(tmp));
-                               util_strlcat(tmp, "/", sizeof(tmp));
-                               util_strlcat(tmp, filename, sizeof(tmp));
-                               util_strlcpy(filename, tmp, sizeof(filename));
-                       }
-
-               attr_subst_subdir(filename, sizeof(filename));
-
-               match = (stat(filename, &statbuf) == 0);
-               info(event->udev, "'%s' %s", filename, match ? "exists\n" : "does not exist\n");
-               if (match && rule->test_mode_mask > 0) {
-                       match = ((statbuf.st_mode & rule->test_mode_mask) > 0);
-                       info(event->udev, "'%s' has mode=%#o and %s %#o\n", filename, statbuf.st_mode,
-                            match ? "matches" : "does not match",
-                            rule->test_mode_mask);
-               }
-               if (match && rule->test.operation == KEY_OP_NOMATCH)
-                       goto nomatch;
-               if (!match && rule->test.operation == KEY_OP_MATCH)
-                       goto nomatch;
-               dbg(event->udev, "TEST key is true\n");
        }
 
-       if (rule->wait_for.operation != KEY_OP_UNSET) {
-               char filename[UTIL_PATH_SIZE];
-               int found;
+       /* remember end of key */
+       temp = linepos;
 
-               util_strlcpy(filename, key_val(rule, &rule->wait_for), sizeof(filename));
-               udev_event_apply_format(event, filename, sizeof(filename));
-               found = (wait_for_file(event, filename, 10) == 0);
-               if (!found && (rule->wait_for.operation != KEY_OP_NOMATCH))
-                       goto nomatch;
-       }
+       /* skip whitespace after key */
+       while (isspace(linepos[0]))
+               linepos++;
+       if (linepos[0] == '\0')
+               return -1;
 
-       /* check for matching sysfs attribute pairs */
-       for (i = 0; i < rule->attr.count; i++) {
-               struct key_pair *pair = &rule->attr.keys[i];
+       /* get operation type */
+       if (linepos[0] == '=' && linepos[1] == '=') {
+               *op = KEY_OP_MATCH;
+               linepos += 2;
+       } else if (linepos[0] == '!' && linepos[1] == '=') {
+               *op = KEY_OP_NOMATCH;
+               linepos += 2;
+       } else if (linepos[0] == '+' && linepos[1] == '=') {
+               *op = KEY_OP_ADD;
+               linepos += 2;
+       } else if (linepos[0] == '=') {
+               *op = KEY_OP_ASSIGN;
+               linepos++;
+       } else if (linepos[0] == ':' && linepos[1] == '=') {
+               *op = KEY_OP_ASSIGN_FINAL;
+               linepos += 2;
+       } else
+               return -1;
 
-               if (pair->key.operation == KEY_OP_MATCH ||
-                   pair->key.operation == KEY_OP_NOMATCH) {
-                       char attr[UTIL_PATH_SIZE];
-                       const char *key_name = key_pair_name(rule, pair);
-                       const char *key_value = key_val(rule, &pair->key);
-                       char value[UTIL_NAME_SIZE] = "";
-                       size_t len;
+       /* terminate key */
+       temp[0] = '\0';
 
-                       util_strlcpy(attr, key_name, sizeof(attr));
-                       udev_event_apply_subsys_kernel(event, attr, value, sizeof(value), 1);
+       /* skip whitespace after operator */
+       while (isspace(linepos[0]))
+               linepos++;
+       if (linepos[0] == '\0')
+               return -1;
 
-                       if (value[0]=='\0') {
-                               const char *val;
+       /* get the value*/
+       if (linepos[0] == '"')
+               linepos++;
+       else
+               return -1;
+       *value = linepos;
 
-                               val = udev_device_get_sysattr_value(dev, key_name);
-                               if (val != NULL)
-                                       util_strlcpy(value, val, sizeof(value));
-                       }
+       temp = strchr(linepos, '"');
+       if (!temp)
+               return -1;
+       temp[0] = '\0';
+       temp++;
+       dbg(udev, "%s '%s'-'%s'\n", operation_str[*op], *key, *value);
 
-                       if (value[0]=='\0')
-                               goto nomatch;
+       /* move line to next key */
+       *line = temp;
+       return 0;
+}
 
-                       /* strip trailing whitespace of value, if not asked to match for it */
-                       len = strlen(key_value);
-                       if (len > 0 && !isspace(key_value[len-1])) {
-                               len = strlen(value);
-                               while (len > 0 && isspace(value[--len]))
-                                       value[len] = '\0';
-                               dbg(event->udev, "removed trailing whitespace from '%s'\n", value);
-                       }
+/* extract possible KEY{attr} */
+static char *get_key_attribute(struct udev *udev, char *str)
+{
+       char *pos;
+       char *attr;
 
-                       if (match_key(event->udev, "ATTR", rule, &pair->key, value))
-                               goto nomatch;
+       attr = strchr(str, '{');
+       if (attr != NULL) {
+               attr++;
+               pos = strchr(attr, '}');
+               if (pos == NULL) {
+                       err(udev, "missing closing brace for format\n");
+                       return NULL;
                }
+               pos[0] = '\0';
+               dbg(udev, "attribute='%s'\n", attr);
+               return attr;
        }
+       return NULL;
+}
 
-       /* walk up the chain of parent devices and find a match */
-       event->dev_parent = dev;
-       while (1) {
-               /* check for matching kernel device name */
-               if (match_key(event->udev, "KERNELS", rule,
-                             &rule->kernels, udev_device_get_sysname(event->dev_parent)))
-                       goto try_parent;
-
-               /* check for matching subsystem value */
-               if (match_key(event->udev, "SUBSYSTEMS", rule,
-                             &rule->subsystems, udev_device_get_subsystem(event->dev_parent)))
-                       goto try_parent;
-
-               /* check for matching driver */
-               if (match_key(event->udev, "DRIVERS", rule,
-                             &rule->drivers, udev_device_get_driver(event->dev_parent)))
-                       goto try_parent;
-
-               /* check for matching sysfs attribute pairs */
-               for (i = 0; i < rule->attrs.count; i++) {
-                       struct key_pair *pair = &rule->attrs.keys[i];
-
-                       if (pair->key.operation == KEY_OP_MATCH ||
-                           pair->key.operation == KEY_OP_NOMATCH) {
-                               const char *key_name = key_pair_name(rule, pair);
-                               const char *key_value = key_val(rule, &pair->key);
-                               const char *val;
-                               char value[UTIL_NAME_SIZE];
-                               size_t len;
-
-                               val = udev_device_get_sysattr_value(event->dev_parent, key_name);
-                               if (val == NULL)
-                                       val = udev_device_get_sysattr_value(dev, key_name);
-                               if (val == NULL)
-                                       goto try_parent;
-                               util_strlcpy(value, val, sizeof(value));
-
-                               /* strip trailing whitespace of value, if not asked to match for it */
-                               len = strlen(key_value);
-                               if (len > 0 && !isspace(key_value[len-1])) {
-                                       len = strlen(value);
-                                       while (len > 0 && isspace(value[--len]))
-                                               value[len] = '\0';
-                                       dbg(event->udev, "removed trailing whitespace from '%s'\n", value);
-                               }
-
-                               if (match_key(event->udev, "ATTRS", rule, &pair->key, value))
-                                       goto try_parent;
-                       }
-               }
-
-               /* found matching device  */
+static int rule_add_token(struct rule_tmp *rule_tmp, enum token_type type,
+                         enum key_operation op,
+                         const char *value, const void *data)
+{
+       struct token *token = &rule_tmp->token[rule_tmp->token_cur];
+       const char *attr = data;
+       mode_t mode = 0000;
+
+       switch (type) {
+       case TK_M_WAITFOR:
+       case TK_M_ACTION:
+       case TK_M_DEVPATH:
+       case TK_M_KERNEL:
+       case TK_M_SUBSYSTEM:
+       case TK_M_DRIVER:
+       case TK_M_DEVLINK:
+       case TK_M_NAME:
+       case TK_M_KERNELS:
+       case TK_M_SUBSYSTEMS:
+       case TK_M_DRIVERS:
+       case TK_M_PROGRAM:
+       case TK_M_IMPORT_FILE:
+       case TK_M_IMPORT_PROG:
+       case TK_M_IMPORT_PARENT:
+       case TK_M_RESULT:
+       case TK_A_OWNER:
+       case TK_A_GROUP:
+       case TK_A_MODE:
+       case TK_A_NAME:
+       case TK_A_DEVLINK:
+       case TK_A_GOTO:
+               token->key.value_off = add_string(rule_tmp->rules, value);
                break;
-try_parent:
-               /* move to parent device */
-               dbg(event->udev, "try parent sysfs device\n");
-               event->dev_parent = udev_device_get_parent(event->dev_parent);
-               if (event->dev_parent == NULL)
-                       goto nomatch;
-               dbg(event->udev, "looking at dev_parent->devpath='%s'\n",
-                   udev_device_get_syspath(event->dev_parent));
+       case TK_M_ENV:
+       case TK_M_ATTR:
+       case TK_M_ATTRS:
+       case TK_A_ATTR:
+       case TK_A_ENV:
+               token->key.value_off = add_string(rule_tmp->rules, value);
+               token->key.attr_off = add_string(rule_tmp->rules, attr);
+               break;
+       case TK_M_TEST:
+               if (data != NULL)
+                       mode = *(mode_t *)data;
+               token->key.value_off = add_string(rule_tmp->rules, value);
+               token->key.mode = mode;
+               break;
+       case TK_A_IGNORE_DEVICE:
+       case TK_A_STRING_ESCAPE_NONE:
+       case TK_A_STRING_ESCAPE_REPLACE:
+       case TK_A_IGNORE_REMOVE:
+       case TK_A_LAST_RULE:
+               break;
+       case TK_A_RUN:
+               token->key.value_off = add_string(rule_tmp->rules, value);
+               token->key.ignore_error = *(int *)data;
+               break;
+       case TK_A_NUM_FAKE_PART:
+               token->key.num_fake_part = *(int *)data;
+               break;
+       case TK_A_DEVLINK_PRIO:
+               token->key.devlink_prio = *(int *)data;
+               break;
+       case TK_A_OWNER_ID:
+               token->key.uid = *(uid_t *)data;
+               break;
+       case TK_A_GROUP_ID:
+               token->key.gid = *(gid_t *)data;
+               break;
+       case TK_A_MODE_ID:
+               token->key.mode = *(mode_t *)data;
+               break;
+       case TK_A_EVENT_TIMEOUT:
+               token->key.event_timeout = *(int *)data;
+               break;
+       case TK_RULE:
+       case TK_PARENTS_MAX:
+       case TK_END:
+       case TK_UNDEF:
+               err(rule_tmp->rules->udev, "wrong type %u\n", type);
+               return -1;
        }
-
-       /* execute external program */
-       if (rule->program.operation != KEY_OP_UNSET) {
-               char program[UTIL_PATH_SIZE];
-               char **envp;
-               char result[UTIL_PATH_SIZE];
-
-               util_strlcpy(program, key_val(rule, &rule->program), sizeof(program));
-               udev_event_apply_format(event, program, sizeof(program));
-               envp = udev_device_get_properties_envp(dev);
-               if (util_run_program(event->udev, program, envp, result, sizeof(result), NULL) != 0) {
-                       dbg(event->udev, "PROGRAM is false\n");
-                       event->program_result[0] = '\0';
-                       if (rule->program.operation != KEY_OP_NOMATCH)
-                               goto nomatch;
-               } else {
-                       int count;
-
-                       dbg(event->udev, "PROGRAM matches\n");
-                       util_remove_trailing_chars(result, '\n');
-                       if (rule->string_escape == ESCAPE_UNSET ||
-                           rule->string_escape == ESCAPE_REPLACE) {
-                               count = util_replace_chars(result, ALLOWED_CHARS_INPUT);
-                               if (count > 0)
-                                       info(event->udev, "%i character(s) replaced\n" , count);
-                       }
-                       dbg(event->udev, "result is '%s'\n", result);
-                       util_strlcpy(event->program_result, result, sizeof(event->program_result));
-                       dbg(event->udev, "PROGRAM returned successful\n");
-                       if (rule->program.operation == KEY_OP_NOMATCH)
-                               goto nomatch;
-               }
-               dbg(event->udev, "PROGRAM key is true\n");
+       token->type = type;
+       token->key.op = op;
+       rule_tmp->token_cur++;
+       if (rule_tmp->token_cur >= ARRAY_SIZE(rule_tmp->token)) {
+               err(rule_tmp->rules->udev, "temporary rule array too small\n");
+               return -1;
        }
+       return 0;
+}
 
-       /* check for matching result of external program */
-       if (match_key(event->udev, "RESULT", rule, &rule->result, event->program_result))
-               goto nomatch;
-
-       /* import variables returned from program or or file into properties */
-       if (rule->import.operation != KEY_OP_UNSET) {
-               char import[UTIL_PATH_SIZE];
-               int rc = -1;
-
-               util_strlcpy(import, key_val(rule, &rule->import), sizeof(import));
-               udev_event_apply_format(event, import, sizeof(import));
-               dbg(event->udev, "check for IMPORT import='%s'\n", import);
-               if (rule->import_type == IMPORT_PROGRAM) {
-                       rc = import_program_into_env(event->dev, import);
-               } else if (rule->import_type == IMPORT_FILE) {
-                       dbg(event->udev, "import file import='%s'\n", import);
-                       rc = import_file_into_env(event->dev, import);
-               } else if (rule->import_type == IMPORT_PARENT) {
-                       dbg(event->udev, "import parent import='%s'\n", import);
-                       rc = import_parent_into_env(event->dev, import);
+#ifdef DEBUG
+static void dump_token(struct udev_rules *rules, struct token *token)
+{
+       enum token_type type = token->type;
+       enum key_operation op = token->key.op;
+       const char *value = &rules->buf[token->key.value_off];
+       const char *attr = &rules->buf[token->key.attr_off];
+
+       switch (type) {
+       case TK_RULE:
+               {
+                       const char *tks_ptr = (char *)rules->tokens;
+                       const char *tk_ptr = (char *)token;
+                       unsigned int off = tk_ptr - tks_ptr;
+
+                       dbg(rules->udev, "* RULE '%s', off: %u(%u), next: %u, label: '%s'\n",
+                           &rules->buf[token->rule.filename_off],
+                           off / (unsigned int) sizeof(struct token), off,
+                           token->rule.next_rule,
+                           &rules->buf[token->rule.label_off]);
+                       break;
                }
-               if (rc != 0) {
-                       dbg(event->udev, "IMPORT failed\n");
-                       if (rule->import.operation != KEY_OP_NOMATCH)
-                               goto nomatch;
-               } else
-                       dbg(event->udev, "IMPORT '%s' imported\n", key_val(rule, &rule->import));
-               dbg(event->udev, "IMPORT key is true\n");
+       case TK_M_WAITFOR:
+       case TK_M_ACTION:
+       case TK_M_DEVPATH:
+       case TK_M_KERNEL:
+       case TK_M_SUBSYSTEM:
+       case TK_M_DRIVER:
+       case TK_M_DEVLINK:
+       case TK_M_NAME:
+       case TK_M_KERNELS:
+       case TK_M_SUBSYSTEMS:
+       case TK_M_DRIVERS:
+       case TK_M_PROGRAM:
+       case TK_M_IMPORT_FILE:
+       case TK_M_IMPORT_PROG:
+       case TK_M_IMPORT_PARENT:
+       case TK_M_RESULT:
+       case TK_A_NAME:
+       case TK_A_DEVLINK:
+       case TK_A_OWNER:
+       case TK_A_GROUP:
+       case TK_A_MODE:
+       case TK_A_RUN:
+               dbg(rules->udev, "%s %s '%s'\n", token_str[type], operation_str[op], value);
+               break;
+       case TK_M_ATTR:
+       case TK_M_ATTRS:
+       case TK_M_ENV:
+       case TK_A_ATTR:
+       case TK_A_ENV:
+               dbg(rules->udev, "%s %s '%s' '%s'\n", token_str[type], operation_str[op], attr, value);
+               break;
+       case TK_A_IGNORE_DEVICE:
+       case TK_A_STRING_ESCAPE_NONE:
+       case TK_A_STRING_ESCAPE_REPLACE:
+       case TK_A_LAST_RULE:
+       case TK_A_IGNORE_REMOVE:
+               dbg(rules->udev, "%s\n", token_str[type]);
+               break;
+       case TK_M_TEST:
+               dbg(rules->udev, "%s %s '%s' %#o\n", token_str[type], operation_str[op], value, token->key.mode);
+               break;
+       case TK_A_NUM_FAKE_PART:
+               dbg(rules->udev, "%s %u\n", token_str[type], token->key.num_fake_part);
+               break;
+       case TK_A_DEVLINK_PRIO:
+               dbg(rules->udev, "%s %s %u\n", token_str[type], operation_str[op], token->key.devlink_prio);
+               break;
+       case TK_A_OWNER_ID:
+               dbg(rules->udev, "%s %s %u\n", token_str[type], operation_str[op], token->key.uid);
+               break;
+       case TK_A_GROUP_ID:
+               dbg(rules->udev, "%s %s %u\n", token_str[type], operation_str[op], token->key.gid);
+               break;
+       case TK_A_MODE_ID:
+               dbg(rules->udev, "%s %s %#o\n", token_str[type], operation_str[op], token->key.mode);
+               break;
+       case TK_A_EVENT_TIMEOUT:
+               dbg(rules->udev, "%s %s %u\n", token_str[type], operation_str[op], token->key.event_timeout);
+               break;
+       case TK_A_GOTO:
+               dbg(rules->udev, "%s '%s' %u\n", token_str[type], value, token->key.rule_goto);
+               break;
+       case TK_END:
+               dbg(rules->udev, "* %s\n", token_str[type]);
+               break;
+       case TK_PARENTS_MAX:
+       case TK_UNDEF:
+               dbg(rules->udev, "unknown type %u\n", type);
+               break;
        }
+}
 
-       /* rule matches, if we have ENV assignments export it */
-       for (i = 0; i < rule->env.count; i++) {
-               struct key_pair *pair = &rule->env.keys[i];
-
-               if (pair->key.operation == KEY_OP_ASSIGN) {
-                       char temp_value[UTIL_NAME_SIZE];
-                       const char *key_name = key_pair_name(rule, pair);
-                       const char *value = key_val(rule, &pair->key);
-
-                       /* make sure we don't write to the same string we possibly read from */
-                       util_strlcpy(temp_value, value, sizeof(temp_value));
-                       udev_event_apply_format(event, temp_value, sizeof(temp_value));
-
-                       if (temp_value[0] != '\0') {
-                               struct udev_list_entry *entry;
+static void dump_rules(struct udev_rules *rules)
+{
+       unsigned int i;
+
+       dbg(rules->udev, "dumping %u (%zu bytes) tokens, %u (%zu bytes) strings\n",
+           rules->token_cur,
+           rules->token_cur * sizeof(struct token),
+           rules->buf_count,
+           rules->buf_cur);
+       for(i = 0; i < rules->token_cur; i++)
+               dump_token(rules, &rules->tokens[i]);
+}
+#else
+static inline void dump_token(struct udev_rules *rules, struct token *token) {}
+static inline void dump_rules(struct udev_rules *rules) {}
+#endif /* DEBUG */
 
-                               info(event->udev, "set ENV '%s=%s'\n", key_name, temp_value);
-                               entry = udev_device_add_property(dev, key_name, temp_value);
-                               /* store in db */
-                               udev_list_entry_set_flag(entry, 1);
+static int sort_token(struct udev_rules *rules, struct rule_tmp *rule_tmp)
+{
+       unsigned int i;
+       unsigned int start = 0;
+       unsigned int end = rule_tmp->token_cur;
+
+       for (i = 0; i < rule_tmp->token_cur; i++) {
+               enum token_type next_val = TK_UNDEF;
+               unsigned int next_idx;
+               unsigned int j;
+
+               /* find smallest value */
+               for (j = start; j < end; j++) {
+                       if (rule_tmp->token[j].type == TK_UNDEF)
+                               continue;
+                       if (next_val == TK_UNDEF || rule_tmp->token[j].type < next_val) {
+                               next_val = rule_tmp->token[j].type;
+                               next_idx = j;
                        }
                }
-       }
 
-       /* if we have ATTR assignments, write value to sysfs file */
-       for (i = 0; i < rule->attr.count; i++) {
-               struct key_pair *pair = &rule->attr.keys[i];
-
-               if (pair->key.operation == KEY_OP_ASSIGN) {
-                       const char *key_name = key_pair_name(rule, pair);
-                       char attr[UTIL_PATH_SIZE];
-                       char value[UTIL_NAME_SIZE];
-                       FILE *f;
-
-                       util_strlcpy(attr, key_name, sizeof(attr));
-                       if (udev_event_apply_subsys_kernel(event, key_name, attr, sizeof(attr), 0) != 0) {
-                               util_strlcpy(attr, udev_device_get_syspath(dev), sizeof(attr));
-                               util_strlcat(attr, "/", sizeof(attr));
-                               util_strlcat(attr, key_name, sizeof(attr));
-                       }
+               /* add token and mark done */
+               if (add_token(rules, &rule_tmp->token[next_idx]) != 0)
+                       return -1;
+               rule_tmp->token[next_idx].type = TK_UNDEF;
 
-                       attr_subst_subdir(attr, sizeof(attr));
-
-                       util_strlcpy(value, key_val(rule, &pair->key), sizeof(value));
-                       udev_event_apply_format(event, value, sizeof(value));
-                       info(event->udev, "writing '%s' to sysfs file '%s'\n", value, attr);
-                       f = fopen(attr, "w");
-                       if (f != NULL) {
-                               if (!event->test)
-                                       if (fprintf(f, "%s", value) <= 0)
-                                               err(event->udev, "error writing ATTR{%s}: %m\n", attr);
-                               fclose(f);
-                       } else
-                               err(event->udev, "error opening ATTR{%s} for writing: %m\n", attr);
-               }
+               /* shrink range */
+               if (next_idx == start)
+                       start++;
+               if (next_idx+1 == end)
+                       end--;
        }
        return 0;
-
-nomatch:
-       return -1;
 }
 
-int udev_rules_get_name(struct udev_rules *rules, struct udev_event *event)
+static int add_rule(struct udev_rules *rules, char *line,
+                   const char *filename, unsigned int filename_off, unsigned int lineno)
 {
-       struct udev_device *dev = event->dev;
-       struct udev_rules_iter iter;
-       struct udev_rule *rule;
-       int name_set = 0;
+       int valid = 0;
+       char *linepos;
+       char *attr;
+       int physdev = 0;
+       struct rule_tmp rule_tmp;
 
-       dbg(event->udev, "device: '%s'\n", udev_device_get_syspath(dev));
+       memset(&rule_tmp, 0x00, sizeof(struct rule_tmp));
+       rule_tmp.rules = rules;
+       rule_tmp.rule.type = TK_RULE;
+       rule_tmp.rule.rule.filename_off = filename_off;
 
-       /* look for a matching rule to apply */
-       udev_rules_iter_init(&iter, rules);
+       linepos = line;
        while (1) {
-               rule = udev_rules_iter_next(&iter);
-               if (rule == NULL)
+               char *key;
+               char *value;
+               enum key_operation op = KEY_OP_UNSET;
+
+               if (get_key(rules->udev, &linepos, &key, &op, &value) != 0)
                        break;
 
-               if (name_set &&
-                   (rule->name.operation == KEY_OP_ASSIGN ||
-                    rule->name.operation == KEY_OP_ASSIGN_FINAL ||
-                    rule->name.operation == KEY_OP_ADD)) {
-                       dbg(event->udev, "node name already set, rule ignored\n");
+               if (strcasecmp(key, "ACTION") == 0) {
+                       if (op != KEY_OP_MATCH && op != KEY_OP_NOMATCH) {
+                               err(rules->udev, "invalid ACTION operation\n");
+                               goto invalid;
+                       }
+                       rule_add_token(&rule_tmp, TK_M_ACTION, op, value, NULL);
+                       valid = 1;
                        continue;
                }
 
-               dbg(event->udev, "process rule\n");
-               if (match_rule(event, rule) == 0) {
-                       /* apply options */
-                       if (rule->ignore_device) {
-                               info(event->udev, "rule applied, '%s' is ignored\n", udev_device_get_sysname(dev));
-                               event->ignore_device = 1;
-                               return 0;
-                       }
-                       if (rule->ignore_remove) {
-                               udev_device_set_ignore_remove(dev, 1);
-                               dbg(event->udev, "remove event should be ignored\n");
-                       }
-                       if (rule->link_priority != 0) {
-                               udev_device_set_devlink_priority(dev, rule->link_priority);
-                               info(event->udev, "devlink_priority=%i\n", rule->link_priority);
-                       }
-                       if (rule->event_timeout >= 0) {
-                               udev_device_set_event_timeout(dev, rule->event_timeout);
-                               info(event->udev, "event_timeout=%i\n", rule->event_timeout);
-                       }
-                       /* apply all_partitions option only at a disk device */
-                       if (rule->partitions > 0 &&
-                           strcmp(udev_device_get_subsystem(dev), "block") == 0 &&
-                           udev_device_get_sysnum(dev) == NULL) {
-                               udev_device_set_num_fake_partitions(dev, rule->partitions);
-                               dbg(event->udev, "creation of partition nodes requested\n");
+               if (strcasecmp(key, "DEVPATH") == 0) {
+                       if (op != KEY_OP_MATCH && op != KEY_OP_NOMATCH) {
+                               err(rules->udev, "invalid DEVPATH operation\n");
+                               goto invalid;
                        }
-
-                       /* apply permissions */
-                       if (!event->mode_final && rule->mode.operation != KEY_OP_UNSET) {
-                               if (rule->mode.operation == KEY_OP_ASSIGN_FINAL)
-                                       event->mode_final = 1;
-                               char buf[20];
-                               util_strlcpy(buf, key_val(rule, &rule->mode), sizeof(buf));
-                               udev_event_apply_format(event, buf, sizeof(buf));
-                               event->mode = strtol(buf, NULL, 8);
-                               dbg(event->udev, "applied mode=%#o to '%s'\n",
-                                   event->mode, udev_device_get_sysname(dev));
-                       }
-                       if (!event->owner_final && rule->owner.operation != KEY_OP_UNSET) {
-                               if (rule->owner.operation == KEY_OP_ASSIGN_FINAL)
-                                       event->owner_final = 1;
-                               util_strlcpy(event->owner, key_val(rule, &rule->owner), sizeof(event->owner));
-                               udev_event_apply_format(event, event->owner, sizeof(event->owner));
-                               dbg(event->udev, "applied owner='%s' to '%s'\n",
-                                   event->owner, udev_device_get_sysname(dev));
-                       }
-                       if (!event->group_final && rule->group.operation != KEY_OP_UNSET) {
-                               if (rule->group.operation == KEY_OP_ASSIGN_FINAL)
-                                       event->group_final = 1;
-                               util_strlcpy(event->group, key_val(rule, &rule->group), sizeof(event->group));
-                               udev_event_apply_format(event, event->group, sizeof(event->group));
-                               dbg(event->udev, "applied group='%s' to '%s'\n",
-                                   event->group, udev_device_get_sysname(dev));
-                       }
-
-                       /* collect symlinks */
-                       if (!event->devlink_final &&
-                           (rule->symlink.operation == KEY_OP_ASSIGN ||
-                            rule->symlink.operation == KEY_OP_ASSIGN_FINAL ||
-                            rule->symlink.operation == KEY_OP_ADD)) {
-                               char temp[UTIL_PATH_SIZE];
-                               char filename[UTIL_PATH_SIZE];
-                               char *pos, *next;
-                               int count = 0;
-
-                               if (rule->symlink.operation == KEY_OP_ASSIGN_FINAL)
-                                       event->devlink_final = 1;
-                               if (rule->symlink.operation == KEY_OP_ASSIGN ||
-                                   rule->symlink.operation == KEY_OP_ASSIGN_FINAL) {
-                                       info(event->udev, "reset symlink list\n");
-                                       udev_device_cleanup_devlinks_list(dev);
-                               }
-                               /* allow  multiple symlinks separated by spaces */
-                               util_strlcpy(temp, key_val(rule, &rule->symlink), sizeof(temp));
-                               udev_event_apply_format(event, temp, sizeof(temp));
-                               if (rule->string_escape == ESCAPE_UNSET)
-                                       count = util_replace_chars(temp, ALLOWED_CHARS_FILE " ");
-                               else if (rule->string_escape == ESCAPE_REPLACE)
-                                       count = util_replace_chars(temp, ALLOWED_CHARS_FILE);
-                               if (count > 0)
-                                       info(event->udev, "%i character(s) replaced\n" , count);
-                               dbg(event->udev, "rule applied, added symlink(s) '%s'\n", temp);
-                               pos = temp;
-                               while (isspace(pos[0]))
-                                       pos++;
-                               next = strchr(pos, ' ');
-                               while (next) {
-                                       next[0] = '\0';
-                                       info(event->udev, "add symlink '%s'\n", pos);
-                                       util_strlcpy(filename, udev_get_dev_path(event->udev), sizeof(filename));
-                                       util_strlcat(filename, "/", sizeof(filename));
-                                       util_strlcat(filename, pos, sizeof(filename));
-                                       udev_device_add_devlink(dev, filename);
-                                       while (isspace(next[1]))
-                                               next++;
-                                       pos = &next[1];
-                                       next = strchr(pos, ' ');
-                               }
-                               if (pos[0] != '\0') {
-                                       info(event->udev, "add symlink '%s'\n", pos);
-                                       util_strlcpy(filename, udev_get_dev_path(event->udev), sizeof(filename));
-                                       util_strlcat(filename, "/", sizeof(filename));
-                                       util_strlcat(filename, pos, sizeof(filename));
-                                       udev_device_add_devlink(dev, filename);
-                               }
-                       }
-
-                       /* set name, later rules with name set will be ignored */
-                       if (rule->name.operation == KEY_OP_ASSIGN ||
-                           rule->name.operation == KEY_OP_ASSIGN_FINAL ||
-                           rule->name.operation == KEY_OP_ADD) {
-                               int count;
-
-                               name_set = 1;
-                               util_strlcpy(event->name, key_val(rule, &rule->name), sizeof(event->name));
-                               udev_event_apply_format(event, event->name, sizeof(event->name));
-                               if (rule->string_escape == ESCAPE_UNSET ||
-                                   rule->string_escape == ESCAPE_REPLACE) {
-                                       count = util_replace_chars(event->name, ALLOWED_CHARS_FILE);
-                                       if (count > 0)
-                                               info(event->udev, "%i character(s) replaced\n", count);
-                               }
-
-                               info(event->udev, "rule applied, '%s' becomes '%s'\n",
-                                    udev_device_get_sysname(dev), event->name);
-                               if (strcmp(udev_device_get_subsystem(dev), "net") != 0)
-                                       dbg(event->udev, "'%s' owner='%s', group='%s', mode=%#o partitions=%i\n",
-                                           event->name, event->owner, event->group, event->mode,
-                                           udev_device_get_num_fake_partitions(dev));
-                       }
-
-                       if (!event->run_final && rule->run.operation != KEY_OP_UNSET) {
-                               struct udev_list_entry *list_entry;
-
-                               if (rule->run.operation == KEY_OP_ASSIGN_FINAL)
-                                       event->run_final = 1;
-                               if (rule->run.operation == KEY_OP_ASSIGN || rule->run.operation == KEY_OP_ASSIGN_FINAL) {
-                                       info(event->udev, "reset run list\n");
-                                       udev_list_cleanup_entries(event->udev, &event->run_list);
-                               }
-                               dbg(event->udev, "add run '%s'\n", key_val(rule, &rule->run));
-                               list_entry = udev_list_entry_add(event->udev, &event->run_list,
-                                                                key_val(rule, &rule->run), NULL, 1, 0);
-                               if (rule->run_ignore_error && list_entry != NULL)
-                                       udev_list_entry_set_flag(list_entry, 1);
-                       }
-
-                       if (rule->last_rule) {
-                               dbg(event->udev, "last rule to be applied\n");
-                               break;
-                       }
-
-                       if (rule->goto_label.operation != KEY_OP_UNSET) {
-                               dbg(event->udev, "moving forward to label '%s'\n", key_val(rule, &rule->goto_label));
-                               udev_rules_iter_goto(&iter, rule->goto_rule_off);
-                       }
-               }
-       }
-
-       if (!name_set) {
-               info(event->udev, "no node name set, will use kernel name '%s'\n",
-                    udev_device_get_sysname(dev));
-               util_strlcpy(event->name, udev_device_get_sysname(dev), sizeof(event->name));
-       }
-
-       if (event->tmp_node[0] != '\0') {
-               dbg(event->udev, "removing temporary device node\n");
-               util_unlink_secure(event->udev, event->tmp_node);
-               event->tmp_node[0] = '\0';
-       }
-       return 0;
-}
-
-int udev_rules_get_run(struct udev_rules *rules, struct udev_event *event)
-{
-       struct udev_device *dev = event->dev;
-       struct udev_rules_iter iter;
-       struct udev_rule *rule;
-
-       dbg(event->udev, "sysname: '%s'\n", udev_device_get_sysname(dev));
-
-       /* look for a matching rule to apply */
-       udev_rules_iter_init(&iter, rules);
-       while (1) {
-               rule = udev_rules_iter_next(&iter);
-               if (rule == NULL)
-                       break;
-
-               dbg(event->udev, "process rule\n");
-               if (rule->name.operation == KEY_OP_ASSIGN ||
-                   rule->name.operation == KEY_OP_ASSIGN_FINAL ||
-                   rule->name.operation == KEY_OP_ADD ||
-                   rule->symlink.operation == KEY_OP_ASSIGN ||
-                   rule->symlink.operation == KEY_OP_ASSIGN_FINAL ||
-                   rule->symlink.operation == KEY_OP_ADD ||
-                   rule->mode.operation != KEY_OP_UNSET ||
-                   rule->owner.operation != KEY_OP_UNSET || rule->group.operation != KEY_OP_UNSET) {
-                       dbg(event->udev, "skip rule that names a device\n");
-                       continue;
-               }
-
-               if (match_rule(event, rule) == 0) {
-                       if (rule->ignore_device) {
-                               info(event->udev, "rule applied, '%s' is ignored\n", udev_device_get_sysname(dev));
-                               event->ignore_device = 1;
-                               return 0;
-                       }
-                       if (rule->ignore_remove) {
-                               udev_device_set_ignore_remove(dev, 1);
-                               dbg(event->udev, "remove event should be ignored\n");
-                       }
-
-                       if (!event->run_final && rule->run.operation != KEY_OP_UNSET) {
-                               struct udev_list_entry *list_entry;
-
-                               if (rule->run.operation == KEY_OP_ASSIGN ||
-                                   rule->run.operation == KEY_OP_ASSIGN_FINAL) {
-                                       info(event->udev, "reset run list\n");
-                                       udev_list_cleanup_entries(event->udev, &event->run_list);
-                               }
-                               dbg(event->udev, "add run '%s'\n", key_val(rule, &rule->run));
-                               list_entry = udev_list_entry_add(event->udev, &event->run_list,
-                                                                key_val(rule, &rule->run), NULL, 1, 0);
-                               if (rule->run_ignore_error && list_entry != NULL)
-                                       udev_list_entry_set_flag(list_entry, 1);
-                               if (rule->run.operation == KEY_OP_ASSIGN_FINAL)
-                                       break;
-                       }
-
-                       if (rule->last_rule) {
-                               dbg(event->udev, "last rule to be applied\n");
-                               break;
-                       }
-
-                       if (rule->goto_label.operation != KEY_OP_UNSET) {
-                               dbg(event->udev, "moving forward to label '%s'\n", key_val(rule, &rule->goto_label));
-                               udev_rules_iter_goto(&iter, rule->goto_rule_off);
-                       }
-               }
-       }
-
-       return 0;
-}
-
-static int get_key(struct udev_rules *rules, char **line, char **key, enum key_operation *operation, char **value)
-{
-       char *linepos;
-       char *temp;
-
-       linepos = *line;
-       if (linepos == NULL && linepos[0] == '\0')
-               return -1;
-
-       /* skip whitespace */
-       while (isspace(linepos[0]) || linepos[0] == ',')
-               linepos++;
-
-       /* get the key */
-       if (linepos[0] == '\0')
-               return -1;
-       *key = linepos;
-
-       while (1) {
-               linepos++;
-               if (linepos[0] == '\0')
-                       return -1;
-               if (isspace(linepos[0]))
-                       break;
-               if (linepos[0] == '=')
-                       break;
-               if ((linepos[0] == '+') || (linepos[0] == '!') || (linepos[0] == ':'))
-                       if (linepos[1] == '=')
-                               break;
-       }
-
-       /* remember end of key */
-       temp = linepos;
-
-       /* skip whitespace after key */
-       while (isspace(linepos[0]))
-               linepos++;
-       if (linepos[0] == '\0')
-               return -1;
-
-       /* get operation type */
-       if (linepos[0] == '=' && linepos[1] == '=') {
-               *operation = KEY_OP_MATCH;
-               linepos += 2;
-               dbg(rules->udev, "match:\n");
-       } else if (linepos[0] == '!' && linepos[1] == '=') {
-               *operation = KEY_OP_NOMATCH;
-               linepos += 2;
-               dbg(rules->udev, "nomatch:\n");
-       } else if (linepos[0] == '+' && linepos[1] == '=') {
-               *operation = KEY_OP_ADD;
-               linepos += 2;
-               dbg(rules->udev, "add:\n");
-       } else if (linepos[0] == '=') {
-               *operation = KEY_OP_ASSIGN;
-               linepos++;
-               dbg(rules->udev, "assign:\n");
-       } else if (linepos[0] == ':' && linepos[1] == '=') {
-               *operation = KEY_OP_ASSIGN_FINAL;
-               linepos += 2;
-               dbg(rules->udev, "assign_final:\n");
-       } else
-               return -1;
-
-       /* terminate key */
-       temp[0] = '\0';
-
-       /* skip whitespace after operator */
-       while (isspace(linepos[0]))
-               linepos++;
-       if (linepos[0] == '\0')
-               return -1;
-
-       /* get the value*/
-       if (linepos[0] == '"')
-               linepos++;
-       else
-               return -1;
-       *value = linepos;
-
-       temp = strchr(linepos, '"');
-       if (!temp)
-               return -1;
-       temp[0] = '\0';
-       temp++;
-       dbg(rules->udev, "'%s'-'%s'\n", *key, *value);
-
-       /* move line to next key */
-       *line = temp;
-       return 0;
-}
-
-/* extract possible KEY{attr} */
-static char *get_key_attribute(struct udev_rules *rules, char *str)
-{
-       char *pos;
-       char *attr;
-
-       attr = strchr(str, '{');
-       if (attr != NULL) {
-               attr++;
-               pos = strchr(attr, '}');
-               if (pos == NULL) {
-                       err(rules->udev, "missing closing brace for format\n");
-                       return NULL;
-               }
-               pos[0] = '\0';
-               dbg(rules->udev, "attribute='%s'\n", attr);
-               return attr;
-       }
-
-       return NULL;
-}
-
-static int add_rule_key(struct udev_rule *rule, struct key *key,
-                       enum key_operation operation, const char *value)
-{
-       size_t val_len = strnlen(value, UTIL_PATH_SIZE);
-
-       key->operation = operation;
-
-       key->val_off = rule->bufsize;
-       util_strlcpy(rule->buf + rule->bufsize, value, val_len+1);
-       rule->bufsize += val_len+1;
-
-       return 0;
-}
-
-static int add_rule_key_pair(struct udev_rules *rules, struct udev_rule *rule, struct key_pairs *pairs,
-                            enum key_operation operation, const char *key, const char *value)
-{
-       size_t key_len = strnlen(key, UTIL_PATH_SIZE);
-
-       if (pairs->count >= PAIRS_MAX) {
-               err(rules->udev, "skip, too many keys of the same type in a single rule\n");
-               return -1;
-       }
-
-       add_rule_key(rule, &pairs->keys[pairs->count].key, operation, value);
-
-       /* add the key-name of the pair */
-       pairs->keys[pairs->count].key_name_off = rule->bufsize;
-       util_strlcpy(rule->buf + rule->bufsize, key, key_len+1);
-       rule->bufsize += key_len+1;
-
-       pairs->count++;
-
-       return 0;
-}
-
-static int add_to_rules(struct udev_rules *rules, char *line, const char *filename, unsigned int lineno)
-{
-       char buf[sizeof(struct udev_rule) + UTIL_LINE_SIZE];
-       struct udev_rule *rule;
-       size_t rule_size;
-       int valid;
-       char *linepos;
-       char *attr;
-       size_t padding;
-       int physdev = 0;
-
-       memset(buf, 0x00, sizeof(buf));
-       rule = (struct udev_rule *) buf;
-       rule->event_timeout = -1;
-       linepos = line;
-       valid = 0;
-
-       /* get all the keys */
-       while (1) {
-               char *key;
-               char *value;
-               enum key_operation operation = KEY_OP_UNSET;
-
-               if (get_key(rules, &linepos, &key, &operation, &value) != 0)
-                       break;
-
-               if (strcasecmp(key, "ACTION") == 0) {
-                       if (operation != KEY_OP_MATCH &&
-                           operation != KEY_OP_NOMATCH) {
-                               err(rules->udev, "invalid ACTION operation\n");
-                               goto invalid;
-                       }
-                       add_rule_key(rule, &rule->action, operation, value);
-                       valid = 1;
-                       continue;
-               }
-
-               if (strcasecmp(key, "DEVPATH") == 0) {
-                       if (operation != KEY_OP_MATCH &&
-                           operation != KEY_OP_NOMATCH) {
-                               err(rules->udev, "invalid DEVPATH operation\n");
-                               goto invalid;
-                       }
-                       add_rule_key(rule, &rule->devpath, operation, value);
-                       valid = 1;
-                       continue;
-               }
+                       rule_add_token(&rule_tmp, TK_M_DEVPATH, op, value, NULL);
+                       valid = 1;
+                       continue;
+               }
 
                if (strcasecmp(key, "KERNEL") == 0) {
-                       if (operation != KEY_OP_MATCH &&
-                           operation != KEY_OP_NOMATCH) {
+                       if (op != KEY_OP_MATCH && op != KEY_OP_NOMATCH) {
                                err(rules->udev, "invalid KERNEL operation\n");
                                goto invalid;
                        }
-                       add_rule_key(rule, &rule->kernel, operation, value);
+                       rule_add_token(&rule_tmp, TK_M_KERNEL, op, value, NULL);
                        valid = 1;
                        continue;
                }
 
                if (strcasecmp(key, "SUBSYSTEM") == 0) {
-                       if (operation != KEY_OP_MATCH &&
-                           operation != KEY_OP_NOMATCH) {
+                       if (op != KEY_OP_MATCH && op != KEY_OP_NOMATCH) {
                                err(rules->udev, "invalid SUBSYSTEM operation\n");
                                goto invalid;
                        }
@@ -1298,79 +885,77 @@ static int add_to_rules(struct udev_rules *rules, char *line, const char *filena
                                if (strcmp(value, "bus") == 0 || strcmp(value, "class") == 0)
                                        err(rules->udev, "'%s' must be specified as 'subsystem' \n"
                                            "please fix it in %s:%u", value, filename, lineno);
-                               add_rule_key(rule, &rule->subsystem, operation, "subsystem|class|bus");
+                               rule_add_token(&rule_tmp, TK_M_SUBSYSTEM, op, "subsystem|class|bus", NULL);
                        } else
-                               add_rule_key(rule, &rule->subsystem, operation, value);
+                               rule_add_token(&rule_tmp, TK_M_SUBSYSTEM, op, value, NULL);
                        valid = 1;
                        continue;
                }
 
                if (strcasecmp(key, "DRIVER") == 0) {
-                       if (operation != KEY_OP_MATCH &&
-                           operation != KEY_OP_NOMATCH) {
+                       if (op != KEY_OP_MATCH && op != KEY_OP_NOMATCH) {
                                err(rules->udev, "invalid DRIVER operation\n");
                                goto invalid;
                        }
-                       add_rule_key(rule, &rule->driver, operation, value);
+                       rule_add_token(&rule_tmp, TK_M_DRIVER, op, value, NULL);
                        valid = 1;
                        continue;
                }
 
                if (strncasecmp(key, "ATTR{", sizeof("ATTR{")-1) == 0) {
-                       attr = get_key_attribute(rules, key + sizeof("ATTR")-1);
+                       attr = get_key_attribute(rules->udev, key + sizeof("ATTR")-1);
                        if (attr == NULL) {
                                err(rules->udev, "error parsing ATTR attribute\n");
                                goto invalid;
                        }
-                       if (add_rule_key_pair(rules, rule, &rule->attr, operation, attr, value) != 0)
-                               goto invalid;
+                       if (op == KEY_OP_MATCH || op == KEY_OP_NOMATCH) {
+                               rule_add_token(&rule_tmp, TK_M_ATTR, op, value, attr);
+                       } else {
+                               rule_add_token(&rule_tmp, TK_A_ATTR, op, value, attr);
+                       }
                        valid = 1;
                        continue;
                }
 
                if (strcasecmp(key, "KERNELS") == 0 ||
                    strcasecmp(key, "ID") == 0) {
-                       if (operation != KEY_OP_MATCH &&
-                           operation != KEY_OP_NOMATCH) {
+                       if (op != KEY_OP_MATCH && op != KEY_OP_NOMATCH) {
                                err(rules->udev, "invalid KERNELS operation\n");
                                goto invalid;
                        }
-                       add_rule_key(rule, &rule->kernels, operation, value);
+                       rule_add_token(&rule_tmp, TK_M_KERNELS, op, value, NULL);
                        valid = 1;
                        continue;
                }
 
                if (strcasecmp(key, "SUBSYSTEMS") == 0 ||
                    strcasecmp(key, "BUS") == 0) {
-                       if (operation != KEY_OP_MATCH &&
-                           operation != KEY_OP_NOMATCH) {
+                       if (op != KEY_OP_MATCH && op != KEY_OP_NOMATCH) {
                                err(rules->udev, "invalid SUBSYSTEMS operation\n");
                                goto invalid;
                        }
-                       add_rule_key(rule, &rule->subsystems, operation, value);
+                       rule_add_token(&rule_tmp, TK_M_SUBSYSTEMS, op, value, NULL);
                        valid = 1;
                        continue;
                }
 
                if (strcasecmp(key, "DRIVERS") == 0) {
-                       if (operation != KEY_OP_MATCH &&
-                           operation != KEY_OP_NOMATCH) {
+                       if (op != KEY_OP_MATCH && op != KEY_OP_NOMATCH) {
                                err(rules->udev, "invalid DRIVERS operation\n");
                                goto invalid;
                        }
-                       add_rule_key(rule, &rule->drivers, operation, value);
+                       rule_add_token(&rule_tmp, TK_M_DRIVERS, op, value, NULL);
                        valid = 1;
                        continue;
                }
 
                if (strncasecmp(key, "ATTRS{", sizeof("ATTRS{")-1) == 0 ||
                    strncasecmp(key, "SYSFS{", sizeof("SYSFS{")-1) == 0) {
-                       if (operation != KEY_OP_MATCH &&
-                           operation != KEY_OP_NOMATCH) {
+                       if (op != KEY_OP_MATCH && op != KEY_OP_NOMATCH) {
                                err(rules->udev, "invalid ATTRS operation\n");
                                goto invalid;
                        }
-                       attr = get_key_attribute(rules, key + sizeof("ATTRS")-1);
+                       attr = get_key_attribute(rules->udev, key + sizeof("ATTRS")-1);
                        if (attr == NULL) {
                                err(rules->udev, "error parsing ATTRS attribute\n");
                                goto invalid;
@@ -1381,54 +966,60 @@ static int add_to_rules(struct udev_rules *rules, char *line, const char *filena
                        else if (strstr(attr, "../") != NULL)
                                err(rules->udev, "do not reference parent sysfs directories directly, "
                                    "it may break with a future kernel, please fix it in %s:%u", filename, lineno);
-                       if (add_rule_key_pair(rules, rule, &rule->attrs, operation, attr, value) != 0)
-                               goto invalid;
+                       rule_add_token(&rule_tmp, TK_M_ATTRS, op, value, attr);
                        valid = 1;
                        continue;
                }
 
                if (strncasecmp(key, "ENV{", sizeof("ENV{")-1) == 0) {
-                       attr = get_key_attribute(rules, key + sizeof("ENV")-1);
+                       attr = get_key_attribute(rules->udev, key + sizeof("ENV")-1);
                        if (attr == NULL) {
                                err(rules->udev, "error parsing ENV attribute\n");
                                goto invalid;
                        }
                        if (strncmp(attr, "PHYSDEV", 7) == 0)
                                physdev = 1;
-                       if (add_rule_key_pair(rules, rule, &rule->env, operation, attr, value) != 0)
-                               goto invalid;
+                       if (op == KEY_OP_MATCH || op == KEY_OP_NOMATCH) {
+                               if (rule_add_token(&rule_tmp, TK_M_ENV, op, value, attr) != 0)
+                                       goto invalid;
+                       } else {
+                               if (rule_add_token(&rule_tmp, TK_A_ENV, op, value, attr) != 0)
+                                       goto invalid;
+                       }
                        valid = 1;
                        continue;
                }
 
                if (strcasecmp(key, "PROGRAM") == 0) {
-                       add_rule_key(rule, &rule->program, operation, value);
+                       rule_add_token(&rule_tmp, TK_M_PROGRAM, op, value, NULL);
                        valid = 1;
                        continue;
                }
 
                if (strcasecmp(key, "RESULT") == 0) {
-                       if (operation != KEY_OP_MATCH &&
-                           operation != KEY_OP_NOMATCH) {
+                       if (op != KEY_OP_MATCH && op != KEY_OP_NOMATCH) {
                                err(rules->udev, "invalid RESULT operation\n");
                                goto invalid;
                        }
-                       add_rule_key(rule, &rule->result, operation, value);
+                       rule_add_token(&rule_tmp, TK_M_RESULT, op, value, NULL);
                        valid = 1;
                        continue;
                }
 
                if (strncasecmp(key, "IMPORT", sizeof("IMPORT")-1) == 0) {
-                       attr = get_key_attribute(rules, key + sizeof("IMPORT")-1);
+                       attr = get_key_attribute(rules->udev, key + sizeof("IMPORT")-1);
                        if (attr != NULL && strstr(attr, "program")) {
                                dbg(rules->udev, "IMPORT will be executed\n");
-                               rule->import_type  = IMPORT_PROGRAM;
+                               rule_add_token(&rule_tmp, TK_M_IMPORT_PROG, op, value, NULL);
+                               valid = 1;
                        } else if (attr != NULL && strstr(attr, "file")) {
                                dbg(rules->udev, "IMPORT will be included as file\n");
-                               rule->import_type  = IMPORT_FILE;
+                               rule_add_token(&rule_tmp, TK_M_IMPORT_FILE, op, value, NULL);
+                               valid = 1;
                        } else if (attr != NULL && strstr(attr, "parent")) {
                                dbg(rules->udev, "IMPORT will include the parent values\n");
-                               rule->import_type = IMPORT_PARENT;
+                               rule_add_token(&rule_tmp, TK_M_IMPORT_PARENT, op, value, NULL);
+                               valid = 1;
                        } else {
                                /* figure it out if it is executable */
                                char file[UTIL_PATH_SIZE];
@@ -1451,129 +1042,141 @@ static int add_to_rules(struct udev_rules *rules, char *line, const char *filena
 
                                dbg(rules->udev, "IMPORT auto mode for '%s'\n", file);
                                if (!lstat(file, &statbuf) && (statbuf.st_mode & S_IXUSR)) {
-                                       dbg(rules->udev, "IMPORT is executable, will be executed (autotype)\n");
-                                       rule->import_type  = IMPORT_PROGRAM;
+                                       dbg(rules->udev, "IMPORT will be executed (autotype)\n");
+                                       rule_add_token(&rule_tmp, TK_M_IMPORT_PROG, op, value, NULL);
+                                       valid = 1;
                                } else {
-                                       dbg(rules->udev, "IMPORT is not executable, will be included as file (autotype)\n");
-                                       rule->import_type  = IMPORT_FILE;
+                                       dbg(rules->udev, "IMPORT will be included as file (autotype)\n");
+                                       rule_add_token(&rule_tmp, TK_M_IMPORT_FILE, op, value, NULL);
+                                       valid = 1;
                                }
                        }
-                       add_rule_key(rule, &rule->import, operation, value);
-                       valid = 1;
                        continue;
                }
 
                if (strncasecmp(key, "TEST", sizeof("TEST")-1) == 0) {
-                       if (operation != KEY_OP_MATCH &&
-                           operation != KEY_OP_NOMATCH) {
+                       mode_t mode = 0;
+
+                       if (op != KEY_OP_MATCH && op != KEY_OP_NOMATCH) {
                                err(rules->udev, "invalid TEST operation\n");
                                goto invalid;
                        }
-                       attr = get_key_attribute(rules, key + sizeof("TEST")-1);
-                       if (attr != NULL)
-                               rule->test_mode_mask = strtol(attr, NULL, 8);
-                       add_rule_key(rule, &rule->test, operation, value);
+                       attr = get_key_attribute(rules->udev, key + sizeof("TEST")-1);
+                       if (attr != NULL) {
+                               mode = strtol(attr, NULL, 8);
+                               rule_add_token(&rule_tmp, TK_M_TEST, op, value, &mode);
+                       } else {
+                               rule_add_token(&rule_tmp, TK_M_TEST, op, value, NULL);
+                       }
                        valid = 1;
                        continue;
                }
 
                if (strncasecmp(key, "RUN", sizeof("RUN")-1) == 0) {
-                       attr = get_key_attribute(rules, key + sizeof("RUN")-1);
-                       if (attr != NULL) {
-                               if (strstr(attr, "ignore_error"))
-                                       rule->run_ignore_error = 1;
-                       }
-                       add_rule_key(rule, &rule->run, operation, value);
+                       int flag = 0;
+
+                       attr = get_key_attribute(rules->udev, key + sizeof("RUN")-1);
+                       if (attr != NULL && strstr(attr, "ignore_error"))
+                               flag = 1;
+                       rule_add_token(&rule_tmp, TK_A_RUN, op, value, &flag);
                        valid = 1;
                        continue;
                }
 
                if (strcasecmp(key, "WAIT_FOR") == 0 || strcasecmp(key, "WAIT_FOR_SYSFS") == 0) {
-                       add_rule_key(rule, &rule->wait_for, operation, value);
+                       rule_add_token(&rule_tmp, TK_M_WAITFOR, 0, value, NULL);
                        valid = 1;
                        continue;
                }
 
                if (strcasecmp(key, "LABEL") == 0) {
-                       add_rule_key(rule, &rule->label, operation, value);
+                       rule_tmp.rule.rule.label_off = add_string(rules, value);
                        valid = 1;
                        continue;
                }
 
                if (strcasecmp(key, "GOTO") == 0) {
-                       add_rule_key(rule, &rule->goto_label, operation, value);
+                       rule_add_token(&rule_tmp, TK_A_GOTO, 0, value, NULL);
                        valid = 1;
                        continue;
                }
 
                if (strncasecmp(key, "NAME", sizeof("NAME")-1) == 0) {
-                       attr = get_key_attribute(rules, key + sizeof("NAME")-1);
-                       if (attr != NULL) {
-                               if (strstr(attr, "all_partitions") != NULL) {
-                                       dbg(rules->udev, "creation of partition nodes requested\n");
-                                       rule->partitions = DEFAULT_FAKE_PARTITIONS_COUNT;
-                               }
-                               if (strstr(attr, "ignore_remove") != NULL) {
-                                       dbg(rules->udev, "remove event should be ignored\n");
-                                       rule->ignore_remove = 1;
+                       if (op == KEY_OP_MATCH || op == KEY_OP_NOMATCH) {
+                               rule_add_token(&rule_tmp, TK_M_NAME, op, value, NULL);
+                       } else {
+                               if (value[0] == '\0')
+                                       dbg(rules->udev, "name empty, node creation suppressed\n");
+                               rule_add_token(&rule_tmp, TK_A_NAME, op, value, NULL);
+                               attr = get_key_attribute(rules->udev, key + sizeof("NAME")-1);
+                               if (attr != NULL) {
+                                       if (strstr(attr, "all_partitions") != NULL) {
+                                               int num = DEFAULT_FAKE_PARTITIONS_COUNT;
+
+                                               dbg(rules->udev, "creation of partition nodes requested\n");
+                                               rule_add_token(&rule_tmp, TK_A_NUM_FAKE_PART, 0, NULL, &num);
+                                       }
+                                       if (strstr(attr, "ignore_remove") != NULL) {
+                                               dbg(rules->udev, "remove event should be ignored\n");
+                                               rule_add_token(&rule_tmp, TK_A_IGNORE_REMOVE, 0, NULL, NULL);
+                                       }
                                }
                        }
-                       if (value[0] == '\0')
-                               dbg(rules->udev, "name empty, node creation supressed\n");
-                       add_rule_key(rule, &rule->name, operation, value);
                        continue;
                }
 
                if (strcasecmp(key, "SYMLINK") == 0) {
-                       if (operation == KEY_OP_MATCH ||
-                           operation == KEY_OP_NOMATCH)
-                               add_rule_key(rule, &rule->symlink_match, operation, value);
-                       else
-                               add_rule_key(rule, &rule->symlink, operation, value);
-                       valid = 1;
-                       continue;
-               }
+                       if (op == KEY_OP_MATCH || op == KEY_OP_NOMATCH)
+                                       rule_add_token(&rule_tmp, TK_M_DEVLINK, op, value, NULL);
+                               else
+                                       rule_add_token(&rule_tmp, TK_A_DEVLINK, op, value, NULL);
+                               valid = 1;
+                               continue;
+                       }
 
                if (strcasecmp(key, "OWNER") == 0) {
-                       valid = 1;
-                       if (rules->resolve_names && (!strchr(value, '$') && !strchr(value, '%'))) {
-                               char *endptr;
-                               strtoul(value, &endptr, 10);
-                               if (endptr[0] != '\0') {
-                                       char owner[32];
-                                       uid_t uid = util_lookup_user(rules->udev, value);
-                                       dbg(rules->udev, "replacing username='%s' by id=%i\n", value, uid);
-                                       sprintf(owner, "%u", (unsigned int) uid);
-                                       add_rule_key(rule, &rule->owner, operation, owner);
-                                       continue;
-                               }
+                       uid_t uid;
+                       char *endptr;
+
+                       uid = strtoul(value, &endptr, 10);
+                       if (endptr[0] == '\0') {
+                               rule_add_token(&rule_tmp, TK_A_OWNER_ID, op, NULL, &uid);
+                       } else if (rules->resolve_names && strchr("$%", value[0]) == NULL) {
+                               uid = util_lookup_user(rules->udev, value);
+                               rule_add_token(&rule_tmp, TK_A_OWNER_ID, op, NULL, &uid);
+                       } else {
+                               rule_add_token(&rule_tmp, TK_A_OWNER, op, value, NULL);
                        }
-
-                       add_rule_key(rule, &rule->owner, operation, value);
+                       valid = 1;
                        continue;
                }
 
                if (strcasecmp(key, "GROUP") == 0) {
-                       valid = 1;
-                       if (rules->resolve_names && (!strchr(value, '$') && !strchr(value, '%'))) {
-                               char *endptr;
-                               strtoul(value, &endptr, 10);
-                               if (endptr[0] != '\0') {
-                                       char group[32];
-                                       gid_t gid = util_lookup_group(rules->udev, value);
-                                       dbg(rules->udev, "replacing groupname='%s' by id=%i\n", value, gid);
-                                       sprintf(group, "%u", (unsigned int) gid);
-                                       add_rule_key(rule, &rule->group, operation, group);
-                                       continue;
-                               }
+                       gid_t gid;
+                       char *endptr;
+
+                       gid = strtoul(value, &endptr, 10);
+                       if (endptr[0] == '\0') {
+                               rule_add_token(&rule_tmp, TK_A_GROUP_ID, op, NULL, &gid);
+                       } else if (rules->resolve_names && strchr("$%", value[0]) == NULL) {
+                               gid = util_lookup_group(rules->udev, value);
+                               rule_add_token(&rule_tmp, TK_A_GROUP_ID, op, NULL, &gid);
+                       } else {
+                               rule_add_token(&rule_tmp, TK_A_GROUP, op, value, NULL);
                        }
-
-                       add_rule_key(rule, &rule->group, operation, value);
+                       valid = 1;
                        continue;
                }
 
                if (strcasecmp(key, "MODE") == 0) {
-                       add_rule_key(rule, &rule->mode, operation, value);
+                       mode_t mode;
+                       char *endptr;
+
+                       mode = strtol(value, &endptr, 8);
+                       if (endptr[0] == '\0')
+                               rule_add_token(&rule_tmp, TK_A_MODE_ID, op, NULL, &mode);
+                       else
+                               rule_add_token(&rule_tmp, TK_A_MODE, op, value, NULL);
                        valid = 1;
                        continue;
                }
@@ -1583,71 +1186,66 @@ static int add_to_rules(struct udev_rules *rules, char *line, const char *filena
 
                        if (strstr(value, "last_rule") != NULL) {
                                dbg(rules->udev, "last rule to be applied\n");
-                               rule->last_rule = 1;
+                               rule_add_token(&rule_tmp, TK_A_LAST_RULE, 0, NULL, NULL);
                        }
                        if (strstr(value, "ignore_device") != NULL) {
                                dbg(rules->udev, "device should be ignored\n");
-                               rule->ignore_device = 1;
+                               rule_add_token(&rule_tmp, TK_A_IGNORE_DEVICE, 0, NULL, NULL);
                        }
                        if (strstr(value, "ignore_remove") != NULL) {
                                dbg(rules->udev, "remove event should be ignored\n");
-                               rule->ignore_remove = 1;
+                               rule_add_token(&rule_tmp, TK_A_IGNORE_REMOVE, 0, NULL, NULL);
                        }
                        pos = strstr(value, "link_priority=");
                        if (pos != NULL) {
-                               rule->link_priority = atoi(&pos[strlen("link_priority=")]);
-                               dbg(rules->udev, "link priority=%i\n", rule->link_priority);
+                               int prio = atoi(&pos[strlen("link_priority=")]);
+
+                               rule_add_token(&rule_tmp, TK_A_DEVLINK_PRIO, 0, NULL, &prio);
+                               dbg(rules->udev, "link priority=%i\n", prio);
                        }
                        pos = strstr(value, "event_timeout=");
                        if (pos != NULL) {
-                               rule->event_timeout = atoi(&pos[strlen("event_timeout=")]);
-                               dbg(rules->udev, "event timout=%i\n", rule->event_timeout);
+                               int tout = atoi(&pos[strlen("event_timeout=")]);
+
+                               rule_add_token(&rule_tmp, TK_A_EVENT_TIMEOUT, 0, NULL, &tout);
+                               dbg(rules->udev, "event timout=%i\n", tout);
                        }
                        pos = strstr(value, "string_escape=");
                        if (pos != NULL) {
                                pos = &pos[strlen("string_escape=")];
                                if (strncmp(pos, "none", strlen("none")) == 0)
-                                       rule->string_escape = ESCAPE_NONE;
+                                       rule_add_token(&rule_tmp, TK_A_STRING_ESCAPE_NONE, 0, NULL, NULL);
                                else if (strncmp(pos, "replace", strlen("replace")) == 0)
-                                       rule->string_escape = ESCAPE_REPLACE;
+                                       rule_add_token(&rule_tmp, TK_A_STRING_ESCAPE_REPLACE, 0, NULL, NULL);
                        }
                        if (strstr(value, "all_partitions") != NULL) {
+                               int num = DEFAULT_FAKE_PARTITIONS_COUNT;
+
+                               rule_add_token(&rule_tmp, TK_A_NUM_FAKE_PART, 0, NULL, &num);
                                dbg(rules->udev, "creation of partition nodes requested\n");
-                               rule->partitions = DEFAULT_FAKE_PARTITIONS_COUNT;
                        }
                        valid = 1;
                        continue;
                }
-
                err(rules->udev, "unknown key '%s' in %s:%u\n", key, filename, lineno);
        }
 
-       if (physdev && rule->wait_for.operation == KEY_OP_UNSET)
-               err(rules->udev, "PHYSDEV* values are deprecated and will be removed from a future kernel, \n"
+       if (physdev)
+               err(rules->udev, "PHYSDEV* values are deprecated and not available on recent kernels, \n"
                    "please fix it in %s:%u", filename, lineno);
 
        /* skip line if not any valid key was found */
        if (!valid)
                goto invalid;
 
-       /* grow buffer and add rule */
-       rule_size = sizeof(struct udev_rule) + rule->bufsize;
-       padding = (sizeof(size_t) - rule_size % sizeof(size_t)) % sizeof(size_t);
-       dbg(rules->udev, "add %zi padding bytes\n", padding);
-       rule_size += padding;
-       rule->bufsize += padding;
-
-       rules->buf = realloc(rules->buf, rules->bufsize + rule_size);
-       if (!rules->buf) {
-               err(rules->udev, "realloc failed\n");
-               goto exit;
-       }
-       dbg(rules->udev, "adding rule to offset %zi\n", rules->bufsize);
-       memcpy(rules->buf + rules->bufsize, rule, rule_size);
-       rules->bufsize += rule_size;
-exit:
-       return 0;
+       /* add rule token */
+       if (add_token(rules, &rule_tmp.rule) != 0)
+               goto invalid;
 
+       /* add tokens to list, sorted by type */
+       if (sort_token(rules, &rule_tmp) != 0)
+               goto invalid;
+       return 0;
 invalid:
        err(rules->udev, "invalid rule '%s:%u'\n", filename, lineno);
        return -1;
@@ -1656,20 +1254,22 @@ invalid:
 static int parse_file(struct udev_rules *rules, const char *filename)
 {
        FILE *f;
+       unsigned int filename_off;
+       unsigned int first_token;
        char line[UTIL_LINE_SIZE];
-       size_t start;
-       struct udev_rule *rule;
-       struct udev_rules_iter iter;
+       int line_nr = 0;
+       unsigned int i;
 
-       start = rules->bufsize;
        info(rules->udev, "reading '%s' as rules file\n", filename);
 
        f = fopen(filename, "r");
        if (f == NULL)
                return -1;
 
+       filename_off = add_string(rules, filename);
+       first_token = rules->token_cur;
+
        while(fgets(line, sizeof(line), f) != NULL) {
-               int line_nr = 0;
                char *key;
                size_t len;
 
@@ -1699,24 +1299,27 @@ static int parse_file(struct udev_rules *rules, const char *filename)
                        err(rules->udev, "line too long '%s':%u, ignored\n", filename, line_nr);
                        continue;
                }
-               add_to_rules(rules, key, filename, line_nr);
+               add_rule(rules, key, filename, filename_off, line_nr);
        }
        fclose(f);
 
-       /* 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'\n", goto_label);
-                       rule->goto_rule_off = find_label(&iter, goto_label);
-                       if (rule->goto_rule_off == 0) {
-                               err(rules->udev, "ignore goto to nonexistent label '%s' in '%s'\n",
-                                   goto_label, filename);
-                               rule->goto_rule_off = iter.current;
+       /* link GOTOs to LABEL rules in this file to be able to fast-forward */
+       for (i = first_token+1; i < rules->token_cur; i++) {
+               if (rules->tokens[i].type == TK_A_GOTO) {
+                       char *label = &rules->buf[rules->tokens[i].key.value_off];
+                       unsigned int j;
+
+                       for (j = i+1; j < rules->token_cur; j++) {
+                               if (rules->tokens[j].type != TK_RULE)
+                                       continue;
+                               if (rules->tokens[j].rule.label_off == 0)
+                                       continue;
+                               if (strcmp(label, &rules->buf[rules->tokens[j].rule.label_off]) != 0)
+                                       continue;
+                               rules->tokens[i].key.rule_goto = j;
                        }
+                       if (rules->tokens[i].key.rule_goto == 0)
+                               err(rules->udev, "GOTO '%s' has no matching label in: '%s'\n", label, filename);
                }
        }
        return 0;
@@ -1771,14 +1374,30 @@ struct udev_rules *udev_rules_new(struct udev *udev, int resolve_names)
        char filename[PATH_MAX];
        struct udev_list_node file_list;
        struct udev_list_entry *file_loop, *file_tmp;
+       unsigned int prev_rule;
+       struct token end_token;
+       unsigned int i;
 
-       rules = calloc(1, sizeof(struct udev_rules));
+       rules = malloc(sizeof(struct udev_rules));
        if (rules == NULL)
-               return rules;
+               return NULL;
+       memset(rules, 0x00, sizeof(struct udev_rules));
        rules->udev = udev;
        rules->resolve_names = resolve_names;
        udev_list_init(&file_list);
 
+       /* init token array and string buffer */
+       rules->tokens = malloc(PREALLOC_TOKEN * sizeof(struct token));
+       if (rules->tokens != NULL)
+               rules->token_max = PREALLOC_TOKEN;
+       rules->buf = malloc(PREALLOC_STRBUF);
+       if (rules->buf != NULL)
+               rules->buf_max = PREALLOC_STRBUF;
+       info(udev, "prealloc %zu bytes tokens (%u * %zu bytes), %zu bytes buffer\n",
+            rules->token_max * sizeof(struct token), rules->token_max, sizeof(struct token), rules->buf_max);
+       /* offset 0 in the string buffer is always empty */
+       add_string(rules, "");
+
        if (udev_get_rules_path(udev) != NULL) {
                /* custom rules location for testing */
                add_matching_files(udev, &file_list, udev_get_rules_path(udev), ".rules");
@@ -1843,6 +1462,42 @@ struct udev_rules *udev_rules_new(struct udev *udev, int resolve_names)
                        info(udev, "can not read '%s'\n", file_name);
                udev_list_entry_remove(file_loop);
        }
+
+       memset(&end_token, 0x00, sizeof(struct token));
+       end_token.type = TK_END;
+       add_token(rules, &end_token);
+
+       /* shrink allocate buffers */
+       if (rules->token_cur < rules->token_max) {
+               struct token *tokens;
+
+               tokens = realloc(rules->tokens, rules->token_cur * sizeof(struct token));
+               if (tokens != NULL || rules->token_cur == 0) {
+                       rules->tokens = tokens;
+                       rules->token_max = rules->token_cur;
+               }
+       }
+       if (rules->buf_cur < rules->buf_max) {
+               char *buf;
+
+               buf = realloc(rules->buf, rules->buf_cur);
+               if (buf != NULL || rules->buf_cur == 0) {
+                       rules->buf = buf;
+                       rules->buf_max = rules->buf_cur;
+               }
+       }
+       info(udev, "shrunk to %lu bytes tokens (%u * %zu bytes), %zu bytes buffer\n",
+            rules->token_max * sizeof(struct token), rules->token_max, sizeof(struct token), rules->buf_max);
+
+       /* link all TK_RULE tokens to be able to fast-forward to next TK_RULE */
+       prev_rule = 0;
+       for (i = 1; i < rules->token_cur; i++) {
+               if (rules->tokens[i].type == TK_RULE) {
+                       rules->tokens[prev_rule].rule.next_rule = i;
+                       prev_rule = i;
+               }
+       }
+       dump_rules(rules);
        return rules;
 }
 
@@ -1850,9 +1505,591 @@ void udev_rules_unref(struct udev_rules *rules)
 {
        if (rules == NULL)
                return;
-       if (rules->buf) {
-               free(rules->buf);
-               rules->buf = NULL;
-       }
+       free(rules->tokens);
+       free(rules->buf);
        free(rules);
 }
+
+static int match_key(struct udev_rules *rules, struct token *token, const char *val)
+{
+       const char *key_name = token_str[token->type];
+       char *key_value = &rules->buf[token->key.value_off];
+       char *pos;
+       int match = 0;
+
+       if (val == NULL)
+               val = "";
+
+       /* look for a matching string, parts are separated by '|' */
+       if (strchr(key_value, '|') != NULL) {
+               char value[UTIL_PATH_SIZE];
+
+               util_strlcpy(value, &rules->buf[token->key.value_off], sizeof(value));
+               key_value = value;
+               while (key_value != NULL) {
+                       pos = strchr(key_value, '|');
+                       if (pos != NULL) {
+                               pos[0] = '\0';
+                               pos = &pos[1];
+                       }
+                       dbg(rules->udev, "match %s '%s' <-> '%s'\n", key_name, key_value, val);
+                       match = (fnmatch(key_value, val, 0) == 0);
+                       if (match)
+                               break;
+                       key_value = pos;
+               }
+       } else {
+               match = (fnmatch(key_value, val, 0) == 0);
+       }
+
+       if (match && (token->key.op == KEY_OP_MATCH)) {
+               dbg(rules->udev, "%s is true (matching value)\n", key_name);
+               return 0;
+       }
+       if (!match && (token->key.op == KEY_OP_NOMATCH)) {
+               dbg(rules->udev, "%s is true (non-matching value)\n", key_name);
+               return 0;
+       }
+       dbg(rules->udev, "%s is not true\n", key_name);
+       return -1;
+}
+
+static int match_attr(struct udev_rules *rules, struct udev_device *dev, struct udev_event *event, struct token *cur)
+{
+       char attr[UTIL_PATH_SIZE];
+       const char *key_name = &rules->buf[cur->key.attr_off];
+       const char *key_value = &rules->buf[cur->key.value_off];
+       char value[UTIL_NAME_SIZE] = "";
+       size_t len;
+
+       util_strlcpy(attr, key_name, sizeof(attr));
+       util_resolve_subsys_kernel(event->udev, attr, value, sizeof(value), 1);
+       if (value[0] == '\0') {
+               const char *val;
+
+               val = udev_device_get_sysattr_value(dev, key_name);
+               if (val != NULL)
+                       util_strlcpy(value, val, sizeof(value));
+       }
+       if (value[0]=='\0')
+               return -1;
+
+       /* strip trailing whitespace of value, if not asked to match for it */
+       len = strlen(key_value);
+       if (len > 0 && !isspace(key_value[len-1])) {
+               len = strlen(value);
+               while (len > 0 && isspace(value[--len]))
+                       value[len] = '\0';
+               dbg(rules->udev, "removed trailing whitespace from '%s'\n", value);
+       }
+       return match_key(rules, cur, value);
+}
+
+enum escape_type {
+       ESCAPE_UNSET,
+       ESCAPE_NONE,
+       ESCAPE_REPLACE,
+};
+
+int udev_rules_apply_to_event(struct udev_rules *rules, struct udev_event *event)
+{
+       struct token *rule;
+       struct token *cur;
+
+       if (rules->tokens == NULL)
+               return -1;
+
+       /* loop through token list, match, run actions or forward to next rule */
+       cur = &rules->tokens[0];
+       while (cur != NULL && cur->type != TK_END) {
+               enum escape_type esc = ESCAPE_UNSET;
+               unsigned int idx;
+
+               dump_token(rules, cur);
+               switch (cur->type) {
+               case TK_RULE:
+                       /* current rule */
+                       rule = cur;
+                       esc = ESCAPE_UNSET;
+                       break;
+               case TK_M_WAITFOR:
+                       {
+                               char filename[UTIL_PATH_SIZE];
+                               int found;
+
+                               util_strlcpy(filename, &rules->buf[cur->key.value_off], sizeof(filename));
+                               udev_event_apply_format(event, filename, sizeof(filename));
+                               found = (wait_for_file(event->dev, filename, 10) == 0);
+                               if (!found && (cur->key.op != KEY_OP_NOMATCH))
+                                       goto nomatch;
+                               break;
+                       }
+               case TK_M_ACTION:
+                       if (match_key(rules, cur, udev_device_get_action(event->dev)) != 0)
+                               goto nomatch;
+                       break;
+               case TK_M_DEVPATH:
+                       if (match_key(rules, cur, udev_device_get_devpath(event->dev)) != 0)
+                               goto nomatch;
+                       break;
+               case TK_M_KERNEL:
+                       if (match_key(rules, cur, udev_device_get_sysname(event->dev)) != 0)
+                               goto nomatch;
+                       break;
+               case TK_M_DEVLINK:
+                       {
+                               size_t devlen = strlen(udev_get_dev_path(event->udev))+1;
+                               struct udev_list_entry *list_entry;
+                               int match = 0;
+
+                               udev_list_entry_foreach(list_entry, udev_device_get_devlinks_list_entry(event->dev)) {
+                                       const char *devlink;
+
+                                       devlink =  &udev_list_entry_get_name(list_entry)[devlen];
+                                       if (match_key(rules, cur, devlink) == 0) {
+                                               match = 1;
+                                               break;
+                                       }
+                               }
+                               if (!match)
+                                       goto nomatch;
+                               break;
+                       }
+               case TK_M_NAME:
+                       if (match_key(rules, cur, event->name) != 0)
+                               goto nomatch;
+                       break;
+               case TK_M_ENV:
+                       {
+                               struct udev_list_entry *list_entry;
+                               const char *key_name = &rules->buf[cur->key.attr_off];
+                               const char *value;
+
+                               list_entry = udev_device_get_properties_list_entry(event->dev);
+                               list_entry = udev_list_entry_get_by_name(list_entry, key_name);
+                               value = udev_list_entry_get_value(list_entry);
+                               if (value == NULL) {
+                                       dbg(event->udev, "ENV{%s} is not set, treat as empty\n", key_name);
+                                       value = "";
+                               }
+                               if (match_key(rules, cur, value))
+                                       goto nomatch;
+                               break;
+                       }
+               case TK_M_SUBSYSTEM:
+                       if (match_key(rules, cur, udev_device_get_subsystem(event->dev)) != 0)
+                               goto nomatch;
+                       break;
+               case TK_M_DRIVER:
+                       if (match_key(rules, cur, udev_device_get_driver(event->dev)) != 0)
+                               goto nomatch;
+                       break;
+               case TK_M_ATTR:
+                       if (match_attr(rules, event->dev, event, cur) != 0)
+                               goto nomatch;
+                       break;
+               case TK_M_KERNELS:
+               case TK_M_SUBSYSTEMS:
+               case TK_M_DRIVERS:
+               case TK_M_ATTRS:
+                       {
+                               struct token *next;
+
+                               /* get whole sequence of parent matches */
+                               next = cur;
+                               while (next->type < TK_PARENTS_MAX)
+                                       next++;
+
+                               /* loop over parents */
+                               event->dev_parent = event->dev;
+                               while (1) {
+                                       struct token *key;
+
+                                       dbg(event->udev, "parent: '%s'\n", udev_device_get_syspath(event->dev_parent));
+                                       /* loop over sequence of parent match keys */
+                                       for (key = cur; key < next; key++ ) {
+                                               dump_token(rules, key);
+                                               switch(key->type) {
+                                               case TK_M_KERNELS:
+                                                       if (match_key(rules, key, udev_device_get_sysname(event->dev_parent)) != 0)
+                                                               goto try_parent;
+                                                       break;
+                                               case TK_M_SUBSYSTEMS:
+                                                       if (match_key(rules, key, udev_device_get_subsystem(event->dev_parent)) != 0)
+                                                               goto try_parent;
+                                                       break;
+                                               case TK_M_DRIVERS:
+                                                       if (match_key(rules, key, udev_device_get_driver(event->dev_parent)) != 0)
+                                                               goto try_parent;
+                                                       break;
+                                               case TK_M_ATTRS:
+                                                       if (match_attr(rules, event->dev_parent, event, key) != 0)
+                                                               goto try_parent;
+                                                       break;
+                                               default:
+                                                       goto nomatch;
+                                               }
+                                               dbg(event->udev, "parent key matched\n");
+                                       }
+                                       dbg(event->udev, "all parent keys matched\n");
+                                       /* all keys matched */
+                                       break;
+
+                               try_parent:
+                                       event->dev_parent = udev_device_get_parent(event->dev_parent);
+                                       if (event->dev_parent == NULL)
+                                               goto nomatch;
+                               }
+                               /* move behind our sequence of parent match keys */
+                               cur = next;
+                               continue;
+                       }
+               case TK_M_TEST:
+                       {
+                               char filename[UTIL_PATH_SIZE];
+                               struct stat statbuf;
+                               int match;
+
+                               util_strlcpy(filename, &rules->buf[cur->key.value_off], sizeof(filename));
+                               udev_event_apply_format(event, filename, sizeof(filename));
+                               if (util_resolve_subsys_kernel(event->udev, NULL, filename, sizeof(filename), 0) != 0)
+                                       if (filename[0] != '/') {
+                                               char tmp[UTIL_PATH_SIZE];
+
+                                               util_strlcpy(tmp, udev_device_get_syspath(event->dev), sizeof(tmp));
+                                               util_strlcat(tmp, "/", sizeof(tmp));
+                                               util_strlcat(tmp, filename, sizeof(tmp));
+                                               util_strlcpy(filename, tmp, sizeof(filename));
+                                       }
+
+                               attr_subst_subdir(filename, sizeof(filename));
+
+                               match = (stat(filename, &statbuf) == 0);
+                               info(event->udev, "'%s' %s", filename, match ? "exists\n" : "does not exist\n");
+                               if (match && cur->key.mode > 0) {
+                                       match = ((statbuf.st_mode & cur->key.mode) > 0);
+                                       info(event->udev, "'%s' has mode=%#o and %s %#o\n", filename, statbuf.st_mode,
+                                            match ? "matches" : "does not match", cur->key.mode);
+                               }
+                               if (match && cur->key.op == KEY_OP_NOMATCH)
+                                       goto nomatch;
+                               if (!match && cur->key.op == KEY_OP_MATCH)
+                                       goto nomatch;
+                               break;
+                       }
+               case TK_M_PROGRAM:
+                       {
+                               char program[UTIL_PATH_SIZE];
+                               char **envp;
+                               char result[UTIL_PATH_SIZE];
+
+                               util_strlcpy(program, &rules->buf[cur->key.value_off], sizeof(program));
+                               udev_event_apply_format(event, program, sizeof(program));
+                               envp = udev_device_get_properties_envp(event->dev);
+                               if (util_run_program(event->udev, program, envp, result, sizeof(result), NULL) != 0) {
+                                       event->program_result[0] = '\0';
+                                       if (cur->key.op != KEY_OP_NOMATCH)
+                                               goto nomatch;
+                               } else {
+                                       int count;
+
+                                       util_remove_trailing_chars(result, '\n');
+                                       if (esc == ESCAPE_UNSET || esc == ESCAPE_REPLACE) {
+                                               count = util_replace_chars(result, ALLOWED_CHARS_INPUT);
+                                               if (count > 0)
+                                                       info(event->udev, "%i character(s) replaced\n" , count);
+                                       }
+                                       util_strlcpy(event->program_result, result, sizeof(event->program_result));
+                                       if (cur->key.op == KEY_OP_NOMATCH)
+                                               goto nomatch;
+                               }
+                               break;
+                       }
+               case TK_M_IMPORT_FILE:
+                       {
+                               char import[UTIL_PATH_SIZE];
+
+                               util_strlcpy(import, &rules->buf[cur->key.value_off], sizeof(import));
+                               udev_event_apply_format(event, import, sizeof(import));
+                               if (import_file_into_properties(event->dev, import) != 0)
+                                       if (cur->key.op != KEY_OP_NOMATCH)
+                                               goto nomatch;
+                               break;
+                       }
+               case TK_M_IMPORT_PROG:
+                       {
+                               char import[UTIL_PATH_SIZE];
+
+                               util_strlcpy(import, &rules->buf[cur->key.value_off], sizeof(import));
+                               udev_event_apply_format(event, import, sizeof(import));
+                               if (import_program_into_properties(event->dev, import) != 0)
+                                       if (cur->key.op != KEY_OP_NOMATCH)
+                                               goto nomatch;
+                               break;
+                       }
+               case TK_M_IMPORT_PARENT:
+                       {
+                               char import[UTIL_PATH_SIZE];
+
+                               util_strlcpy(import, &rules->buf[cur->key.value_off], sizeof(import));
+                               udev_event_apply_format(event, import, sizeof(import));
+                               if (import_parent_into_properties(event->dev, import) != 0)
+                                       if (cur->key.op != KEY_OP_NOMATCH)
+                                               goto nomatch;
+                               break;
+                       }
+               case TK_M_RESULT:
+                       if (match_key(rules, cur, event->program_result) != 0)
+                               goto nomatch;
+                       break;
+
+               case TK_A_IGNORE_DEVICE:
+                       event->ignore_device = 1;
+                       return 0;
+                       break;
+               case TK_A_STRING_ESCAPE_NONE:
+                       esc = ESCAPE_NONE;
+                       break;
+               case TK_A_STRING_ESCAPE_REPLACE:
+                       esc = ESCAPE_REPLACE;
+                       break;
+               case TK_A_NUM_FAKE_PART:
+                       if (strcmp(udev_device_get_subsystem(event->dev), "block") != 0)
+                               break;
+                       if (udev_device_get_sysnum(event->dev) != NULL)
+                               break;
+                       udev_device_set_num_fake_partitions(event->dev, cur->key.num_fake_part);
+                       break;
+               case TK_A_DEVLINK_PRIO:
+                       udev_device_set_devlink_priority(event->dev, cur->key.devlink_prio);
+                       break;
+               case TK_A_OWNER:
+                       {
+                               char owner[UTIL_NAME_SIZE];
+
+                               if (event->owner_final)
+                                       break;
+                               if (cur->key.op == KEY_OP_ASSIGN_FINAL)
+                                       event->owner_final = 1;
+                               util_strlcpy(owner,  &rules->buf[cur->key.value_off], sizeof(owner));
+                               udev_event_apply_format(event, owner, sizeof(owner));
+                               event->uid = util_lookup_user(event->udev, owner);
+                               break;
+                       }
+               case TK_A_GROUP:
+                       {
+                               char group[UTIL_NAME_SIZE];
+
+                               if (event->group_final)
+                                       break;
+                               if (cur->key.op == KEY_OP_ASSIGN_FINAL)
+                                       event->group_final = 1;
+                               util_strlcpy(group,  &rules->buf[cur->key.value_off], sizeof(group));
+                               udev_event_apply_format(event, group, sizeof(group));
+                               event->gid = util_lookup_group(event->udev, group);
+                               break;
+                       }
+               case TK_A_MODE:
+                       {
+                               char mode[UTIL_NAME_SIZE];
+                               char *endptr;
+
+                               if (event->mode_final)
+                                       break;
+                               if (cur->key.op == KEY_OP_ASSIGN_FINAL)
+                                       event->mode_final = 1;
+                               util_strlcpy(mode,  &rules->buf[cur->key.value_off], sizeof(mode));
+                               udev_event_apply_format(event, mode, sizeof(mode));
+                               event->mode = strtol(mode, &endptr, 8);
+                               if (endptr[0] != '\0') {
+                                       err(event->udev, "invalide mode '%s' set default mode 0660\n", mode);
+                                       event->mode = 0660;
+                               }
+                               break;
+                       }
+               case TK_A_OWNER_ID:
+                       if (event->owner_final)
+                               break;
+                       if (cur->key.op == KEY_OP_ASSIGN_FINAL)
+                               event->owner_final = 1;
+                       event->uid = cur->key.uid;
+                       break;
+               case TK_A_GROUP_ID:
+                       if (event->group_final)
+                               break;
+                       if (cur->key.op == KEY_OP_ASSIGN_FINAL)
+                               event->group_final = 1;
+                       event->gid = cur->key.gid;
+                       break;
+               case TK_A_MODE_ID:
+                       if (event->mode_final)
+                               break;
+                       if (cur->key.op == KEY_OP_ASSIGN_FINAL)
+                               event->mode_final = 1;
+                       event->mode = cur->key.mode;
+                       break;
+               case TK_A_ENV:
+                       {
+                               const char *name = &rules->buf[cur->key.attr_off];
+                               char *value = &rules->buf[cur->key.value_off];
+
+                               if (value[0] != '\0') {
+                                       char temp_value[UTIL_NAME_SIZE];
+                                       struct udev_list_entry *entry;
+
+                                       util_strlcpy(temp_value, value, sizeof(temp_value));
+                                       udev_event_apply_format(event, temp_value, sizeof(temp_value));
+                                       entry = udev_device_add_property(event->dev, name, temp_value);
+                                       /* store in db */
+                                       udev_list_entry_set_flag(entry, 1);
+                               } else {
+                                       udev_device_add_property(event->dev, name, NULL);
+                               }
+                               break;
+                       }
+               case TK_A_NAME:
+                       {
+                               const char *name  = &rules->buf[cur->key.value_off];
+                               int count;
+
+                               if (event->name_final)
+                                       break;
+                               if (cur->key.op == KEY_OP_ASSIGN_FINAL)
+                                       event->name_final = 1;
+                               if (name[0] == '\0') {
+                                       event->name[0] = '\0';
+                                       event->name_ignore = 1;
+                                       break;
+                               }
+                               event->name_ignore = 0;
+                               util_strlcpy(event->name, name, sizeof(event->name));
+                               udev_event_apply_format(event, event->name, sizeof(event->name));
+                               if (esc == ESCAPE_UNSET || esc == ESCAPE_REPLACE) {
+                                       count = util_replace_chars(event->name, ALLOWED_CHARS_FILE);
+                                       if (count > 0)
+                                               info(event->udev, "%i character(s) replaced\n", count);
+                               }
+                               break;
+                       }
+               case TK_A_DEVLINK:
+                       {
+                               char temp[UTIL_PATH_SIZE];
+                               char filename[UTIL_PATH_SIZE];
+                               char *pos, *next;
+                               int count = 0;
+
+                               if (event->devlink_final)
+                                       break;
+                               if (cur->key.op == KEY_OP_ASSIGN_FINAL)
+                                       event->devlink_final = 1;
+                               if (cur->key.op == KEY_OP_ASSIGN || cur->key.op == KEY_OP_ASSIGN_FINAL)
+                                       udev_device_cleanup_devlinks_list(event->dev);
+
+                               /* allow  multiple symlinks separated by spaces */
+                               util_strlcpy(temp, &rules->buf[cur->key.value_off], sizeof(temp));
+                               udev_event_apply_format(event, temp, sizeof(temp));
+                               if (esc == ESCAPE_UNSET)
+                                       count = util_replace_chars(temp, ALLOWED_CHARS_FILE " ");
+                               else if (esc == ESCAPE_REPLACE)
+                                       count = util_replace_chars(temp, ALLOWED_CHARS_FILE);
+                               if (count > 0)
+                                       info(event->udev, "%i character(s) replaced\n" , count);
+                               dbg(event->udev, "rule applied, added symlink(s) '%s'\n", temp);
+                               pos = temp;
+                               while (isspace(pos[0]))
+                                       pos++;
+                               next = strchr(pos, ' ');
+                               while (next) {
+                                       next[0] = '\0';
+                                       info(event->udev, "add symlink '%s'\n", pos);
+                                       util_strlcpy(filename, udev_get_dev_path(event->udev), sizeof(filename));
+                                       util_strlcat(filename, "/", sizeof(filename));
+                                       util_strlcat(filename, pos, sizeof(filename));
+                                       udev_device_add_devlink(event->dev, filename);
+                                       while (isspace(next[1]))
+                                               next++;
+                                       pos = &next[1];
+                                       next = strchr(pos, ' ');
+                               }
+                               if (pos[0] != '\0') {
+                                       info(event->udev, "add symlink '%s'\n", pos);
+                                       util_strlcpy(filename, udev_get_dev_path(event->udev), sizeof(filename));
+                                       util_strlcat(filename, "/", sizeof(filename));
+                                       util_strlcat(filename, pos, sizeof(filename));
+                                       udev_device_add_devlink(event->dev, filename);
+                               }
+                       }
+                       break;
+               case TK_A_EVENT_TIMEOUT:
+                       udev_device_set_event_timeout(event->dev, cur->key.event_timeout);
+                       break;
+               case TK_A_IGNORE_REMOVE:
+                       udev_device_set_ignore_remove(event->dev, 1);
+                       break;
+               case TK_A_ATTR:
+                       {
+                               const char *key_name = &rules->buf[cur->key.attr_off];
+                               char attr[UTIL_PATH_SIZE];
+                               char value[UTIL_NAME_SIZE];
+                               FILE *f;
+
+                               util_strlcpy(attr, key_name, sizeof(attr));
+                               if (util_resolve_subsys_kernel(event->udev, key_name, attr, sizeof(attr), 0) != 0) {
+                                       util_strlcpy(attr, udev_device_get_syspath(event->dev), sizeof(attr));
+                                       util_strlcat(attr, "/", sizeof(attr));
+                                       util_strlcat(attr, key_name, sizeof(attr));
+                               }
+
+                               attr_subst_subdir(attr, sizeof(attr));
+
+                               util_strlcpy(value, &rules->buf[cur->key.value_off], sizeof(value));
+                               udev_event_apply_format(event, value, sizeof(value));
+                               info(event->udev, "writing '%s' to sysfs file '%s'\n", value, attr);
+                               f = fopen(attr, "w");
+                               if (f != NULL) {
+                                       if (!event->test)
+                                               if (fprintf(f, "%s", value) <= 0)
+                                                       err(event->udev, "error writing ATTR{%s}: %m\n", attr);
+                                       fclose(f);
+                               } else {
+                                       err(event->udev, "error opening ATTR{%s} for writing: %m\n", attr);
+                               }
+                               break;
+                       }
+               case TK_A_RUN:
+                       {
+                               struct udev_list_entry *list_entry;
+
+                               if (cur->key.op == KEY_OP_ASSIGN || cur->key.op == KEY_OP_ASSIGN_FINAL)
+                                       udev_list_cleanup_entries(event->udev, &event->run_list);
+                               list_entry = udev_list_entry_add(event->udev, &event->run_list,
+                                                                &rules->buf[cur->key.value_off], NULL, 1, 0);
+                               if (cur->key.ignore_error)
+                                       udev_list_entry_set_flag(list_entry, 1);
+                               break;
+                       }
+               case TK_A_GOTO:
+                       cur = &rules->tokens[cur->key.rule_goto];
+                       continue;
+               case TK_A_LAST_RULE:
+                       break;
+
+               case TK_PARENTS_MAX:
+               case TK_END:
+               case TK_UNDEF:
+                       err(rules->udev, "wrong type %u\n", cur->type);
+                       goto nomatch;
+               }
+
+               cur++;
+               continue;
+       nomatch:
+               /* fast-forward to next rule */
+               idx = rule->rule.next_rule;
+               if (idx == 0)
+                       break;
+               dbg(rules->udev, "forward to rule: %u\n", idx);
+               cur = &rules->tokens[idx];
+       }
+       return 0;
+}
index 217e942..a00be37 100644 (file)
@@ -61,18 +61,19 @@ struct udev_event {
        struct udev_device *dev;
        struct udev_device *dev_parent;
        int devlink_final;
-       int owner_final;
-       int group_final;
-       int mode_final;
-       char tmp_node[UTIL_PATH_SIZE];
        char program_result[UTIL_PATH_SIZE];
-       int run_final;
-
        char name[UTIL_PATH_SIZE];
+       int name_final;
+       int name_ignore;
+       char tmp_node[UTIL_PATH_SIZE];
        mode_t mode;
-       char owner[UTIL_NAME_SIZE];
-       char group[UTIL_NAME_SIZE];
+       int mode_final;
+       uid_t uid;
+       int owner_final;
+       gid_t gid;
+       int group_final;
        struct udev_list_node run_list;
+       int run_final;
        int ignore_device;
        int test;
 
@@ -86,8 +87,7 @@ struct udev_event {
 struct udev_rules;
 extern struct udev_rules *udev_rules_new(struct udev *udev, int resolve_names);
 extern void udev_rules_unref(struct udev_rules *rules);
-extern int udev_rules_get_name(struct udev_rules *rules, struct udev_event *event);
-extern int udev_rules_get_run(struct udev_rules *rules, struct udev_event *event);
+extern int udev_rules_apply_to_event(struct udev_rules *rules, struct udev_event *event);
 
 /* udev-event.c */
 extern struct udev_event *udev_event_new(struct udev_device *dev);
@@ -100,7 +100,7 @@ extern int udev_event_apply_subsys_kernel(struct udev_event *event, const char *
 
 /* udev-node.c */
 extern int udev_node_mknod(struct udev_device *dev, const char *file, dev_t devnum, mode_t mode, uid_t uid, gid_t gid);
-extern int udev_node_add(struct udev_device *dev, mode_t mode, const char *owner, const char *group, int test);
+extern int udev_node_add(struct udev_device *dev, mode_t mode, uid_t uid, gid_t gid, int test);
 extern int udev_node_remove(struct udev_device *dev, int test);
 extern void udev_node_update_old_links(struct udev_device *dev, struct udev_device *dev_old, int test);
 
index 51e2fdc..c4e99f1 100644 (file)
             <varlistentry>
               <term><option>ATTR{<replaceable>filename</replaceable>}</option></term>
               <listitem>
-                <para>Match sysfs attribute values of the event device. Up to five
-                <option>ATTR</option> keys can be specified per rule. Trailing
+                <para>Match sysfs attribute values of the event device. Trailing
                 whitespace in the attribute values is ignored, if the specified match
                 value does not contain trailing whitespace itself. Depending on the type
                 of operator, this key is also used to set the value of a sysfs attribute.
               <term><option>ATTRS{<replaceable>filename</replaceable>}</option></term>
               <listitem>
                 <para>Search the devpath upwards for a device with matching sysfs attribute values.
-                Up to five <option>ATTRS</option> keys can be specified per rule, but all of them
+                If multiple <option>ATTRS</option> matches are specified, all of them
                 must match on the same device. Trailing whitespace in the attribute values is ignored,
                 if the specified match value does not contain trailing whitespace itself.</para>
               </listitem>
             <varlistentry>
               <term><option>ENV{<replaceable>key</replaceable>}</option></term>
               <listitem>
-                <para>Match against the value of an environment variable. Up to five <option>ENV</option>
-                keys can be specified per rule. Depending on the type of operator, this key is also used
-                to export a variable to the environment.</para>
+                <para>Match against a device property value.</para>
               </listitem>
             </varlistentry>
 
             <varlistentry>
               <term><option>PROGRAM</option></term>
               <listitem>
-                <para>Execute external program. The key is true, if the program returns
-                with exit code zero. The whole event environment is available to the
-                executed program. The program's output printed to stdout, is available in
-                the RESULT key.</para>
+                <para>Execute a program. The key is true, if the program returns
+                successfully. The device properties are made available to the
+                executed program in the environment. The program's output printed to
+                stdout, is available in the RESULT key.</para>
               </listitem>
             </varlistentry>
 
             <varlistentry>
               <term><option>ENV{<replaceable>key</replaceable>}</option></term>
               <listitem>
-                <para>Export a variable to the environment. Depending on the type of operator,
-                this key is also to match against an environment variable.</para>
+                <para>Set a device property value.</para>
               </listitem>
             </varlistentry>
 
             <varlistentry>
               <term><option>IMPORT{<replaceable>type</replaceable>}</option></term>
               <listitem>
-                <para>Import a set of variables into the event environment,
+                <para>Import a set of variables as device properties,
                 depending on <replaceable>type</replaceable>:</para>
                 <variablelist>
                   <varlistentry>
           <option>OWNER</option>, <option>GROUP</option>, <option>MODE</option>  and  <option>RUN</option>
           fields support simple printf-like string substitutions. The <option>RUN</option>
           format chars gets applied after all rules have been processed, right before the program
-          is executed. It allows the use of the complete environment set by earlier matching
+          is executed. It allows the use of device properties set by earlier matching
           rules. For all other fields, substitutions are applied while the individual rule is
           being processed. The available substitutions are:</para>
           <variablelist>
             <varlistentry>
               <term><option>$env{<replaceable>key</replaceable>}</option>, <option>%E{<replaceable>key</replaceable>}</option></term>
               <listitem>
-                <para>The value of an environment variable.</para>
+                <para>A device property value.</para>
               </listitem>
             </varlistentry>