Head

GCC Code Coverage Report

Directory:	cvmfs/		Exec	Total	Coverage
File:	cvmfs/catalog_balancer_impl.h	Lines:	82	85	96.5 %
Date:	2019-02-03 02:48:13	Branches:	39	55	70.9 %


/**
 * This file is part of the CernVM File System.
 */

#ifndef CVMFS_CATALOG_BALANCER_IMPL_H_
#define CVMFS_CATALOG_BALANCER_IMPL_H_


#include <inttypes.h>

#include <cassert>
#include <cstdlib>
#include <string>
#include <vector>

#include "catalog_mgr.h"
#include "compression.h"
#include "directory_entry.h"
#include "hash.h"
#include "logging.h"


using namespace std;  // NOLINT

namespace catalog {

template <class CatalogMgrT>
DirectoryEntryBase
CatalogBalancer<CatalogMgrT>::MakeEmptyDirectoryEntryBase(
  string name,
  uid_t uid,
  gid_t gid)
{
  // Note that another entity needs to ensure that the object of an empty
  // file is in the repository!  It is currently done by the sync_mediator.
  shash::Algorithms algorithm = catalog_mgr_->spooler_->GetHashAlgorithm();
  shash::Any file_hash(algorithm);
  void *empty_compressed;
  uint64_t sz_empty_compressed;
  bool retval = zlib::CompressMem2Mem(
    NULL, 0, &empty_compressed, &sz_empty_compressed);
  assert(retval);
  shash::HashMem(static_cast<unsigned char *>(empty_compressed),
                 sz_empty_compressed, &file_hash);
  free(empty_compressed);

  DirectoryEntryBase deb;
  deb.name_ = NameString(name);
  deb.mode_ = S_IFREG | S_IRUSR | S_IWUSR;
  deb.checksum_ = file_hash;
  deb.mtime_ = time(NULL);
  deb.uid_ = uid;
  deb.gid_ = gid;
  return deb;
}

template <class CatalogMgrT>
void CatalogBalancer<CatalogMgrT>::AddCatalogMarker(string path) {
  XattrList xattr;
  DirectoryEntry parent;
  bool retval;
  retval = catalog_mgr_->LookupPath(PathString(path), kLookupSole, &parent);
  assert(retval);
  DirectoryEntryBase cvmfscatalog =
      MakeEmptyDirectoryEntryBase(".cvmfscatalog", parent.uid(),
                                           parent.gid());
  DirectoryEntryBase cvmfsautocatalog =
      MakeEmptyDirectoryEntryBase(".cvmfsautocatalog", parent.uid(),
                                           parent.gid());
  string relative_path = path.substr(1);
  catalog_mgr_->AddFile(cvmfscatalog, xattr, relative_path);
  catalog_mgr_->AddFile(cvmfsautocatalog, xattr, relative_path);
}

template <class CatalogMgrT>
void CatalogBalancer<CatalogMgrT>::Balance(catalog_t *catalog) {
  if (catalog == NULL) {
    // obtain a copy of the catalogs
    vector<catalog_t*> catalogs = catalog_mgr_->GetCatalogs();
    // we need to reverse the catalog list in order to analyze the
    // last added ones first. This is necessary in the weird case the child
    // catalog's underflow provokes an overflow in the father
    reverse(catalogs.begin(), catalogs.end());
    for (unsigned i = 0; i < catalogs.size(); ++i)
      Balance(catalogs[i]);
    return;
  }
  string catalog_path = catalog->mountpoint().ToString();
  virtual_node_t root_node(catalog_path, catalog_mgr_);
  root_node.ExtractChildren(catalog_mgr_);
  // we have just recursively loaded the entire virtual tree!
  PartitionOptimally(&root_node);
}

template <class CatalogMgrT>
void CatalogBalancer<CatalogMgrT>::PartitionOptimally(
    virtual_node_t *virtual_node) {
  // postorder track of the fs-tree
  for (unsigned i = 0; i < virtual_node->children.size(); ++i) {
    virtual_node_t *virtual_child =
        &virtual_node->children[i];
    if (virtual_child->IsDirectory() && !virtual_child->IsCatalog())
      PartitionOptimally(virtual_child);
  }
  virtual_node->FixWeight();
  while (virtual_node->weight > catalog_mgr_->balance_weight_) {
    virtual_node_t *heaviest_node =
        MaxChild(virtual_node);
    // we directly add a catalog in this node
    // TODO(molina) apply heuristics here
    if (heaviest_node != NULL &&
        heaviest_node->weight >= catalog_mgr_->min_weight_) {
      // the catalog now generated _cannot_ be overflowed because the tree is
      // being traversed in postorder, handling the lightest nodes first
      unsigned max_weight = heaviest_node->weight;
      AddCatalogMarker(heaviest_node->path);
      AddCatalog(heaviest_node);
      virtual_node->weight -= (max_weight - 1);
    } else {
      // there is no possibility for any this directory's children
      // to be a catalog
      LogCvmfs(kLogPublish, kLogStdout, "Couldn't create a new nested catalog"
        " in any subdirectory of '%s' even though"
        " currently it is overflowed", virtual_node->path.c_str());
      break;
    }
  }
}

template <class CatalogMgrT>
typename CatalogBalancer<CatalogMgrT>::VirtualNode*
CatalogBalancer<CatalogMgrT>::MaxChild(
    virtual_node_t *virtual_node)
{
  virtual_node_t *max_child = NULL;
  unsigned max_weight = 0;
  if (virtual_node->IsDirectory() &&
      !virtual_node->IsCatalog() &&
      !virtual_node->is_new_nested_catalog) {
    for (unsigned i = 0; i < virtual_node->children.size(); ++i) {
      virtual_node_t *child = &virtual_node->children[i];
      if (child->IsDirectory() &&
          !child->IsCatalog() &&
          max_weight < child->weight) {
        max_weight = child->weight;
        max_child = child;
      }
    }
  }
  return max_child;
}

template <class CatalogMgrT>
void CatalogBalancer<CatalogMgrT>::AddCatalog(virtual_node_t *child_node) {
  assert(child_node != NULL);
  string new_catalog_path = child_node->path.substr(1);
  catalog_mgr_->CreateNestedCatalog(new_catalog_path);
  child_node->weight = 1;
  child_node->is_new_nested_catalog = true;
  LogCvmfs(kLogPublish, kLogStdout, "Automatic creation of nested"
      " catalog in '%s'", child_node->path.c_str());
}

template <class CatalogMgrT>
void CatalogBalancer<CatalogMgrT>::VirtualNode::ExtractChildren(
    CatalogMgrT *catalog_mgr) {
  DirectoryEntryList direntlist;
  catalog_mgr->Listing(path, &direntlist);
  for (unsigned i = 0; i < direntlist.size(); ++i) {
    string child_path = path + "/" + direntlist[i].name().ToString();
    children.push_back(virtual_node_t(
        child_path, direntlist[i], catalog_mgr));
    weight += children[i].weight;
  }
}

/**
 * This function is called in the father node when one of its children has
 * changed its weight. This phenomenon only occurs when one of its children has
 * become a new autogenerated nested catalog, and its weight is now 1 (which
 * represents the sole DirectoryEntry of that directory).
 * However this is not propagated to the top or the bottom of the tree, but each
 * VirtualNode that represents a directory is responsible for calling it when
 * previous operations might have changed the weight of its children (and
 * consequently its own weight).
 * This function is also called the first time this VirtualNodeit is used to
 * set its weight to the actual value. Initially the weight of any VirtualNode
 * is always 1.
 */
template <class CatalogMgrT>
void CatalogBalancer<CatalogMgrT>::VirtualNode::FixWeight() {
  weight = 1;
  if (!IsCatalog() && IsDirectory()) {
    for (unsigned i = 0; i < children.size(); ++i) {
      weight += children[i].weight;
    }
  }
}

}  // namespace catalog

#endif  // CVMFS_CATALOG_BALANCER_IMPL_H_


Generated by: GCOVR (Version 4.1)

Line	Branch	Exec	Source
1			/**
2			* This file is part of the CernVM File System.
3			*/
4
5			#ifndef CVMFS_CATALOG_BALANCER_IMPL_H_
6			#define CVMFS_CATALOG_BALANCER_IMPL_H_
7
8
9			#include <inttypes.h>
10
11			#include <cassert>
12			#include <cstdlib>
13			#include <string>
14			#include <vector>
15
16			#include "catalog_mgr.h"
17			#include "compression.h"
18			#include "directory_entry.h"
19			#include "hash.h"
20			#include "logging.h"
21
22
23			using namespace std; // NOLINT
24
25			namespace catalog {
26
27			template <class CatalogMgrT>
28			DirectoryEntryBase
29		2	CatalogBalancer<CatalogMgrT>::MakeEmptyDirectoryEntryBase(
30			string name,
31			uid_t uid,
32			gid_t gid)
33			{
34			// Note that another entity needs to ensure that the object of an empty
35			// file is in the repository! It is currently done by the sync_mediator.
36		2	shash::Algorithms algorithm = catalog_mgr_->spooler_->GetHashAlgorithm();
37		2	shash::Any file_hash(algorithm);
38			void *empty_compressed;
39			uint64_t sz_empty_compressed;
40			bool retval = zlib::CompressMem2Mem(
41		2	NULL, 0, &empty_compressed, &sz_empty_compressed);
42	✗✓	2	assert(retval);
43		2	shash::HashMem(static_cast<unsigned char *>(empty_compressed),
44			sz_empty_compressed, &file_hash);
45		2	free(empty_compressed);
46
47		2	DirectoryEntryBase deb;
48		2	deb.name_ = NameString(name);
49		2	deb.mode_ = S_IFREG \| S_IRUSR \| S_IWUSR;
50	✗✓	2	deb.checksum_ = file_hash;
51		2	deb.mtime_ = time(NULL);
52		2	deb.uid_ = uid;
53		2	deb.gid_ = gid;
54		2	return deb;
55			}
56
57			template <class CatalogMgrT>
58		1	void CatalogBalancer<CatalogMgrT>::AddCatalogMarker(string path) {
59		1	XattrList xattr;
60		1	DirectoryEntry parent;
61			bool retval;
62		1	retval = catalog_mgr_->LookupPath(PathString(path), kLookupSole, &parent);
63	✗✓	1	assert(retval);
64			DirectoryEntryBase cvmfscatalog =
65			MakeEmptyDirectoryEntryBase(".cvmfscatalog", parent.uid(),
66		1	parent.gid());
67			DirectoryEntryBase cvmfsautocatalog =
68			MakeEmptyDirectoryEntryBase(".cvmfsautocatalog", parent.uid(),
69		1	parent.gid());
70		1	string relative_path = path.substr(1);
71		1	catalog_mgr_->AddFile(cvmfscatalog, xattr, relative_path);
72		1	catalog_mgr_->AddFile(cvmfsautocatalog, xattr, relative_path);
73		1	}
74
75			template <class CatalogMgrT>
76		2	void CatalogBalancer<CatalogMgrT>::Balance(catalog_t *catalog) {
77	✓✓	2	if (catalog == NULL) {
78			// obtain a copy of the catalogs
79		1	vector<catalog_t*> catalogs = catalog_mgr_->GetCatalogs();
80			// we need to reverse the catalog list in order to analyze the
81			// last added ones first. This is necessary in the weird case the child
82			// catalog's underflow provokes an overflow in the father
83		1	reverse(catalogs.begin(), catalogs.end());
84	✓✓	2	for (unsigned i = 0; i < catalogs.size(); ++i)
85		1	Balance(catalogs[i]);
86			return;
87			}
88		1	string catalog_path = catalog->mountpoint().ToString();
89		1	virtual_node_t root_node(catalog_path, catalog_mgr_);
90		1	root_node.ExtractChildren(catalog_mgr_);
91			// we have just recursively loaded the entire virtual tree!
92		1	PartitionOptimally(&root_node);
93			}
94
95			template <class CatalogMgrT>
96		3	void CatalogBalancer<CatalogMgrT>::PartitionOptimally(
97			virtual_node_t *virtual_node) {
98			// postorder track of the fs-tree
99	✓✓	8	for (unsigned i = 0; i < virtual_node->children.size(); ++i) {
100			virtual_node_t *virtual_child =
101		5	&virtual_node->children[i];
102	✓✓✓✓ ✓✓	5	if (virtual_child->IsDirectory() && !virtual_child->IsCatalog())
103		2	PartitionOptimally(virtual_child);
104			}
105		3	virtual_node->FixWeight();
106	✓✓	3	while (virtual_node->weight > catalog_mgr_->balance_weight_) {
107			virtual_node_t *heaviest_node =
108		1	MaxChild(virtual_node);
109			// we directly add a catalog in this node
110			// TODO(molina) apply heuristics here
111	✓✗✓✗	2	if (heaviest_node != NULL &&
112			heaviest_node->weight >= catalog_mgr_->min_weight_) {
113			// the catalog now generated _cannot_ be overflowed because the tree is
114			// being traversed in postorder, handling the lightest nodes first
115		1	unsigned max_weight = heaviest_node->weight;
116		1	AddCatalogMarker(heaviest_node->path);
117		1	AddCatalog(heaviest_node);
118		1	virtual_node->weight -= (max_weight - 1);
119			} else {
120			// there is no possibility for any this directory's children
121			// to be a catalog
122			LogCvmfs(kLogPublish, kLogStdout, "Couldn't create a new nested catalog"
123			" in any subdirectory of '%s' even though"
124			" currently it is overflowed", virtual_node->path.c_str());
125			break;
126			}
127			}
128		3	}
129
130			template <class CatalogMgrT>
131			typename CatalogBalancer<CatalogMgrT>::VirtualNode*
132		1	CatalogBalancer<CatalogMgrT>::MaxChild(
133			virtual_node_t *virtual_node)
134			{
135		1	virtual_node_t *max_child = NULL;
136		1	unsigned max_weight = 0;
137	✓✗✓✗ ✓✗✓✗	1	if (virtual_node->IsDirectory() &&
138			!virtual_node->IsCatalog() &&
139			!virtual_node->is_new_nested_catalog) {
140	✓✓	2	for (unsigned i = 0; i < virtual_node->children.size(); ++i) {
141		1	virtual_node_t *child = &virtual_node->children[i];
142	✓✗✓✗ ✓✗✓✗	1	if (child->IsDirectory() &&
143			!child->IsCatalog() &&
144			max_weight < child->weight) {
145		1	max_weight = child->weight;
146		1	max_child = child;
147			}
148			}
149			}
150		1	return max_child;
151			}
152
153			template <class CatalogMgrT>
154		1	void CatalogBalancer<CatalogMgrT>::AddCatalog(virtual_node_t *child_node) {
155	✗✓	1	assert(child_node != NULL);
156		1	string new_catalog_path = child_node->path.substr(1);
157		1	catalog_mgr_->CreateNestedCatalog(new_catalog_path);
158		1	child_node->weight = 1;
159		1	child_node->is_new_nested_catalog = true;
160		1	LogCvmfs(kLogPublish, kLogStdout, "Automatic creation of nested"
161			" catalog in '%s'", child_node->path.c_str());
162		1	}
163
164			template <class CatalogMgrT>
165		3	void CatalogBalancer<CatalogMgrT>::VirtualNode::ExtractChildren(
166			CatalogMgrT *catalog_mgr) {
167		3	DirectoryEntryList direntlist;
168		3	catalog_mgr->Listing(path, &direntlist);
169	✗✓✓	8	for (unsigned i = 0; i < direntlist.size(); ++i) {
170		5	string child_path = path + "/" + direntlist[i].name().ToString();
171		5	children.push_back(virtual_node_t(
172			child_path, direntlist[i], catalog_mgr));
173		5	weight += children[i].weight;
174			}
175		3	}
176
177			/**
178			* This function is called in the father node when one of its children has
179			* changed its weight. This phenomenon only occurs when one of its children has
180			* become a new autogenerated nested catalog, and its weight is now 1 (which
181			* represents the sole DirectoryEntry of that directory).
182			* However this is not propagated to the top or the bottom of the tree, but each
183			* VirtualNode that represents a directory is responsible for calling it when
184			* previous operations might have changed the weight of its children (and
185			* consequently its own weight).
186			* This function is also called the first time this VirtualNodeit is used to
187			* set its weight to the actual value. Initially the weight of any VirtualNode
188			* is always 1.
189			*/
190			template <class CatalogMgrT>
191		3	void CatalogBalancer<CatalogMgrT>::VirtualNode::FixWeight() {
192		3	weight = 1;
193	✓✓✓✗ ✓✓	3	if (!IsCatalog() && IsDirectory()) {
194	✓✓	5	for (unsigned i = 0; i < children.size(); ++i) {
195		3	weight += children[i].weight;
196			}
197			}
198		3	}
199
200			} // namespace catalog
201
202			#endif // CVMFS_CATALOG_BALANCER_IMPL_H_