X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=elogind.git;a=blobdiff_plain;f=udev%2Fudev-rules.c;h=9861a88a52b3a6a7f5fbe91bb4b4d073d6cc5253;hp=810a863a18914be57191f78e80ad3e7b0e5bd32d;hb=0c057e9c75f8acad2cd89b8ad8b9ec09f2c615af;hpb=5d6a1fa6e92b9760c243725ea543ade85b8b2b79 diff --git a/udev/udev-rules.c b/udev/udev-rules.c index 810a863a1..9861a88a5 100644 --- a/udev/udev-rules.c +++ b/udev/udev-rules.c @@ -1,5 +1,6 @@ /* * Copyright (C) 2008 Kay Sievers + * Copyright (C) 2008 Alan Jenkins * * 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 @@ -16,6 +17,7 @@ */ #include +#include #include #include #include @@ -30,6 +32,7 @@ #define PREALLOC_TOKEN 2048 #define PREALLOC_STRBUF 32 * 1024 +#define PREALLOC_TRIE 256 struct uid_gid { unsigned int name_off; @@ -39,7 +42,18 @@ struct uid_gid { }; }; -/* KEY=="", KEY!="", KEY+="", KEY="", KEY:="" */ +struct trie_node { + /* this node's first child */ + unsigned int child_idx; + /* the next child of our parent node's child list */ + unsigned int next_child_idx; + /* this node's last child (shortcut for append) */ + unsigned int last_child_idx; + unsigned int value_off; + unsigned short value_len; + unsigned char key; +}; + struct udev_rules { struct udev *udev; int resolve_names; @@ -55,7 +69,12 @@ struct udev_rules { size_t buf_max; unsigned int buf_count; - /* during rule parsing, we cache uid/gid lookup results */ + /* during rule parsing, strings are indexed to find duplicates */ + struct trie_node *trie_nodes; + unsigned int trie_nodes_cur; + unsigned int trie_nodes_max; + + /* during rule parsing, uid/gid lookup results are cached */ struct uid_gid *uids; unsigned int uids_cur; unsigned int uids_max; @@ -64,6 +83,7 @@ struct udev_rules { unsigned int gids_max; }; +/* KEY=="", KEY!="", KEY+="", KEY="", KEY:="" */ enum operation_type { OP_UNSET, @@ -392,25 +412,19 @@ static inline void dump_token(struct udev_rules *rules, struct token *token) {} static inline void dump_rules(struct udev_rules *rules) {} #endif /* DEBUG */ -/* we could lookup and return existing strings, or tails of strings */ -static int add_string(struct udev_rules *rules, const char *str) +static int add_new_string(struct udev_rules *rules, const char *str, size_t bytes) { - size_t len = strlen(str)+1; int off; - /* offset 0 is always '\0' */ - if (str[0] == '\0') - return 0; - /* grow buffer if needed */ - if (rules->buf_cur + len+1 >= rules->buf_max) { + if (rules->buf_cur + bytes+1 >= rules->buf_max) { char *buf; unsigned int add; /* double the buffer size */ add = rules->buf_max; - if (add < len * 8) - add = len * 8; + if (add < bytes * 8) + add = bytes * 8; buf = realloc(rules->buf, rules->buf_max + add); if (buf == NULL) @@ -420,15 +434,101 @@ static int add_string(struct udev_rules *rules, const char *str) rules->buf_max += add; } off = rules->buf_cur; - memcpy(&rules->buf[rules->buf_cur], str, len); - rules->buf_cur += len; + memcpy(&rules->buf[rules->buf_cur], str, bytes); + rules->buf_cur += bytes; rules->buf_count++; return off; } -static int add_token(struct udev_rules *rules, struct token *token) +static int add_string(struct udev_rules *rules, const char *str) { + unsigned int node_idx; + struct trie_node *new_node; + unsigned int new_node_idx; + unsigned char key; + unsigned short len; + unsigned int depth; + unsigned int off; + struct trie_node *parent; + + /* walk trie, start from last character of str to find matching tails */ + len = strlen(str); + key = str[len-1]; + node_idx = 0; + for (depth = 0; depth <= len; depth++) { + struct trie_node *node; + unsigned int child_idx; + + node = &rules->trie_nodes[node_idx]; + off = node->value_off + node->value_len - len; + + /* match against current node */ + if (depth == len || (node->value_len >= len && memcmp(&rules->buf[off], str, len) == 0)) + return off; + + /* lookup child node */ + key = str[len - 1 - depth]; + child_idx = node->child_idx; + while (child_idx > 0) { + struct trie_node *child; + + child = &rules->trie_nodes[child_idx]; + if (child->key == key) + break; + child_idx = child->next_child_idx; + } + if (child_idx == 0) + break; + node_idx = child_idx; + } + + /* string not found, add it */ + off = add_new_string(rules, str, len + 1); + /* grow trie nodes if needed */ + if (rules->trie_nodes_cur >= rules->trie_nodes_max) { + struct trie_node *nodes; + unsigned int add; + + /* double the buffer size */ + add = rules->trie_nodes_max; + if (add < 8) + add = 8; + + nodes = realloc(rules->trie_nodes, (rules->trie_nodes_max + add) * sizeof(struct trie_node)); + if (nodes == NULL) + return -1; + dbg(rules->udev, "extend trie nodes from %u to %u\n", + rules->trie_nodes_max, rules->trie_nodes_max + add); + rules->trie_nodes = nodes; + rules->trie_nodes_max += add; + } + + /* get a new node */ + new_node_idx = rules->trie_nodes_cur; + rules->trie_nodes_cur++; + new_node = &rules->trie_nodes[new_node_idx]; + memset(new_node, 0x00, sizeof(struct trie_node)); + new_node->value_off = off; + new_node->value_len = len; + new_node->key = key; + + /* join the parent's child list */ + parent = &rules->trie_nodes[node_idx]; + if (parent->child_idx == 0) { + parent->child_idx = new_node_idx; + } else { + struct trie_node *last_child; + + last_child = &rules->trie_nodes[parent->last_child_idx]; + last_child->next_child_idx = new_node_idx; + } + parent->last_child_idx = new_node_idx; + return off; +} + +static int add_token(struct udev_rules *rules, struct token *token) +{ /* grow buffer if needed */ if (rules->token_cur+1 >= rules->token_max) { struct token *tokens; @@ -1035,6 +1135,7 @@ static int add_rule(struct udev_rules *rules, char *line, char *linepos; char *attr; int physdev = 0; + int waitfor = 0; struct rule_tmp rule_tmp; memset(&rule_tmp, 0x00, sizeof(struct rule_tmp)); @@ -1295,6 +1396,7 @@ static int add_rule(struct udev_rules *rules, char *line, if (strcasecmp(key, "WAIT_FOR") == 0 || strcasecmp(key, "WAIT_FOR_SYSFS") == 0) { rule_add_key(&rule_tmp, TK_M_WAITFOR, 0, value, NULL); valid = 1; + waitfor = 1; continue; } @@ -1444,11 +1546,11 @@ static int add_rule(struct udev_rules *rules, char *line, err(rules->udev, "unknown key '%s' in %s:%u\n", key, filename, lineno); } - if (physdev) - err(rules->udev, "PHYSDEV* values are deprecated and not available on recent kernels, \n" - "please fix it in %s:%u", filename, lineno); + if (physdev && !waitfor) + err(rules->udev, "PHYSDEV* values are deprecated and not available on recent kernels, " + "please fix it in %s:%u\n", filename, lineno); - /* skip line if not any valid key was found */ + /* skip line if no valid key was found */ if (!valid) goto invalid; @@ -1603,6 +1705,7 @@ struct udev_rules *udev_rules_new(struct udev *udev, int resolve_names) if (rules->tokens == NULL) return NULL; rules->token_max = PREALLOC_TOKEN; + rules->buf = malloc(PREALLOC_STRBUF); if (rules->buf == NULL) return NULL; @@ -1613,6 +1716,14 @@ struct udev_rules *udev_rules_new(struct udev *udev, int resolve_names) dbg(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); + rules->trie_nodes = malloc(PREALLOC_TRIE * sizeof(struct trie_node)); + if (rules->trie_nodes == NULL) + return NULL; + rules->trie_nodes_max = PREALLOC_TRIE; + /* offset 0 is the trie root, with an empty string */ + memset(rules->trie_nodes, 0x00, sizeof(struct trie_node)); + rules->trie_nodes_cur = 1; + if (udev_get_rules_path(udev) != NULL) { /* custom rules location for testing */ add_matching_files(udev, &file_list, udev_get_rules_path(udev), ".rules"); @@ -1723,8 +1834,17 @@ struct udev_rules *udev_rules_new(struct udev *udev, int resolve_names) rules->buf_max = rules->buf_cur; } } - info(udev, "shrunk to %zu bytes tokens (%u * %zu bytes), %zu bytes buffer\n", + info(udev, "rules use %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); + info(udev, "temporary index used %zu bytes (%u * %zu bytes)\n", + rules->trie_nodes_cur * sizeof(struct trie_node), + rules->trie_nodes_cur, sizeof(struct trie_node)); + + /* cleanup trie */ + free(rules->trie_nodes); + rules->trie_nodes = NULL; + rules->trie_nodes_cur = 0; + rules->trie_nodes_max = 0; /* cleanup uid/gid cache */ free(rules->uids); @@ -1746,6 +1866,7 @@ void udev_rules_unref(struct udev_rules *rules) return; free(rules->tokens); free(rules->buf); + free(rules->trie_nodes); free(rules->uids); free(rules->gids); free(rules); @@ -1898,7 +2019,7 @@ int udev_rules_apply_to_event(struct udev_rules *rules, struct udev_event *event rule = cur; /* possibly skip rules which want to set NAME, SYMLINK, OWNER, GROUP, MODE */ if (!can_set_name && rule->rule.flags) - ;//goto nomatch; + goto nomatch; esc = ESCAPE_UNSET; break; case TK_M_ACTION: