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