Implement FSMID. Use one of the spare 64 bit fields in the stat structure
authorMatthew Dillon <dillon@dragonflybsd.org>
Thu, 25 Aug 2005 18:34:17 +0000 (18:34 +0000)
committerMatthew Dillon <dillon@dragonflybsd.org>
Thu, 25 Aug 2005 18:34:17 +0000 (18:34 +0000)
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
sys/kern/vfs_syscalls.c
sys/kern/vfs_vnops.c
sys/kern/vfs_vopops.c
sys/sys/namecache.h
sys/sys/stat.h

index 9ebd587..7ccb1ce 100644 (file)
@@ -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 <sys/param.h>
@@ -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
index 5165322..494fb84 100644 (file)
@@ -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 <sys/param.h>
@@ -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);
 }
index ce83bee..b748c73 100644 (file)
@@ -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 <sys/param.h>
@@ -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);
 }
 
index 0756cf1..4d619ce 100644 (file)
@@ -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 <sys/param.h>
@@ -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);
 }
 
index 6b1fe8a..b7eec52 100644 (file)
@@ -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
 
index d1fb4a5..417c0be 100644 (file)
@@ -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_
 #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