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