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