tree.c 12.7 KB
Newer Older
1
2
3
4
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wconversion"
#pragma GCC diagnostic ignored "-Wsign-conversion"

Sheppy's avatar
Sheppy committed
5
6
7
#include <linux/slab.h>
#include <linux/string.h>

8
9
#pragma GCC diagnostic pop

Sheppy's avatar
Sheppy committed
10
#include "tree.h"
Sheppy's avatar
Sheppy committed
11

12
13
14
15
16
17
#define CHILD_CAP 4
#define CHILD_GROWTH 2

#define RULES_CAP 4
#define RULES_GROWTH 2

Sheppy's avatar
Sheppy committed
18

19
20
21
/**
 * rules - currently effective ruleset
 */
22
static struct tree_node __rcu *rules;
Lukas Braun's avatar
Lukas Braun committed
23
static DEFINE_MUTEX(mutex);
24
25
26
27
28
29
30
31
32
33
34
35


/************************************************************************
 * tree destruction
 ************************************************************************/

/**
 * slsm_free_subtree - frees a subtree and all associated resources
 *
 * TODO: limit recursion or rewrite without recursion
 */
static void slsm_free_subtree(struct tree_node *t) {
36
	size_t i;
37
38
	for (i = 0; i < t->children_used; i++) {
		slsm_free_subtree(&t->children[i]);
Sheppy's avatar
Sheppy committed
39
	}
40
41
42
	for (i = 0; i < t->rules_used; i++) {
		kfree(t->rules[i].app);
	}
43
44
45
46
47
48
49
50
51

	kfree(t->buf);
	kfree(t->children);
	kfree(t->rules);
}



/************************************************************************
52
 * tree access
53
54
 ************************************************************************/

55
56
57
58
59

static const char *next_path_component(const char **path, size_t *length) {
	const char *start = *path;
	const char *next = strchr(*path, '/');
	if (next) {
Simon Ruderich's avatar
Simon Ruderich committed
60
		*length = (size_t)(next - start);
61
62
63
64
65
66
67
68
69
		next++; /* skip '/' */
	} else {
		*length = strlen(start);
	}
	*path = next;

	return start;
}

70
71
/**
 * @t: node in which to search for children
72
73
 * @path: search key (not null terminated)
 * @length: length of search string
74
75
76
 *
 * Returns: NULL or pointer to child with name @path
 */
Lukas Braun's avatar
Lukas Braun committed
77
static struct tree_node *slsm_find_matching_child(const struct tree_node *t,
78
		const char *path, size_t length) {
79
	size_t i;
80
	for (i = 0; i < t->children_used; i++) {
81
82
		if (!strncmp(t->children[i].name, path, length)
				&& t->children[i].name[length] == '\0')
83
84
85
86
87
88
89
			return &t->children[i];
	}

	return NULL;
}


90
91
92
93
/**
 * slsm_last_match - find the last match in a ruleset
 * @t: node in which we search
 * @app: application we are looking for
94
 * @perms: where to write the new perms if one is found;
95
 */
Lukas Braun's avatar
Lukas Braun committed
96
97
static void slsm_last_match(const struct tree_node *t, const char *app,
		struct slsm_perms *perms, unsigned at_path_end) {
98
	size_t i;
99

100
	if (!t->rules || t->rules_used == 0)
101
		return;
102

103
104
	i = t->rules_used - 1;
	do {
105
		if (!t->rules[i].app || !strcmp(t->rules[i].app, app)) {
Lukas Braun's avatar
Lukas Braun committed
106
107
108
109
110
			struct slsm_perms tmp = t->rules[i].perms;
			if (!(tmp.flags & SLSM_FLAG_EXACT) || at_path_end) {
				*perms = tmp;
				return;
			}
111
		}
112
	} while (i-- > 0);
113
114
115
}


Lukas Braun's avatar
Lukas Braun committed
116
/**
117
 * slsm_query_perms - query the applying perms
Lukas Braun's avatar
Lukas Braun committed
118
119
120
 * @path: the path in question (object)
 * @app: the application (subject)
 *
121
 * Returns: the perms for @app at @path or SLSM_UNRESTRICTED
Lukas Braun's avatar
Lukas Braun committed
122
 */
123
struct slsm_perms slsm_query_perms(const char *path, const char *app) {
124
125
	const char *component;
	struct tree_node *t;
126
	struct slsm_perms ret = { .mode = SLSM_MODE_RWX, .flags = 0 };
127
128

	if (!rules)
129
		return ret;
130

131
132
	BUG_ON(!path || *path != '/');
	BUG_ON(!app);
133

134
	path++; // skip leading "/"
135

136
137
	rcu_read_lock();
	t = rcu_dereference(rules);
138
139

	do {
140
141
		size_t length;

Lukas Braun's avatar
Lukas Braun committed
142
		slsm_last_match(t, app, &ret, path == NULL);
143
144

		if (!path)
145
			break;
146
147
148
		component = next_path_component(&path, &length);
		t = slsm_find_matching_child(t, component, length);
	} while (t);
149

150
	rcu_read_unlock();
151
152
153
154

	return ret;
}

155
156
157
unsigned slsm_perms_mode_grant(struct slsm_perms perms, struct slsm_perms perms_want) {
	return (perms.mode & perms_want.mode) == perms_want.mode;
}
158

159
160
unsigned slsm_perms_would_elevate(struct slsm_perms perms, struct slsm_perms perms_would_get) {
	unsigned flags, flags_would_get;
161
	unsigned restrictions = SLSM_FLAG_INHERIT | SLSM_FLAG_CONFINE | SLSM_FLAG_PROTECT;
162
163
164
165
166
167
168
169
170
171
172
	if (!slsm_perms_mode_grant(perms, perms_would_get))
		return 1;

	flags = perms.flags & restrictions;
	flags_would_get = perms_would_get.flags & restrictions;
	if ((flags & flags_would_get) != flags)
		return 1;
	return 0;
}


173

Lukas Braun's avatar
Lukas Braun committed
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
/************************************************************************
 * serializing
 ************************************************************************/

/* a resizeable string buffer */
struct slsm_str {
	size_t size;
	size_t used;
	char *buf;
};

int slsm_str_init(struct slsm_str *buf, size_t size) {
	buf->used = 0;
	buf->size = size;
	buf->buf = kzalloc(size, GFP_KERNEL);

	if (!buf->buf)
		return -ENOMEM;

	return 0;
}

/* appends a trailing null byte */
int slsm_str_append(struct slsm_str *buf, const char *fmt, ...) {
	va_list args;
	int written;

201
	while (1) {
Lukas Braun's avatar
Lukas Braun committed
202
203
		char *new_buf;
		size_t new_size = buf->size * 2;
204
205
206
207
208
209
210

		va_start(args, fmt); // must call va_start per loop iteration
		written = vsnprintf(buf->buf + buf->used, buf->size - buf->used, fmt, args) + 1;
		if (written <= buf->size - buf->used)
			break;
		va_end(args);

Lukas Braun's avatar
Lukas Braun committed
211
212
213
		if (new_size > (ssize_t)new_size)
			return -EFBIG;

214
		new_buf = krealloc(buf->buf, new_size, GFP_KERNEL);
Lukas Braun's avatar
Lukas Braun committed
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
		if (!new_buf)
			return -ENOMEM;

		buf->buf = new_buf;
		buf->size = new_size;
	}

	buf->used += (size_t)written;

	return 0;
}


/* path_buf->used doesn't include trailing null
 *
 * TODO: limit recursion */
ssize_t slsm_serialize_subtree(struct slsm_str *buf, struct slsm_str *path_buf,
		struct tree_node *t) {
	ssize_t ret;
	size_t old_path_len = path_buf->used;
	int i;
	BUG_ON(!t);

	// appends null to path_buf and includes it in ->used
	ret = slsm_str_append(path_buf, "/%s", t->name ? t->name : "");
	if (ret)
		return ret;

	for (i = 0; i < t->rules_used; i++) {
244
		ret = slsm_str_append(buf, "p=%s%ca=%s%cm=%u%cf=%u%c",
Lukas Braun's avatar
Lukas Braun committed
245
				path_buf->buf, '\0',
246
				t->rules[i].app ? t->rules[i].app : "", '\0',
Lukas Braun's avatar
Lukas Braun committed
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
				t->rules[i].perms.mode, '\0',
				t->rules[i].perms.flags, '\0');
		if (ret)
			return ret;
	}

	// exclude null for the recursive calls
	path_buf->used--;
	// if we're at root, also remove the / because we'll append one anyway
	if (!t->name)
		path_buf->used--;
	for (i = 0; i < t->children_used; i++) {
		ret = slsm_serialize_subtree(buf, path_buf, &t->children[i]);
		if (ret)
			return ret;
	}

	path_buf->used = old_path_len;

	return 0;
}

ssize_t slsm_serialize_tree(char **retbuf) {
	ssize_t ret;
271
272
	struct slsm_str buf = {};
	struct slsm_str path_buf = {};
Lukas Braun's avatar
Lukas Braun committed
273
274
275
276
277
278

	if (!rules)
		return 0;

	ret = slsm_str_init(&path_buf, 4096);
	if (ret)
279
280
281
282
		goto out;
	ret = slsm_str_init(&buf, 4096);
	if (ret)
		goto out;
Lukas Braun's avatar
Lukas Braun committed
283

284
285
286
	mutex_lock(&mutex);
	ret = slsm_serialize_subtree(&buf, &path_buf, rules);
	mutex_unlock(&mutex);
Lukas Braun's avatar
Lukas Braun committed
287

288
289
290
291
	if (ret) {
		kfree(buf.buf);
		goto out;
	}
Lukas Braun's avatar
Lukas Braun committed
292
293

	*retbuf = buf.buf;
294
295
296
297
298
	ret = (ssize_t)buf.used;

out:
	kfree(path_buf.buf);
	return ret;
Lukas Braun's avatar
Lukas Braun committed
299
300
301
}


302
303
304
305
306

/************************************************************************
 * tree creation
 ************************************************************************/

307
308
309
/**
 * @t: root of the tree in which the rule should be inserted
 * @path: where the rule is to be inserted, takes ownership
310
 * @rule: the rule, will be copied, takes ownership of references (e.g. app)
311
312
313
314
315
316
317
318
 *
 * Returns: 0 or error value
 */
static int slsm_insert_helper(struct tree_node *t, char *path,
		const struct slsm_rule *rule) {
	char *component, *next = path + 1; /* skip leading slash */
	struct tree_node *t_next = t;

319
320
321
	if (!*path || *path != '/') {
		kfree(path);
		kfree(rule->app);
322
		return -EINVAL;
323
	}
324
325
326
327
328
329
330

	if (!*next) {
		/* / is target node, we're already there */
		kfree(path);
		goto insert_rule;
	}

331
332
333
334
335
336
337
338
339
340
	/* first descend the tree as far as the path already exists */
	do {
		t = t_next;
		component = strsep(&next, "/");
		if (!component) {
			/* all nodes already exist, we don't need to keep @path
			 * nor allocate new nodes */
			kfree(path);
			goto insert_rule;
		}
341
	} while ((t_next = slsm_find_matching_child(t, component, strlen(component))));
342
343

	/* modify the deepest existing node on the path */
344
	BUG_ON(t->children_used > t->children_capacity);
345
346
347
	if (t->children_used == t->children_capacity) {
		/* node had no children so far or we're at the last element,
		 * need more space in any case */
348
		size_t new_capacity = t->children_capacity
349
350
351
			? t->children_capacity * CHILD_GROWTH
			: CHILD_CAP;
		struct tree_node *more_children = krealloc(t->children,
352
353
				new_capacity * sizeof(*more_children),
				GFP_KERNEL);
354
355
		if (!more_children) {
			kfree(path); /* no reference stored so far */
356
			goto enomem;
357
358
359
360
361
362
363
364
365
366
367
368
369
370
		}

		t->children = more_children;
		t->children_capacity = new_capacity;
	}

	/* mark this node as the first one referencing path */
	t->children[t->children_used] =
		(struct tree_node){ .name = component, .buf = path };
	t->children_used++;
	t = &t->children[t->children_used - 1];

	/* now create the rest */
	while ((component = strsep(&next, "/"))) {
371
		size_t new_capacity = CHILD_CAP;
372
		t->children = kcalloc(new_capacity, sizeof(*t->children),
373
				GFP_KERNEL);
374
375
376
		if (!t->children)
			/* what we alloced so far is already referenced and
			 * consistent, leave it in place */
377
			goto enomem;
378
379
380

		t->children[t->children_used] =
 			(struct tree_node){ .name = component };
381
		t->children_capacity = new_capacity;
382
383
384
385
386
387
388
		t->children_used++;
		t = &t->children[t->children_used - 1];
	}

	/* now t points to the node in which rule is to be inserted */

insert_rule:
389
	BUG_ON(t->rules_used > t->rules_capacity);
390
	if (t->rules_used == t->rules_capacity) {
391
		size_t new_capacity = t->rules_capacity
392
393
394
			? t->rules_capacity * RULES_GROWTH
			: RULES_CAP;
		struct slsm_rule *more_rules = krealloc(t->rules,
395
396
				new_capacity * sizeof(*more_rules),
				GFP_KERNEL);
397
		if (!more_rules)
398
			goto enomem;
399
400
401

		t->rules = more_rules;
		t->rules_capacity = new_capacity;
Sheppy's avatar
Sheppy committed
402
	}
403
404
405
406
407

	t->rules[t->rules_used] = *rule;
	t->rules_used++;

	return 0;
408
409
410
411

enomem:
	kfree(rule->app);
	return -ENOMEM;
412
413
414
415
416
417
418
419
420
421
422
}




/**
 * parse_component - validate @rule points to a 0-terminated string and save
 * 	its beginning in @component
 *
 * Returns: new remaining or negative error
 */
423
424
static const char *slsm_parse_component(const char *rule, size_t *remaining) {
	size_t len;
425
	if (*remaining == 0 || *rule != '=')
Sheppy's avatar
Sheppy committed
426
		return NULL;
427
428
429
430
	(*remaining)--;
	rule++;

	len = strnlen(rule, *remaining);
431
	if (len == *remaining || rule[len])
432
433
434
435
436
437
438
439
440
441
442
443
444
		/* no 0 at end of string */
		return NULL;

	*remaining -= len + 1;

	return rule + len + 1;
}


/**
 * slsm_insert_rule - parse a rule and insert it into a tree
 * @t: root node of the current tree (NOT NULL)
 * @rule: rule to parse (NOT NULL)
445
 * @remaining: pointer to bytes from @rule to end of buffer, NOT end of the rule
446
 *
447
 * Returns: 0 or negative on error
448
 */
449
450
static int slsm_insert_rule(struct tree_node *t, const char *rule,
		size_t *remaining) {
451
452
	const char *app = NULL, *path = NULL, *mode_str = NULL, *flags_str = NULL;
	struct slsm_rule r = { .app = NULL, .perms = { .mode = 0, .flags = 0 }};
453
454
455
	char *path_components = NULL;
	int error = 0;

456
	if (*remaining == 0)
457
458
		return -EINVAL;

459
	while (*remaining > 0) {
460
		char c = *rule++;
461
		(*remaining)--;
462
463
464
465

		switch (c) {
		case 'a':
			app = rule + 1;
466
			goto parse_component;
467
		case 'p':
468
469
470
471
472
473
474
475
			path = rule + 1;
			goto parse_component;
		case 'm':
			mode_str = rule + 1;
			goto parse_component;
		case 'f':
			flags_str = rule + 1;
			goto parse_component;
476
477
		case '\0':
			goto insert;
478
479
480
		default:
			printk(KERN_ERR "slsm_insert_rule: unexpected char %c\n", c);
			return -EINVAL;
481
		}
482
483
484
485
486
487
488

parse_component:
		rule = slsm_parse_component(rule, remaining);
		if (!rule) {
			printk(KERN_ERR "slsm_insert_rule: format error after key '%c'\n", c);
			return -EINVAL;
		}
Sheppy's avatar
Sheppy committed
489
	}
490
491

insert:
492
493
494
495
	if (!path) {
		printk(KERN_ERR "slsm_insert_rule: format error: mandatory parameter path missing\n");
		return -EINVAL;
	}
496
497
	if (!mode_str) {
		printk(KERN_ERR "slsm_insert_rule: format error: mandatory parameter mode missing\n");
498
499
		return -EINVAL;
	}
500
501
502
503
504
	if ((error = kstrtouint(mode_str, 10, &r.perms.mode))) {
		printk(KERN_ERR "slsm_insert_rule: format error: mode not a number: %s\n",
				mode_str);
		return error;
	}
505
506
	if (flags_str && *flags_str
			&& (error = kstrtouint(flags_str, 10, &r.perms.flags))) {
507
508
		printk(KERN_ERR "slsm_insert_rule: format error: flags not a number: %s\n",
				flags_str);
509
510
511
		return error;
	}

512
513
514
515
	path_components = kstrdup(path, GFP_KERNEL);
	if (!path_components)
		return -ENOMEM;

516
	if (app && *app) {
517
518
519
520
521
522
523
		r.app = kstrdup(app, GFP_KERNEL);
		if (!r.app) {
			kfree(path_components);
			return -ENOMEM;
		}
	} else
		r.app = NULL;
524

525
	return slsm_insert_helper(t, path_components, &r);
526
527
528
}


529
int slsm_new_tree(const char *buf, size_t buflen) {
530
	const char *current_rule = buf;
531
	size_t remaining = buflen;
532
	struct tree_node *t, *old_rules;
533
534
535
536
537

	if (buflen <= 0)
		/* something probably went wrong, keep the old rules */
		return -EINVAL;

538
539
	t = kzalloc(sizeof(*t), GFP_KERNEL);
	if (!t)
540
541
542
		return -ENOMEM;

	while (remaining > 0) {
543
544
		int err = slsm_insert_rule(t, current_rule, &remaining);
		if (err) {
545
			slsm_free_subtree(t);
546
			kfree(t);
547
			return err;
Sheppy's avatar
Sheppy committed
548
		}
549
550

		current_rule = &buf[buflen - remaining];
Sheppy's avatar
Sheppy committed
551
	}
552

553
554
555
556
557
558
	mutex_lock(&mutex);
	old_rules = rules;
	rcu_assign_pointer(rules, t);
	mutex_unlock(&mutex);

	if (old_rules) {
559
		synchronize_rcu();
560
561
562
		slsm_free_subtree(old_rules);
		kfree(old_rules);
	}
563
564

	return 0;
Sheppy's avatar
Sheppy committed
565
}