[sheepdog] [PATCH RFC 3/5] dog/farm: use rb_tree for vdi management

[Liu Yuan]

On Thu, Sep 05, 2013 at 02:22:54PM +0900, MORITA Kazutaka wrote:
> At Thu, 5 Sep 2013 10:58:43 +0800,
> Liu Yuan wrote:
> > 
> > On Thu, Sep 05, 2013 at 09:29:18AM +0900, MORITA Kazutaka wrote:
> > > From: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
> > > 
> > > Signed-off-by: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
> > > ---
> > >  dog/farm/farm.c |   27 +++++++++++++++------------
> > >  1 file changed, 15 insertions(+), 12 deletions(-)
> > > 
> > > diff --git a/dog/farm/farm.c b/dog/farm/farm.c
> > > index d034c7a..878d14d 100644
> > > --- a/dog/farm/farm.c
> > > +++ b/dog/farm/farm.c
> > > @@ -16,7 +16,7 @@
> > >  #include <pthread.h>
> > >  
> > >  #include "farm.h"
> > > -#include "list.h"
> > > +#include "rbtree.h"
> > >  
> > >  static char farm_object_dir[PATH_MAX];
> > >  static char farm_dir[PATH_MAX];
> > > @@ -28,9 +28,9 @@ struct vdi_entry {
> > >  	uint32_t vdi_id;
> > >  	uint32_t snap_id;
> > >  	uint8_t  nr_copies;
> > > -	struct list_node list;
> > > +	struct rb_node rb;
> > >  };
> > > -static LIST_HEAD(last_vdi_list);
> > > +static struct rb_root last_vdi_tree = RB_ROOT;
> > >  
> > >  struct snapshot_work {
> > >  	struct trunk_entry entry;
> > > @@ -40,15 +40,18 @@ struct snapshot_work {
> > >  static struct work_queue *wq;
> > >  static uatomic_bool work_error;
> > >  
> > > +static int vdi_cmp(const struct vdi_entry *e1, const struct vdi_entry *e2)
> > > +{
> > > +	return strcmp(e1->name, e2->name);
> > > +}
> > > +
> > >  static struct vdi_entry *find_vdi(const char *name)
> > >  {
> > > -	struct vdi_entry *vdi;
> > > +	struct vdi_entry key = {};
> > >  
> > > -	list_for_each_entry(vdi, &last_vdi_list, list) {
> > > -		if (!strcmp(vdi->name, name))
> > > -			return vdi;
> > > -	}
> > > -	return NULL;
> > > +	pstrcpy(key.name, sizeof(key.name), name);
> > > +
> > > +	return rb_search(&last_vdi_tree, &key, rb, vdi_cmp);
> > >  }
> > >  
> > >  static struct vdi_entry *new_vdi(const char *name, uint64_t vdi_size,
> > > @@ -75,7 +78,7 @@ static void insert_vdi(struct sd_inode *new)
> > >  			      new->vdi_id,
> > >  			      new->snap_id,
> > >  			      new->nr_copies);
> > > -		list_add(&vdi->list, &last_vdi_list);
> > > +		rb_insert(&last_vdi_tree, vdi, rb, vdi_cmp);
> > >  	} else if (vdi->snap_id < new->snap_id) {
> > >  		vdi->vdi_size = new->vdi_size;
> > >  		vdi->vdi_id = new->vdi_id;
> > > @@ -88,7 +91,7 @@ static int create_active_vdis(void)
> > >  {
> > >  	struct vdi_entry *vdi;
> > >  	uint32_t new_vid;
> > > -	list_for_each_entry(vdi, &last_vdi_list, list) {
> > > +	rb_for_each_entry(vdi, &last_vdi_tree, rb) {
> > >  		if (do_vdi_create(vdi->name,
> > >  				  vdi->vdi_size,
> > >  				  vdi->vdi_id, &new_vid,
> > > @@ -101,7 +104,7 @@ static int create_active_vdis(void)
> > >  static void free_vdi_list(void)
> > >  {
> > >  	struct vdi_entry *vdi;
> > > -	list_for_each_entry(vdi, &last_vdi_list, list)
> > > +	rb_for_each_entry(vdi, &last_vdi_tree, rb)
> > >  		free(vdi);
> > 
> > we need rb_erase() too here?
> 
> Looks necessary.  I wonder why the current code doesn't call
> list_del() here.
> 

I think it is just a bug. Anyway, I have added a rb_destroy() helper in my
latest patch set, and we can use it to exclude possible memory leak.

Thanks
Yuan