X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?a=blobdiff_plain;f=udev%2Fudev-rules.c;h=dc4009f74aefeb29a2bfa1bb4896c5c130ba720a;hb=1c8af93aca64033f00d493bad7d505757c1ab414;hp=4713352826d524daaff101ee72dcd31d85af19fa;hpb=e230e966f44c0ebb4954cbd30740384e14c1ca0f;p=elogind.git diff --git a/udev/udev-rules.c b/udev/udev-rules.c index 471335282..dc4009f74 100644 --- a/udev/udev-rules.c +++ b/udev/udev-rules.c @@ -16,6 +16,7 @@ */ #include +#include #include #include #include @@ -30,6 +31,7 @@ #define PREALLOC_TOKEN 2048 #define PREALLOC_STRBUF 32 * 1024 +#define PREALLOC_TRIE 256 struct uid_gid { unsigned int name_off; @@ -39,7 +41,16 @@ struct uid_gid { }; }; -/* KEY=="", KEY!="", KEY+="", KEY="", KEY:="" */ +#define TRIE_CHILD_MAX 10 + +struct trie_node { + unsigned int value_off; + size_t value_len; + unsigned char child_cur; + unsigned char child_key[TRIE_CHILD_MAX]; + unsigned short child[TRIE_CHILD_MAX]; +}; + struct udev_rules { struct udev *udev; int resolve_names; @@ -55,6 +66,12 @@ struct udev_rules { size_t buf_max; unsigned int buf_count; + /* key strings are indexed to avoid wasting space with duplicates */ + struct trie_node *trie; + unsigned short trie_cur; + unsigned short trie_max; + unsigned short *trie_root; + /* during rule parsing, we cache uid/gid lookup results */ struct uid_gid *uids; unsigned int uids_cur; @@ -64,6 +81,7 @@ struct udev_rules { unsigned int gids_max; }; +/* KEY=="", KEY!="", KEY+="", KEY="", KEY:="" */ enum operation_type { OP_UNSET, @@ -184,80 +202,95 @@ struct rule_tmp { }; #ifdef DEBUG -static const char *operation_str[] = { - [OP_UNSET] = "UNSET", - [OP_MATCH] = "match", - [OP_NOMATCH] = "nomatch", - [OP_MATCH_MAX] = "MATCH_MAX", - - [OP_ADD] = "add", - [OP_ASSIGN] = "assign", - [OP_ASSIGN_FINAL] = "assign-final", -}; +static const char *operation_str(enum operation_type type) +{ + static const char *operation_strs[] = { + [OP_UNSET] = "UNSET", + [OP_MATCH] = "match", + [OP_NOMATCH] = "nomatch", + [OP_MATCH_MAX] = "MATCH_MAX", + + [OP_ADD] = "add", + [OP_ASSIGN] = "assign", + [OP_ASSIGN_FINAL] = "assign-final", +} ; + + return operation_strs[type]; +} -static const char *string_glob_str[] = { - [GL_UNSET] = "UNSET", - [GL_PLAIN] = "plain", - [GL_GLOB] = "glob", - [GL_SPLIT] = "split", - [GL_SPLIT_GLOB] = "split-glob", - [GL_SOMETHING] = "split-glob", - [GL_FORMAT] = "format", -}; +static const char *string_glob_str(enum string_glob_type type) +{ + static const char *string_glob_strs[] = { + [GL_UNSET] = "UNSET", + [GL_PLAIN] = "plain", + [GL_GLOB] = "glob", + [GL_SPLIT] = "split", + [GL_SPLIT_GLOB] = "split-glob", + [GL_SOMETHING] = "split-glob", + [GL_FORMAT] = "format", + }; -static const char *token_str[] = { - [TK_UNSET] = "UNSET", - [TK_RULE] = "RULE", - - [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_WAITFOR] = "M WAITFOR", - [TK_M_ATTR] = "M ATTR", - - [TK_M_PARENTS_MIN] = "M PARENTS_MIN", - [TK_M_KERNELS] = "M KERNELS", - [TK_M_SUBSYSTEMS] = "M SUBSYSTEMS", - [TK_M_DRIVERS] = "M DRIVERS", - [TK_M_ATTRS] = "M ATTRS", - [TK_M_PARENTS_MAX] = "M 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_M_MAX] = "M MAX", - - [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", -}; + return string_glob_strs[type]; +} + +static const char *token_str(enum token_type type) +{ + static const char *token_strs[] = { + [TK_UNSET] = "UNSET", + [TK_RULE] = "RULE", + + [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_WAITFOR] = "M WAITFOR", + [TK_M_ATTR] = "M ATTR", + + [TK_M_PARENTS_MIN] = "M PARENTS_MIN", + [TK_M_KERNELS] = "M KERNELS", + [TK_M_SUBSYSTEMS] = "M SUBSYSTEMS", + [TK_M_DRIVERS] = "M DRIVERS", + [TK_M_ATTRS] = "M ATTRS", + [TK_M_PARENTS_MAX] = "M 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_M_MAX] = "M MAX", + + [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", + }; + + return token_strs[type]; +} static void dump_token(struct udev_rules *rules, struct token *token) { @@ -272,13 +305,11 @@ static void dump_token(struct udev_rules *rules, struct token *token) { const char *tks_ptr = (char *)rules->tokens; const char *tk_ptr = (char *)token; - unsigned int off = tk_ptr - tks_ptr; + unsigned int idx = (tk_ptr - tks_ptr) / sizeof(struct token); - dbg(rules->udev, "* RULE %s:%u, off: %u(%u), token_count: %u(%u), label: '%s', flags: 0x%02x\n", + dbg(rules->udev, "* RULE %s:%u, token: %u, count: %u, label: '%s', flags: 0x%02x\n", &rules->buf[token->rule.filename_off], token->rule.filename_line, - off / (unsigned int) sizeof(struct token), off, - token->rule.token_count, - token->rule.token_count * (unsigned int) sizeof(struct token), + idx, token->rule.token_count, &rules->buf[token->rule.label_off], token->rule.flags); break; @@ -306,7 +337,7 @@ static void dump_token(struct udev_rules *rules, struct token *token) case TK_A_MODE: case TK_A_RUN: dbg(rules->udev, "%s %s '%s'(%s)\n", - token_str[type], operation_str[op], value, string_glob_str[glob]); + token_str(type), operation_str(op), value, string_glob_str(glob)); break; case TK_M_ATTR: case TK_M_ATTRS: @@ -314,42 +345,42 @@ static void dump_token(struct udev_rules *rules, struct token *token) case TK_A_ATTR: case TK_A_ENV: dbg(rules->udev, "%s %s '%s' '%s'(%s)\n", - token_str[type], operation_str[op], attr, value, string_glob_str[glob]); + token_str(type), operation_str(op), attr, value, string_glob_str(glob)); 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]); + dbg(rules->udev, "%s\n", token_str(type)); break; case TK_M_TEST: dbg(rules->udev, "%s %s '%s'(%s) %#o\n", - token_str[type], operation_str[op], value, string_glob_str[glob], token->key.mode); + token_str(type), operation_str(op), value, string_glob_str(glob), token->key.mode); break; case TK_A_NUM_FAKE_PART: - dbg(rules->udev, "%s %u\n", token_str[type], token->key.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); + 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); + 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); + 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); + 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); + 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); + 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]); + dbg(rules->udev, "* %s\n", token_str(type)); break; case TK_M_PARENTS_MIN: case TK_M_PARENTS_MAX: @@ -373,31 +404,25 @@ static void dump_rules(struct udev_rules *rules) dump_token(rules, &rules->tokens[i]); } #else -static const char **operation_str; -static const char **token_str; +static inline const char *operation_str(enum operation_type type) { return NULL; } +static inline const char *token_str(enum token_type type) { return NULL; } 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) @@ -407,15 +432,128 @@ 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 unsigned char trie_child_slot(struct trie_node *node, char key) { + unsigned char child_slot; + + for (child_slot = 0; child_slot < node->child_cur; child_slot++) { + if (node->child_key[child_slot] == key) + break; + } + + return child_slot; +} + +static int add_string(struct udev_rules *rules, const char *str) +{ + struct trie_node *child; + unsigned short child_off; + unsigned short node_off; + unsigned char key; + size_t len; + unsigned int depth; + unsigned int off; + + len = strlen(str); + /* offset 0 is always '\0' */ + if (len == 0) + return 0; + + /* strings with spaces are probably commands e.g. modprobe, + with unique arguments. */ + if (strchr(str, ' ') != NULL) + return add_new_string(rules, str, len + 1); + + /* descend root - start from last character of str */ + key = str[len - 1]; + node_off = rules->trie_root[key]; + depth = 0; + + /* descend suffix trie */ + if (node_off != 0) { + while (1) { + struct trie_node *node = &rules->trie[node_off]; + unsigned char child_slot; + + depth++; + 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_slot = trie_child_slot(node, key); + + if(child_slot == node->child_cur) + break; + + node_off = node->child[child_slot]; + } + } + + /* string not found, add it */ + off = add_new_string(rules, str, len + 1); + + /* grow trie storage if needed */ + if (rules->trie_cur >= rules->trie_max) { + struct trie_node *trie; + unsigned short add; + + /* double the buffer size */ + add = rules->trie_max; + if (add < 8) + add = 8; + + trie = realloc(rules->trie, (rules->trie_max + add) * sizeof(struct trie_node)); + if (trie == NULL) + return -1; + dbg(rules->udev, "extend string index nodes from %u to %u\n", rules->trie_max, rules->trie_max + add); + rules->trie = trie; + rules->trie_max += add; + } + + /* insert new child node */ + child_off = rules->trie_cur; + if (depth == 0) { + rules->trie_root[key] = child_off; + } else { + struct trie_node *parent = &rules->trie[node_off]; + unsigned char child_slot = parent->child_cur; + + /* no space in parent, we can't index this string, nevermind */ + if (child_slot == TRIE_CHILD_MAX) + return off; + + parent->child[child_slot] = child_off; + parent->child_key[child_slot] = key; + parent->child_cur = child_slot + 1; + } + + /* allocate and construct the child node */ + rules->trie_cur++; + child = &rules->trie[child_off]; + memset(child, 0x00, sizeof(struct trie_node)); + child->value_off = off; + child->value_len = len; + + 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; @@ -828,7 +966,7 @@ static int get_key(struct udev *udev, char **line, char **key, enum operation_ty return -1; temp[0] = '\0'; temp++; - dbg(udev, "%s '%s'-'%s'\n", operation_str[*op], *key, *value); + dbg(udev, "%s '%s'-'%s'\n", operation_str(*op), *key, *value); /* move line to next key */ *line = temp; @@ -1594,9 +1732,16 @@ struct udev_rules *udev_rules_new(struct udev *udev, int resolve_names) if (rules->buf == NULL) return NULL; rules->buf_max = PREALLOC_STRBUF; + rules->trie = malloc(PREALLOC_TRIE * sizeof(struct trie_node)); + if (rules->trie == NULL) + return NULL; + rules->trie_max = PREALLOC_TRIE; + rules->trie_root = calloc(UCHAR_MAX + 1, sizeof(unsigned short)); /* offset 0 is always '\0' */ rules->buf[0] = '\0'; rules->buf_cur = 1; + /* offset 0 is reserved for the null trie node */ + rules->trie_cur = 1; 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); @@ -1712,6 +1857,16 @@ struct udev_rules *udev_rules_new(struct udev *udev, int resolve_names) } info(udev, "shrunk to %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, "used %zu bytes of string index nodes (%hu * %zu bytes)\n", + rules->trie_cur * sizeof(struct trie_node), rules->trie_cur, sizeof(struct trie_node)); + + /* cleanup trie */ + free(rules->trie); + rules->trie = NULL; + rules->trie_cur = 0; + rules->trie_max = 0; + free(rules->trie_root); + rules->trie_root = NULL; /* cleanup uid/gid cache */ free(rules->uids); @@ -1733,6 +1888,8 @@ void udev_rules_unref(struct udev_rules *rules) return; free(rules->tokens); free(rules->buf); + free(rules->trie); + free(rules->trie_root); free(rules->uids); free(rules->gids); free(rules); @@ -1791,7 +1948,7 @@ static int match_key(struct udev_rules *rules, struct token *token, const char * pos[0] = '\0'; pos = &pos[1]; } - dbg(rules->udev, "match %s '%s' <-> '%s'\n", token_str[token->type], key_value, val); + dbg(rules->udev, "match %s '%s' <-> '%s'\n", token_str(token->type), key_value, val); match = (fnmatch(key_value, val, 0) == 0); if (match) break; @@ -1808,14 +1965,14 @@ static int match_key(struct udev_rules *rules, struct token *token, const char * } if (match && (token->key.op == OP_MATCH)) { - dbg(rules->udev, "%s is true (matching value)\n", token_str[token->type]); + dbg(rules->udev, "%s is true (matching value)\n", token_str(token->type)); return 0; } if (!match && (token->key.op == OP_NOMATCH)) { - dbg(rules->udev, "%s is true (non-matching value)\n", token_str[token->type]); + dbg(rules->udev, "%s is true (non-matching value)\n", token_str(token->type)); return 0; } - dbg(rules->udev, "%s is not true\n", token_str[token->type]); + dbg(rules->udev, "%s is not true\n", token_str(token->type)); return -1; }