fs/overlayfs/readdir.c

   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         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
  48 struct 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
  57 static 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
  62 static 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
  83 static 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
 108 static 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
 142 static 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
 162 void 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
 173 static 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
 188 static 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
 202 static 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
 239 static 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
 267 static 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
 284 static 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
 317 static 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
 331 static 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
 363 static 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
 397 static 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         }
 431 out_unlock:
 432         mutex_unlock(&file_inode(file)->i_mutex);
 433
 434         return res;
 435 }
 436
 437 static 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
 477 static 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
 494 static 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
 519 const 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
 528 int 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
 556 void 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 }