[PATCH] udevd: Shrink struct token to 12 bytes

[PATCH] udevd: Shrink struct token to 12 bytes

[Alan Jenkins]

Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>

diff --git a/udev/udev-rules.c b/udev/udev-rules.c
index e07cd32..a0564e2 100644
--- a/udev/udev-rules.c
+++ b/udev/udev-rules.c
@@ -144,20 +144,20 @@ enum token_type {
 /* we try to pack stuff in a way that we take only 16 bytes per token */
 struct token {
 	union {
-		unsigned short type;		/* same as in rule and key */
+		unsigned char type;		/* same as in rule and key */
 		struct {
-			unsigned short type;
-			unsigned short flags;
-			unsigned int next_rule;
+			unsigned char type;
+			unsigned char flags;
+			unsigned short token_count;
 			unsigned int label_off;
 			unsigned short filename_off;
 			unsigned short filename_line;
 		} rule;
 		struct {
-			unsigned short type;
-			unsigned short flags;
-			unsigned short op;
-			unsigned short glob;
+			unsigned char type;
+			unsigned char flags;
+			unsigned char op;
+			unsigned char glob;
 			unsigned int value_off;
 			union {
 				unsigned int attr_off;
@@ -274,10 +274,11 @@ static void dump_token(struct udev_rules *rules, struct token *token)
 			const char *tk_ptr = (char *)token;
 			unsigned int off = tk_ptr - tks_ptr;
 
-			dbg(rules->udev, "* RULE %s:%u, off: %u(%u), next: %u, label: '%s', flags: 0x%02x\n",
+			dbg(rules->udev, "* RULE %s:%u, off: %u(%u), token_count: %u(%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.next_rule,
+			    token->rule.token_count,
+			    token->rule.token_count * (unsigned int) sizeof(struct token),
 			    &rules->buf[token->rule.label_off],
 			    token->rule.flags);
 			break;
@@ -1439,12 +1440,14 @@ static int add_rule(struct udev_rules *rules, char *line,
 		goto invalid;
 
 	/* add rule token */
+	rule_tmp.rule.rule.token_count = 1 + rule_tmp.token_cur;
 	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);
@@ -1689,15 +1692,6 @@ struct udev_rules *udev_rules_new(struct udev *udev, int resolve_names)
 	end_token.type = TK_END;
 	add_token(rules, &end_token);
 
-	/* 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;
-		}
-	}
-
 	/* shrink allocated token and string buffer */
 	if (rules->token_cur < rules->token_max) {
 		struct token *tokens;
@@ -2426,10 +2420,8 @@ int udev_rules_apply_to_event(struct udev_rules *rules, struct udev_event *event
 		continue;
 	nomatch:
 		/* fast-forward to next rule */
-		idx = rule->rule.next_rule;
-		if (idx = 0)
-			return 0;
-		dbg(rules->udev, "forward to rule: %u\n", idx);
-		cur = &rules->tokens[idx];
+		cur = rule + rule->rule.token_count;
+		dbg(rules->udev, "forward to rule: %u\n",
+		                 (unsigned int) (cur - rules->tokens));
 	}
 }

Re: [PATCH] udevd: Shrink struct token to 12 bytes

[Kay Sievers]

On Wed, Nov 5, 2008 at 20:55, Alan Jenkins <alan-jenkins@tuffmail.co.uk> wrote:
> Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
>
> diff --git a/udev/udev-rules.c b/udev/udev-rules.c

I liked the 16 byes, and now we can have only 255 keys per rule. :)

I get now with: "shrunk to 81012 bytes tokens (6751 * 12 bytes), 68009
bytes buffer". Maybe we should check the duplicates in the strings and
tail of strings while parsing, we can get rid of another 20kb, I
guess. :)

It boots here. Applied.

Thanks,
Kay

Re: [PATCH] udevd: Shrink struct token to 12 bytes

[Alan Jenkins]

Kay Sievers wrote:
> On Wed, Nov 5, 2008 at 20:55, Alan Jenkins <alan-jenkins@tuffmail.co.uk> wrote:
>   
>> Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
>>
>> diff --git a/udev/udev-rules.c b/udev/udev-rules.c
>>     
>
> I liked the 16 byes, and now we can have only 255 keys per rule. :)
>   

Hmm, that wasn't my intention.  rule.token_count is a short so it should 
be good for 64k.  You'd hit the line buffer limit first.

> I get now with: "shrunk to 81012 bytes tokens (6751 * 12 bytes), 68009
> bytes buffer". Maybe we should check the duplicates in the strings and
> tail of strings while parsing, we can get rid of another 20kb, I
> guess. :)
>   

Not sure about the O(n^2) scanning though.  I tried a trie, but it's 
100+ lines of dense C and needs a hundred K or so during parsing - it 
just seemed like overkill.  It did shave ~15K off my ~25K string 
buffer.  I can send it if you like.

Re: [PATCH] udevd: Shrink struct token to 12 bytes

[Kay Sievers]

On Thu, Nov 6, 2008 at 00:04, Alan Jenkins <alan-jenkins@tuffmail.co.uk> wrote:
> Kay Sievers wrote:
>>
>> On Wed, Nov 5, 2008 at 20:55, Alan Jenkins <alan-jenkins@tuffmail.co.uk>
>> wrote:
>>
>>>
>>> Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
>>>
>>> diff --git a/udev/udev-rules.c b/udev/udev-rules.c
>>>
>>
>> I liked the 16 byes, and now we can have only 255 keys per rule. :)
>>
>
> Hmm, that wasn't my intention.  rule.token_count is a short so it should be
> good for 64k.  You'd hit the line buffer limit first.

Ah, you are right, it's a short. Yeah, even with 255 we would hit the
line buffer probably. :)

>> I get now with: "shrunk to 81012 bytes tokens (6751 * 12 bytes), 68009
>> bytes buffer". Maybe we should check the duplicates in the strings and
>> tail of strings while parsing, we can get rid of another 20kb, I
>> guess. :)
>>
>
> Not sure about the O(n^2) scanning though.  I tried a trie, but it's 100+
> lines of dense C and needs a hundred K or so during parsing - it just seemed
> like overkill.  It did shave ~15K off my ~25K string buffer.  I can send it
> if you like.

Hmm, maybe it's not worth, and may cost too much at bootup. But if you
have it working, I would like to see how much it is here. But don't
bother if it's too much effort, we will probably not apply that.

Thanks,
Kay

Re: [PATCH] udevd: Shrink struct token to 12 bytes

[Alan Jenkins]

Kay Sievers wrote:
> On Thu, Nov 6, 2008 at 00:04, Alan Jenkins <alan-jenkins@tuffmail.co.uk> wrote:
>   
>> Kay Sievers wrote:
>>     
>>> On Wed, Nov 5, 2008 at 20:55, Alan Jenkins <alan-jenkins@tuffmail.co.uk>
>>> wrote:
>>>
>>>       
>>>> Signed-off-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
>>>>
>>>> diff --git a/udev/udev-rules.c b/udev/udev-rules.c
>>>>
>>>>         
>>> I liked the 16 byes, and now we can have only 255 keys per rule. :)
>>>
>>>       
>> Hmm, that wasn't my intention.  rule.token_count is a short so it should be
>> good for 64k.  You'd hit the line buffer limit first.
>>     
>
> Ah, you are right, it's a short. Yeah, even with 255 we would hit the
> line buffer probably. :)
>
>   
>>> I get now with: "shrunk to 81012 bytes tokens (6751 * 12 bytes), 68009
>>> bytes buffer". Maybe we should check the duplicates in the strings and
>>> tail of strings while parsing, we can get rid of another 20kb, I
>>> guess. :)
>>>
>>>       
>> Not sure about the O(n^2) scanning though.  I tried a trie, but it's 100+
>> lines of dense C and needs a hundred K or so during parsing - it just seemed
>> like overkill.  It did shave ~15K off my ~25K string buffer.  I can send it
>> if you like.
>>     
>
> Hmm, maybe it's not worth, and may cost too much at bootup. But if you
> have it working, I would like to see how much it is here. But don't
> bother if it's too much effort, we will probably not apply that.
>   
I had another go and got the index down to ~25K for my installation.  So 
I guess it's worth having a look at.