VFS accounting: add in-memory storage counters
authorFrancois Tigeot <ftigeot@wolfpond.org>
Sat, 13 Aug 2011 09:34:39 +0000 (11:34 +0200)
committerFrançois Tigeot <ftigeot@wolfpond.org>
Sat, 10 Dec 2011 22:07:49 +0000 (23:07 +0100)
* Use a red-black tree of small arrays to store uid and gid accounting
  information.
  User and group ids often come in small groups of consecutive numbers;
  small arrays have a high probability of having more than one element
  used at the same time, reducing pointer chasing in the binary tree.

* Also use a global per mount-point counter

* Only enable data collection for volumes which have been properly
  initialized

* Protect the counters by a per mount-point spinlock

sys/kern/vfs_default.c
sys/kern/vfs_init.c
sys/kern/vfs_quota.c
sys/sys/mount.h
sys/sys/vfs_quota.h

index a32f77f..baa3888 100644 (file)
@@ -1484,8 +1484,6 @@ vfs_stdac_init(struct mount *mp)
        if (fstype_ok == 0)
                return (0);
 
-       kprintf("vfs_quota: enabling accounting for %s\n",
-                                       mp->mnt_stat.f_mntonname);
        vq_init(mp);
        return (0);
 }
@@ -1516,16 +1514,4 @@ vfs_stdac_done(struct mount *mp)
        return (0);
 }
 
-int
-vfs_stdaccount(struct mount *mp, uid_t uid, gid_t gid, int64_t delta)
-{
-       return(0);
-}
-
-int
-vfs_noaccount(struct mount *mp, uid_t uid, gid_t gid, int64_t delta)
-{
-       return(0);
-}
-
 /* end of vfs default ops */
index 020812b..11b2560 100644 (file)
@@ -428,9 +428,6 @@ vfs_register(struct vfsconf *vfc)
        if (vfsops->vfs_acdone == NULL) {
                vfsops->vfs_acdone = vfs_stdac_done;
        }
-       if (vfsops->vfs_account == NULL) {
-               vfsops->vfs_account = vfs_stdaccount;
-       }
 
        /*
         * Call init function for this VFS...
index c7aa371..fef0f33 100644 (file)
@@ -1,11 +1,11 @@
 /*
  * Copyright (c) 2011 François Tigeot <ftigeot@wolpond.org>
  * All rights reserved.
- * 
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
- * 
+ *
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
@@ -15,7 +15,7 @@
  * 3. Neither the name of The DragonFly Project nor the names of its
  *    contributors may be used to endorse or promote products derived
  *    from this software without specific, prior written permission.
- * 
+ *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 #include <sys/vnode.h>
 #include <sys/stat.h>
 #include <sys/vfs_quota.h>
+#include <sys/spinlock.h>
+#include <sys/spinlock2.h>
+
+/* in-memory accounting, red-black tree based */
+
+/* FIXME: code duplication caused by uid_t / gid_t differences */
+RB_PROTOTYPE(ac_utree, ac_unode, rb_entry, rb_ac_unode_cmp);
+RB_PROTOTYPE(ac_gtree, ac_gnode, rb_entry, rb_ac_gnode_cmp);
+
+static int
+rb_ac_unode_cmp(struct ac_unode *a, struct ac_unode *b);
+static int
+rb_ac_gnode_cmp(struct ac_gnode *a, struct ac_gnode *b);
+
+RB_GENERATE(ac_utree, ac_unode, rb_entry, rb_ac_unode_cmp);
+RB_GENERATE(ac_gtree, ac_gnode, rb_entry, rb_ac_gnode_cmp);
+
+struct ac_unode* unode_insert(struct mount*, uid_t);
+struct ac_gnode* gnode_insert(struct mount*, gid_t);
+
+static int
+rb_ac_unode_cmp(struct ac_unode *a, struct ac_unode *b)
+{
+       if (a->left_bits < b->left_bits)
+               return(-1);
+       else if (a->left_bits > b->left_bits)
+               return(1);
+       return(0);
+}
+
+static int
+rb_ac_gnode_cmp(struct ac_gnode *a, struct ac_gnode *b)
+{
+       if (a->left_bits < b->left_bits)
+               return(-1);
+       else if (a->left_bits > b->left_bits)
+               return(1);
+       return(0);
+}
+
+struct ac_unode*
+unode_insert(struct mount *mp, uid_t uid)
+{
+       struct ac_unode *unp, *res;
+
+       unp = kmalloc(sizeof(struct ac_unode),
+                               M_MOUNT, M_ZERO|M_WAITOK);
+
+       unp->left_bits = (uid >> ACCT_CHUNK_BITS);
+       res = RB_INSERT(ac_utree, &mp->mnt_acct.ac_uroot, unp);
+       KASSERT(res == NULL, ("unode_insert(): RB_INSERT didn't return NULL\n"));
+
+       return unp;
+}
+
+struct ac_gnode*
+gnode_insert(struct mount *mp, gid_t gid)
+{
+       struct ac_gnode *gnp, *res;
+
+       gnp = kmalloc(sizeof(struct ac_gnode),
+                               M_MOUNT, M_ZERO|M_WAITOK);
+
+       gnp->left_bits = (gid >> ACCT_CHUNK_BITS);
+       res = RB_INSERT(ac_gtree, &mp->mnt_acct.ac_groot, gnp);
+       KASSERT(res == NULL, ("gnode_insert(): RB_INSERT didn't return NULL\n"));
+
+       return gnp;
+}
 
 /* initializes global accounting data */
 void
 vq_init(struct mount *mp) {
+
+       /* initialize the rb trees */
+       RB_INIT(&mp->mnt_acct.ac_uroot);
+       RB_INIT(&mp->mnt_acct.ac_groot);
+       spin_init(&mp->mnt_acct.ac_spin);
+
+       mp->mnt_acct.ac_bytes = 0;
+
+       /* and enable data collection */
+       mp->mnt_op->vfs_account = vfs_stdaccount;
+       kprintf("vfs accounting enabled for %s\n",
+                               mp->mnt_stat.f_mntonname);
 }
 
 
 void
 vq_done(struct mount *mp) {
+       /* TODO: remove the rb trees here */
+}
+
+void
+vfs_stdaccount(struct mount *mp, uid_t uid, gid_t gid, int64_t delta)
+{
+       struct ac_unode ufind, *unp;
+       struct ac_gnode gfind, *gnp;
+
+       /* find or create address of chunk */
+       ufind.left_bits = (uid >> ACCT_CHUNK_BITS);
+       gfind.left_bits = (gid >> ACCT_CHUNK_BITS);
+
+       spin_lock(&mp->mnt_acct.ac_spin);
+
+       mp->mnt_acct.ac_bytes += delta;
+
+       if ((unp = RB_FIND(ac_utree, &mp->mnt_acct.ac_uroot, &ufind)) == NULL)
+               unp = unode_insert(mp, uid);
+       if ((gnp = RB_FIND(ac_gtree, &mp->mnt_acct.ac_groot, &gfind)) == NULL)
+               gnp = gnode_insert(mp, gid);
+
+       /* update existing chunk */
+       unp->uid_chunk[(uid & ACCT_CHUNK_MASK)] += delta;
+       gnp->gid_chunk[(gid & ACCT_CHUNK_MASK)] += delta;
+
+       spin_unlock(&mp->mnt_acct.ac_spin);
 }
index 2289880..44277be 100644 (file)
@@ -39,6 +39,7 @@
 #define _SYS_MOUNT_H_
 
 #include <sys/ucred.h>
+#include <sys/tree.h>
 
 #ifndef _KERNEL
 #if !defined(_POSIX_C_SOURCE) && !defined(_XOPEN_SOURCE)
@@ -144,6 +145,36 @@ struct bio_ops {
 };
 
 /*
+ * storage accounting
+ *
+ * uids and gids often come in contiguous blocks; use a small linear
+ * array as the basic in-memory accounting allocation unit
+ */
+#define ACCT_CHUNK_BITS        5
+#define ACCT_CHUNK_NIDS        (1<<ACCT_CHUNK_BITS)
+#define ACCT_CHUNK_MASK        (ACCT_CHUNK_NIDS - 1)
+
+struct ac_unode {
+       RB_ENTRY(ac_unode)      rb_entry;
+       uid_t                   left_bits;
+       uint64_t                uid_chunk[ACCT_CHUNK_NIDS];
+};
+
+struct ac_gnode {
+       RB_ENTRY(ac_gnode)      rb_entry;
+       gid_t                   left_bits;
+       uint64_t                gid_chunk[ACCT_CHUNK_NIDS];
+};
+
+struct vfs_acct {
+       RB_HEAD(ac_utree,ac_unode)      ac_uroot;
+       RB_HEAD(ac_gtree,ac_gnode)      ac_groot;
+       uint64_t                        ac_bytes;       /* total bytes used */
+       struct spinlock                 ac_spin;        /* protective spinlock */
+};
+
+
+/*
  * Structure per mounted file system.  Each mounted file system has an
  * array of operations and an instance record.  The file systems are
  * put on a doubly linked list.
@@ -209,6 +240,8 @@ struct mount {
        int16_t         mnt_streamid;           /* last streamid */
 
        struct bio_ops  *mnt_bioops;            /* BIO ops (hammer, softupd) */
+
+       struct vfs_acct mnt_acct;               /* vfs space accounting */
 };
 
 #endif /* _KERNEL || _KERNEL_STRUCTURES */
@@ -504,7 +537,7 @@ typedef int vfs_extattrctl_t(struct mount *mp, int cmd, struct vnode *vp,
                    struct ucred *cred);
 typedef int vfs_acinit_t(struct mount *mp);
 typedef int vfs_acdone_t(struct mount *mp);
-typedef int vfs_account_t(struct mount *mp,
+typedef void vfs_account_t(struct mount *mp,
                        uid_t uid, gid_t gid, int64_t delta);
 
 int vfs_mount(struct mount *mp, char *path, caddr_t data, struct ucred *cred);
index b4676cd..afc86aa 100644 (file)
@@ -2,13 +2,10 @@
  * Copyright (c) 2011 François Tigeot <ftigeot@wolpond.org>
  * All rights reserved.
  *
- * This code is derived from software contributed to The DragonFly Project
- * by François Tigeot <ftigeot@wolfpond.org>
- * 
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
- * 
+ *
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
@@ -18,7 +15,7 @@
  * 3. Neither the name of The DragonFly Project nor the names of its
  *    contributors may be used to endorse or promote products derived
  *    from this software without specific, prior written permission.
- * 
+ *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS