3 * Copyright (C) 2011 Novell Inc.
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.
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 <linux/ratelimit.h>
19 #include "overlayfs.h"
21 struct ovl_cache_entry {
26 struct list_head l_node;
28 struct ovl_cache_entry *next_maybe_whiteout;
34 struct ovl_dir_cache {
37 struct list_head entries;
41 struct ovl_readdir_data {
42 struct dir_context ctx;
43 struct dentry *dentry;
46 struct list_head *list;
47 struct list_head middle;
48 struct ovl_cache_entry *first_maybe_whiteout;
52 bool d_type_supported;
58 struct ovl_dir_cache *cache;
59 struct list_head *cursor;
60 struct file *realfile;
61 struct file *upperfile;
64 static struct ovl_cache_entry *ovl_cache_entry_from_node(struct rb_node *n)
66 return rb_entry(n, struct ovl_cache_entry, node);
69 static bool ovl_cache_entry_find_link(const char *name, int len,
70 struct rb_node ***link,
71 struct rb_node **parent)
74 struct rb_node **newp = *link;
76 while (!found && *newp) {
78 struct ovl_cache_entry *tmp;
81 tmp = ovl_cache_entry_from_node(*newp);
82 cmp = strncmp(name, tmp->name, len);
84 newp = &tmp->node.rb_right;
85 else if (cmp < 0 || len < tmp->len)
86 newp = &tmp->node.rb_left;
95 static struct ovl_cache_entry *ovl_cache_entry_find(struct rb_root *root,
96 const char *name, int len)
98 struct rb_node *node = root->rb_node;
102 struct ovl_cache_entry *p = ovl_cache_entry_from_node(node);
104 cmp = strncmp(name, p->name, len);
106 node = p->node.rb_right;
107 else if (cmp < 0 || len < p->len)
108 node = p->node.rb_left;
116 static bool ovl_calc_d_ino(struct ovl_readdir_data *rdd,
117 struct ovl_cache_entry *p)
119 /* Don't care if not doing ovl_iter() */
123 /* Always recalc d_ino for parent */
124 if (strcmp(p->name, "..") == 0)
127 /* If this is lower, then native d_ino will do */
132 * Recalc d_ino for '.' and for all entries if dir is impure (contains
135 if ((p->name[0] == '.' && p->len == 1) ||
136 ovl_test_flag(OVL_IMPURE, d_inode(rdd->dentry)))
142 static struct ovl_cache_entry *ovl_cache_entry_new(struct ovl_readdir_data *rdd,
143 const char *name, int len,
144 u64 ino, unsigned int d_type)
146 struct ovl_cache_entry *p;
147 size_t size = offsetof(struct ovl_cache_entry, name[len + 1]);
149 p = kmalloc(size, GFP_KERNEL);
153 memcpy(p->name, name, len);
159 /* Defer setting d_ino for upper entry to ovl_iterate() */
160 if (ovl_calc_d_ino(rdd, p))
162 p->is_upper = rdd->is_upper;
163 p->is_whiteout = false;
165 if (d_type == DT_CHR) {
166 p->next_maybe_whiteout = rdd->first_maybe_whiteout;
167 rdd->first_maybe_whiteout = p;
172 static int ovl_cache_entry_add_rb(struct ovl_readdir_data *rdd,
173 const char *name, int len, u64 ino,
176 struct rb_node **newp = &rdd->root->rb_node;
177 struct rb_node *parent = NULL;
178 struct ovl_cache_entry *p;
180 if (ovl_cache_entry_find_link(name, len, &newp, &parent))
183 p = ovl_cache_entry_new(rdd, name, len, ino, d_type);
189 list_add_tail(&p->l_node, rdd->list);
190 rb_link_node(&p->node, parent, newp);
191 rb_insert_color(&p->node, rdd->root);
196 static int ovl_fill_lowest(struct ovl_readdir_data *rdd,
197 const char *name, int namelen,
198 loff_t offset, u64 ino, unsigned int d_type)
200 struct ovl_cache_entry *p;
202 p = ovl_cache_entry_find(rdd->root, name, namelen);
204 list_move_tail(&p->l_node, &rdd->middle);
206 p = ovl_cache_entry_new(rdd, name, namelen, ino, d_type);
210 list_add_tail(&p->l_node, &rdd->middle);
216 void ovl_cache_free(struct list_head *list)
218 struct ovl_cache_entry *p;
219 struct ovl_cache_entry *n;
221 list_for_each_entry_safe(p, n, list, l_node)
224 INIT_LIST_HEAD(list);
227 void ovl_dir_cache_free(struct inode *inode)
229 struct ovl_dir_cache *cache = ovl_dir_cache(inode);
232 ovl_cache_free(&cache->entries);
237 static void ovl_cache_put(struct ovl_dir_file *od, struct dentry *dentry)
239 struct ovl_dir_cache *cache = od->cache;
241 WARN_ON(cache->refcount <= 0);
243 if (!cache->refcount) {
244 if (ovl_dir_cache(d_inode(dentry)) == cache)
245 ovl_set_dir_cache(d_inode(dentry), NULL);
247 ovl_cache_free(&cache->entries);
252 static int ovl_fill_merge(struct dir_context *ctx, const char *name,
253 int namelen, loff_t offset, u64 ino,
256 struct ovl_readdir_data *rdd =
257 container_of(ctx, struct ovl_readdir_data, ctx);
261 return ovl_cache_entry_add_rb(rdd, name, namelen, ino, d_type);
263 return ovl_fill_lowest(rdd, name, namelen, offset, ino, d_type);
266 static int ovl_check_whiteouts(struct dentry *dir, struct ovl_readdir_data *rdd)
269 struct ovl_cache_entry *p;
270 struct dentry *dentry;
271 const struct cred *old_cred;
273 old_cred = ovl_override_creds(rdd->dentry->d_sb);
275 err = down_write_killable(&dir->d_inode->i_rwsem);
277 while (rdd->first_maybe_whiteout) {
278 p = rdd->first_maybe_whiteout;
279 rdd->first_maybe_whiteout = p->next_maybe_whiteout;
280 dentry = lookup_one_len(p->name, dir, p->len);
281 if (!IS_ERR(dentry)) {
282 p->is_whiteout = ovl_is_whiteout(dentry);
286 inode_unlock(dir->d_inode);
288 revert_creds(old_cred);
293 static inline int ovl_dir_read(struct path *realpath,
294 struct ovl_readdir_data *rdd)
296 struct file *realfile;
299 realfile = ovl_path_open(realpath, O_RDONLY | O_DIRECTORY);
300 if (IS_ERR(realfile))
301 return PTR_ERR(realfile);
303 rdd->first_maybe_whiteout = NULL;
308 err = iterate_dir(realfile, &rdd->ctx);
311 } while (!err && rdd->count);
313 if (!err && rdd->first_maybe_whiteout && rdd->dentry)
314 err = ovl_check_whiteouts(realpath->dentry, rdd);
322 * Can we iterate real dir directly?
324 * Non-merge dir may contain whiteouts from a time it was a merge upper, before
325 * lower dir was removed under it and possibly before it was rotated from upper
328 static bool ovl_dir_is_real(struct dentry *dir)
330 return !ovl_test_flag(OVL_WHITEOUTS, d_inode(dir));
333 static void ovl_dir_reset(struct file *file)
335 struct ovl_dir_file *od = file->private_data;
336 struct ovl_dir_cache *cache = od->cache;
337 struct dentry *dentry = file->f_path.dentry;
340 if (cache && ovl_dentry_version_get(dentry) != cache->version) {
341 ovl_cache_put(od, dentry);
345 is_real = ovl_dir_is_real(dentry);
346 if (od->is_real != is_real) {
347 /* is_real can only become false when dir is copied up */
348 if (WARN_ON(is_real))
354 static int ovl_dir_read_merged(struct dentry *dentry, struct list_head *list,
355 struct rb_root *root)
358 struct path realpath;
359 struct ovl_readdir_data rdd = {
360 .ctx.actor = ovl_fill_merge,
368 for (idx = 0; idx != -1; idx = next) {
369 next = ovl_path_next(idx, dentry, &realpath);
370 rdd.is_upper = ovl_dentry_upper(dentry) == realpath.dentry;
373 err = ovl_dir_read(&realpath, &rdd);
378 * Insert lowest layer entries before upper ones, this
379 * allows offsets to be reasonably constant
381 list_add(&rdd.middle, rdd.list);
382 rdd.is_lowest = true;
383 err = ovl_dir_read(&realpath, &rdd);
384 list_del(&rdd.middle);
390 static void ovl_seek_cursor(struct ovl_dir_file *od, loff_t pos)
395 list_for_each(p, &od->cache->entries) {
400 /* Cursor is safe since the cache is stable */
404 static struct ovl_dir_cache *ovl_cache_get(struct dentry *dentry)
407 struct ovl_dir_cache *cache;
409 cache = ovl_dir_cache(d_inode(dentry));
410 if (cache && ovl_dentry_version_get(dentry) == cache->version) {
411 WARN_ON(!cache->refcount);
415 ovl_set_dir_cache(d_inode(dentry), NULL);
417 cache = kzalloc(sizeof(struct ovl_dir_cache), GFP_KERNEL);
419 return ERR_PTR(-ENOMEM);
422 INIT_LIST_HEAD(&cache->entries);
423 cache->root = RB_ROOT;
425 res = ovl_dir_read_merged(dentry, &cache->entries, &cache->root);
427 ovl_cache_free(&cache->entries);
432 cache->version = ovl_dentry_version_get(dentry);
433 ovl_set_dir_cache(d_inode(dentry), cache);
439 * Set d_ino for upper entries. Non-upper entries should always report
440 * the uppermost real inode ino and should not call this function.
442 * When not all layer are on same fs, report real ino also for upper.
444 * When all layers are on the same fs, and upper has a reference to
445 * copy up origin, call vfs_getattr() on the overlay entry to make
446 * sure that d_ino will be consistent with st_ino from stat(2).
448 static int ovl_cache_update_ino(struct path *path, struct ovl_cache_entry *p)
451 struct dentry *dir = path->dentry;
452 struct dentry *this = NULL;
453 enum ovl_path_type type;
454 u64 ino = p->real_ino;
457 if (!ovl_same_sb(dir->d_sb))
460 if (p->name[0] == '.') {
465 if (p->len == 2 && p->name[1] == '.') {
466 /* we shall not be moved */
467 this = dget(dir->d_parent);
471 this = lookup_one_len(p->name, dir, p->len);
472 if (IS_ERR_OR_NULL(this) || !this->d_inode) {
482 type = ovl_path_type(this);
483 if (OVL_TYPE_ORIGIN(type)) {
485 struct path statpath = *path;
487 statpath.dentry = this;
488 err = vfs_getattr(&statpath, &stat, STATX_INO, 0);
492 WARN_ON_ONCE(dir->d_sb->s_dev != stat.dev);
502 pr_warn_ratelimited("overlayfs: failed to look up (%s) for ino (%i)\n",
507 static int ovl_fill_plain(struct dir_context *ctx, const char *name,
508 int namelen, loff_t offset, u64 ino,
511 struct ovl_cache_entry *p;
512 struct ovl_readdir_data *rdd =
513 container_of(ctx, struct ovl_readdir_data, ctx);
516 p = ovl_cache_entry_new(rdd, name, namelen, ino, d_type);
521 list_add_tail(&p->l_node, rdd->list);
526 static int ovl_dir_read_impure(struct path *path, struct list_head *list,
527 struct rb_root *root)
530 struct path realpath;
531 struct ovl_cache_entry *p, *n;
532 struct ovl_readdir_data rdd = {
533 .ctx.actor = ovl_fill_plain,
538 INIT_LIST_HEAD(list);
540 ovl_path_upper(path->dentry, &realpath);
542 err = ovl_dir_read(&realpath, &rdd);
546 list_for_each_entry_safe(p, n, list, l_node) {
547 if (strcmp(p->name, ".") != 0 &&
548 strcmp(p->name, "..") != 0) {
549 err = ovl_cache_update_ino(path, p);
553 if (p->ino == p->real_ino) {
554 list_del(&p->l_node);
557 struct rb_node **newp = &root->rb_node;
558 struct rb_node *parent = NULL;
560 if (WARN_ON(ovl_cache_entry_find_link(p->name, p->len,
564 rb_link_node(&p->node, parent, newp);
565 rb_insert_color(&p->node, root);
571 static struct ovl_dir_cache *ovl_cache_get_impure(struct path *path)
574 struct dentry *dentry = path->dentry;
575 struct ovl_dir_cache *cache;
577 cache = ovl_dir_cache(d_inode(dentry));
578 if (cache && ovl_dentry_version_get(dentry) == cache->version)
581 /* Impure cache is not refcounted, free it here */
582 ovl_dir_cache_free(d_inode(dentry));
583 ovl_set_dir_cache(d_inode(dentry), NULL);
585 cache = kzalloc(sizeof(struct ovl_dir_cache), GFP_KERNEL);
587 return ERR_PTR(-ENOMEM);
589 res = ovl_dir_read_impure(path, &cache->entries, &cache->root);
591 ovl_cache_free(&cache->entries);
595 if (list_empty(&cache->entries)) {
596 /* Good oportunity to get rid of an unnecessary "impure" flag */
597 ovl_do_removexattr(ovl_dentry_upper(dentry), OVL_XATTR_IMPURE);
598 ovl_clear_flag(OVL_IMPURE, d_inode(dentry));
603 cache->version = ovl_dentry_version_get(dentry);
604 ovl_set_dir_cache(d_inode(dentry), cache);
609 struct ovl_readdir_translate {
610 struct dir_context *orig_ctx;
611 struct ovl_dir_cache *cache;
612 struct dir_context ctx;
616 static int ovl_fill_real(struct dir_context *ctx, const char *name,
617 int namelen, loff_t offset, u64 ino,
620 struct ovl_readdir_translate *rdt =
621 container_of(ctx, struct ovl_readdir_translate, ctx);
622 struct dir_context *orig_ctx = rdt->orig_ctx;
624 if (rdt->parent_ino && strcmp(name, "..") == 0)
625 ino = rdt->parent_ino;
626 else if (rdt->cache) {
627 struct ovl_cache_entry *p;
629 p = ovl_cache_entry_find(&rdt->cache->root, name, namelen);
634 return orig_ctx->actor(orig_ctx, name, namelen, offset, ino, d_type);
637 static int ovl_iterate_real(struct file *file, struct dir_context *ctx)
640 struct ovl_dir_file *od = file->private_data;
641 struct dentry *dir = file->f_path.dentry;
642 struct ovl_readdir_translate rdt = {
643 .ctx.actor = ovl_fill_real,
647 if (OVL_TYPE_MERGE(ovl_path_type(dir->d_parent))) {
649 struct path statpath = file->f_path;
651 statpath.dentry = dir->d_parent;
652 err = vfs_getattr(&statpath, &stat, STATX_INO, 0);
656 WARN_ON_ONCE(dir->d_sb->s_dev != stat.dev);
657 rdt.parent_ino = stat.ino;
660 if (ovl_test_flag(OVL_IMPURE, d_inode(dir))) {
661 rdt.cache = ovl_cache_get_impure(&file->f_path);
662 if (IS_ERR(rdt.cache))
663 return PTR_ERR(rdt.cache);
666 err = iterate_dir(od->realfile, &rdt.ctx);
667 ctx->pos = rdt.ctx.pos;
673 static int ovl_iterate(struct file *file, struct dir_context *ctx)
675 struct ovl_dir_file *od = file->private_data;
676 struct dentry *dentry = file->f_path.dentry;
677 struct ovl_cache_entry *p;
685 * If parent is merge, then need to adjust d_ino for '..', if
686 * dir is impure then need to adjust d_ino for copied up
689 if (ovl_same_sb(dentry->d_sb) &&
690 (ovl_test_flag(OVL_IMPURE, d_inode(dentry)) ||
691 OVL_TYPE_MERGE(ovl_path_type(dentry->d_parent)))) {
692 return ovl_iterate_real(file, ctx);
694 return iterate_dir(od->realfile, ctx);
698 struct ovl_dir_cache *cache;
700 cache = ovl_cache_get(dentry);
702 return PTR_ERR(cache);
705 ovl_seek_cursor(od, ctx->pos);
708 while (od->cursor != &od->cache->entries) {
709 p = list_entry(od->cursor, struct ovl_cache_entry, l_node);
710 if (!p->is_whiteout) {
712 err = ovl_cache_update_ino(&file->f_path, p);
716 if (!dir_emit(ctx, p->name, p->len, p->ino, p->type))
719 od->cursor = p->l_node.next;
725 static loff_t ovl_dir_llseek(struct file *file, loff_t offset, int origin)
728 struct ovl_dir_file *od = file->private_data;
730 inode_lock(file_inode(file));
735 res = vfs_llseek(od->realfile, offset, origin);
736 file->f_pos = od->realfile->f_pos;
742 offset += file->f_pos;
752 if (offset != file->f_pos) {
753 file->f_pos = offset;
755 ovl_seek_cursor(od, offset);
760 inode_unlock(file_inode(file));
765 static int ovl_dir_fsync(struct file *file, loff_t start, loff_t end,
768 struct ovl_dir_file *od = file->private_data;
769 struct dentry *dentry = file->f_path.dentry;
770 struct file *realfile = od->realfile;
773 * Need to check if we started out being a lower dir, but got copied up
775 if (!od->is_upper && OVL_TYPE_UPPER(ovl_path_type(dentry))) {
776 struct inode *inode = file_inode(file);
778 realfile = READ_ONCE(od->upperfile);
780 struct path upperpath;
782 ovl_path_upper(dentry, &upperpath);
783 realfile = ovl_path_open(&upperpath, O_RDONLY);
786 if (!od->upperfile) {
787 if (IS_ERR(realfile)) {
789 return PTR_ERR(realfile);
791 smp_store_release(&od->upperfile, realfile);
793 /* somebody has beaten us to it */
794 if (!IS_ERR(realfile))
796 realfile = od->upperfile;
802 return vfs_fsync_range(realfile, start, end, datasync);
805 static int ovl_dir_release(struct inode *inode, struct file *file)
807 struct ovl_dir_file *od = file->private_data;
811 ovl_cache_put(od, file->f_path.dentry);
822 static int ovl_dir_open(struct inode *inode, struct file *file)
824 struct path realpath;
825 struct file *realfile;
826 struct ovl_dir_file *od;
827 enum ovl_path_type type;
829 od = kzalloc(sizeof(struct ovl_dir_file), GFP_KERNEL);
833 type = ovl_path_real(file->f_path.dentry, &realpath);
834 realfile = ovl_path_open(&realpath, file->f_flags);
835 if (IS_ERR(realfile)) {
837 return PTR_ERR(realfile);
839 od->realfile = realfile;
840 od->is_real = ovl_dir_is_real(file->f_path.dentry);
841 od->is_upper = OVL_TYPE_UPPER(type);
842 file->private_data = od;
847 const struct file_operations ovl_dir_operations = {
848 .read = generic_read_dir,
849 .open = ovl_dir_open,
850 .iterate = ovl_iterate,
851 .llseek = ovl_dir_llseek,
852 .fsync = ovl_dir_fsync,
853 .release = ovl_dir_release,
856 int ovl_check_empty_dir(struct dentry *dentry, struct list_head *list)
859 struct ovl_cache_entry *p, *n;
860 struct rb_root root = RB_ROOT;
862 err = ovl_dir_read_merged(dentry, list, &root);
868 list_for_each_entry_safe(p, n, list, l_node) {
870 * Select whiteouts in upperdir, they should
871 * be cleared when deleting this directory.
873 if (p->is_whiteout) {
879 if (p->name[0] == '.') {
882 if (p->len == 2 && p->name[1] == '.')
889 list_del(&p->l_node);
896 void ovl_cleanup_whiteouts(struct dentry *upper, struct list_head *list)
898 struct ovl_cache_entry *p;
900 inode_lock_nested(upper->d_inode, I_MUTEX_CHILD);
901 list_for_each_entry(p, list, l_node) {
902 struct dentry *dentry;
904 if (WARN_ON(!p->is_whiteout || !p->is_upper))
907 dentry = lookup_one_len(p->name, upper, p->len);
908 if (IS_ERR(dentry)) {
909 pr_err("overlayfs: lookup '%s/%.*s' failed (%i)\n",
910 upper->d_name.name, p->len, p->name,
911 (int) PTR_ERR(dentry));
915 ovl_cleanup(upper->d_inode, dentry);
918 inode_unlock(upper->d_inode);
921 static int ovl_check_d_type(struct dir_context *ctx, const char *name,
922 int namelen, loff_t offset, u64 ino,
925 struct ovl_readdir_data *rdd =
926 container_of(ctx, struct ovl_readdir_data, ctx);
928 /* Even if d_type is not supported, DT_DIR is returned for . and .. */
929 if (!strncmp(name, ".", namelen) || !strncmp(name, "..", namelen))
932 if (d_type != DT_UNKNOWN)
933 rdd->d_type_supported = true;
939 * Returns 1 if d_type is supported, 0 not supported/unknown. Negative values
940 * if error is encountered.
942 int ovl_check_d_type_supported(struct path *realpath)
945 struct ovl_readdir_data rdd = {
946 .ctx.actor = ovl_check_d_type,
947 .d_type_supported = false,
950 err = ovl_dir_read(realpath, &rdd);
954 return rdd.d_type_supported;
957 static void ovl_workdir_cleanup_recurse(struct path *path, int level)
960 struct inode *dir = path->dentry->d_inode;
962 struct rb_root root = RB_ROOT;
963 struct ovl_cache_entry *p;
964 struct ovl_readdir_data rdd = {
965 .ctx.actor = ovl_fill_merge,
972 err = ovl_dir_read(path, &rdd);
976 inode_lock_nested(dir, I_MUTEX_PARENT);
977 list_for_each_entry(p, &list, l_node) {
978 struct dentry *dentry;
980 if (p->name[0] == '.') {
983 if (p->len == 2 && p->name[1] == '.')
986 dentry = lookup_one_len(p->name, path->dentry, p->len);
990 ovl_workdir_cleanup(dir, path->mnt, dentry, level);
995 ovl_cache_free(&list);
998 void ovl_workdir_cleanup(struct inode *dir, struct vfsmount *mnt,
999 struct dentry *dentry, int level)
1003 if (!d_is_dir(dentry) || level > 1) {
1004 ovl_cleanup(dir, dentry);
1008 err = ovl_do_rmdir(dir, dentry);
1010 struct path path = { .mnt = mnt, .dentry = dentry };
1013 ovl_workdir_cleanup_recurse(&path, level + 1);
1014 inode_lock_nested(dir, I_MUTEX_PARENT);
1015 ovl_cleanup(dir, dentry);
1019 int ovl_indexdir_cleanup(struct dentry *dentry, struct vfsmount *mnt,
1020 struct ovl_path *lower, unsigned int numlower)
1023 struct dentry *index = NULL;
1024 struct inode *dir = dentry->d_inode;
1025 struct path path = { .mnt = mnt, .dentry = dentry };
1027 struct rb_root root = RB_ROOT;
1028 struct ovl_cache_entry *p;
1029 struct ovl_readdir_data rdd = {
1030 .ctx.actor = ovl_fill_merge,
1037 err = ovl_dir_read(&path, &rdd);
1041 inode_lock_nested(dir, I_MUTEX_PARENT);
1042 list_for_each_entry(p, &list, l_node) {
1043 if (p->name[0] == '.') {
1046 if (p->len == 2 && p->name[1] == '.')
1049 index = lookup_one_len(p->name, dentry, p->len);
1050 if (IS_ERR(index)) {
1051 err = PTR_ERR(index);
1055 err = ovl_verify_index(index, lower, numlower);
1056 /* Cleanup stale and orphan index entries */
1057 if (err && (err == -ESTALE || err == -ENOENT))
1058 err = ovl_cleanup(dir, index);
1068 ovl_cache_free(&list);
1070 pr_err("overlayfs: failed index dir cleanup (%i)\n", err);