2 * Copyright (C) 2005-2012 Junjiro R. Okajima
4 * This program, aufs is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 * virtual or vertical directory
25 static unsigned int calc_size(int nlen)
27 return ALIGN(sizeof(struct au_vdir_de) + nlen, sizeof(ino_t));
30 static int set_deblk_end(union au_vdir_deblk_p *p,
31 union au_vdir_deblk_p *deblk_end)
33 if (calc_size(0) <= deblk_end->deblk - p->deblk) {
34 p->de->de_str.len = 0;
38 return -1; /* error */
41 /* returns true or false */
42 static int is_deblk_end(union au_vdir_deblk_p *p,
43 union au_vdir_deblk_p *deblk_end)
45 if (calc_size(0) <= deblk_end->deblk - p->deblk)
46 return !p->de->de_str.len;
50 static unsigned char *last_deblk(struct au_vdir *vdir)
52 return vdir->vd_deblk[vdir->vd_nblk - 1];
55 /* ---------------------------------------------------------------------- */
57 /* estimate the apropriate size for name hash table */
58 unsigned int au_rdhash_est(loff_t sz)
66 if (sz < AUFS_RDHASH_DEF)
68 /* pr_info("n %u\n", n); */
73 * the allocated memory has to be freed by
74 * au_nhash_wh_free() or au_nhash_de_free().
76 int au_nhash_alloc(struct au_nhash *nhash, unsigned int num_hash, gfp_t gfp)
78 struct hlist_head *head;
81 head = kmalloc(sizeof(*nhash->nh_head) * num_hash, gfp);
83 nhash->nh_num = num_hash;
84 nhash->nh_head = head;
85 for (u = 0; u < num_hash; u++)
86 INIT_HLIST_HEAD(head++);
87 return 0; /* success */
93 static void nhash_count(struct hlist_head *head)
97 struct hlist_node *pos;
100 hlist_for_each(pos, head)
106 static void au_nhash_wh_do_free(struct hlist_head *head)
108 struct au_vdir_wh *tpos;
109 struct hlist_node *pos, *node;
111 hlist_for_each_entry_safe(tpos, pos, node, head, wh_hash) {
112 /* hlist_del(pos); */
117 static void au_nhash_de_do_free(struct hlist_head *head)
119 struct au_vdir_dehstr *tpos;
120 struct hlist_node *pos, *node;
122 hlist_for_each_entry_safe(tpos, pos, node, head, hash) {
123 /* hlist_del(pos); */
124 au_cache_free_vdir_dehstr(tpos);
128 static void au_nhash_do_free(struct au_nhash *nhash,
129 void (*free)(struct hlist_head *head))
132 struct hlist_head *head;
138 head = nhash->nh_head;
143 kfree(nhash->nh_head);
146 void au_nhash_wh_free(struct au_nhash *whlist)
148 au_nhash_do_free(whlist, au_nhash_wh_do_free);
151 static void au_nhash_de_free(struct au_nhash *delist)
153 au_nhash_do_free(delist, au_nhash_de_do_free);
156 /* ---------------------------------------------------------------------- */
158 int au_nhash_test_longer_wh(struct au_nhash *whlist, aufs_bindex_t btgt,
163 struct hlist_head *head;
164 struct au_vdir_wh *tpos;
165 struct hlist_node *pos;
169 head = whlist->nh_head;
170 for (u = 0; u < n; u++, head++)
171 hlist_for_each_entry(tpos, pos, head, wh_hash)
172 if (tpos->wh_bindex == btgt && ++num > limit)
177 static struct hlist_head *au_name_hash(struct au_nhash *nhash,
182 /* const unsigned int magic_bit = 12; */
184 AuDebugOn(!nhash->nh_num || !nhash->nh_head);
189 /* v = hash_long(v, magic_bit); */
191 return nhash->nh_head + v;
194 static int au_nhash_test_name(struct au_vdir_destr *str, const char *name,
197 return str->len == nlen && !memcmp(str->name, name, nlen);
200 /* returns found or not */
201 int au_nhash_test_known_wh(struct au_nhash *whlist, char *name, int nlen)
203 struct hlist_head *head;
204 struct au_vdir_wh *tpos;
205 struct hlist_node *pos;
206 struct au_vdir_destr *str;
208 head = au_name_hash(whlist, name, nlen);
209 hlist_for_each_entry(tpos, pos, head, wh_hash) {
211 AuDbg("%.*s\n", str->len, str->name);
212 if (au_nhash_test_name(str, name, nlen))
218 /* returns found(true) or not */
219 static int test_known(struct au_nhash *delist, char *name, int nlen)
221 struct hlist_head *head;
222 struct au_vdir_dehstr *tpos;
223 struct hlist_node *pos;
224 struct au_vdir_destr *str;
226 head = au_name_hash(delist, name, nlen);
227 hlist_for_each_entry(tpos, pos, head, hash) {
229 AuDbg("%.*s\n", str->len, str->name);
230 if (au_nhash_test_name(str, name, nlen))
236 static void au_shwh_init_wh(struct au_vdir_wh *wh, ino_t ino,
237 unsigned char d_type)
239 #ifdef CONFIG_AUFS_SHWH
241 wh->wh_type = d_type;
245 /* ---------------------------------------------------------------------- */
247 int au_nhash_append_wh(struct au_nhash *whlist, char *name, int nlen, ino_t ino,
248 unsigned int d_type, aufs_bindex_t bindex,
252 struct au_vdir_destr *str;
253 struct au_vdir_wh *wh;
255 AuDbg("%.*s\n", nlen, name);
256 AuDebugOn(!whlist->nh_num || !whlist->nh_head);
259 wh = kmalloc(sizeof(*wh) + nlen, GFP_NOFS);
264 wh->wh_bindex = bindex;
266 au_shwh_init_wh(wh, ino, d_type);
269 memcpy(str->name, name, nlen);
270 hlist_add_head(&wh->wh_hash, au_name_hash(whlist, name, nlen));
277 static int append_deblk(struct au_vdir *vdir)
281 const unsigned int deblk_sz = vdir->vd_deblk_sz;
282 union au_vdir_deblk_p p, deblk_end;
286 o = krealloc(vdir->vd_deblk, sizeof(*o) * (vdir->vd_nblk + 1),
292 p.deblk = kmalloc(deblk_sz, GFP_NOFS);
294 ul = vdir->vd_nblk++;
295 vdir->vd_deblk[ul] = p.deblk;
296 vdir->vd_last.ul = ul;
297 vdir->vd_last.p.deblk = p.deblk;
298 deblk_end.deblk = p.deblk + deblk_sz;
299 err = set_deblk_end(&p, &deblk_end);
306 static int append_de(struct au_vdir *vdir, char *name, int nlen, ino_t ino,
307 unsigned int d_type, struct au_nhash *delist)
311 const unsigned int deblk_sz = vdir->vd_deblk_sz;
312 union au_vdir_deblk_p p, *room, deblk_end;
313 struct au_vdir_dehstr *dehstr;
315 p.deblk = last_deblk(vdir);
316 deblk_end.deblk = p.deblk + deblk_sz;
317 room = &vdir->vd_last.p;
318 AuDebugOn(room->deblk < p.deblk || deblk_end.deblk <= room->deblk
319 || !is_deblk_end(room, &deblk_end));
321 sz = calc_size(nlen);
322 if (unlikely(sz > deblk_end.deblk - room->deblk)) {
323 err = append_deblk(vdir);
327 p.deblk = last_deblk(vdir);
328 deblk_end.deblk = p.deblk + deblk_sz;
330 AuDebugOn(room->deblk != p.deblk);
334 dehstr = au_cache_alloc_vdir_dehstr();
335 if (unlikely(!dehstr))
338 dehstr->str = &room->de->de_str;
339 hlist_add_head(&dehstr->hash, au_name_hash(delist, name, nlen));
340 room->de->de_ino = ino;
341 room->de->de_type = d_type;
342 room->de->de_str.len = nlen;
343 memcpy(room->de->de_str.name, name, nlen);
347 if (unlikely(set_deblk_end(room, &deblk_end)))
348 err = append_deblk(vdir);
355 /* ---------------------------------------------------------------------- */
357 void au_vdir_free(struct au_vdir *vdir)
359 unsigned char **deblk;
361 deblk = vdir->vd_deblk;
362 while (vdir->vd_nblk--)
364 kfree(vdir->vd_deblk);
365 au_cache_free_vdir(vdir);
368 static struct au_vdir *alloc_vdir(struct file *file)
370 struct au_vdir *vdir;
371 struct super_block *sb;
374 sb = file->f_dentry->d_sb;
378 vdir = au_cache_alloc_vdir();
382 vdir->vd_deblk = kzalloc(sizeof(*vdir->vd_deblk), GFP_NOFS);
383 if (unlikely(!vdir->vd_deblk))
386 vdir->vd_deblk_sz = au_sbi(sb)->si_rdblk;
387 if (!vdir->vd_deblk_sz) {
388 /* estimate the apropriate size for deblk */
389 vdir->vd_deblk_sz = au_dir_size(file, /*dentry*/NULL);
390 /* pr_info("vd_deblk_sz %u\n", vdir->vd_deblk_sz); */
393 vdir->vd_version = 0;
395 err = append_deblk(vdir);
397 return vdir; /* success */
399 kfree(vdir->vd_deblk);
402 au_cache_free_vdir(vdir);
408 static int reinit_vdir(struct au_vdir *vdir)
411 union au_vdir_deblk_p p, deblk_end;
413 while (vdir->vd_nblk > 1) {
414 kfree(vdir->vd_deblk[vdir->vd_nblk - 1]);
415 /* vdir->vd_deblk[vdir->vd_nblk - 1] = NULL; */
418 p.deblk = vdir->vd_deblk[0];
419 deblk_end.deblk = p.deblk + vdir->vd_deblk_sz;
420 err = set_deblk_end(&p, &deblk_end);
421 /* keep vd_dblk_sz */
422 vdir->vd_last.ul = 0;
423 vdir->vd_last.p.deblk = vdir->vd_deblk[0];
424 vdir->vd_version = 0;
430 /* ---------------------------------------------------------------------- */
432 #define AuFillVdir_CALLED 1
433 #define AuFillVdir_WHABLE (1 << 1)
434 #define AuFillVdir_SHWH (1 << 2)
435 #define au_ftest_fillvdir(flags, name) ((flags) & AuFillVdir_##name)
436 #define au_fset_fillvdir(flags, name) \
437 do { (flags) |= AuFillVdir_##name; } while (0)
438 #define au_fclr_fillvdir(flags, name) \
439 do { (flags) &= ~AuFillVdir_##name; } while (0)
441 #ifndef CONFIG_AUFS_SHWH
442 #undef AuFillVdir_SHWH
443 #define AuFillVdir_SHWH 0
446 struct fillvdir_arg {
448 struct au_vdir *vdir;
449 struct au_nhash delist;
450 struct au_nhash whlist;
451 aufs_bindex_t bindex;
456 static int fillvdir(void *__arg, const char *__name, int nlen,
457 loff_t offset __maybe_unused, u64 h_ino,
460 struct fillvdir_arg *arg = __arg;
461 char *name = (void *)__name;
462 struct super_block *sb;
464 const unsigned char shwh = !!au_ftest_fillvdir(arg->flags, SHWH);
467 sb = arg->file->f_dentry->d_sb;
468 au_fset_fillvdir(arg->flags, CALLED);
470 if (nlen <= AUFS_WH_PFX_LEN
471 || memcmp(name, AUFS_WH_PFX, AUFS_WH_PFX_LEN)) {
472 if (test_known(&arg->delist, name, nlen)
473 || au_nhash_test_known_wh(&arg->whlist, name, nlen))
474 goto out; /* already exists or whiteouted */
476 sb = arg->file->f_dentry->d_sb;
477 arg->err = au_ino(sb, arg->bindex, h_ino, d_type, &ino);
479 if (unlikely(nlen > AUFS_MAX_NAMELEN))
481 arg->err = append_de(arg->vdir, name, nlen, ino,
482 d_type, &arg->delist);
484 } else if (au_ftest_fillvdir(arg->flags, WHABLE)) {
485 name += AUFS_WH_PFX_LEN;
486 nlen -= AUFS_WH_PFX_LEN;
487 if (au_nhash_test_known_wh(&arg->whlist, name, nlen))
488 goto out; /* already whiteouted */
491 arg->err = au_wh_ino(sb, arg->bindex, h_ino, d_type,
494 if (nlen <= AUFS_MAX_NAMELEN + AUFS_WH_PFX_LEN)
496 arg->err = au_nhash_append_wh
497 (&arg->whlist, name, nlen, ino, d_type,
504 arg->vdir->vd_jiffy = jiffies;
506 AuTraceErr(arg->err);
510 static int au_handle_shwh(struct super_block *sb, struct au_vdir *vdir,
511 struct au_nhash *whlist, struct au_nhash *delist)
513 #ifdef CONFIG_AUFS_SHWH
516 struct hlist_head *head;
517 struct au_vdir_wh *tpos;
518 struct hlist_node *pos, *n;
520 struct au_vdir_destr *destr;
522 AuDebugOn(!au_opt_test(au_mntflags(sb), SHWH));
525 o = p = __getname_gfp(GFP_NOFS);
531 memcpy(p, AUFS_WH_PFX, AUFS_WH_PFX_LEN);
532 p += AUFS_WH_PFX_LEN;
533 for (u = 0; u < nh; u++) {
534 head = whlist->nh_head + u;
535 hlist_for_each_entry_safe(tpos, pos, n, head, wh_hash) {
536 destr = &tpos->wh_str;
537 memcpy(p, destr->name, destr->len);
538 err = append_de(vdir, o, destr->len + AUFS_WH_PFX_LEN,
539 tpos->wh_ino, tpos->wh_type, delist);
555 static int au_do_read_vdir(struct fillvdir_arg *arg)
560 aufs_bindex_t bend, bindex, bstart;
562 struct file *hf, *file;
563 struct super_block *sb;
566 sb = file->f_dentry->d_sb;
569 rdhash = au_sbi(sb)->si_rdhash;
571 rdhash = au_rdhash_est(au_dir_size(file, /*dentry*/NULL));
572 err = au_nhash_alloc(&arg->delist, rdhash, GFP_NOFS);
575 err = au_nhash_alloc(&arg->whlist, rdhash, GFP_NOFS);
582 if (au_opt_test(au_mntflags(sb), SHWH)) {
584 au_fset_fillvdir(arg->flags, SHWH);
586 bstart = au_fbstart(file);
587 bend = au_fbend_dir(file);
588 for (bindex = bstart; !err && bindex <= bend; bindex++) {
589 hf = au_hf_dir(file, bindex);
593 offset = vfsub_llseek(hf, 0, SEEK_SET);
595 if (unlikely(offset))
598 arg->bindex = bindex;
599 au_fclr_fillvdir(arg->flags, WHABLE);
602 && au_br_whable(au_sbr_perm(sb, bindex))))
603 au_fset_fillvdir(arg->flags, WHABLE);
606 au_fclr_fillvdir(arg->flags, CALLED);
608 err = vfsub_readdir(hf, fillvdir, arg);
611 } while (!err && au_ftest_fillvdir(arg->flags, CALLED));
615 err = au_handle_shwh(sb, arg->vdir, &arg->whlist, &arg->delist);
617 au_nhash_wh_free(&arg->whlist);
620 au_nhash_de_free(&arg->delist);
625 static int read_vdir(struct file *file, int may_read)
628 unsigned long expire;
629 unsigned char do_read;
630 struct fillvdir_arg arg;
632 struct au_vdir *vdir, *allocated;
635 inode = file->f_dentry->d_inode;
637 SiMustAnyLock(inode->i_sb);
641 expire = au_sbi(inode->i_sb)->si_rdcache;
642 vdir = au_ivdir(inode);
645 vdir = alloc_vdir(file);
652 && (inode->i_version != vdir->vd_version
653 || time_after(jiffies, vdir->vd_jiffy + expire))) {
655 err = reinit_vdir(vdir);
661 return 0; /* success */
665 err = au_do_read_vdir(&arg);
667 /* file->f_pos = 0; */
668 vdir->vd_version = inode->i_version;
669 vdir->vd_last.ul = 0;
670 vdir->vd_last.p.deblk = vdir->vd_deblk[0];
672 au_set_ivdir(inode, allocated);
673 } else if (allocated)
674 au_vdir_free(allocated);
680 static int copy_vdir(struct au_vdir *tgt, struct au_vdir *src)
684 const unsigned int deblk_sz = src->vd_deblk_sz;
686 AuDebugOn(tgt->vd_nblk != 1);
689 if (tgt->vd_nblk < src->vd_nblk) {
692 p = krealloc(tgt->vd_deblk, sizeof(*p) * src->vd_nblk,
699 if (tgt->vd_deblk_sz != deblk_sz) {
702 tgt->vd_deblk_sz = deblk_sz;
703 p = krealloc(tgt->vd_deblk[0], deblk_sz, GFP_NOFS);
706 tgt->vd_deblk[0] = p;
708 memcpy(tgt->vd_deblk[0], src->vd_deblk[0], deblk_sz);
709 tgt->vd_version = src->vd_version;
710 tgt->vd_jiffy = src->vd_jiffy;
713 for (ul = 1; ul < n; ul++) {
714 tgt->vd_deblk[ul] = kmemdup(src->vd_deblk[ul], deblk_sz,
716 if (unlikely(!tgt->vd_deblk[ul]))
721 tgt->vd_last.ul = tgt->vd_last.ul;
722 tgt->vd_last.p.deblk = tgt->vd_deblk[tgt->vd_last.ul];
723 tgt->vd_last.p.deblk += src->vd_last.p.deblk
724 - src->vd_deblk[src->vd_last.ul];
726 return 0; /* success */
729 rerr = reinit_vdir(tgt);
734 int au_vdir_init(struct file *file)
738 struct au_vdir *vdir_cache, *allocated;
740 err = read_vdir(file, !file->f_pos);
745 vdir_cache = au_fvdir_cache(file);
747 vdir_cache = alloc_vdir(file);
748 err = PTR_ERR(vdir_cache);
749 if (IS_ERR(vdir_cache))
751 allocated = vdir_cache;
752 } else if (!file->f_pos && vdir_cache->vd_version != file->f_version) {
753 err = reinit_vdir(vdir_cache);
757 return 0; /* success */
759 inode = file->f_dentry->d_inode;
760 err = copy_vdir(vdir_cache, au_ivdir(inode));
762 file->f_version = inode->i_version;
764 au_set_fvdir_cache(file, allocated);
765 } else if (allocated)
766 au_vdir_free(allocated);
772 static loff_t calc_offset(struct au_vdir *vdir)
775 union au_vdir_deblk_p p;
777 p.deblk = vdir->vd_deblk[vdir->vd_last.ul];
778 offset = vdir->vd_last.p.deblk - p.deblk;
779 offset += vdir->vd_deblk_sz * vdir->vd_last.ul;
783 /* returns true or false */
784 static int seek_vdir(struct file *file)
787 unsigned int deblk_sz;
790 union au_vdir_deblk_p p, deblk_end;
791 struct au_vdir *vdir_cache;
794 vdir_cache = au_fvdir_cache(file);
795 offset = calc_offset(vdir_cache);
796 AuDbg("offset %lld\n", offset);
797 if (file->f_pos == offset)
800 vdir_cache->vd_last.ul = 0;
801 vdir_cache->vd_last.p.deblk = vdir_cache->vd_deblk[0];
806 deblk_sz = vdir_cache->vd_deblk_sz;
807 ul = div64_u64(file->f_pos, deblk_sz);
808 AuDbg("ul %lu\n", ul);
809 if (ul >= vdir_cache->vd_nblk)
812 n = vdir_cache->vd_nblk;
813 for (; ul < n; ul++) {
814 p.deblk = vdir_cache->vd_deblk[ul];
815 deblk_end.deblk = p.deblk + deblk_sz;
818 while (!is_deblk_end(&p, &deblk_end) && offset < file->f_pos) {
821 l = calc_size(p.de->de_str.len);
825 if (!is_deblk_end(&p, &deblk_end)) {
827 vdir_cache->vd_last.ul = ul;
828 vdir_cache->vd_last.p = p;
839 int au_vdir_fill_de(struct file *file, void *dirent, filldir_t filldir)
842 unsigned int l, deblk_sz;
843 union au_vdir_deblk_p deblk_end;
844 struct au_vdir *vdir_cache;
845 struct au_vdir_de *de;
847 vdir_cache = au_fvdir_cache(file);
848 if (!seek_vdir(file))
851 deblk_sz = vdir_cache->vd_deblk_sz;
853 deblk_end.deblk = vdir_cache->vd_deblk[vdir_cache->vd_last.ul];
854 deblk_end.deblk += deblk_sz;
855 while (!is_deblk_end(&vdir_cache->vd_last.p, &deblk_end)) {
856 de = vdir_cache->vd_last.p.de;
857 AuDbg("%.*s, off%lld, i%lu, dt%d\n",
858 de->de_str.len, de->de_str.name, file->f_pos,
859 (unsigned long)de->de_ino, de->de_type);
860 err = filldir(dirent, de->de_str.name, de->de_str.len,
861 file->f_pos, de->de_ino, de->de_type);
864 /* todo: ignore the error caused by udba? */
869 l = calc_size(de->de_str.len);
870 vdir_cache->vd_last.p.deblk += l;
873 if (vdir_cache->vd_last.ul < vdir_cache->vd_nblk - 1) {
874 vdir_cache->vd_last.ul++;
875 vdir_cache->vd_last.p.deblk
876 = vdir_cache->vd_deblk[vdir_cache->vd_last.ul];
877 file->f_pos = deblk_sz * vdir_cache->vd_last.ul;