client: xlist link dentries instead of set

This saves space and avoids unnecessary set logic. In particular, we no longer
need to do a heap allocation for each Dentry * in the std::set.

Before:

(gdb) print sizeof(Inode)
$1 = 1336
(gdb) print sizeof(Inode::dn_set)
$2 = 48

After:

(gdb) print sizeof(Inode)
$1 = 1360
(gdb) print sizeof(Inode::dentries)
$2 = 24

I'm not sure why the Inode size increased when the member size decreased (weird
padding by g++)? Anyway, we still get the benefit of no heap allocations for
the Dentry *s.

Signed-off-by: Patrick Donnelly <pdonnell@redhat.com>

7 files changed, 114 insertions, 86 deletions

diff --git a/src/client/Client.cc b/src/client/Client.cc
index 67074b78d3e..dd620f2e46a 100644
--- a/src/client/Client.cc
+++ b/src/client/Client.cc
@@ -1434,7 +1434,7 @@ mds_rank_t Client::choose_target_mds(MetaRequest *req, Inode** phash_diri)
       while (in->snapid != CEPH_NOSNAP) {
         if (in->snapid == CEPH_SNAPDIR)
 	  in = in->snapdir_parent.get();
-        else if (!in->dn_set.empty())
+        else if (!in->dentries.empty())
           /* In most cases there will only be one dentry, so getting it
            * will be the correct action. If there are multiple hard links,
            * I think the MDS should be able to redirect as needed*/
@@ -2941,8 +2941,8 @@ void Client::close_dir(Dir *dir)
   ldout(cct, 15) << "close_dir dir " << dir << " on " << in << dendl;
   assert(dir->is_empty());
   assert(in->dir == dir);
-  assert(in->dn_set.size() < 2);     // dirs can't be hard-linked
-  if (!in->dn_set.empty())
+  assert(in->dentries.size() < 2);     // dirs can't be hard-linked
+  if (!in->dentries.empty())
     in->get_first_parent()->put();   // unpin dentry
   
   delete in->dir;
@@ -2959,9 +2959,8 @@ Dentry* Client::link(Dir *dir, const string& name, Inode *in, Dentry *dn)
 {
   if (!dn) {
     // create a new Dentry
-    dn = new Dentry;
-    dn->name = name;
-    
+    dn = new Dentry(name);
+
     // link to dir
     dn->dir = dir;
     dir->dentries[dn->name] = dn;
@@ -2975,18 +2974,8 @@ Dentry* Client::link(Dir *dir, const string& name, Inode *in, Dentry *dn)
   }
 
   if (in) {    // link to inode
-    dn->inode = in;
-    if (in->is_dir()) {
-      if (in->dir)
-	dn->get(); // dir -> dn pin
-      if (in->ll_ref)
-	dn->get(); // ll_ref -> dn pin
-    }
-
-    assert(in->dn_set.count(dn) == 0);
-
     // only one parent for directories!
-    if (in->is_dir() && !in->dn_set.empty()) {
+    if (in->is_dir() && !in->dentries.empty()) {
       Dentry *olddn = in->get_first_parent();
       assert(olddn->dir != dir || olddn->name != name);
       Inode *old_diri = olddn->dir->parent_inode;
@@ -2995,9 +2984,8 @@ Dentry* Client::link(Dir *dir, const string& name, Inode *in, Dentry *dn)
       unlink(olddn, true, true);  // keep dir, dentry
     }
 
-    in->dn_set.insert(dn);
-
-    ldout(cct, 20) << "link  inode " << in << " parents now " << in->dn_set << dendl; 
+    dn->link(in);
+    ldout(cct, 20) << "link  inode " << in << " parents now " << in->dentries << dendl;
   }
   
   return dn;
@@ -3005,23 +2993,14 @@ Dentry* Client::link(Dir *dir, const string& name, Inode *in, Dentry *dn)
 
 void Client::unlink(Dentry *dn, bool keepdir, bool keepdentry)
 {
-  InodeRef in;
-  in.swap(dn->inode);
+  InodeRef in(dn->inode);
   ldout(cct, 15) << "unlink dir " << dn->dir->parent_inode << " '" << dn->name << "' dn " << dn
 		 << " inode " << dn->inode << dendl;
 
   // unlink from inode
-  if (in) {
-    if (in->is_dir()) {
-      if (in->dir)
-	dn->put(); // dir -> dn pin
-      if (in->ll_ref)
-	dn->put(); // ll_ref -> dn pin
-    }
-    dn->inode = 0;
-    assert(in->dn_set.count(dn));
-    in->dn_set.erase(dn);
-    ldout(cct, 20) << "unlink  inode " << in << " parents now " << in->dn_set << dendl; 
+  if (dn->inode) {
+    dn->unlink();
+    ldout(cct, 20) << "unlink  inode " << in << " parents now " << in->dentries << dendl;
   }
 
   if (keepdentry) {
@@ -4080,9 +4059,10 @@ void Client::trim_caps(MetaSession *s, uint64_t max)
     } else {
       ldout(cct, 20) << " trying to trim dentries for " << *in << dendl;
       bool all = true;
-      set<Dentry*>::iterator q = in->dn_set.begin();
-      while (q != in->dn_set.end()) {
-	Dentry *dn = *q++;
+      auto q = in->dentries.begin();
+      while (q != in->dentries.end()) {
+        Dentry *dn = *q;
+        ++q;
 	if (dn->lru_is_expireable()) {
 	  if (can_invalidate_dentries &&
 	      dn->dir->parent_inode->ino == MDS_INO_ROOT) {
@@ -4979,11 +4959,12 @@ void Client::_try_to_trim_inode(Inode *in, bool sched_inval)
   }
 
   if (ref > 0 && in->ll_ref > 0 && sched_inval) {
-    set<Dentry*>::iterator q = in->dn_set.begin();
-    while (q != in->dn_set.end()) {
-      Dentry *dn = *q++;
+    auto q = in->dentries.begin();
+    while (q != in->dentries.end()) {
+      Dentry *dn = *q;
+      ++q;
       // FIXME: we play lots of unlink/link tricks when handling MDS replies,
-      //        so in->dn_set doesn't always reflect the state of kernel's dcache.
+      //        so in->dentries doesn't always reflect the state of kernel's dcache.
       _schedule_invalidate_dentry_callback(dn, true);
       unlink(dn, true, true);
     }
@@ -6079,7 +6060,7 @@ int Client::_lookup(Inode *dir, const string& dname, int mask, InodeRef *target,
   }
 
   if (dname == "..") {
-    if (dir->dn_set.empty())
+    if (dir->dentries.empty())
       *target = dir;
     else
       *target = dir->get_first_parent()->dir->parent_inode; //dirs can't be hard-linked
@@ -7749,7 +7730,7 @@ int Client::readdir_r_cb(dir_result_t *d, add_dirent_cb_t cb, void *p,
 
   if (dirp->offset == 0) {
     ldout(cct, 15) << " including ." << dendl;
-    assert(diri->dn_set.size() < 2); // can't have multiple hard-links to a dir
+    assert(diri->dentries.size() < 2); // can't have multiple hard-links to a dir
     uint64_t next_off = 1;
 
     int r;
@@ -7780,7 +7761,7 @@ int Client::readdir_r_cb(dir_result_t *d, add_dirent_cb_t cb, void *p,
     ldout(cct, 15) << " including .." << dendl;
     uint64_t next_off = 2;
     InodeRef in;
-    if (diri->dn_set.empty())
+    if (diri->dentries.empty())
       in = diri;
     else
       in = diri->get_first_parent()->dir->parent_inode;
@@ -8262,7 +8243,7 @@ int Client::lookup_parent(Inode *ino, const UserPerm& perms, Inode **parent)
   if (unmounting)
     return -ENOTCONN;
 
-  if (!ino->dn_set.empty()) {
+  if (!ino->dentries.empty()) {
     // if we exposed the parent here, we'd need to check permissions,
     // but right now we just rely on the MDS doing so in make_request
     ldout(cct, 3) << "lookup_parent dentry already present" << dendl;
@@ -9564,10 +9545,10 @@ void Client::_getcwd(string& dir, const UserPerm& perms)
 
   Inode *in = cwd.get();
   while (in != root) {
-    assert(in->dn_set.size() < 2); // dirs can't be hard-linked
+    assert(in->dentries.size() < 2); // dirs can't be hard-linked
 
     // A cwd or ancester is unlinked
-    if (in->dn_set.empty()) {
+    if (in->dentries.empty()) {
       return;
     }
 
@@ -10390,8 +10371,8 @@ void Client::_ll_get(Inode *in)
 {
   if (in->ll_ref == 0) {
     in->get();
-    if (in->is_dir() && !in->dn_set.empty()) {
-      assert(in->dn_set.size() == 1); // dirs can't be hard-linked
+    if (in->is_dir() && !in->dentries.empty()) {
+      assert(in->dentries.size() == 1); // dirs can't be hard-linked
       in->get_first_parent()->get(); // pin dentry
     }
   }
@@ -10404,8 +10385,8 @@ int Client::_ll_put(Inode *in, int num)
   in->ll_put(num);
   ldout(cct, 20) << "_ll_put " << in << " " << in->ino << " " << num << " -> " << in->ll_ref << dendl;
   if (in->ll_ref == 0) {
-    if (in->is_dir() && !in->dn_set.empty()) {
-      assert(in->dn_set.size() == 1); // dirs can't be hard-linked
+    if (in->is_dir() && !in->dentries.empty()) {
+      assert(in->dentries.size() == 1); // dirs can't be hard-linked
       in->get_first_parent()->put(); // unpin dentry
     }
     put_inode(in);
@@ -11458,10 +11439,8 @@ int Client::ll_readlink(Inode *in, char *buf, size_t buflen, const UserPerm& per
   tout(cct) << "ll_readlink" << std::endl;
   tout(cct) << vino.ino.val << std::endl;
 
-  set<Dentry*>::iterator dn = in->dn_set.begin();
-  while (dn != in->dn_set.end()) {
-    touch_dn(*dn);
-    ++dn;
+  for (auto dn : in->dentries) {
+    touch_dn(dn);
   }
 
   int r = _readlink(in, buf, buflen); // FIXME: no permission checking!
@@ -13516,9 +13495,8 @@ Inode *Client::get_quota_root(Inode *in, const UserPerm& perms)
       break;
 
     Inode *parent_in = NULL;
-    if (!cur->dn_set.empty()) {
-      for (auto p = cur->dn_set.begin(); p != cur->dn_set.end(); ++p) {
-	Dentry *dn = *p;
+    if (!cur->dentries.empty()) {
+      for (auto dn : cur->dentries) {
 	if (dn->lease_mds >= 0 &&
 	    dn->lease_ttl > now &&
 	    mds_sessions.count(dn->lease_mds)) {
diff --git a/src/client/Dentry.cc b/src/client/Dentry.cc
index bf45708cda7..f8741050a44 100644
--- a/src/client/Dentry.cc
+++ b/src/client/Dentry.cc
@@ -26,3 +26,8 @@ void Dentry::dump(Formatter *f) const
   }
   f->dump_int("cap_shared_gen", cap_shared_gen);
 }
+
+std::ostream &operator<<(std::ostream &oss, const Dentry &dn)
+{
+  return oss << dn.dir->parent_inode->vino() << "[\"" << dn.name << "\"]";
+}
diff --git a/src/client/Dentry.h b/src/client/Dentry.h
index bad3ce82bb8..4401078a56c 100644
--- a/src/client/Dentry.h
+++ b/src/client/Dentry.h
@@ -5,15 +5,15 @@
 #include "include/xlist.h"
 
 #include "mds/mdstypes.h"
+#include "Inode.h"
 #include "InodeRef.h"
 
-class Dir;
-struct Inode;
-
 class Dentry : public LRUObject {
 public:
+  explicit Dentry(const std::string &name) : name(name), inode_xlist_link(this) {}
   ~Dentry() {
     assert(ref == 0);
+    inode_xlist_link.remove_myself();
   }
 
   /*
@@ -34,11 +34,33 @@ public:
     if (ref == 0)
       delete this;
   }
+  void link(InodeRef in) {
+    inode = in;
+    inode->dentries.push_back(&inode_xlist_link);
+    if (inode->is_dir()) {
+      if (inode->dir)
+        get(); // dir -> dn pin
+      if (inode->ll_ref)
+        get(); // ll_ref -> dn pin
+    }
+  }
+  void unlink(void) {
+    if (inode->is_dir()) {
+      if (inode->dir)
+        put(); // dir -> dn pin
+      if (inode->ll_ref)
+        put(); // ll_ref -> dn pin
+    }
+    assert(inode_xlist_link.get_list() == &inode->dentries);
+    inode_xlist_link.remove_myself();
+    inode.reset();
+  }
 
   void dump(Formatter *f) const;
+  friend std::ostream &operator<<(std::ostream &oss, const Dentry &Dentry);
 
   string   name;                      // sort of lame
-  Dir	   *dir = nullptr;
+  class Dir	   *dir = nullptr;
   InodeRef inode;
   int	   ref = 1; // 1 if there's a dir beneath me.
   int64_t offset = 0;
@@ -47,6 +69,9 @@ public:
   uint64_t lease_gen = 0;
   ceph_seq_t lease_seq = 0;
   int cap_shared_gen = 0;
+
+private:
+  xlist<Dentry *>::item inode_xlist_link;
 };
 
 #endif
diff --git a/src/client/Inode.cc b/src/client/Inode.cc
index 2690ea38761..86dbd030db0 100644
--- a/src/client/Inode.cc
+++ b/src/client/Inode.cc
@@ -69,8 +69,8 @@ ostream& operator<<(ostream &out, const Inode &in)
   if (in.is_file())
     out << " " << in.oset;
 
-  if (!in.dn_set.empty())
-    out << " parents=" << in.dn_set;
+  if (!in.dentries.empty())
+    out << " parents=" << in.dentries;
 
   if (in.is_dir() && in.has_dir_layout())
     out << " has_dir_layout";
@@ -85,10 +85,11 @@ ostream& operator<<(ostream &out, const Inode &in)
 
 void Inode::make_long_path(filepath& p)
 {
-  if (!dn_set.empty()) {
-    assert((*dn_set.begin())->dir && (*dn_set.begin())->dir->parent_inode);
-    (*dn_set.begin())->dir->parent_inode->make_long_path(p);
-    p.push_dentry((*dn_set.begin())->name);
+  if (!dentries.empty()) {
+    Dentry *dn = get_first_parent();
+    assert(dn->dir && dn->dir->parent_inode);
+    dn->dir->parent_inode->make_long_path(p);
+    p.push_dentry(dn->name);
   } else if (snapdir_parent) {
     snapdir_parent->make_nosnap_relative_path(p);
     string empty;
@@ -110,10 +111,11 @@ void Inode::make_nosnap_relative_path(filepath& p)
     snapdir_parent->make_nosnap_relative_path(p);
     string empty;
     p.push_dentry(empty);
-  } else if (!dn_set.empty()) {
-    assert((*dn_set.begin())->dir && (*dn_set.begin())->dir->parent_inode);
-    (*dn_set.begin())->dir->parent_inode->make_nosnap_relative_path(p);
-    p.push_dentry((*dn_set.begin())->name);
+  } else if (!dentries.empty()) {
+    Dentry *dn = get_first_parent();
+    assert(dn->dir && dn->dir->parent_inode);
+    dn->dir->parent_inode->make_nosnap_relative_path(p);
+    p.push_dentry(dn->name);
   } else {
     p = filepath(ino);
   }
@@ -322,9 +324,9 @@ Dir *Inode::open_dir()
   if (!dir) {
     dir = new Dir(this);
     lsubdout(client->cct, client, 15) << "open_dir " << dir << " on " << this << dendl;
-    assert(dn_set.size() < 2); // dirs can't be hard-linked
-    if (!dn_set.empty())
-      (*dn_set.begin())->get();      // pin dentry
+    assert(dentries.size() < 2); // dirs can't be hard-linked
+    if (!dentries.empty())
+      get_first_parent()->get();      // pin dentry
     get();                  // pin inode
   }
   return dir;
@@ -495,12 +497,12 @@ void Inode::dump(Formatter *f) const
   f->dump_int("ref", _ref);
   f->dump_int("ll_ref", ll_ref);
 
-  if (!dn_set.empty()) {
+  if (!dentries.empty()) {
     f->open_array_section("parents");
-    for (set<Dentry*>::const_iterator p = dn_set.begin(); p != dn_set.end(); ++p) {
+    for (const auto &dn : dentries) {
       f->open_object_section("dentry");
-      f->dump_stream("dir_ino") << (*p)->dir->parent_inode->ino;
-      f->dump_string("name", (*p)->name);
+      f->dump_stream("dir_ino") << dn->dir->parent_inode->ino;
+      f->dump_string("name", dn->name);
       f->close_section();
     }
     f->close_section();
diff --git a/src/client/Inode.h b/src/client/Inode.h
index a18a5616f43..c5fbb8ff9ec 100644
--- a/src/client/Inode.h
+++ b/src/client/Inode.h
@@ -215,7 +215,7 @@ struct Inode {
 
   int       _ref;      // ref count. 1 for each dentry, fh that links to me.
   int       ll_ref;   // separate ref count for ll client
-  set<Dentry*> dn_set;      // if i'm linked to a dentry.
+  xlist<Dentry *> dentries; // if i'm linked to a dentry.
   string    symlink;  // symlink content, if it's a symlink
   map<string,bufferptr> xattrs;
   map<frag_t,int> fragmap;  // known frag -> mds mappings
@@ -225,8 +225,8 @@ struct Inode {
   list<Cond*>	    waitfor_deleg;
 
   Dentry *get_first_parent() {
-    assert(!dn_set.empty());
-    return *dn_set.begin();
+    assert(!dentries.empty());
+    return *dentries.begin();
   }
 
   void make_long_path(filepath& p);
@@ -272,7 +272,7 @@ struct Inode {
       snaprealm(0), snaprealm_item(this),
       oset((void *)this, newlayout->pool_id, this->ino),
       reported_size(0), wanted_max_size(0), requested_max_size(0),
-      _ref(0), ll_ref(0), dn_set()
+      _ref(0), ll_ref(0)
   {
     memset(&dir_layout, 0, sizeof(dir_layout));
     memset(&quota, 0, sizeof(quota));
diff --git a/src/include/xlist.h b/src/include/xlist.h
index 3b3cd9fcaac..3e39333e511 100644
--- a/src/include/xlist.h
+++ b/src/include/xlist.h
@@ -192,10 +192,28 @@ public:
       return *this;
     }
     bool end() const { return cur == 0; }
+    bool operator==(const_iterator& rhs) const {
+      return cur == rhs.cur;
+    }
+    bool operator!=(const_iterator& rhs) const {
+      return cur != rhs.cur;
+    }
   };
 
   const_iterator begin() const { return const_iterator(_front); }
   const_iterator end() const { return const_iterator(NULL); }
+
+  friend std::ostream &operator<<(std::ostream &oss, const xlist<T> &list) {
+    bool first = true;
+    for (const auto &item : list) {
+      if (!first) {
+        oss << ", ";
+      }
+      oss << *item; /* item should be a pointer */
+      first = false;
+    }
+    return oss;
+  }
 };
 
 
diff --git a/src/tools/ceph-client-debug.cc b/src/tools/ceph-client-debug.cc
index 2984db678cf..7af2ec6f87c 100644
--- a/src/tools/ceph-client-debug.cc
+++ b/src/tools/ceph-client-debug.cc
@@ -39,11 +39,11 @@ void usage()
  */
 void traverse_dentries(Inode *ino, std::vector<Dentry*> &parts)
 {
-  if (ino->dn_set.empty()) {
+  if (ino->dentries.empty()) {
     return;
   }
   
-  Dentry* dn = *(ino->dn_set.begin());
+  Dentry* dn = *(ino->dentries.begin());
   parts.push_back(dn);
   traverse_dentries(dn->dir->parent_inode, parts);
 }
@@ -61,8 +61,8 @@ int lookup_trace(ceph_mount_info *client, inodeno_t const ino)
   if (r != 0) {
     return r;
   } else {
-    if (!inode->dn_set.empty()) {
-      Dentry *dn = *(inode->dn_set.begin());
+    if (!inode->dentries.empty()) {
+      Dentry *dn = *(inode->dentries.begin());
       assert(dn->dir);
       assert(dn->dir->parent_inode);
       r = lookup_trace(client, dn->dir->parent_inode->ino);