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 ovl_cleanup(upper->d_inode, dentry); 575 dput(dentry); 576 } 577 mutex_unlock(&upper->d_inode->i_mutex); 578 } 579