Head

GCC Code Coverage Report

Directory:	cvmfs/		Exec	Total	Coverage
File:	cvmfs/glue_buffer.h	Lines:	187	289	64.7 %
Date:	2019-02-03 02:48:13	Branches:	29	78	37.2 %


/**
 * This file is part of the CernVM File System.
 *
 * This module provides the inode tracker in order to remember inodes
 * and their parents that are in use by the kernel.
 *
 * These objects have to survive reloading of the library, so no virtual
 * functions.
 */

#include <pthread.h>
#include <sched.h>
#include <stdint.h>

#include <cassert>
#include <cstring>
#include <map>
#include <string>
#include <vector>

#include "atomic.h"
#include "bigvector.h"
#include "hash.h"
#include "shortstring.h"
#include "smallhash.h"
#include "smalloc.h"
#include "util/posix.h"
#include "util/string.h"

#ifndef CVMFS_GLUE_BUFFER_H_
#define CVMFS_GLUE_BUFFER_H_

namespace glue {

static inline uint32_t hasher_md5(const shash::Md5 &key) {
  // Don't start with the first bytes, because == is using them as well
  return (uint32_t) *(reinterpret_cast<const uint32_t *>(key.digest) + 1);
}


static inline uint32_t hasher_inode(const uint64_t &inode) {
  return MurmurHash2(&inode, sizeof(inode), 0x07387a4f);
}


//------------------------------------------------------------------------------


/**
 * Pointer to a 2 byte length information followed by the characters
 */
class StringRef {
 public:
  StringRef() {
    length_ = NULL;
  }

  uint16_t length() const { return *length_; }
  uint16_t size() const { return sizeof(uint16_t) + *length_; }
  static uint16_t size(const uint16_t length) {
    return sizeof(uint16_t) + length;
  }
  char *data() const { return reinterpret_cast<char *>(length_ + 1); }
  static StringRef Place(const uint16_t length, const char *str,
                         void *addr)
  {
    StringRef result;
    result.length_ = reinterpret_cast<uint16_t *>(addr);
    *result.length_ = length;
    if (length > 0)
      memcpy(result.length_ + 1, str, length);
    return result;
  }
 private:
  uint16_t *length_;
};


//------------------------------------------------------------------------------


/**
 * Manages memory bins with immutable strings (deleting is a no-op).
 * When the fraction of garbage is too large, the user of the StringHeap
 * can copy the entire contents to a new heap.
 */
class StringHeap : public SingleCopy {
 public:
  StringHeap() {
    Init(128*1024);  // 128kB (should be >= 64kB+2B which is largest string)
  }

  explicit StringHeap(const uint32_t minimum_size) {
    Init(minimum_size);
  }

  void Init(const uint32_t minimum_size) {
    size_ = 0;
    used_ = 0;

    // Initial bin: 128kB or smallest power of 2 >= minimum size
    uint32_t pow2_size = minimum_size < 128*1024 ? 128*1024 : minimum_size;
    pow2_size--;
    pow2_size |= pow2_size >> 1;
    pow2_size |= pow2_size >> 2;
    pow2_size |= pow2_size >> 4;
    pow2_size |= pow2_size >> 8;
    pow2_size |= pow2_size >> 16;
    pow2_size++;
    AddBin(pow2_size);
  }

  ~StringHeap() {
    for (unsigned i = 0; i < bins_.size(); ++i) {
      smunmap(bins_.At(i));
    }
  }

  StringRef AddString(const uint16_t length, const char *str) {
    const uint16_t str_size = StringRef::size(length);
    const uint64_t remaining_bin_size = bin_size_ - bin_used_;
    // May require opening of new bin
    if (remaining_bin_size < str_size) {
      size_ += remaining_bin_size;
      AddBin(2*bin_size_);
    }
    StringRef result =
      StringRef::Place(length, str,
                       static_cast<char *>(bins_.At(bins_.size()-1))+bin_used_);
    size_ += str_size;
    used_ += str_size;
    bin_used_ += str_size;
    return result;
  }

  void RemoveString(const StringRef str_ref) {
    used_ -= str_ref.size();
  }

  double GetUsage() const {
    if (size_ == 0) return 1.0;
    return static_cast<double>(used_) / static_cast<double>(size_);
  }

  uint64_t used() const { return used_; }

 private:
  void AddBin(const uint64_t size) {
    void *bin = smmap(size);
    bins_.PushBack(bin);
    bin_size_ = size;
    bin_used_ = 0;
  }

  uint64_t size_;
  uint64_t used_;
  uint64_t bin_size_;
  uint64_t bin_used_;
  BigVector<void *> bins_;
};


//------------------------------------------------------------------------------


class PathStore {
 public:
  /**
   * Used to enumerate all paths
   */
  struct Cursor {
    Cursor() : idx(0) { }
    uint32_t idx;
  };


  PathStore() {
    map_.Init(16, shash::Md5(shash::AsciiPtr("!")), hasher_md5);
    string_heap_ = new StringHeap();
  }

  ~PathStore() {
    delete string_heap_;
  }

  explicit PathStore(const PathStore &other);
  PathStore &operator= (const PathStore &other);

  void Insert(const shash::Md5 &md5path, const PathString &path) {
    PathInfo info;
    bool found = map_.Lookup(md5path, &info);
    if (found) {
      info.refcnt++;
      map_.Insert(md5path, info);
      return;
    }

    PathInfo new_entry;
    if (path.IsEmpty()) {
      new_entry.name = string_heap_->AddString(0, "");
      map_.Insert(md5path, new_entry);
      return;
    }

    PathString parent_path = GetParentPath(path);
    new_entry.parent = shash::Md5(parent_path.GetChars(),
                                  parent_path.GetLength());
    Insert(new_entry.parent, parent_path);

    const uint16_t name_length = path.GetLength() - parent_path.GetLength() - 1;
    const char *name_str = path.GetChars() + parent_path.GetLength() + 1;
    new_entry.name = string_heap_->AddString(name_length, name_str);
    map_.Insert(md5path, new_entry);
  }

  bool Lookup(const shash::Md5 &md5path, PathString *path) {
    PathInfo info;
    bool retval = map_.Lookup(md5path, &info);
    if (!retval)
      return false;

    if (info.parent.IsNull())
      return true;

    retval = Lookup(info.parent, path);
    assert(retval);
    path->Append("/", 1);
    path->Append(info.name.data(), info.name.length());
    return true;
  }

  void Erase(const shash::Md5 &md5path) {
    PathInfo info;
    bool found = map_.Lookup(md5path, &info);
    if (!found)
      return;

    info.refcnt--;
    if (info.refcnt == 0) {
      map_.Erase(md5path);
      string_heap_->RemoveString(info.name);
      if (string_heap_->GetUsage() < 0.75) {
        StringHeap *new_string_heap = new StringHeap(string_heap_->used());
        shash::Md5 empty_path = map_.empty_key();
        for (unsigned i = 0; i < map_.capacity(); ++i) {
          if (map_.keys()[i] != empty_path) {
            (map_.values() + i)->name =
              new_string_heap->AddString(map_.values()[i].name.length(),
                                         map_.values()[i].name.data());
          }
        }
        delete string_heap_;
        string_heap_ = new_string_heap;
      }
      Erase(info.parent);
    } else {
      map_.Insert(md5path, info);
    }
  }

  void Clear() {
    map_.Clear();
    delete string_heap_;
    string_heap_ = new StringHeap();
  }

  Cursor BeginEnumerate() {
    return Cursor();
  }

  bool Next(Cursor *cursor, shash::Md5 *parent, StringRef *name) {
    shash::Md5 empty_key = map_.empty_key();
    while (cursor->idx < map_.capacity()) {
      if (map_.keys()[cursor->idx] == empty_key) {
        cursor->idx++;
        continue;
      }
      *parent = map_.values()[cursor->idx].parent;
      *name = map_.values()[cursor->idx].name;
      cursor->idx++;
      return true;
    }
    return false;
  }

 private:
  struct PathInfo {
    PathInfo() {
      refcnt = 1;
    }
    shash::Md5 parent;
    uint32_t refcnt;
    StringRef name;
  };

  void CopyFrom(const PathStore &other);

  SmallHashDynamic<shash::Md5, PathInfo> map_;
  StringHeap *string_heap_;
};


//------------------------------------------------------------------------------


class PathMap {
 public:
  PathMap() {
    map_.Init(16, shash::Md5(shash::AsciiPtr("!")), hasher_md5);
  }

  bool LookupPath(const shash::Md5 &md5path, PathString *path) {
    bool found = path_store_.Lookup(md5path, path);
    return found;
  }

  uint64_t LookupInodeByPath(const PathString &path) {
    uint64_t inode;
    bool found = map_.Lookup(shash::Md5(path.GetChars(), path.GetLength()),
                             &inode);
    if (found) return inode;
    return 0;
  }

  uint64_t LookupInodeByMd5Path(const shash::Md5 &md5path) {
    uint64_t inode;
    bool found = map_.Lookup(md5path, &inode);
    if (found) return inode;
    return 0;
  }

  shash::Md5 Insert(const PathString &path, const uint64_t inode) {
    shash::Md5 md5path(path.GetChars(), path.GetLength());
    if (!map_.Contains(md5path)) {
      path_store_.Insert(md5path, path);
      map_.Insert(md5path, inode);
    }
    return md5path;
  }

  void Erase(const shash::Md5 &md5path) {
    bool found = map_.Contains(md5path);
    if (found) {
      path_store_.Erase(md5path);
      map_.Erase(md5path);
    }
  }

  void Clear() {
    map_.Clear();
    path_store_.Clear();
  }

  // For enumerating
  PathStore *path_store() { return &path_store_; }

 private:
  SmallHashDynamic<shash::Md5, uint64_t> map_;
  PathStore path_store_;
};


//------------------------------------------------------------------------------


class InodeMap {
 public:
  InodeMap() {
    map_.Init(16, 0, hasher_inode);
  }

  bool LookupMd5Path(const uint64_t inode, shash::Md5 *md5path) {
    bool found = map_.Lookup(inode, md5path);
    return found;
  }

  void Insert(const uint64_t inode, const shash::Md5 &md5path) {
    map_.Insert(inode, md5path);
  }

  void Erase(const uint64_t inode) {
    map_.Erase(inode);
  }

  void Clear() { map_.Clear(); }

 private:
  SmallHashDynamic<uint64_t, shash::Md5> map_;
};


//------------------------------------------------------------------------------


class InodeReferences {
 public:
  /**
   * Used to enumerate all inodes
   */
  struct Cursor {
    Cursor() : idx(0) { }
    uint32_t idx;
  };

  InodeReferences() {
    map_.Init(16, 0, hasher_inode);
  }

  bool Get(const uint64_t inode, const uint32_t by) {
    uint32_t refcounter = 0;
    const bool found = map_.Lookup(inode, &refcounter);
    const bool new_inode = !found;
    refcounter += by;  // This is 0 if the inode is not found
    map_.Insert(inode, refcounter);
    return new_inode;
  }

  bool Put(const uint64_t inode, const uint32_t by) {
    uint32_t refcounter;
    bool found = map_.Lookup(inode, &refcounter);
    assert(found);
    assert(refcounter >= by);
    if (refcounter == by) {
      map_.Erase(inode);
      return true;
    }
    refcounter -= by;
    map_.Insert(inode, refcounter);
    return false;
  }

  void Clear() {
    map_.Clear();
  }

  Cursor BeginEnumerate() {
    return Cursor();
  }

  bool Next(Cursor *cursor, uint64_t *inode) {
    uint64_t empty_key = map_.empty_key();
    while (cursor->idx < map_.capacity()) {
      if (map_.keys()[cursor->idx] == empty_key) {
        cursor->idx++;
        continue;
      }
      *inode = map_.keys()[cursor->idx];
      cursor->idx++;
      return true;
    }
    return false;
  }

 private:
  SmallHashDynamic<uint64_t, uint32_t> map_;
};


//------------------------------------------------------------------------------


/**
 * Tracks inode reference counters as given by Fuse.
 */
class InodeTracker {
 public:
  /**
   * Used to actively evict all known paths from kernel caches
   */
  struct Cursor {
    explicit Cursor(
      const PathStore::Cursor &p,
      const InodeReferences::Cursor &i)
      : csr_paths(p)
      , csr_inos(i)
    { }
    PathStore::Cursor csr_paths;
    InodeReferences::Cursor csr_inos;
  };

  // Cannot be moved to the statistics manager because it has to survive
  // reloads.  Added manually in the fuse module initialization and in talk.cc.
  struct Statistics {
    Statistics() {
      atomic_init64(&num_inserts);
      atomic_init64(&num_removes);
      atomic_init64(&num_references);
      atomic_init64(&num_hits_inode);
      atomic_init64(&num_hits_path);
      atomic_init64(&num_misses_path);
    }
    std::string Print() {
      return
      "inserts: " + StringifyInt(atomic_read64(&num_inserts)) +
      "  removes: " + StringifyInt(atomic_read64(&num_removes)) +
      "  references: " + StringifyInt(atomic_read64(&num_references)) +
      "  hits(inode): " + StringifyInt(atomic_read64(&num_hits_inode)) +
      "  hits(path): " + StringifyInt(atomic_read64(&num_hits_path)) +
      "  misses(path): " + StringifyInt(atomic_read64(&num_misses_path));
    }
    atomic_int64 num_inserts;
    atomic_int64 num_removes;
    atomic_int64 num_references;
    atomic_int64 num_hits_inode;
    atomic_int64 num_hits_path;
    atomic_int64 num_misses_path;
  };
  Statistics GetStatistics() { return statistics_; }

  InodeTracker();
  explicit InodeTracker(const InodeTracker &other);
  InodeTracker &operator= (const InodeTracker &other);
  ~InodeTracker();

  void VfsGetBy(const uint64_t inode, const uint32_t by, const PathString &path)
  {
    Lock();
    bool new_inode = inode_references_.Get(inode, by);
    shash::Md5 md5path = path_map_.Insert(path, inode);
    inode_map_.Insert(inode, md5path);
    Unlock();

    atomic_xadd64(&statistics_.num_references, by);
    if (new_inode) atomic_inc64(&statistics_.num_inserts);
  }

  void VfsGet(const uint64_t inode, const PathString &path) {
    VfsGetBy(inode, 1, path);
  }

  void VfsPut(const uint64_t inode, const uint32_t by) {
    Lock();
    bool removed = inode_references_.Put(inode, by);
    if (removed) {
      // TODO(jblomer): pop operation (Lookup+Erase)
      shash::Md5 md5path;
      bool found = inode_map_.LookupMd5Path(inode, &md5path);
      assert(found);
      inode_map_.Erase(inode);
      path_map_.Erase(md5path);
      atomic_inc64(&statistics_.num_removes);
    }
    Unlock();
    atomic_xadd64(&statistics_.num_references, -int32_t(by));
  }

  bool FindPath(const uint64_t inode, PathString *path) {
    Lock();
    shash::Md5 md5path;
    bool found = inode_map_.LookupMd5Path(inode, &md5path);
    if (found) {
      found = path_map_.LookupPath(md5path, path);
      assert(found);
    }
    Unlock();

    if (found) {
      atomic_inc64(&statistics_.num_hits_path);
    } else {
      atomic_inc64(&statistics_.num_misses_path);
    }
    return found;
  }

  uint64_t FindInode(const PathString &path) {
    Lock();
    uint64_t inode = path_map_.LookupInodeByPath(path);
    Unlock();
    atomic_inc64(&statistics_.num_hits_inode);
    return inode;
  }

  Cursor BeginEnumerate() {
    Lock();
    return Cursor(path_map_.path_store()->BeginEnumerate(),
                  inode_references_.BeginEnumerate());
  }

  bool NextEntry(Cursor *cursor, uint64_t *inode_parent, NameString *name) {
    shash::Md5 parent_md5;
    StringRef name_ref;
    bool result = path_map_.path_store()->Next(
      &(cursor->csr_paths), &parent_md5, &name_ref);
    if (!result)
      return false;
    if (parent_md5.IsNull())
      *inode_parent = 0;
    else
      *inode_parent = path_map_.LookupInodeByMd5Path(parent_md5);
    name->Assign(name_ref.data(), name_ref.length());
    return true;
  }

  bool NextInode(Cursor *cursor, uint64_t *inode) {
    return inode_references_.Next(&(cursor->csr_inos), inode);
  }

  void EndEnumerate(Cursor *cursor) {
    Unlock();
  }

 private:
  static const unsigned kVersion = 4;

  void InitLock();
  void CopyFrom(const InodeTracker &other);
  inline void Lock() const {
    int retval = pthread_mutex_lock(lock_);
    assert(retval == 0);
  }
  inline void Unlock() const {
    int retval = pthread_mutex_unlock(lock_);
    assert(retval == 0);
  }

  unsigned version_;
  pthread_mutex_t *lock_;
  PathMap path_map_;
  InodeMap inode_map_;
  InodeReferences inode_references_;
  Statistics statistics_;
};  // class InodeTracker


}  // namespace glue

#endif  // CVMFS_GLUE_BUFFER_H_


Generated by: GCOVR (Version 4.1)

Line	Branch	Exec	Source
1			/**
2			* This file is part of the CernVM File System.
3			*
4			* This module provides the inode tracker in order to remember inodes
5			* and their parents that are in use by the kernel.
6			*
7			* These objects have to survive reloading of the library, so no virtual
8			* functions.
9			*/
10
11			#include <pthread.h>
12			#include <sched.h>
13			#include <stdint.h>
14
15			#include <cassert>
16			#include <cstring>
17			#include <map>
18			#include <string>
19			#include <vector>
20
21			#include "atomic.h"
22			#include "bigvector.h"
23			#include "hash.h"
24			#include "shortstring.h"
25			#include "smallhash.h"
26			#include "smalloc.h"
27			#include "util/posix.h"
28			#include "util/string.h"
29
30			#ifndef CVMFS_GLUE_BUFFER_H_
31			#define CVMFS_GLUE_BUFFER_H_
32
33			namespace glue {
34
35		10172	static inline uint32_t hasher_md5(const shash::Md5 &key) {
36			// Don't start with the first bytes, because == is using them as well
37		10172	return (uint32_t) (reinterpret_cast<const uint32_t >(key.digest) + 1);
38			}
39
40
41		7093	static inline uint32_t hasher_inode(const uint64_t &inode) {
42		7093	return MurmurHash2(&inode, sizeof(inode), 0x07387a4f);
43			}
44
45
46			//------------------------------------------------------------------------------
47
48
49			/**
50			* Pointer to a 2 byte length information followed by the characters
51			*/
52			class StringRef {
53			public:
54		10202	StringRef() {
55		10202	length_ = NULL;
56		10202	}
57
58		3	uint16_t length() const { return *length_; }
59			uint16_t size() const { return sizeof(uint16_t) + *length_; }
60		1027	static uint16_t size(const uint16_t length) {
61		1027	return sizeof(uint16_t) + length;
62			}
63		3	char data() const { return reinterpret_cast<char >(length_ + 1); }
64		1027	static StringRef Place(const uint16_t length, const char *str,
65			void *addr)
66			{
67		1027	StringRef result;
68		1027	result.length_ = reinterpret_cast<uint16_t *>(addr);
69		1027	*result.length_ = length;
70	✓✓	1027	if (length > 0)
71		1025	memcpy(result.length_ + 1, str, length);
72		1027	return result;
73			}
74			private:
75			uint16_t *length_;
76			};
77
78
79			//------------------------------------------------------------------------------
80
81
82			/**
83			* Manages memory bins with immutable strings (deleting is a no-op).
84			* When the fraction of garbage is too large, the user of the StringHeap
85			* can copy the entire contents to a new heap.
86			*/
87			class StringHeap : public SingleCopy {
88			public:
89		36	StringHeap() {
90		36	Init(128*1024); // 128kB (should be >= 64kB+2B which is largest string)
91			}
92
93			explicit StringHeap(const uint32_t minimum_size) {
94			Init(minimum_size);
95			}
96
97		36	void Init(const uint32_t minimum_size) {
98		36	size_ = 0;
99		36	used_ = 0;
100
101			// Initial bin: 128kB or smallest power of 2 >= minimum size
102		36	uint32_t pow2_size = minimum_size < 1281024 ? 1281024 : minimum_size;
103		36	pow2_size--;
104		36	pow2_size \|= pow2_size >> 1;
105		36	pow2_size \|= pow2_size >> 2;
106		36	pow2_size \|= pow2_size >> 4;
107		36	pow2_size \|= pow2_size >> 8;
108		36	pow2_size \|= pow2_size >> 16;
109		36	pow2_size++;
110		36	AddBin(pow2_size);
111		36	}
112
113		36	~StringHeap() {
114	✓✓	72	for (unsigned i = 0; i < bins_.size(); ++i) {
115		36	smunmap(bins_.At(i));
116			}
117			}
118
119		1027	StringRef AddString(const uint16_t length, const char *str) {
120		1027	const uint16_t str_size = StringRef::size(length);
121		1027	const uint64_t remaining_bin_size = bin_size_ - bin_used_;
122			// May require opening of new bin
123	✗✓	1027	if (remaining_bin_size < str_size) {
124			size_ += remaining_bin_size;
125			AddBin(2*bin_size_);
126			}
127			StringRef result =
128			StringRef::Place(length, str,
129		1027	static_cast<char *>(bins_.At(bins_.size()-1))+bin_used_);
130		1027	size_ += str_size;
131		1027	used_ += str_size;
132		1027	bin_used_ += str_size;
133		1027	return result;
134			}
135
136			void RemoveString(const StringRef str_ref) {
137			used_ -= str_ref.size();
138			}
139
140			double GetUsage() const {
141			if (size_ == 0) return 1.0;
142			return static_cast<double>(used_) / static_cast<double>(size_);
143			}
144
145			uint64_t used() const { return used_; }
146
147			private:
148		36	void AddBin(const uint64_t size) {
149		36	void *bin = smmap(size);
150		36	bins_.PushBack(bin);
151		36	bin_size_ = size;
152		36	bin_used_ = 0;
153		36	}
154
155			uint64_t size_;
156			uint64_t used_;
157			uint64_t bin_size_;
158			uint64_t bin_used_;
159			BigVector<void *> bins_;
160			};
161
162
163			//------------------------------------------------------------------------------
164
165
166			class PathStore {
167			public:
168			/**
169			* Used to enumerate all paths
170			*/
171			struct Cursor {
172		5	Cursor() : idx(0) { }
173			uint32_t idx;
174			};
175
176
177		36	PathStore() {
178		36	map_.Init(16, shash::Md5(shash::AsciiPtr("!")), hasher_md5);
179		36	string_heap_ = new StringHeap();
180		36	}
181
182		36	~PathStore() {
183	✓✗	36	delete string_heap_;
184			}
185
186			explicit PathStore(const PathStore &other);
187			PathStore &operator= (const PathStore &other);
188
189		2052	void Insert(const shash::Md5 &md5path, const PathString &path) {
190		2052	PathInfo info;
191		2052	bool found = map_.Lookup(md5path, &info);
192	✓✓	2052	if (found) {
193		1025	info.refcnt++;
194		1025	map_.Insert(md5path, info);
195		1025	return;
196			}
197
198		1027	PathInfo new_entry;
199	✓✓	1027	if (path.IsEmpty()) {
200		2	new_entry.name = string_heap_->AddString(0, "");
201		2	map_.Insert(md5path, new_entry);
202		2	return;
203			}
204
205		1025	PathString parent_path = GetParentPath(path);
206			new_entry.parent = shash::Md5(parent_path.GetChars(),
207	✗✓	1025	parent_path.GetLength());
208		1025	Insert(new_entry.parent, parent_path);
209
210		1025	const uint16_t name_length = path.GetLength() - parent_path.GetLength() - 1;
211		1025	const char *name_str = path.GetChars() + parent_path.GetLength() + 1;
212		1025	new_entry.name = string_heap_->AddString(name_length, name_str);
213		1025	map_.Insert(md5path, new_entry);
214			}
215
216			bool Lookup(const shash::Md5 &md5path, PathString *path) {
217			PathInfo info;
218			bool retval = map_.Lookup(md5path, &info);
219			if (!retval)
220			return false;
221
222			if (info.parent.IsNull())
223			return true;
224
225			retval = Lookup(info.parent, path);
226			assert(retval);
227			path->Append("/", 1);
228			path->Append(info.name.data(), info.name.length());
229			return true;
230			}
231
232			void Erase(const shash::Md5 &md5path) {
233			PathInfo info;
234			bool found = map_.Lookup(md5path, &info);
235			if (!found)
236			return;
237
238			info.refcnt--;
239			if (info.refcnt == 0) {
240			map_.Erase(md5path);
241			string_heap_->RemoveString(info.name);
242			if (string_heap_->GetUsage() < 0.75) {
243			StringHeap *new_string_heap = new StringHeap(string_heap_->used());
244			shash::Md5 empty_path = map_.empty_key();
245			for (unsigned i = 0; i < map_.capacity(); ++i) {
246			if (map_.keys()[i] != empty_path) {
247			(map_.values() + i)->name =
248			new_string_heap->AddString(map_.values()[i].name.length(),
249			map_.values()[i].name.data());
250			}
251			}
252			delete string_heap_;
253			string_heap_ = new_string_heap;
254			}
255			Erase(info.parent);
256			} else {
257			map_.Insert(md5path, info);
258			}
259			}
260
261			void Clear() {
262			map_.Clear();
263			delete string_heap_;
264			string_heap_ = new StringHeap();
265			}
266
267		5	Cursor BeginEnumerate() {
268		5	return Cursor();
269			}
270
271		6	bool Next(Cursor cursor, shash::Md5 parent, StringRef *name) {
272		6	shash::Md5 empty_key = map_.empty_key();
273	✓✓	6	while (cursor->idx < map_.capacity()) {
274	✓✓	42	if (map_.keys()[cursor->idx] == empty_key) {
275		39	cursor->idx++;
276		39	continue;
277			}
278	✗✓	3	*parent = map_.values()[cursor->idx].parent;
279		3	*name = map_.values()[cursor->idx].name;
280		3	cursor->idx++;
281		3	return true;
282			}
283		3	return false;
284			}
285
286			private:
287		6090	struct PathInfo {
288		9169	PathInfo() {
289		9169	refcnt = 1;
290		9169	}
291			shash::Md5 parent;
292			uint32_t refcnt;
293			StringRef name;
294			};
295
296			void CopyFrom(const PathStore &other);
297
298			SmallHashDynamic<shash::Md5, PathInfo> map_;
299			StringHeap *string_heap_;
300			};
301
302
303			//------------------------------------------------------------------------------
304
305
306		36	class PathMap {
307			public:
308		36	PathMap() {
309		36	map_.Init(16, shash::Md5(shash::AsciiPtr("!")), hasher_md5);
310		36	}
311
312			bool LookupPath(const shash::Md5 &md5path, PathString *path) {
313			bool found = path_store_.Lookup(md5path, path);
314			return found;
315			}
316
317			uint64_t LookupInodeByPath(const PathString &path) {
318			uint64_t inode;
319			bool found = map_.Lookup(shash::Md5(path.GetChars(), path.GetLength()),
320			&inode);
321			if (found) return inode;
322			return 0;
323			}
324
325		2	uint64_t LookupInodeByMd5Path(const shash::Md5 &md5path) {
326			uint64_t inode;
327		2	bool found = map_.Lookup(md5path, &inode);
328	✓✗	2	if (found) return inode;
329			return 0;
330			}
331
332		1027	shash::Md5 Insert(const PathString &path, const uint64_t inode) {
333		1027	shash::Md5 md5path(path.GetChars(), path.GetLength());
334	✓✗	1027	if (!map_.Contains(md5path)) {
335		1027	path_store_.Insert(md5path, path);
336		1027	map_.Insert(md5path, inode);
337			}
338		1027	return md5path;
339			}
340
341			void Erase(const shash::Md5 &md5path) {
342			bool found = map_.Contains(md5path);
343			if (found) {
344			path_store_.Erase(md5path);
345			map_.Erase(md5path);
346			}
347			}
348
349			void Clear() {
350			map_.Clear();
351			path_store_.Clear();
352			}
353
354			// For enumerating
355		11	PathStore *path_store() { return &path_store_; }
356
357			private:
358			SmallHashDynamic<shash::Md5, uint64_t> map_;
359			PathStore path_store_;
360			};
361
362
363			//------------------------------------------------------------------------------
364
365
366		36	class InodeMap {
367			public:
368		36	InodeMap() {
369		36	map_.Init(16, 0, hasher_inode);
370			}
371
372			bool LookupMd5Path(const uint64_t inode, shash::Md5 *md5path) {
373			bool found = map_.Lookup(inode, md5path);
374			return found;
375			}
376
377		1027	void Insert(const uint64_t inode, const shash::Md5 &md5path) {
378		1027	map_.Insert(inode, md5path);
379		1027	}
380
381			void Erase(const uint64_t inode) {
382			map_.Erase(inode);
383			}
384
385			void Clear() { map_.Clear(); }
386
387			private:
388			SmallHashDynamic<uint64_t, shash::Md5> map_;
389			};
390
391
392			//------------------------------------------------------------------------------
393
394
395		36	class InodeReferences {
396			public:
397			/**
398			* Used to enumerate all inodes
399			*/
400			struct Cursor {
401		5	Cursor() : idx(0) { }
402			uint32_t idx;
403			};
404
405		36	InodeReferences() {
406		36	map_.Init(16, 0, hasher_inode);
407			}
408
409		1027	bool Get(const uint64_t inode, const uint32_t by) {
410		1027	uint32_t refcounter = 0;
411		1027	const bool found = map_.Lookup(inode, &refcounter);
412		1027	const bool new_inode = !found;
413		1027	refcounter += by; // This is 0 if the inode is not found
414		1027	map_.Insert(inode, refcounter);
415		1027	return new_inode;
416			}
417
418			bool Put(const uint64_t inode, const uint32_t by) {
419			uint32_t refcounter;
420			bool found = map_.Lookup(inode, &refcounter);
421			assert(found);
422			assert(refcounter >= by);
423			if (refcounter == by) {
424			map_.Erase(inode);
425			return true;
426			}
427			refcounter -= by;
428			map_.Insert(inode, refcounter);
429			return false;
430			}
431
432			void Clear() {
433			map_.Clear();
434			}
435
436		5	Cursor BeginEnumerate() {
437		5	return Cursor();
438			}
439
440		3080	bool Next(Cursor cursor, uint64_t inode) {
441		3080	uint64_t empty_key = map_.empty_key();
442	✓✓	11191	while (cursor->idx < map_.capacity()) {
443	✓✓	8106	if (map_.keys()[cursor->idx] == empty_key) {
444		5031	cursor->idx++;
445		5031	continue;
446			}
447		3075	*inode = map_.keys()[cursor->idx];
448		3075	cursor->idx++;
449		3075	return true;
450			}
451		5	return false;
452			}
453
454			private:
455			SmallHashDynamic<uint64_t, uint32_t> map_;
456			};
457
458
459			//------------------------------------------------------------------------------
460
461
462			/**
463			* Tracks inode reference counters as given by Fuse.
464			*/
465			class InodeTracker {
466			public:
467			/**
468			* Used to actively evict all known paths from kernel caches
469			*/
470			struct Cursor {
471		5	explicit Cursor(
472			const PathStore::Cursor &p,
473			const InodeReferences::Cursor &i)
474			: csr_paths(p)
475		5	, csr_inos(i)
476		5	{ }
477			PathStore::Cursor csr_paths;
478			InodeReferences::Cursor csr_inos;
479			};
480
481			// Cannot be moved to the statistics manager because it has to survive
482			// reloads. Added manually in the fuse module initialization and in talk.cc.
483			struct Statistics {
484		36	Statistics() {
485		36	atomic_init64(&num_inserts);
486		36	atomic_init64(&num_removes);
487		36	atomic_init64(&num_references);
488		36	atomic_init64(&num_hits_inode);
489		36	atomic_init64(&num_hits_path);
490		36	atomic_init64(&num_misses_path);
491		36	}
492			std::string Print() {
493			return
494			"inserts: " + StringifyInt(atomic_read64(&num_inserts)) +
495			" removes: " + StringifyInt(atomic_read64(&num_removes)) +
496			" references: " + StringifyInt(atomic_read64(&num_references)) +
497			" hits(inode): " + StringifyInt(atomic_read64(&num_hits_inode)) +
498			" hits(path): " + StringifyInt(atomic_read64(&num_hits_path)) +
499			" misses(path): " + StringifyInt(atomic_read64(&num_misses_path));
500			}
501			atomic_int64 num_inserts;
502			atomic_int64 num_removes;
503			atomic_int64 num_references;
504			atomic_int64 num_hits_inode;
505			atomic_int64 num_hits_path;
506			atomic_int64 num_misses_path;
507			};
508			Statistics GetStatistics() { return statistics_; }
509
510			InodeTracker();
511			explicit InodeTracker(const InodeTracker &other);
512			InodeTracker &operator= (const InodeTracker &other);
513			~InodeTracker();
514
515		1027	void VfsGetBy(const uint64_t inode, const uint32_t by, const PathString &path)
516			{
517		1027	Lock();
518		1027	bool new_inode = inode_references_.Get(inode, by);
519		1027	shash::Md5 md5path = path_map_.Insert(path, inode);
520		1027	inode_map_.Insert(inode, md5path);
521		1027	Unlock();
522
523		1027	atomic_xadd64(&statistics_.num_references, by);
524	✓✗	1027	if (new_inode) atomic_inc64(&statistics_.num_inserts);
525		1027	}
526
527		1027	void VfsGet(const uint64_t inode, const PathString &path) {
528		1027	VfsGetBy(inode, 1, path);
529		1027	}
530
531			void VfsPut(const uint64_t inode, const uint32_t by) {
532			Lock();
533			bool removed = inode_references_.Put(inode, by);
534			if (removed) {
535			// TODO(jblomer): pop operation (Lookup+Erase)
536			shash::Md5 md5path;
537			bool found = inode_map_.LookupMd5Path(inode, &md5path);
538			assert(found);
539			inode_map_.Erase(inode);
540			path_map_.Erase(md5path);
541			atomic_inc64(&statistics_.num_removes);
542			}
543			Unlock();
544			atomic_xadd64(&statistics_.num_references, -int32_t(by));
545			}
546
547			bool FindPath(const uint64_t inode, PathString *path) {
548			Lock();
549			shash::Md5 md5path;
550			bool found = inode_map_.LookupMd5Path(inode, &md5path);
551			if (found) {
552			found = path_map_.LookupPath(md5path, path);
553			assert(found);
554			}
555			Unlock();
556
557			if (found) {
558			atomic_inc64(&statistics_.num_hits_path);
559			} else {
560			atomic_inc64(&statistics_.num_misses_path);
561			}
562			return found;
563			}
564
565			uint64_t FindInode(const PathString &path) {
566			Lock();
567			uint64_t inode = path_map_.LookupInodeByPath(path);
568			Unlock();
569			atomic_inc64(&statistics_.num_hits_inode);
570			return inode;
571			}
572
573		5	Cursor BeginEnumerate() {
574		5	Lock();
575			return Cursor(path_map_.path_store()->BeginEnumerate(),
576		5	inode_references_.BeginEnumerate());
577			}
578
579		6	bool NextEntry(Cursor cursor, uint64_t inode_parent, NameString *name) {
580		6	shash::Md5 parent_md5;
581		6	StringRef name_ref;
582			bool result = path_map_.path_store()->Next(
583		6	&(cursor->csr_paths), &parent_md5, &name_ref);
584	✓✓	6	if (!result)
585		3	return false;
586	✓✓	3	if (parent_md5.IsNull())
587		1	*inode_parent = 0;
588			else
589		2	*inode_parent = path_map_.LookupInodeByMd5Path(parent_md5);
590		3	name->Assign(name_ref.data(), name_ref.length());
591		3	return true;
592			}
593
594		3080	bool NextInode(Cursor cursor, uint64_t inode) {
595		3080	return inode_references_.Next(&(cursor->csr_inos), inode);
596			}
597
598		5	void EndEnumerate(Cursor *cursor) {
599		5	Unlock();
600		5	}
601
602			private:
603			static const unsigned kVersion = 4;
604
605			void InitLock();
606			void CopyFrom(const InodeTracker &other);
607		1032	inline void Lock() const {
608		1032	int retval = pthread_mutex_lock(lock_);
609	✗✓	1032	assert(retval == 0);
610		1032	}
611		1032	inline void Unlock() const {
612		1032	int retval = pthread_mutex_unlock(lock_);
613	✗✓	1032	assert(retval == 0);
614		1032	}
615
616			unsigned version_;
617			pthread_mutex_t *lock_;
618			PathMap path_map_;
619			InodeMap inode_map_;
620			InodeReferences inode_references_;
621			Statistics statistics_;
622			}; // class InodeTracker
623
624
625			} // namespace glue
626
627			#endif // CVMFS_GLUE_BUFFER_H_