From 7d15906a7a159575b1983f7c1fadde4bd6266d29 Mon Sep 17 00:00:00 2001 From: Matthew Dillon Date: Thu, 25 Aug 2005 18:34:17 +0000 Subject: [PATCH] Implement FSMID. Use one of the spare 64 bit fields in the stat structure for the FSMID. The FSMID is a recursively updated field which allows one to determine whether a subdirectory hierarchy has changed simply by checking the base directory of the desired hierarchy. The new field is st_fsmid. The initial implementation stores the FSMID in the namecache, which means that the FSMID will indicate a false change if a namecache entry is destroyed and recreated. A more deterministic test can be made by holding a file or directory descriptor open. However, it should be noted that DragonFly implements a coherent and hierarchically consistent namecache so simply having a subdirectory or file open will prevent the namecache records from that point through to the root from being destroyed. The FSMID can be used to greatly reduce the directories that must be searched when synchronizing a filesystem. The immediate intention is to use it to provide a more efficient way to resynchronize a mirror (to generate journal records 'diff'ing the current filesystem against a mirror), to improve filesystem mirroring utilities, and to provide for an alternative backup strategy that involves generating a diff set between two filesystems. Normally such schemes would require the entire filesystem to be scanned, but with FSMID the number of directories that must be searched can be greatly reduced. TODO: It is desireable for the FSMID information to be stored more permanently in the inode to survive reboots and to not return false hits due to namecache thrash. Note that the FSMID facility does not work on an NFS client if the NFS server or some other client modifies the filesystem. --- sys/kern/vfs_cache.c | 37 ++++++++++++++++++++++++++++++++++++- sys/kern/vfs_syscalls.c | 13 ++++++++++++- sys/kern/vfs_vnops.c | 16 +++++++++++++--- sys/kern/vfs_vopops.c | 36 +++++++++++++++++++++++++++++++++++- sys/sys/namecache.h | 6 +++++- sys/sys/stat.h | 15 +++++++++++++-- 6 files changed, 114 insertions(+), 9 deletions(-) diff --git a/sys/kern/vfs_cache.c b/sys/kern/vfs_cache.c index 9ebd5873f0..7ccb1ce554 100644 --- a/sys/kern/vfs_cache.c +++ b/sys/kern/vfs_cache.c @@ -67,7 +67,7 @@ * * @(#)vfs_cache.c 8.5 (Berkeley) 3/22/95 * $FreeBSD: src/sys/kern/vfs_cache.c,v 1.42.2.6 2001/10/05 20:07:03 dillon Exp $ - * $DragonFly: src/sys/kern/vfs_cache.c,v 1.54 2005/04/19 17:54:42 dillon Exp $ + * $DragonFly: src/sys/kern/vfs_cache.c,v 1.55 2005/08/25 18:34:14 dillon Exp $ */ #include @@ -112,6 +112,7 @@ MALLOC_DEFINE(M_VFSCACHE, "vfscache", "VFS name cache entries"); static LIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */ static struct namecache_list ncneglist; /* instead of vnode */ +static int64_t last_fsmid; /* node change id */ /* * ncvp_debug - debug cache_fromvp(). This is used by the NFS server @@ -294,6 +295,7 @@ cache_alloc(int nlen) ncp->nc_flag = NCF_UNRESOLVED; ncp->nc_error = ENOTCONN; /* needs to be resolved */ ncp->nc_refs = 1; + ncp->nc_fsmid = ++last_fsmid; TAILQ_INIT(&ncp->nc_list); cache_lock(ncp); return(ncp); @@ -822,6 +824,39 @@ again: return(error); } +void +cache_update_fsmid(struct namecache *ncp) +{ + struct vnode *vp; + struct namecache *scan; + int64_t fsmid = ++last_fsmid; + + if ((vp = ncp->nc_vp) != NULL) { + TAILQ_FOREACH(ncp, &vp->v_namecache, nc_vnode) { + for (scan = ncp; scan; scan = scan->nc_parent) + scan->nc_fsmid = fsmid; + } + } else { + while (ncp) { + ncp->nc_fsmid = fsmid; + ncp = ncp->nc_parent; + } + } +} + +void +cache_update_fsmid_vp(struct vnode *vp) +{ + struct namecache *ncp; + struct namecache *scan; + int64_t fsmid = ++last_fsmid; + + TAILQ_FOREACH(ncp, &vp->v_namecache, nc_vnode) { + for (scan = ncp; scan; scan = scan->nc_parent) + scan->nc_fsmid = fsmid; + } +} + /* * Convert a directory vnode to a namecache record without any other * knowledge of the topology. This ONLY works with directory vnodes and diff --git a/sys/kern/vfs_syscalls.c b/sys/kern/vfs_syscalls.c index 51653221bf..494fb84bb0 100644 --- a/sys/kern/vfs_syscalls.c +++ b/sys/kern/vfs_syscalls.c @@ -37,7 +37,7 @@ * * @(#)vfs_syscalls.c 8.13 (Berkeley) 4/15/94 * $FreeBSD: src/sys/kern/vfs_syscalls.c,v 1.151.2.18 2003/04/04 20:35:58 tegge Exp $ - * $DragonFly: src/sys/kern/vfs_syscalls.c,v 1.69 2005/08/15 07:26:47 dillon Exp $ + * $DragonFly: src/sys/kern/vfs_syscalls.c,v 1.70 2005/08/25 18:34:14 dillon Exp $ */ #include @@ -1891,6 +1891,17 @@ again: goto again; } } + + /* + * The fsmid can be used to detect that something has changed + * at or below the specified file/dir in the filesystem. At + * a minimum the fsmid is synthesized by the kernel via the + * namecache and requires an open descriptor for deterministic + * operation. Filesystems supporting fsmid may store it in the + * inode, but this is not a requirement. + */ + st->st_fsmid = nd->nl_ncp->nc_fsmid; + vput(vp); return (error); } diff --git a/sys/kern/vfs_vnops.c b/sys/kern/vfs_vnops.c index ce83bee5f8..b748c73ece 100644 --- a/sys/kern/vfs_vnops.c +++ b/sys/kern/vfs_vnops.c @@ -37,7 +37,7 @@ * * @(#)vfs_vnops.c 8.2 (Berkeley) 1/21/94 * $FreeBSD: src/sys/kern/vfs_vnops.c,v 1.87.2.13 2002/12/29 18:19:53 dillon Exp $ - * $DragonFly: src/sys/kern/vfs_vnops.c,v 1.30 2005/07/13 01:38:50 dillon Exp $ + * $DragonFly: src/sys/kern/vfs_vnops.c,v 1.31 2005/08/25 18:34:14 dillon Exp $ */ #include @@ -722,6 +722,7 @@ vn_stat(struct vnode *vp, struct stat *sb, struct thread *td) { struct vattr vattr; struct vattr *vap; + struct namecache *ncp; int error; u_short mode; dev_t dev; @@ -735,8 +736,7 @@ vn_stat(struct vnode *vp, struct stat *sb, struct thread *td) * Zero the spare stat fields */ sb->st_lspare = 0; - sb->st_qspare[0] = 0; - sb->st_qspare[1] = 0; + sb->st_qspare = 0; /* * Copy from vattr table @@ -846,6 +846,16 @@ vn_stat(struct vnode *vp, struct stat *sb, struct thread *td) #else sb->st_blocks = vap->va_bytes / S_BLKSIZE; #endif + + /* + * Set the fsmid from the namecache. Use the first available + * namecache record. + */ + if ((ncp = TAILQ_FIRST(&vp->v_namecache)) != NULL) + sb->st_fsmid = ncp->nc_fsmid; + else + sb->st_fsmid = 0; + return (0); } diff --git a/sys/kern/vfs_vopops.c b/sys/kern/vfs_vopops.c index 0756cf1fc4..4d619ce3c2 100644 --- a/sys/kern/vfs_vopops.c +++ b/sys/kern/vfs_vopops.c @@ -32,7 +32,7 @@ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $DragonFly: src/sys/kern/vfs_vopops.c,v 1.13 2004/12/29 02:40:02 dillon Exp $ + * $DragonFly: src/sys/kern/vfs_vopops.c,v 1.14 2005/08/25 18:34:14 dillon Exp $ */ #include @@ -474,6 +474,8 @@ vop_setattr(struct vop_ops *ops, struct vnode *vp, struct vattr *vap, ap.a_td = td; DO_OPS(ops, error, &ap, vop_setattr); + if (error == 0) + cache_update_fsmid_vp(vp); return(error); } @@ -510,6 +512,8 @@ vop_write(struct vop_ops *ops, struct vnode *vp, struct uio *uio, int ioflag, ap.a_cred = cred; DO_OPS(ops, error, &ap, vop_write); + if (error == 0) + cache_update_fsmid_vp(vp); return(error); } @@ -875,6 +879,8 @@ vop_strategy(struct vop_ops *ops, struct vnode *vp, struct buf *bp) ap.a_bp = bp; DO_OPS(ops, error, &ap, vop_strategy); + if (error == 0 && (bp->b_flags & B_READ) == 0) + cache_update_fsmid_vp(vp); return(error); } @@ -1001,6 +1007,8 @@ vop_putpages(struct vop_ops *ops, struct vnode *vp, vm_page_t *m, int count, ap.a_offset = offset; DO_OPS(ops, error, &ap, vop_putpages); + if (error == 0) + cache_update_fsmid_vp(vp); return(error); } @@ -1033,6 +1041,8 @@ vop_bwrite(struct vop_ops *ops, struct vnode *vp, struct buf *bp) ap.a_bp = bp; DO_OPS(ops, error, &ap, vop_bwrite); + if (error == 0) + cache_update_fsmid_vp(vp); return(error); } @@ -1071,6 +1081,8 @@ vop_setacl(struct vop_ops *ops, struct vnode *vp, acl_type_t type, ap.a_td = td; DO_OPS(ops, error, &ap, vop_setacl); + if (error == 0) + cache_update_fsmid_vp(vp); return(error); } @@ -1128,6 +1140,8 @@ vop_setextattr(struct vop_ops *ops, struct vnode *vp, char *name, ap.a_td = td; DO_OPS(ops, error, &ap, vop_setextattr); + if (error == 0) + cache_update_fsmid_vp(vp); return(error); } @@ -1264,6 +1278,8 @@ vop_ncreate(struct vop_ops *ops, struct namecache *ncp, ap.a_vap = vap; DO_OPS(ops, error, &ap, vop_ncreate); + if (error == 0 && *vpp) + cache_update_fsmid_vp(*vpp); return(error); } @@ -1290,6 +1306,8 @@ vop_nmkdir(struct vop_ops *ops, struct namecache *ncp, ap.a_vap = vap; DO_OPS(ops, error, &ap, vop_nmkdir); + if (error == 0 && *vpp) + cache_update_fsmid_vp(*vpp); return(error); } @@ -1316,6 +1334,8 @@ vop_nmknod(struct vop_ops *ops, struct namecache *ncp, ap.a_vap = vap; DO_OPS(ops, error, &ap, vop_nmknod); + if (error == 0 && *vpp) + cache_update_fsmid_vp(*vpp); return(error); } @@ -1342,6 +1362,8 @@ vop_nlink(struct vop_ops *ops, struct namecache *ncp, ap.a_cred = cred; DO_OPS(ops, error, &ap, vop_nlink); + if (error == 0) + cache_update_fsmid(ncp); return(error); } @@ -1371,6 +1393,8 @@ vop_nsymlink(struct vop_ops *ops, struct namecache *ncp, ap.a_target = target; DO_OPS(ops, error, &ap, vop_nsymlink); + if (error == 0) + cache_update_fsmid(ncp); return(error); } @@ -1395,6 +1419,8 @@ vop_nwhiteout(struct vop_ops *ops, struct namecache *ncp, ap.a_flags = flags; DO_OPS(ops, error, &ap, vop_nwhiteout); + if (error == 0) + cache_update_fsmid(ncp); return(error); } @@ -1417,6 +1443,8 @@ vop_nremove(struct vop_ops *ops, struct namecache *ncp, struct ucred *cred) ap.a_cred = cred; DO_OPS(ops, error, &ap, vop_nremove); + if (error == 0) + cache_update_fsmid(ncp); return(error); } @@ -1439,6 +1467,8 @@ vop_nrmdir(struct vop_ops *ops, struct namecache *ncp, struct ucred *cred) ap.a_cred = cred; DO_OPS(ops, error, &ap, vop_nrmdir); + if (error == 0) + cache_update_fsmid(ncp); return(error); } @@ -1466,6 +1496,10 @@ vop_nrename(struct vop_ops *ops, struct namecache *fncp, ap.a_cred = cred; DO_OPS(ops, error, &ap, vop_nrename); + if (error == 0) { + cache_update_fsmid(fncp); + cache_update_fsmid(tncp); + } return(error); } diff --git a/sys/sys/namecache.h b/sys/sys/namecache.h index 6b1fe8a55c..b7eec52e99 100644 --- a/sys/sys/namecache.h +++ b/sys/sys/namecache.h @@ -62,7 +62,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $DragonFly: src/sys/sys/namecache.h,v 1.19 2005/02/12 18:56:47 dillon Exp $ + * $DragonFly: src/sys/sys/namecache.h,v 1.20 2005/08/25 18:34:17 dillon Exp $ */ #ifndef _SYS_NAMECACHE_H_ @@ -113,6 +113,7 @@ struct namecache { int nc_exlocks; /* namespace locking */ struct thread *nc_locktd; /* namespace locking */ struct mount *nc_mount; /* associated mount for vopops */ + int64_t nc_fsmid; /* filesystem modified id */ }; typedef struct namecache *namecache_t; @@ -172,6 +173,9 @@ int cache_vget(struct namecache *, struct ucred *, int, struct vnode **); int cache_vref(struct namecache *, struct ucred *, struct vnode **); struct namecache *cache_fromdvp(struct vnode *, struct ucred *, int); int cache_fullpath(struct proc *, struct namecache *, char **, char **); +void cache_update_fsmid(struct namecache *); +void cache_update_fsmid_vp(struct vnode *); + #endif diff --git a/sys/sys/stat.h b/sys/sys/stat.h index d1fb4a5b25..417c0be0cb 100644 --- a/sys/sys/stat.h +++ b/sys/sys/stat.h @@ -33,7 +33,7 @@ * * @(#)stat.h 8.12 (Berkeley) 6/16/95 * $FreeBSD: src/sys/sys/stat.h,v 1.20 1999/12/29 04:24:47 peter Exp $ - * $DragonFly: src/sys/sys/stat.h,v 1.7 2005/08/02 13:03:55 joerg Exp $ + * $DragonFly: src/sys/sys/stat.h,v 1.8 2005/08/25 18:34:17 dillon Exp $ */ #ifndef _SYS_STAT_H_ @@ -53,6 +53,14 @@ #define __dev_t dev_t #endif +/* + * stat structure notes: + * + * (1) st_fsmid (DragonFly only). This is a DragonFly supported field that + * is incremented if the represented file or directory changes or, for + * directories, if any change is made within the directory or any sub- + * directory, recursively. + */ struct stat { ino_t st_ino; /* inode's number */ nlink_t st_nlink; /* number of hard links */ @@ -80,9 +88,12 @@ struct stat { u_int32_t st_flags; /* user defined flags for file */ u_int32_t st_gen; /* file generation number */ int32_t st_lspare; - int64_t st_qspare[2]; + int64_t st_fsmid; /* recursive change detect */ + int64_t st_qspare; }; +#define _ST_FSMID_PRESENT_ + #undef __dev_t #ifndef _POSIX_SOURCE -- 2.41.0