[PATCH 0/2] cifs: convert tlink_tree to a rbtree

[PATCH 0/2] cifs: convert tlink_tree to a rbtree

[Jeff Layton]

The new multiuser mount code in CIFS uses a radix tree to track
tcon_link entries. The main reason for this is historical. The initial
implementation that I did used a radix tree with pointers to
cifsTconInfo structs.

I chose that because it was possible that a tcon could be in more than
one tree at a time. It became evident in later versions however that I
needed a separate tracking struct to handle the refcounting. Thus, the
tcon_link was born, but I kept the initial design of a radix tree.

We recently had a bit of a kerfuffle surrounding the use of radix trees
with IMA to track inodes. While we'll likely have considerably fewer
radix tree entries, it's not really the best choice here either. The
tcon_link struct will only ever be in one tlink_tree, so we can embed
a tracking structure inside it.

This patchset converts that code to use a rbtree instead. This should
be as fast or faster than using a radix tree. It also has the benefit of
not requiring memory allocations on insertion which simplifies the
error handling in those codepaths.

Jeff Layton (2):
  cifs: store pointer to master tlink in superblock
  cifs: convert tlink_tree to a rbtree

 fs/cifs/cifs_fs_sb.h |    6 +-
 fs/cifs/cifsfs.c     |    2 +-
 fs/cifs/cifsglob.h   |    3 +-
 fs/cifs/connect.c    |  191 +++++++++++++++++++++++++------------------------
 4 files changed, 103 insertions(+), 99 deletions(-)

-- 
1.7.2.3

[PATCH 1/2] cifs: store pointer to master tlink in superblock

[Jeff Layton]

Instead of keeping a tag on the master tlink in the tree, just keep a
pointer to the master in the superblock. That eliminates the need for
using the radix tree to look up a tagged entry.

Signed-off-by: Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
---
 fs/cifs/cifs_fs_sb.h |    2 +-
 fs/cifs/connect.c    |   18 +++---------------
 2 files changed, 4 insertions(+), 16 deletions(-)

diff --git a/fs/cifs/cifs_fs_sb.h b/fs/cifs/cifs_fs_sb.h
index 525ba59..79576da 100644
--- a/fs/cifs/cifs_fs_sb.h
+++ b/fs/cifs/cifs_fs_sb.h
@@ -43,8 +43,8 @@
 
 struct cifs_sb_info {
 	struct radix_tree_root tlink_tree;
-#define CIFS_TLINK_MASTER_TAG		0	/* is "master" (mount) tcon */
 	spinlock_t tlink_tree_lock;
+	struct tcon_link *master_tlink;
 	struct nls_table *local_nls;
 	unsigned int rsize;
 	unsigned int wsize;
diff --git a/fs/cifs/connect.c b/fs/cifs/connect.c
index 469c3dd..364eb96 100644
--- a/fs/cifs/connect.c
+++ b/fs/cifs/connect.c
@@ -2917,11 +2917,11 @@ remote_path_check:
 
 	spin_lock(&cifs_sb->tlink_tree_lock);
 	radix_tree_insert(&cifs_sb->tlink_tree, pSesInfo->linux_uid, tlink);
-	radix_tree_tag_set(&cifs_sb->tlink_tree, pSesInfo->linux_uid,
-			   CIFS_TLINK_MASTER_TAG);
 	spin_unlock(&cifs_sb->tlink_tree_lock);
 	radix_tree_preload_end();
 
+	cifs_sb->master_tlink = tlink;
+
 	queue_delayed_work(system_nrt_wq, &cifs_sb->prune_tlinks,
 				TLINK_IDLE_EXPIRE);
 
@@ -3275,19 +3275,7 @@ out:
 static struct tcon_link *
 cifs_sb_master_tlink(struct cifs_sb_info *cifs_sb)
 {
-	struct tcon_link *tlink;
-	unsigned int ret;
-
-	spin_lock(&cifs_sb->tlink_tree_lock);
-	ret = radix_tree_gang_lookup_tag(&cifs_sb->tlink_tree, (void **)&tlink,
-					0, 1, CIFS_TLINK_MASTER_TAG);
-	spin_unlock(&cifs_sb->tlink_tree_lock);
-
-	/* the master tcon should always be present */
-	if (ret == 0)
-		BUG();
-
-	return tlink;
+	return cifs_sb->master_tlink;
 }
 
 struct cifsTconInfo *
-- 
1.7.2.3

Re: [PATCH 1/2] cifs: store pointer to master tlink in superblock

[Shirish Pargaonkar]

On Thu, Oct 28, 2010 at 6:33 AM, Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> Instead of keeping a tag on the master tlink in the tree, just keep a
> pointer to the master in the superblock. That eliminates the need for
> using the radix tree to look up a tagged entry.
>
> Signed-off-by: Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
> ---
>  fs/cifs/cifs_fs_sb.h |    2 +-
>  fs/cifs/connect.c    |   18 +++---------------
>  2 files changed, 4 insertions(+), 16 deletions(-)
>
> diff --git a/fs/cifs/cifs_fs_sb.h b/fs/cifs/cifs_fs_sb.h
> index 525ba59..79576da 100644
> --- a/fs/cifs/cifs_fs_sb.h
> +++ b/fs/cifs/cifs_fs_sb.h
> @@ -43,8 +43,8 @@
>
>  struct cifs_sb_info {
>        struct radix_tree_root tlink_tree;
> -#define CIFS_TLINK_MASTER_TAG          0       /* is "master" (mount) tcon */
>        spinlock_t tlink_tree_lock;
> +       struct tcon_link *master_tlink;
>        struct nls_table *local_nls;
>        unsigned int rsize;
>        unsigned int wsize;
> diff --git a/fs/cifs/connect.c b/fs/cifs/connect.c
> index 469c3dd..364eb96 100644
> --- a/fs/cifs/connect.c
> +++ b/fs/cifs/connect.c
> @@ -2917,11 +2917,11 @@ remote_path_check:
>
>        spin_lock(&cifs_sb->tlink_tree_lock);
>        radix_tree_insert(&cifs_sb->tlink_tree, pSesInfo->linux_uid, tlink);
> -       radix_tree_tag_set(&cifs_sb->tlink_tree, pSesInfo->linux_uid,
> -                          CIFS_TLINK_MASTER_TAG);
>        spin_unlock(&cifs_sb->tlink_tree_lock);
>        radix_tree_preload_end();
>
> +       cifs_sb->master_tlink = tlink;
> +
>        queue_delayed_work(system_nrt_wq, &cifs_sb->prune_tlinks,
>                                TLINK_IDLE_EXPIRE);
>
> @@ -3275,19 +3275,7 @@ out:
>  static struct tcon_link *
>  cifs_sb_master_tlink(struct cifs_sb_info *cifs_sb)
>  {
> -       struct tcon_link *tlink;
> -       unsigned int ret;
> -
> -       spin_lock(&cifs_sb->tlink_tree_lock);
> -       ret = radix_tree_gang_lookup_tag(&cifs_sb->tlink_tree, (void **)&tlink,
> -                                       0, 1, CIFS_TLINK_MASTER_TAG);
> -       spin_unlock(&cifs_sb->tlink_tree_lock);
> -
> -       /* the master tcon should always be present */
> -       if (ret == 0)
> -               BUG();
> -
> -       return tlink;
> +       return cifs_sb->master_tlink;

Wondering whether we need a function just to return master_tlink
within a cifs_sb.
Could the caller(s) of cifs_sb_master_tlink() access master_tlink directly?

>  }
>
>  struct cifsTconInfo *
> --
> 1.7.2.3
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-cifs" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: [PATCH 1/2] cifs: store pointer to master tlink in superblock

[Jeff Layton]

On Thu, 28 Oct 2010 10:06:05 -0500
Shirish Pargaonkar <shirishpargaonkar-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:

> On Thu, Oct 28, 2010 at 6:33 AM, Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> > Instead of keeping a tag on the master tlink in the tree, just keep a
> > pointer to the master in the superblock. That eliminates the need for
> > using the radix tree to look up a tagged entry.
> >
> > Signed-off-by: Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
> > ---
> >  fs/cifs/cifs_fs_sb.h |    2 +-
> >  fs/cifs/connect.c    |   18 +++---------------
> >  2 files changed, 4 insertions(+), 16 deletions(-)
> >
> > diff --git a/fs/cifs/cifs_fs_sb.h b/fs/cifs/cifs_fs_sb.h
> > index 525ba59..79576da 100644
> > --- a/fs/cifs/cifs_fs_sb.h
> > +++ b/fs/cifs/cifs_fs_sb.h
> > @@ -43,8 +43,8 @@
> >
> >  struct cifs_sb_info {
> >        struct radix_tree_root tlink_tree;
> > -#define CIFS_TLINK_MASTER_TAG          0       /* is "master" (mount) tcon */
> >        spinlock_t tlink_tree_lock;
> > +       struct tcon_link *master_tlink;
> >        struct nls_table *local_nls;
> >        unsigned int rsize;
> >        unsigned int wsize;
> > diff --git a/fs/cifs/connect.c b/fs/cifs/connect.c
> > index 469c3dd..364eb96 100644
> > --- a/fs/cifs/connect.c
> > +++ b/fs/cifs/connect.c
> > @@ -2917,11 +2917,11 @@ remote_path_check:
> >
> >        spin_lock(&cifs_sb->tlink_tree_lock);
> >        radix_tree_insert(&cifs_sb->tlink_tree, pSesInfo->linux_uid, tlink);
> > -       radix_tree_tag_set(&cifs_sb->tlink_tree, pSesInfo->linux_uid,
> > -                          CIFS_TLINK_MASTER_TAG);
> >        spin_unlock(&cifs_sb->tlink_tree_lock);
> >        radix_tree_preload_end();
> >
> > +       cifs_sb->master_tlink = tlink;
> > +
> >        queue_delayed_work(system_nrt_wq, &cifs_sb->prune_tlinks,
> >                                TLINK_IDLE_EXPIRE);
> >
> > @@ -3275,19 +3275,7 @@ out:
> >  static struct tcon_link *
> >  cifs_sb_master_tlink(struct cifs_sb_info *cifs_sb)
> >  {
> > -       struct tcon_link *tlink;
> > -       unsigned int ret;
> > -
> > -       spin_lock(&cifs_sb->tlink_tree_lock);
> > -       ret = radix_tree_gang_lookup_tag(&cifs_sb->tlink_tree, (void **)&tlink,
> > -                                       0, 1, CIFS_TLINK_MASTER_TAG);
> > -       spin_unlock(&cifs_sb->tlink_tree_lock);
> > -
> > -       /* the master tcon should always be present */
> > -       if (ret == 0)
> > -               BUG();
> > -
> > -       return tlink;
> > +       return cifs_sb->master_tlink;
> 
> Wondering whether we need a function just to return master_tlink
> within a cifs_sb.
> Could the caller(s) of cifs_sb_master_tlink() access master_tlink directly?
> 

Sure, but accessor functions are generally a good thing. It insulates
the callers from needing to know anything about the underlying data
structure.

-- 
Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>

Re: [PATCH 1/2] cifs: store pointer to master tlink in superblock

[Jeff Layton]

On Thu, 28 Oct 2010 12:23:25 -0400
Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:

> On Thu, 28 Oct 2010 10:06:05 -0500
> Shirish Pargaonkar <shirishpargaonkar-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> 
> > On Thu, Oct 28, 2010 at 6:33 AM, Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> > > Instead of keeping a tag on the master tlink in the tree, just keep a
> > > pointer to the master in the superblock. That eliminates the need for
> > > using the radix tree to look up a tagged entry.
> > >
> > > Signed-off-by: Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
> > > ---
> > >  fs/cifs/cifs_fs_sb.h |    2 +-
> > >  fs/cifs/connect.c    |   18 +++---------------
> > >  2 files changed, 4 insertions(+), 16 deletions(-)
> > >
> > > diff --git a/fs/cifs/cifs_fs_sb.h b/fs/cifs/cifs_fs_sb.h
> > > index 525ba59..79576da 100644
> > > --- a/fs/cifs/cifs_fs_sb.h
> > > +++ b/fs/cifs/cifs_fs_sb.h
> > > @@ -43,8 +43,8 @@
> > >
> > >  struct cifs_sb_info {
> > >        struct radix_tree_root tlink_tree;
> > > -#define CIFS_TLINK_MASTER_TAG          0       /* is "master" (mount) tcon */
> > >        spinlock_t tlink_tree_lock;
> > > +       struct tcon_link *master_tlink;
> > >        struct nls_table *local_nls;
> > >        unsigned int rsize;
> > >        unsigned int wsize;
> > > diff --git a/fs/cifs/connect.c b/fs/cifs/connect.c
> > > index 469c3dd..364eb96 100644
> > > --- a/fs/cifs/connect.c
> > > +++ b/fs/cifs/connect.c
> > > @@ -2917,11 +2917,11 @@ remote_path_check:
> > >
> > >        spin_lock(&cifs_sb->tlink_tree_lock);
> > >        radix_tree_insert(&cifs_sb->tlink_tree, pSesInfo->linux_uid, tlink);
> > > -       radix_tree_tag_set(&cifs_sb->tlink_tree, pSesInfo->linux_uid,
> > > -                          CIFS_TLINK_MASTER_TAG);
> > >        spin_unlock(&cifs_sb->tlink_tree_lock);
> > >        radix_tree_preload_end();
> > >
> > > +       cifs_sb->master_tlink = tlink;
> > > +
> > >        queue_delayed_work(system_nrt_wq, &cifs_sb->prune_tlinks,
> > >                                TLINK_IDLE_EXPIRE);
> > >
> > > @@ -3275,19 +3275,7 @@ out:
> > >  static struct tcon_link *
> > >  cifs_sb_master_tlink(struct cifs_sb_info *cifs_sb)
> > >  {
> > > -       struct tcon_link *tlink;
> > > -       unsigned int ret;
> > > -
> > > -       spin_lock(&cifs_sb->tlink_tree_lock);
> > > -       ret = radix_tree_gang_lookup_tag(&cifs_sb->tlink_tree, (void **)&tlink,
> > > -                                       0, 1, CIFS_TLINK_MASTER_TAG);
> > > -       spin_unlock(&cifs_sb->tlink_tree_lock);
> > > -
> > > -       /* the master tcon should always be present */
> > > -       if (ret == 0)
> > > -               BUG();
> > > -
> > > -       return tlink;
> > > +       return cifs_sb->master_tlink;
> > 
> > Wondering whether we need a function just to return master_tlink
> > within a cifs_sb.
> > Could the caller(s) of cifs_sb_master_tlink() access master_tlink directly?
> > 
> 
> Sure, but accessor functions are generally a good thing. It insulates
> the callers from needing to know anything about the underlying data
> structure.
> 

What may make some sense however is turning this function into a static
inline or macro. Thoughts?

-- 
Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>

Re: [PATCH 1/2] cifs: store pointer to master tlink in superblock

[Shirish Pargaonkar]

On Thu, Oct 28, 2010 at 11:50 AM, Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> On Thu, 28 Oct 2010 12:23:25 -0400
> Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
>
>> On Thu, 28 Oct 2010 10:06:05 -0500
>> Shirish Pargaonkar <shirishpargaonkar-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>>
>> > On Thu, Oct 28, 2010 at 6:33 AM, Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
>> > > Instead of keeping a tag on the master tlink in the tree, just keep a
>> > > pointer to the master in the superblock. That eliminates the need for
>> > > using the radix tree to look up a tagged entry.
>> > >
>> > > Signed-off-by: Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
>> > > ---
>> > >  fs/cifs/cifs_fs_sb.h |    2 +-
>> > >  fs/cifs/connect.c    |   18 +++---------------
>> > >  2 files changed, 4 insertions(+), 16 deletions(-)
>> > >
>> > > diff --git a/fs/cifs/cifs_fs_sb.h b/fs/cifs/cifs_fs_sb.h
>> > > index 525ba59..79576da 100644
>> > > --- a/fs/cifs/cifs_fs_sb.h
>> > > +++ b/fs/cifs/cifs_fs_sb.h
>> > > @@ -43,8 +43,8 @@
>> > >
>> > >  struct cifs_sb_info {
>> > >        struct radix_tree_root tlink_tree;
>> > > -#define CIFS_TLINK_MASTER_TAG          0       /* is "master" (mount) tcon */
>> > >        spinlock_t tlink_tree_lock;
>> > > +       struct tcon_link *master_tlink;
>> > >        struct nls_table *local_nls;
>> > >        unsigned int rsize;
>> > >        unsigned int wsize;
>> > > diff --git a/fs/cifs/connect.c b/fs/cifs/connect.c
>> > > index 469c3dd..364eb96 100644
>> > > --- a/fs/cifs/connect.c
>> > > +++ b/fs/cifs/connect.c
>> > > @@ -2917,11 +2917,11 @@ remote_path_check:
>> > >
>> > >        spin_lock(&cifs_sb->tlink_tree_lock);
>> > >        radix_tree_insert(&cifs_sb->tlink_tree, pSesInfo->linux_uid, tlink);
>> > > -       radix_tree_tag_set(&cifs_sb->tlink_tree, pSesInfo->linux_uid,
>> > > -                          CIFS_TLINK_MASTER_TAG);
>> > >        spin_unlock(&cifs_sb->tlink_tree_lock);
>> > >        radix_tree_preload_end();
>> > >
>> > > +       cifs_sb->master_tlink = tlink;
>> > > +
>> > >        queue_delayed_work(system_nrt_wq, &cifs_sb->prune_tlinks,
>> > >                                TLINK_IDLE_EXPIRE);
>> > >
>> > > @@ -3275,19 +3275,7 @@ out:
>> > >  static struct tcon_link *
>> > >  cifs_sb_master_tlink(struct cifs_sb_info *cifs_sb)
>> > >  {
>> > > -       struct tcon_link *tlink;
>> > > -       unsigned int ret;
>> > > -
>> > > -       spin_lock(&cifs_sb->tlink_tree_lock);
>> > > -       ret = radix_tree_gang_lookup_tag(&cifs_sb->tlink_tree, (void **)&tlink,
>> > > -                                       0, 1, CIFS_TLINK_MASTER_TAG);
>> > > -       spin_unlock(&cifs_sb->tlink_tree_lock);
>> > > -
>> > > -       /* the master tcon should always be present */
>> > > -       if (ret == 0)
>> > > -               BUG();
>> > > -
>> > > -       return tlink;
>> > > +       return cifs_sb->master_tlink;
>> >
>> > Wondering whether we need a function just to return master_tlink
>> > within a cifs_sb.
>> > Could the caller(s) of cifs_sb_master_tlink() access master_tlink directly?
>> >
>>
>> Sure, but accessor functions are generally a good thing. It insulates
>> the callers from needing to know anything about the underlying data
>> structure.
>>
>
> What may make some sense however is turning this function into a static
> inline or macro. Thoughts?
>
> --
> Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
>

I think inline function would be my preferred choice.

[PATCH 2/2] cifs: convert tlink_tree to a rbtree

[Jeff Layton]

Radix trees are ideal when you want to track a bunch of pointers and
can't embed a tracking structure within the target of those pointers.
The tradeoff is an increase in memory, particularly if the tree is
sparse.

In CIFS, we use the tlink_tree to track tcon_link structs. A tcon_link
can never be in more than one tlink_tree, so there's no impediment to
using a rb_tree here instead of a radix tree.

Convert the new multiuser mount code to use a rb_tree instead. This
should reduce the memory required to manage the tlink_tree.

Signed-off-by: Jeff Layton <jlayton-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
---
 fs/cifs/cifs_fs_sb.h |    4 +-
 fs/cifs/cifsfs.c     |    2 +-
 fs/cifs/cifsglob.h   |    3 +-
 fs/cifs/connect.c    |  177 +++++++++++++++++++++++++++-----------------------
 4 files changed, 101 insertions(+), 85 deletions(-)

diff --git a/fs/cifs/cifs_fs_sb.h b/fs/cifs/cifs_fs_sb.h
index 79576da..e9a393c 100644
--- a/fs/cifs/cifs_fs_sb.h
+++ b/fs/cifs/cifs_fs_sb.h
@@ -15,7 +15,7 @@
  *   the GNU Lesser General Public License for more details.
  *
  */
-#include <linux/radix-tree.h>
+#include <linux/rbtree.h>
 
 #ifndef _CIFS_FS_SB_H
 #define _CIFS_FS_SB_H
@@ -42,7 +42,7 @@
 #define CIFS_MOUNT_MULTIUSER	0x20000 /* multiuser mount */
 
 struct cifs_sb_info {
-	struct radix_tree_root tlink_tree;
+	struct rb_root tlink_tree;
 	spinlock_t tlink_tree_lock;
 	struct tcon_link *master_tlink;
 	struct nls_table *local_nls;
diff --git a/fs/cifs/cifsfs.c b/fs/cifs/cifsfs.c
index 17baeab..c5f136c 100644
--- a/fs/cifs/cifsfs.c
+++ b/fs/cifs/cifsfs.c
@@ -116,7 +116,7 @@ cifs_read_super(struct super_block *sb, void *data,
 		return -ENOMEM;
 
 	spin_lock_init(&cifs_sb->tlink_tree_lock);
-	INIT_RADIX_TREE(&cifs_sb->tlink_tree, GFP_KERNEL);
+	cifs_sb->tlink_tree = RB_ROOT;
 
 	rc = bdi_setup_and_register(&cifs_sb->bdi, "cifs", BDI_CAP_MAP_COPY);
 	if (rc) {
diff --git a/fs/cifs/cifsglob.h b/fs/cifs/cifsglob.h
index ab94982..4434d5d 100644
--- a/fs/cifs/cifsglob.h
+++ b/fs/cifs/cifsglob.h
@@ -338,7 +338,8 @@ struct cifsTconInfo {
  * "get" on the container.
  */
 struct tcon_link {
-	unsigned long		tl_index;
+	struct rb_node		tl_rbnode;
+	uid_t			tl_uid;
 	unsigned long		tl_flags;
 #define TCON_LINK_MASTER	0
 #define TCON_LINK_PENDING	1
diff --git a/fs/cifs/connect.c b/fs/cifs/connect.c
index 364eb96..f02b38b 100644
--- a/fs/cifs/connect.c
+++ b/fs/cifs/connect.c
@@ -116,6 +116,7 @@ struct smb_vol {
 
 static int ipv4_connect(struct TCP_Server_Info *server);
 static int ipv6_connect(struct TCP_Server_Info *server);
+static void tlink_rb_insert(struct rb_root *root, struct tcon_link *new_tlink);
 static void cifs_prune_tlinks(struct work_struct *work);
 
 /*
@@ -2903,24 +2904,16 @@ remote_path_check:
 		goto mount_fail_check;
 	}
 
-	tlink->tl_index = pSesInfo->linux_uid;
+	tlink->tl_uid = pSesInfo->linux_uid;
 	tlink->tl_tcon = tcon;
 	tlink->tl_time = jiffies;
 	set_bit(TCON_LINK_MASTER, &tlink->tl_flags);
 	set_bit(TCON_LINK_IN_TREE, &tlink->tl_flags);
 
-	rc = radix_tree_preload(GFP_KERNEL);
-	if (rc == -ENOMEM) {
-		kfree(tlink);
-		goto mount_fail_check;
-	}
-
+	cifs_sb->master_tlink = tlink;
 	spin_lock(&cifs_sb->tlink_tree_lock);
-	radix_tree_insert(&cifs_sb->tlink_tree, pSesInfo->linux_uid, tlink);
+	tlink_rb_insert(&cifs_sb->tlink_tree, tlink);
 	spin_unlock(&cifs_sb->tlink_tree_lock);
-	radix_tree_preload_end();
-
-	cifs_sb->master_tlink = tlink;
 
 	queue_delayed_work(system_nrt_wq, &cifs_sb->prune_tlinks,
 				TLINK_IDLE_EXPIRE);
@@ -3110,32 +3103,25 @@ CIFSTCon(unsigned int xid, struct cifsSesInfo *ses,
 int
 cifs_umount(struct super_block *sb, struct cifs_sb_info *cifs_sb)
 {
-	int i, ret;
+	struct rb_root *root = &cifs_sb->tlink_tree;
+	struct rb_node *node;
+	struct tcon_link *tlink;
 	char *tmp;
-	struct tcon_link *tlink[8];
-	unsigned long index = 0;
 
 	cancel_delayed_work_sync(&cifs_sb->prune_tlinks);
 
-	do {
-		spin_lock(&cifs_sb->tlink_tree_lock);
-		ret = radix_tree_gang_lookup(&cifs_sb->tlink_tree,
-					     (void **)tlink, index,
-					     ARRAY_SIZE(tlink));
-		/* increment index for next pass */
-		if (ret > 0)
-			index = tlink[ret - 1]->tl_index + 1;
-		for (i = 0; i < ret; i++) {
-			cifs_get_tlink(tlink[i]);
-			clear_bit(TCON_LINK_IN_TREE, &tlink[i]->tl_flags);
-			radix_tree_delete(&cifs_sb->tlink_tree,
-							tlink[i]->tl_index);
-		}
-		spin_unlock(&cifs_sb->tlink_tree_lock);
+	spin_lock(&cifs_sb->tlink_tree_lock);
+	while ((node = rb_first(root))) {
+		tlink = rb_entry(node, struct tcon_link, tl_rbnode);
+		cifs_get_tlink(tlink);
+		clear_bit(TCON_LINK_IN_TREE, &tlink->tl_flags);
+		rb_erase(node, root);
 
-		for (i = 0; i < ret; i++)
-			cifs_put_tlink(tlink[i]);
-	} while (ret != 0);
+		spin_unlock(&cifs_sb->tlink_tree_lock);
+		cifs_put_tlink(tlink);
+		spin_lock(&cifs_sb->tlink_tree_lock);
+	}
+	spin_unlock(&cifs_sb->tlink_tree_lock);
 
 	tmp = cifs_sb->prepath;
 	cifs_sb->prepathlen = 0;
@@ -3291,6 +3277,47 @@ cifs_sb_tcon_pending_wait(void *unused)
 	return signal_pending(current) ? -ERESTARTSYS : 0;
 }
 
+/* find and return a tlink with given uid */
+static struct tcon_link *
+tlink_rb_search(struct rb_root *root, uid_t uid)
+{
+	struct rb_node *node = root->rb_node;
+	struct tcon_link *tlink;
+
+	while (node) {
+		tlink = rb_entry(node, struct tcon_link, tl_rbnode);
+
+		if (tlink->tl_uid > uid)
+			node = node->rb_left;
+		else if (tlink->tl_uid < uid)
+			node = node->rb_right;
+		else
+			return tlink;
+	}
+	return NULL;
+}
+
+/* insert a tcon_link into the tree */
+static void
+tlink_rb_insert(struct rb_root *root, struct tcon_link *new_tlink)
+{
+	struct rb_node **new = &(root->rb_node), *parent = NULL;
+	struct tcon_link *tlink;
+
+	while (*new) {
+		tlink = rb_entry(*new, struct tcon_link, tl_rbnode);
+		parent = *new;
+
+		if (tlink->tl_uid > new_tlink->tl_uid)
+			new = &((*new)->rb_left);
+		else
+			new = &((*new)->rb_right);
+	}
+
+	rb_link_node(&new_tlink->tl_rbnode, parent, new);
+	rb_insert_color(&new_tlink->tl_rbnode, root);
+}
+
 /*
  * Find or construct an appropriate tcon given a cifs_sb and the fsuid of the
  * current task.
@@ -3311,14 +3338,14 @@ struct tcon_link *
 cifs_sb_tlink(struct cifs_sb_info *cifs_sb)
 {
 	int ret;
-	unsigned long fsuid = (unsigned long) current_fsuid();
+	uid_t fsuid = current_fsuid();
 	struct tcon_link *tlink, *newtlink;
 
 	if (!(cifs_sb->mnt_cifs_flags & CIFS_MOUNT_MULTIUSER))
 		return cifs_get_tlink(cifs_sb_master_tlink(cifs_sb));
 
 	spin_lock(&cifs_sb->tlink_tree_lock);
-	tlink = radix_tree_lookup(&cifs_sb->tlink_tree, fsuid);
+	tlink = tlink_rb_search(&cifs_sb->tlink_tree, fsuid);
 	if (tlink)
 		cifs_get_tlink(tlink);
 	spin_unlock(&cifs_sb->tlink_tree_lock);
@@ -3327,36 +3354,24 @@ cifs_sb_tlink(struct cifs_sb_info *cifs_sb)
 		newtlink = kzalloc(sizeof(*tlink), GFP_KERNEL);
 		if (newtlink == NULL)
 			return ERR_PTR(-ENOMEM);
-		newtlink->tl_index = fsuid;
+		newtlink->tl_uid = fsuid;
 		newtlink->tl_tcon = ERR_PTR(-EACCES);
 		set_bit(TCON_LINK_PENDING, &newtlink->tl_flags);
 		set_bit(TCON_LINK_IN_TREE, &newtlink->tl_flags);
 		cifs_get_tlink(newtlink);
 
-		ret = radix_tree_preload(GFP_KERNEL);
-		if (ret != 0) {
-			kfree(newtlink);
-			return ERR_PTR(ret);
-		}
-
 		spin_lock(&cifs_sb->tlink_tree_lock);
 		/* was one inserted after previous search? */
-		tlink = radix_tree_lookup(&cifs_sb->tlink_tree, fsuid);
+		tlink = tlink_rb_search(&cifs_sb->tlink_tree, fsuid);
 		if (tlink) {
 			cifs_get_tlink(tlink);
 			spin_unlock(&cifs_sb->tlink_tree_lock);
-			radix_tree_preload_end();
 			kfree(newtlink);
 			goto wait_for_construction;
 		}
-		ret = radix_tree_insert(&cifs_sb->tlink_tree, fsuid, newtlink);
-		spin_unlock(&cifs_sb->tlink_tree_lock);
-		radix_tree_preload_end();
-		if (ret) {
-			kfree(newtlink);
-			return ERR_PTR(ret);
-		}
 		tlink = newtlink;
+		tlink_rb_insert(&cifs_sb->tlink_tree, tlink);
+		spin_unlock(&cifs_sb->tlink_tree_lock);
 	} else {
 wait_for_construction:
 		ret = wait_on_bit(&tlink->tl_flags, TCON_LINK_PENDING,
@@ -3402,39 +3417,39 @@ cifs_prune_tlinks(struct work_struct *work)
 {
 	struct cifs_sb_info *cifs_sb = container_of(work, struct cifs_sb_info,
 						    prune_tlinks.work);
-	struct tcon_link *tlink[8];
-	unsigned long now = jiffies;
-	unsigned long index = 0;
-	int i, ret;
+	struct rb_root *root = &cifs_sb->tlink_tree;
+	struct rb_node *node = rb_first(root);
+	struct rb_node *tmp;
+	struct tcon_link *tlink;
 
-	do {
-		spin_lock(&cifs_sb->tlink_tree_lock);
-		ret = radix_tree_gang_lookup(&cifs_sb->tlink_tree,
-					     (void **)tlink, index,
-					     ARRAY_SIZE(tlink));
-		/* increment index for next pass */
-		if (ret > 0)
-			index = tlink[ret - 1]->tl_index + 1;
-		for (i = 0; i < ret; i++) {
-			if (test_bit(TCON_LINK_MASTER, &tlink[i]->tl_flags) ||
-			    atomic_read(&tlink[i]->tl_count) != 0 ||
-			    time_after(tlink[i]->tl_time + TLINK_IDLE_EXPIRE,
-				       now)) {
-				tlink[i] = NULL;
-				continue;
-			}
-			cifs_get_tlink(tlink[i]);
-			clear_bit(TCON_LINK_IN_TREE, &tlink[i]->tl_flags);
-			radix_tree_delete(&cifs_sb->tlink_tree,
-					  tlink[i]->tl_index);
-		}
-		spin_unlock(&cifs_sb->tlink_tree_lock);
+	/*
+	 * Because we drop the spinlock in the loop in order to put the tlink
+	 * it's not guarded against removal of links from the tree. The only
+	 * places that remove entries from the tree are this function and
+	 * umounts. Because this function is non-reentrant and is canceled
+	 * before umount can proceed, this is safe.
+	 */
+	spin_lock(&cifs_sb->tlink_tree_lock);
+	node = rb_first(root);
+	while (node != NULL) {
+		tmp = node;
+		node = rb_next(tmp);
+		tlink = rb_entry(tmp, struct tcon_link, tl_rbnode);
+
+		if (test_bit(TCON_LINK_MASTER, &tlink->tl_flags) ||
+		    atomic_read(&tlink->tl_count) != 0 ||
+		    time_after(tlink->tl_time + TLINK_IDLE_EXPIRE, jiffies))
+			continue;
 
-		for (i = 0; i < ret; i++) {
-			if (tlink[i] != NULL)
-				cifs_put_tlink(tlink[i]);
-		}
-	} while (ret != 0);
+		cifs_get_tlink(tlink);
+		clear_bit(TCON_LINK_IN_TREE, &tlink->tl_flags);
+		rb_erase(tmp, root);
+
+		spin_unlock(&cifs_sb->tlink_tree_lock);
+		cifs_put_tlink(tlink);
+		spin_lock(&cifs_sb->tlink_tree_lock);
+	}
+	spin_unlock(&cifs_sb->tlink_tree_lock);
 
 	queue_delayed_work(system_nrt_wq, &cifs_sb->prune_tlinks,
 				TLINK_IDLE_EXPIRE);
-- 
1.7.2.3