Module Name: src
Committed By: reinoud
Date: Tue Jul 7 10:23:36 UTC 2009
Modified Files:
src/sys/fs/udf: udf.h udf_subr.c udf_subr.h udf_vfsops.c udf_vnops.c
Log Message:
Replace the old hashtable and sorted list implemenation by a RB-tree.
Benefits are significant speed improvements on node creation/insertion while
keeping the lookup times low and still allowing sequential iteration over the
nodes.
To generate a diff of this commit:
cvs rdiff -u -r1.35 -r1.36 src/sys/fs/udf/udf.h
cvs rdiff -u -r1.97 -r1.98 src/sys/fs/udf/udf_subr.c
cvs rdiff -u -r1.16 -r1.17 src/sys/fs/udf/udf_subr.h
cvs rdiff -u -r1.58 -r1.59 src/sys/fs/udf/udf_vfsops.c
cvs rdiff -u -r1.50 -r1.51 src/sys/fs/udf/udf_vnops.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/fs/udf/udf.h
diff -u src/sys/fs/udf/udf.h:1.35 src/sys/fs/udf/udf.h:1.36
--- src/sys/fs/udf/udf.h:1.35 Mon Jul 6 17:08:04 2009
+++ src/sys/fs/udf/udf.h Tue Jul 7 10:23:36 2009
@@ -1,4 +1,4 @@
-/* $NetBSD: udf.h,v 1.35 2009/07/06 17:08:04 reinoud Exp $ */
+/* $NetBSD: udf.h,v 1.36 2009/07/07 10:23:36 reinoud Exp $ */
/*
* Copyright (c) 2006, 2008 Reinoud Zandijk
@@ -30,6 +30,7 @@
#define _FS_UDF_UDF_H_
#include <sys/queue.h>
+#include <sys/rb.h>
#include <sys/uio.h>
#include <sys/mutex.h>
@@ -333,8 +334,7 @@
/* hash table to lookup icb -> udf_node and sorted list for sync */
kmutex_t ihash_lock;
kmutex_t get_node_lock;
- LIST_HEAD(, udf_node) udf_nodes[UDF_INODE_HASHSIZE];
- LIST_HEAD(, udf_node) sorted_udf_nodes; /* sorted sync list */
+ struct rb_tree udf_node_tree;
/* syncing */
int syncing; /* are we syncing? */
@@ -354,6 +354,11 @@
};
+#define RBTOUDFNODE(node) \
+ ((node) ? \
+ (void *)((uintptr_t)(node) - offsetof(struct udf_node, rbnode)) \
+ : NULL)
+
/*
* UDF node describing a file/directory.
*
@@ -369,6 +374,9 @@
char const *lock_fname;
int lock_lineno;
+ /* rb_node for fast lookup and fast sequentual visiting */
+ struct rb_node rbnode;
+
/* one of `fe' or `efe' can be set, not both (UDF file entry dscr.) */
struct file_entry *fe;
struct extfile_entry *efe;
Index: src/sys/fs/udf/udf_subr.c
diff -u src/sys/fs/udf/udf_subr.c:1.97 src/sys/fs/udf/udf_subr.c:1.98
--- src/sys/fs/udf/udf_subr.c:1.97 Mon Jul 6 17:06:57 2009
+++ src/sys/fs/udf/udf_subr.c Tue Jul 7 10:23:36 2009
@@ -1,4 +1,4 @@
-/* $NetBSD: udf_subr.c,v 1.97 2009/07/06 17:06:57 reinoud Exp $ */
+/* $NetBSD: udf_subr.c,v 1.98 2009/07/07 10:23:36 reinoud Exp $ */
/*
* Copyright (c) 2006, 2008 Reinoud Zandijk
@@ -29,7 +29,7 @@
#include <sys/cdefs.h>
#ifndef lint
-__KERNEL_RCSID(0, "$NetBSD: udf_subr.c,v 1.97 2009/07/06 17:06:57 reinoud Exp $");
+__KERNEL_RCSID(0, "$NetBSD: udf_subr.c,v 1.98 2009/07/07 10:23:36 reinoud Exp $");
#endif /* not lint */
@@ -3366,7 +3366,7 @@
/* To make absolutely sure we are NOT returning zero, add one :) */
long
-udf_calchash(struct long_ad *icbptr)
+udf_get_node_id(const struct long_ad *icbptr)
{
/* ought to be enough since each mountpoint has its own chain */
return udf_rw32(icbptr->loc.lb_num) + 1;
@@ -3374,120 +3374,102 @@
int
-udf_check_icb_equal(struct long_ad *a, struct long_ad *b)
+udf_compare_icb(const struct long_ad *a, const struct long_ad *b)
{
- return (a->loc.lb_num == b->loc.lb_num &&
- a->loc.part_num == b->loc.part_num);
+ if (udf_rw16(a->loc.part_num) < udf_rw16(b->loc.part_num))
+ return -1;
+ if (udf_rw16(a->loc.part_num) > udf_rw16(b->loc.part_num))
+ return 1;
+
+ if (udf_rw32(a->loc.lb_num) < udf_rw32(b->loc.lb_num))
+ return -1;
+ if (udf_rw32(a->loc.lb_num) > udf_rw32(b->loc.lb_num))
+ return 1;
+
+ return 0;
}
-static struct udf_node *
-udf_hash_lookup(struct udf_mount *ump, struct long_ad *icbptr)
+static int
+udf_compare_rbnodes(const struct rb_node *a, const struct rb_node *b)
{
- struct udf_node *node;
- struct vnode *vp;
- uint32_t hashline;
-
-loop:
- mutex_enter(&ump->ihash_lock);
+ struct udf_node *a_node = RBTOUDFNODE(a);
+ struct udf_node *b_node = RBTOUDFNODE(b);
- hashline = udf_calchash(icbptr) & UDF_INODE_HASHMASK;
- LIST_FOREACH(node, &ump->udf_nodes[hashline], hashchain) {
- assert(node);
- if (udf_check_icb_equal(&node->loc, icbptr)) {
- vp = node->vnode;
- assert(vp);
- mutex_enter(&vp->v_interlock);
- mutex_exit(&ump->ihash_lock);
- if (vget(vp, LK_EXCLUSIVE | LK_INTERLOCK))
- goto loop;
- return node;
- }
- }
- mutex_exit(&ump->ihash_lock);
-
- return NULL;
+ return udf_compare_icb(&a_node->loc, &b_node->loc);
}
-static void
-udf_sorted_list_insert(struct udf_node *node)
+static int
+udf_compare_rbnode_icb(const struct rb_node *a, const void *key)
{
- struct udf_mount *ump;
- struct udf_node *s_node, *last_node;
- uint32_t loc, s_loc;
+ struct udf_node *a_node = RBTOUDFNODE(a);
+ const struct long_ad * const icb = key;
- ump = node->ump;
- last_node = NULL; /* XXX gcc */
+ return udf_compare_icb(&a_node->loc, icb);
+}
- if (LIST_EMPTY(&ump->sorted_udf_nodes)) {
- LIST_INSERT_HEAD(&ump->sorted_udf_nodes, node, sortchain);
- return;
- }
- /*
- * We sort on logical block number here and not on physical block
- * number here. Ideally we should go for the physical block nr to get
- * better sync performance though this sort will ensure that packets
- * won't get spit up unnessisarily.
- */
+static const struct rb_tree_ops udf_node_rbtree_ops = {
+ .rbto_compare_nodes = udf_compare_rbnodes,
+ .rbto_compare_key = udf_compare_rbnode_icb,
+};
- loc = udf_rw32(node->loc.loc.lb_num);
- LIST_FOREACH(s_node, &ump->sorted_udf_nodes, sortchain) {
- s_loc = udf_rw32(s_node->loc.loc.lb_num);
- if (s_loc > loc) {
- LIST_INSERT_BEFORE(s_node, node, sortchain);
- return;
- }
- last_node = s_node;
- }
- LIST_INSERT_AFTER(last_node, node, sortchain);
+
+void
+udf_init_nodes_tree(struct udf_mount *ump)
+{
+ rb_tree_init(&ump->udf_node_tree, &udf_node_rbtree_ops);
}
-static void
-udf_register_node(struct udf_node *node)
+static struct udf_node *
+udf_node_lookup(struct udf_mount *ump, struct long_ad *icbptr)
{
- struct udf_mount *ump;
- struct udf_node *chk;
- uint32_t hashline;
+ struct rb_node *rb_node;
+ struct udf_node *udf_node;
+ struct vnode *vp;
- ump = node->ump;
+loop:
mutex_enter(&ump->ihash_lock);
- /* add to our hash table */
- hashline = udf_calchash(&node->loc) & UDF_INODE_HASHMASK;
-#ifdef DEBUG
- LIST_FOREACH(chk, &ump->udf_nodes[hashline], hashchain) {
- assert(chk);
- if (chk->loc.loc.lb_num == node->loc.loc.lb_num &&
- chk->loc.loc.part_num == node->loc.loc.part_num)
- panic("Double node entered\n");
+ rb_node = rb_tree_find_node(&ump->udf_node_tree, icbptr);
+ if (rb_node) {
+ udf_node = RBTOUDFNODE(rb_node);
+ vp = udf_node->vnode;
+ assert(vp);
+ mutex_enter(&vp->v_interlock);
+ mutex_exit(&ump->ihash_lock);
+ if (vget(vp, LK_EXCLUSIVE | LK_INTERLOCK))
+ goto loop;
+ return udf_node;
}
-#else
- chk = NULL;
-#endif
- LIST_INSERT_HEAD(&ump->udf_nodes[hashline], node, hashchain);
-
- /* add to our sorted list */
- udf_sorted_list_insert(node);
-
mutex_exit(&ump->ihash_lock);
+
+ return NULL;
}
static void
-udf_deregister_node(struct udf_node *node)
+udf_register_node(struct udf_node *udf_node)
{
- struct udf_mount *ump;
+ struct udf_mount *ump = udf_node->ump;
- ump = node->ump;
+ /* add node to the rb tree */
mutex_enter(&ump->ihash_lock);
+ rb_tree_insert_node(&ump->udf_node_tree, &udf_node->rbnode);
+ mutex_exit(&ump->ihash_lock);
+}
- /* from hash and sorted list */
- LIST_REMOVE(node, hashchain);
- LIST_REMOVE(node, sortchain);
+static void
+udf_deregister_node(struct udf_node *udf_node)
+{
+ struct udf_mount *ump = udf_node->ump;
+
+ /* remove node from the rb tree */
+ mutex_enter(&ump->ihash_lock);
+ rb_tree_remove_node(&ump->udf_node_tree, &udf_node->rbnode);
mutex_exit(&ump->ihash_lock);
}
@@ -5274,7 +5256,7 @@
/* lookup in hash table */
assert(ump);
assert(node_icb_loc);
- udf_node = udf_hash_lookup(ump, node_icb_loc);
+ udf_node = udf_node_lookup(ump, node_icb_loc);
if (udf_node) {
DPRINTF(NODE, ("\tgot it from the hash!\n"));
/* vnode is returned locked */
@@ -6319,7 +6301,7 @@
if (fid->file_char & UDF_FILE_CHAR_PAR)
strcpy(dirent->d_name, "..");
- dirent->d_fileno = udf_calchash(&fid->icb); /* inode hash XXX */
+ dirent->d_fileno = udf_get_node_id(&fid->icb); /* inode hash XXX */
dirent->d_namlen = strlen(dirent->d_name);
dirent->d_reclen = _DIRENT_SIZE(dirent);
@@ -6355,7 +6337,7 @@
KASSERT(mutex_owned(&mntvnode_lock));
DPRINTF(SYNC, ("sync_pass %d\n", pass));
- udf_node = LIST_FIRST(&ump->sorted_udf_nodes);
+ udf_node = RBTOUDFNODE(RB_TREE_MIN(&ump->udf_node_tree));
for (;udf_node; udf_node = n_udf_node) {
DPRINTF(SYNC, ("."));
@@ -6363,7 +6345,10 @@
vp = udf_node->vnode;
mutex_enter(&vp->v_interlock);
- n_udf_node = LIST_NEXT(udf_node, sortchain);
+ n_udf_node = RBTOUDFNODE(rb_tree_iterate(
+ &ump->udf_node_tree, &udf_node->rbnode,
+ RB_DIR_RIGHT));
+
if (n_udf_node)
n_udf_node->i_flags |= IN_SYNCED;
Index: src/sys/fs/udf/udf_subr.h
diff -u src/sys/fs/udf/udf_subr.h:1.16 src/sys/fs/udf/udf_subr.h:1.17
--- src/sys/fs/udf/udf_subr.h:1.16 Thu Jun 25 17:16:33 2009
+++ src/sys/fs/udf/udf_subr.h Tue Jul 7 10:23:36 2009
@@ -1,4 +1,4 @@
-/* $NetBSD: udf_subr.h,v 1.16 2009/06/25 17:16:33 reinoud Exp $ */
+/* $NetBSD: udf_subr.h,v 1.17 2009/07/07 10:23:36 reinoud Exp $ */
/*
* Copyright (c) 2006, 2008 Reinoud Zandijk
@@ -182,8 +182,9 @@
struct timespec *mod, struct timespec *birth, int updflags);
/* helpers and converters */
-long udf_calchash(struct long_ad *icbptr); /* for `inode' numbering */
-int udf_check_icb_equal(struct long_ad *a, struct long_ad *b);
+void udf_init_nodes_tree(struct udf_mount *ump);
+long udf_get_node_id(const struct long_ad *icbptr); /* for `inode' numbering */
+int udf_compare_icb(const struct long_ad *a, const struct long_ad *b);
uint32_t udf_getaccessmode(struct udf_node *node);
void udf_setaccessmode(struct udf_node *udf_node, mode_t mode);
void udf_getownership(struct udf_node *udf_node, uid_t *uidp, gid_t *gidp);
Index: src/sys/fs/udf/udf_vfsops.c
diff -u src/sys/fs/udf/udf_vfsops.c:1.58 src/sys/fs/udf/udf_vfsops.c:1.59
--- src/sys/fs/udf/udf_vfsops.c:1.58 Mon Jun 29 05:08:17 2009
+++ src/sys/fs/udf/udf_vfsops.c Tue Jul 7 10:23:36 2009
@@ -1,4 +1,4 @@
-/* $NetBSD: udf_vfsops.c,v 1.58 2009/06/29 05:08:17 dholland Exp $ */
+/* $NetBSD: udf_vfsops.c,v 1.59 2009/07/07 10:23:36 reinoud Exp $ */
/*
* Copyright (c) 2006, 2008 Reinoud Zandijk
@@ -28,7 +28,7 @@
#include <sys/cdefs.h>
#ifndef lint
-__KERNEL_RCSID(0, "$NetBSD: udf_vfsops.c,v 1.58 2009/06/29 05:08:17 dholland Exp $");
+__KERNEL_RCSID(0, "$NetBSD: udf_vfsops.c,v 1.59 2009/07/07 10:23:36 reinoud Exp $");
#endif /* not lint */
@@ -565,7 +565,7 @@
struct udf_mount *ump;
uint32_t sector_size, lb_size, bshift;
uint32_t logvol_integrity;
- int num_anchors, error, lst;
+ int num_anchors, error;
/* flush out any old buffers remaining from a previous use. */
if ((error = vinvalbuf(devvp, V_SAVE, l->l_cred, l, 0, 0)))
@@ -578,6 +578,7 @@
mp->mnt_stat.f_fsid = mp->mnt_stat.f_fsidx.__fsid_val[0];
mp->mnt_stat.f_namemax = UDF_MAX_NAMELEN;
mp->mnt_flag |= MNT_LOCAL;
+// mp->mnt_iflag |= IMNT_MPSAFE;
/* allocate udf part of mount structure; malloc always succeeds */
ump = malloc(sizeof(struct udf_mount), M_UDFMNT, M_WAITOK | M_ZERO);
@@ -589,10 +590,8 @@
mutex_init(&ump->allocate_mutex, MUTEX_DEFAULT, IPL_NONE);
cv_init(&ump->dirtynodes_cv, "udfsync2");
- /* init `ino_t' to udf_node hash table and other lists */
- for (lst = 0; lst < UDF_INODE_HASHSIZE; lst++) {
- LIST_INIT(&ump->udf_nodes[lst]);
- }
+ /* init rbtree for nodes, ordered by their icb address (long_ad) */
+ udf_init_nodes_tree(ump);
/* set up linkage */
mp->mnt_data = ump;
Index: src/sys/fs/udf/udf_vnops.c
diff -u src/sys/fs/udf/udf_vnops.c:1.50 src/sys/fs/udf/udf_vnops.c:1.51
--- src/sys/fs/udf/udf_vnops.c:1.50 Mon Jul 6 17:06:57 2009
+++ src/sys/fs/udf/udf_vnops.c Tue Jul 7 10:23:36 2009
@@ -1,4 +1,4 @@
-/* $NetBSD: udf_vnops.c,v 1.50 2009/07/06 17:06:57 reinoud Exp $ */
+/* $NetBSD: udf_vnops.c,v 1.51 2009/07/07 10:23:36 reinoud Exp $ */
/*
* Copyright (c) 2006, 2008 Reinoud Zandijk
@@ -32,7 +32,7 @@
#include <sys/cdefs.h>
#ifndef lint
-__KERNEL_RCSID(0, "$NetBSD: udf_vnops.c,v 1.50 2009/07/06 17:06:57 reinoud Exp $");
+__KERNEL_RCSID(0, "$NetBSD: udf_vnops.c,v 1.51 2009/07/07 10:23:36 reinoud Exp $");
#endif /* not lint */
@@ -561,7 +561,7 @@
if (uio->uio_offset == 0) {
DPRINTF(READDIR, ("\t'.' inserted\n"));
strcpy(dirent->d_name, ".");
- dirent->d_fileno = udf_calchash(&udf_node->loc);
+ dirent->d_fileno = udf_get_node_id(&udf_node->loc);
dirent->d_type = DT_DIR;
dirent->d_namlen = strlen(dirent->d_name);
dirent->d_reclen = _DIRENT_SIZE(dirent);
@@ -889,7 +889,7 @@
vap->va_uid = uid;
vap->va_gid = gid;
vap->va_fsid = vp->v_mount->mnt_stat.f_fsidx.__fsid_val[0];
- vap->va_fileid = udf_calchash(&udf_node->loc); /* inode hash XXX */
+ vap->va_fileid = udf_get_node_id(&udf_node->loc); /* inode hash XXX */
vap->va_size = filesize;
vap->va_blocksize = udf_node->ump->discinfo.sector_size; /* wise? */
@@ -1871,13 +1871,13 @@
root_icb = &ump->fileset_desc->rootdir_icb;
/* if nodes are equal, it is no use looking */
- if (udf_check_icb_equal(&source->loc, &target->loc)) {
+ if (udf_compare_icb(&source->loc, &target->loc) == 0) {
error = EEXIST;
goto out;
}
/* nothing can exist before the root */
- if (udf_check_icb_equal(root_icb, &target->loc)) {
+ if (udf_compare_icb(root_icb, &target->loc) == 0) {
error = 0;
goto out;
}
@@ -1905,13 +1905,13 @@
goto out;
/* did we encounter source node? */
- if (udf_check_icb_equal(&icb_loc, &source->loc)) {
+ if (udf_compare_icb(&icb_loc, &source->loc) == 0) {
error = EINVAL;
goto out;
}
/* did we encounter the root node? */
- if (udf_check_icb_equal(&icb_loc, root_icb)) {
+ if (udf_compare_icb(&icb_loc, root_icb) == 0) {
error = 0;
goto out;
}
