xref: /openbmc/linux/fs/overlayfs/readdir.c (revision 7587eb18)
1 /*
2  *
3  * Copyright (C) 2011 Novell Inc.
4  *
5  * This program is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 as published by
7  * the Free Software Foundation.
8  */
9 
10 #include <linux/fs.h>
11 #include <linux/slab.h>
12 #include <linux/namei.h>
13 #include <linux/file.h>
14 #include <linux/xattr.h>
15 #include <linux/rbtree.h>
16 #include <linux/security.h>
17 #include <linux/cred.h>
18 #include "overlayfs.h"
19 
20 struct ovl_cache_entry {
21 	unsigned int len;
22 	unsigned int type;
23 	u64 ino;
24 	struct list_head l_node;
25 	struct rb_node node;
26 	struct ovl_cache_entry *next_maybe_whiteout;
27 	bool is_whiteout;
28 	char name[];
29 };
30 
31 struct ovl_dir_cache {
32 	long refcount;
33 	u64 version;
34 	struct list_head entries;
35 };
36 
37 struct ovl_readdir_data {
38 	struct dir_context ctx;
39 	struct dentry *dentry;
40 	bool is_lowest;
41 	struct rb_root root;
42 	struct list_head *list;
43 	struct list_head middle;
44 	struct ovl_cache_entry *first_maybe_whiteout;
45 	int count;
46 	int err;
47 	bool d_type_supported;
48 };
49 
50 struct ovl_dir_file {
51 	bool is_real;
52 	bool is_upper;
53 	struct ovl_dir_cache *cache;
54 	struct list_head *cursor;
55 	struct file *realfile;
56 	struct file *upperfile;
57 };
58 
59 static struct ovl_cache_entry *ovl_cache_entry_from_node(struct rb_node *n)
60 {
61 	return container_of(n, struct ovl_cache_entry, node);
62 }
63 
64 static struct ovl_cache_entry *ovl_cache_entry_find(struct rb_root *root,
65 						    const char *name, int len)
66 {
67 	struct rb_node *node = root->rb_node;
68 	int cmp;
69 
70 	while (node) {
71 		struct ovl_cache_entry *p = ovl_cache_entry_from_node(node);
72 
73 		cmp = strncmp(name, p->name, len);
74 		if (cmp > 0)
75 			node = p->node.rb_right;
76 		else if (cmp < 0 || len < p->len)
77 			node = p->node.rb_left;
78 		else
79 			return p;
80 	}
81 
82 	return NULL;
83 }
84 
85 static struct ovl_cache_entry *ovl_cache_entry_new(struct ovl_readdir_data *rdd,
86 						   const char *name, int len,
87 						   u64 ino, unsigned int d_type)
88 {
89 	struct ovl_cache_entry *p;
90 	size_t size = offsetof(struct ovl_cache_entry, name[len + 1]);
91 
92 	p = kmalloc(size, GFP_KERNEL);
93 	if (!p)
94 		return NULL;
95 
96 	memcpy(p->name, name, len);
97 	p->name[len] = '\0';
98 	p->len = len;
99 	p->type = d_type;
100 	p->ino = ino;
101 	p->is_whiteout = false;
102 
103 	if (d_type == DT_CHR) {
104 		p->next_maybe_whiteout = rdd->first_maybe_whiteout;
105 		rdd->first_maybe_whiteout = p;
106 	}
107 	return p;
108 }
109 
110 static int ovl_cache_entry_add_rb(struct ovl_readdir_data *rdd,
111 				  const char *name, int len, u64 ino,
112 				  unsigned int d_type)
113 {
114 	struct rb_node **newp = &rdd->root.rb_node;
115 	struct rb_node *parent = NULL;
116 	struct ovl_cache_entry *p;
117 
118 	while (*newp) {
119 		int cmp;
120 		struct ovl_cache_entry *tmp;
121 
122 		parent = *newp;
123 		tmp = ovl_cache_entry_from_node(*newp);
124 		cmp = strncmp(name, tmp->name, len);
125 		if (cmp > 0)
126 			newp = &tmp->node.rb_right;
127 		else if (cmp < 0 || len < tmp->len)
128 			newp = &tmp->node.rb_left;
129 		else
130 			return 0;
131 	}
132 
133 	p = ovl_cache_entry_new(rdd, name, len, ino, d_type);
134 	if (p == NULL)
135 		return -ENOMEM;
136 
137 	list_add_tail(&p->l_node, rdd->list);
138 	rb_link_node(&p->node, parent, newp);
139 	rb_insert_color(&p->node, &rdd->root);
140 
141 	return 0;
142 }
143 
144 static int ovl_fill_lowest(struct ovl_readdir_data *rdd,
145 			   const char *name, int namelen,
146 			   loff_t offset, u64 ino, unsigned int d_type)
147 {
148 	struct ovl_cache_entry *p;
149 
150 	p = ovl_cache_entry_find(&rdd->root, name, namelen);
151 	if (p) {
152 		list_move_tail(&p->l_node, &rdd->middle);
153 	} else {
154 		p = ovl_cache_entry_new(rdd, name, namelen, ino, d_type);
155 		if (p == NULL)
156 			rdd->err = -ENOMEM;
157 		else
158 			list_add_tail(&p->l_node, &rdd->middle);
159 	}
160 
161 	return rdd->err;
162 }
163 
164 void ovl_cache_free(struct list_head *list)
165 {
166 	struct ovl_cache_entry *p;
167 	struct ovl_cache_entry *n;
168 
169 	list_for_each_entry_safe(p, n, list, l_node)
170 		kfree(p);
171 
172 	INIT_LIST_HEAD(list);
173 }
174 
175 static void ovl_cache_put(struct ovl_dir_file *od, struct dentry *dentry)
176 {
177 	struct ovl_dir_cache *cache = od->cache;
178 
179 	WARN_ON(cache->refcount <= 0);
180 	cache->refcount--;
181 	if (!cache->refcount) {
182 		if (ovl_dir_cache(dentry) == cache)
183 			ovl_set_dir_cache(dentry, NULL);
184 
185 		ovl_cache_free(&cache->entries);
186 		kfree(cache);
187 	}
188 }
189 
190 static int ovl_fill_merge(struct dir_context *ctx, const char *name,
191 			  int namelen, loff_t offset, u64 ino,
192 			  unsigned int d_type)
193 {
194 	struct ovl_readdir_data *rdd =
195 		container_of(ctx, struct ovl_readdir_data, ctx);
196 
197 	rdd->count++;
198 	if (!rdd->is_lowest)
199 		return ovl_cache_entry_add_rb(rdd, name, namelen, ino, d_type);
200 	else
201 		return ovl_fill_lowest(rdd, name, namelen, offset, ino, d_type);
202 }
203 
204 static int ovl_check_whiteouts(struct dentry *dir, struct ovl_readdir_data *rdd)
205 {
206 	int err;
207 	struct ovl_cache_entry *p;
208 	struct dentry *dentry;
209 	const struct cred *old_cred;
210 
211 	old_cred = ovl_override_creds(rdd->dentry->d_sb);
212 
213 	err = down_write_killable(&dir->d_inode->i_rwsem);
214 	if (!err) {
215 		while (rdd->first_maybe_whiteout) {
216 			p = rdd->first_maybe_whiteout;
217 			rdd->first_maybe_whiteout = p->next_maybe_whiteout;
218 			dentry = lookup_one_len(p->name, dir, p->len);
219 			if (!IS_ERR(dentry)) {
220 				p->is_whiteout = ovl_is_whiteout(dentry);
221 				dput(dentry);
222 			}
223 		}
224 		inode_unlock(dir->d_inode);
225 	}
226 	revert_creds(old_cred);
227 
228 	return err;
229 }
230 
231 static inline int ovl_dir_read(struct path *realpath,
232 			       struct ovl_readdir_data *rdd)
233 {
234 	struct file *realfile;
235 	int err;
236 
237 	realfile = ovl_path_open(realpath, O_RDONLY | O_DIRECTORY);
238 	if (IS_ERR(realfile))
239 		return PTR_ERR(realfile);
240 
241 	rdd->first_maybe_whiteout = NULL;
242 	rdd->ctx.pos = 0;
243 	do {
244 		rdd->count = 0;
245 		rdd->err = 0;
246 		err = iterate_dir(realfile, &rdd->ctx);
247 		if (err >= 0)
248 			err = rdd->err;
249 	} while (!err && rdd->count);
250 
251 	if (!err && rdd->first_maybe_whiteout)
252 		err = ovl_check_whiteouts(realpath->dentry, rdd);
253 
254 	fput(realfile);
255 
256 	return err;
257 }
258 
259 static void ovl_dir_reset(struct file *file)
260 {
261 	struct ovl_dir_file *od = file->private_data;
262 	struct ovl_dir_cache *cache = od->cache;
263 	struct dentry *dentry = file->f_path.dentry;
264 	enum ovl_path_type type = ovl_path_type(dentry);
265 
266 	if (cache && ovl_dentry_version_get(dentry) != cache->version) {
267 		ovl_cache_put(od, dentry);
268 		od->cache = NULL;
269 		od->cursor = NULL;
270 	}
271 	WARN_ON(!od->is_real && !OVL_TYPE_MERGE(type));
272 	if (od->is_real && OVL_TYPE_MERGE(type))
273 		od->is_real = false;
274 }
275 
276 static int ovl_dir_read_merged(struct dentry *dentry, struct list_head *list)
277 {
278 	int err;
279 	struct path realpath;
280 	struct ovl_readdir_data rdd = {
281 		.ctx.actor = ovl_fill_merge,
282 		.dentry = dentry,
283 		.list = list,
284 		.root = RB_ROOT,
285 		.is_lowest = false,
286 	};
287 	int idx, next;
288 
289 	for (idx = 0; idx != -1; idx = next) {
290 		next = ovl_path_next(idx, dentry, &realpath);
291 
292 		if (next != -1) {
293 			err = ovl_dir_read(&realpath, &rdd);
294 			if (err)
295 				break;
296 		} else {
297 			/*
298 			 * Insert lowest layer entries before upper ones, this
299 			 * allows offsets to be reasonably constant
300 			 */
301 			list_add(&rdd.middle, rdd.list);
302 			rdd.is_lowest = true;
303 			err = ovl_dir_read(&realpath, &rdd);
304 			list_del(&rdd.middle);
305 		}
306 	}
307 	return err;
308 }
309 
310 static void ovl_seek_cursor(struct ovl_dir_file *od, loff_t pos)
311 {
312 	struct list_head *p;
313 	loff_t off = 0;
314 
315 	list_for_each(p, &od->cache->entries) {
316 		if (off >= pos)
317 			break;
318 		off++;
319 	}
320 	/* Cursor is safe since the cache is stable */
321 	od->cursor = p;
322 }
323 
324 static struct ovl_dir_cache *ovl_cache_get(struct dentry *dentry)
325 {
326 	int res;
327 	struct ovl_dir_cache *cache;
328 
329 	cache = ovl_dir_cache(dentry);
330 	if (cache && ovl_dentry_version_get(dentry) == cache->version) {
331 		cache->refcount++;
332 		return cache;
333 	}
334 	ovl_set_dir_cache(dentry, NULL);
335 
336 	cache = kzalloc(sizeof(struct ovl_dir_cache), GFP_KERNEL);
337 	if (!cache)
338 		return ERR_PTR(-ENOMEM);
339 
340 	cache->refcount = 1;
341 	INIT_LIST_HEAD(&cache->entries);
342 
343 	res = ovl_dir_read_merged(dentry, &cache->entries);
344 	if (res) {
345 		ovl_cache_free(&cache->entries);
346 		kfree(cache);
347 		return ERR_PTR(res);
348 	}
349 
350 	cache->version = ovl_dentry_version_get(dentry);
351 	ovl_set_dir_cache(dentry, cache);
352 
353 	return cache;
354 }
355 
356 static int ovl_iterate(struct file *file, struct dir_context *ctx)
357 {
358 	struct ovl_dir_file *od = file->private_data;
359 	struct dentry *dentry = file->f_path.dentry;
360 	struct ovl_cache_entry *p;
361 
362 	if (!ctx->pos)
363 		ovl_dir_reset(file);
364 
365 	if (od->is_real)
366 		return iterate_dir(od->realfile, ctx);
367 
368 	if (!od->cache) {
369 		struct ovl_dir_cache *cache;
370 
371 		cache = ovl_cache_get(dentry);
372 		if (IS_ERR(cache))
373 			return PTR_ERR(cache);
374 
375 		od->cache = cache;
376 		ovl_seek_cursor(od, ctx->pos);
377 	}
378 
379 	while (od->cursor != &od->cache->entries) {
380 		p = list_entry(od->cursor, struct ovl_cache_entry, l_node);
381 		if (!p->is_whiteout)
382 			if (!dir_emit(ctx, p->name, p->len, p->ino, p->type))
383 				break;
384 		od->cursor = p->l_node.next;
385 		ctx->pos++;
386 	}
387 	return 0;
388 }
389 
390 static loff_t ovl_dir_llseek(struct file *file, loff_t offset, int origin)
391 {
392 	loff_t res;
393 	struct ovl_dir_file *od = file->private_data;
394 
395 	inode_lock(file_inode(file));
396 	if (!file->f_pos)
397 		ovl_dir_reset(file);
398 
399 	if (od->is_real) {
400 		res = vfs_llseek(od->realfile, offset, origin);
401 		file->f_pos = od->realfile->f_pos;
402 	} else {
403 		res = -EINVAL;
404 
405 		switch (origin) {
406 		case SEEK_CUR:
407 			offset += file->f_pos;
408 			break;
409 		case SEEK_SET:
410 			break;
411 		default:
412 			goto out_unlock;
413 		}
414 		if (offset < 0)
415 			goto out_unlock;
416 
417 		if (offset != file->f_pos) {
418 			file->f_pos = offset;
419 			if (od->cache)
420 				ovl_seek_cursor(od, offset);
421 		}
422 		res = offset;
423 	}
424 out_unlock:
425 	inode_unlock(file_inode(file));
426 
427 	return res;
428 }
429 
430 static int ovl_dir_fsync(struct file *file, loff_t start, loff_t end,
431 			 int datasync)
432 {
433 	struct ovl_dir_file *od = file->private_data;
434 	struct dentry *dentry = file->f_path.dentry;
435 	struct file *realfile = od->realfile;
436 
437 	/*
438 	 * Need to check if we started out being a lower dir, but got copied up
439 	 */
440 	if (!od->is_upper && OVL_TYPE_UPPER(ovl_path_type(dentry))) {
441 		struct inode *inode = file_inode(file);
442 
443 		realfile = lockless_dereference(od->upperfile);
444 		if (!realfile) {
445 			struct path upperpath;
446 
447 			ovl_path_upper(dentry, &upperpath);
448 			realfile = ovl_path_open(&upperpath, O_RDONLY);
449 			smp_mb__before_spinlock();
450 			inode_lock(inode);
451 			if (!od->upperfile) {
452 				if (IS_ERR(realfile)) {
453 					inode_unlock(inode);
454 					return PTR_ERR(realfile);
455 				}
456 				od->upperfile = realfile;
457 			} else {
458 				/* somebody has beaten us to it */
459 				if (!IS_ERR(realfile))
460 					fput(realfile);
461 				realfile = od->upperfile;
462 			}
463 			inode_unlock(inode);
464 		}
465 	}
466 
467 	return vfs_fsync_range(realfile, start, end, datasync);
468 }
469 
470 static int ovl_dir_release(struct inode *inode, struct file *file)
471 {
472 	struct ovl_dir_file *od = file->private_data;
473 
474 	if (od->cache) {
475 		inode_lock(inode);
476 		ovl_cache_put(od, file->f_path.dentry);
477 		inode_unlock(inode);
478 	}
479 	fput(od->realfile);
480 	if (od->upperfile)
481 		fput(od->upperfile);
482 	kfree(od);
483 
484 	return 0;
485 }
486 
487 static int ovl_dir_open(struct inode *inode, struct file *file)
488 {
489 	struct path realpath;
490 	struct file *realfile;
491 	struct ovl_dir_file *od;
492 	enum ovl_path_type type;
493 
494 	od = kzalloc(sizeof(struct ovl_dir_file), GFP_KERNEL);
495 	if (!od)
496 		return -ENOMEM;
497 
498 	type = ovl_path_real(file->f_path.dentry, &realpath);
499 	realfile = ovl_path_open(&realpath, file->f_flags);
500 	if (IS_ERR(realfile)) {
501 		kfree(od);
502 		return PTR_ERR(realfile);
503 	}
504 	od->realfile = realfile;
505 	od->is_real = !OVL_TYPE_MERGE(type);
506 	od->is_upper = OVL_TYPE_UPPER(type);
507 	file->private_data = od;
508 
509 	return 0;
510 }
511 
512 const struct file_operations ovl_dir_operations = {
513 	.read		= generic_read_dir,
514 	.open		= ovl_dir_open,
515 	.iterate	= ovl_iterate,
516 	.llseek		= ovl_dir_llseek,
517 	.fsync		= ovl_dir_fsync,
518 	.release	= ovl_dir_release,
519 };
520 
521 int ovl_check_empty_dir(struct dentry *dentry, struct list_head *list)
522 {
523 	int err;
524 	struct ovl_cache_entry *p;
525 
526 	err = ovl_dir_read_merged(dentry, list);
527 	if (err)
528 		return err;
529 
530 	err = 0;
531 
532 	list_for_each_entry(p, list, l_node) {
533 		if (p->is_whiteout)
534 			continue;
535 
536 		if (p->name[0] == '.') {
537 			if (p->len == 1)
538 				continue;
539 			if (p->len == 2 && p->name[1] == '.')
540 				continue;
541 		}
542 		err = -ENOTEMPTY;
543 		break;
544 	}
545 
546 	return err;
547 }
548 
549 void ovl_cleanup_whiteouts(struct dentry *upper, struct list_head *list)
550 {
551 	struct ovl_cache_entry *p;
552 
553 	inode_lock_nested(upper->d_inode, I_MUTEX_CHILD);
554 	list_for_each_entry(p, list, l_node) {
555 		struct dentry *dentry;
556 
557 		if (!p->is_whiteout)
558 			continue;
559 
560 		dentry = lookup_one_len(p->name, upper, p->len);
561 		if (IS_ERR(dentry)) {
562 			pr_err("overlayfs: lookup '%s/%.*s' failed (%i)\n",
563 			       upper->d_name.name, p->len, p->name,
564 			       (int) PTR_ERR(dentry));
565 			continue;
566 		}
567 		if (dentry->d_inode)
568 			ovl_cleanup(upper->d_inode, dentry);
569 		dput(dentry);
570 	}
571 	inode_unlock(upper->d_inode);
572 }
573 
574 static int ovl_check_d_type(struct dir_context *ctx, const char *name,
575 			  int namelen, loff_t offset, u64 ino,
576 			  unsigned int d_type)
577 {
578 	struct ovl_readdir_data *rdd =
579 		container_of(ctx, struct ovl_readdir_data, ctx);
580 
581 	/* Even if d_type is not supported, DT_DIR is returned for . and .. */
582 	if (!strncmp(name, ".", namelen) || !strncmp(name, "..", namelen))
583 		return 0;
584 
585 	if (d_type != DT_UNKNOWN)
586 		rdd->d_type_supported = true;
587 
588 	return 0;
589 }
590 
591 /*
592  * Returns 1 if d_type is supported, 0 not supported/unknown. Negative values
593  * if error is encountered.
594  */
595 int ovl_check_d_type_supported(struct path *realpath)
596 {
597 	int err;
598 	struct ovl_readdir_data rdd = {
599 		.ctx.actor = ovl_check_d_type,
600 		.d_type_supported = false,
601 	};
602 
603 	err = ovl_dir_read(realpath, &rdd);
604 	if (err)
605 		return err;
606 
607 	return rdd.d_type_supported;
608 }
609