GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/catalog_balancer_impl.h
Date: 2025-02-02 02:34:22
Exec Total Coverage
Lines: 91 93 97.8%
Branches: 70 122 57.4%
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/compression.h"
18 #include "crypto/hash.h"
19 #include "directory_entry.h"
20 #include "util/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
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 shash::Any file_hash(algorithm);
38 void *empty_compressed;
39 uint64_t sz_empty_compressed;
40
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 bool retval = zlib::CompressMem2Mem(
41 NULL, 0, &empty_compressed, &sz_empty_compressed);
42
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 assert(retval);
43
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 shash::HashMem(static_cast<unsigned char *>(empty_compressed),
44 sz_empty_compressed, &file_hash);
45 2 free(empty_compressed);
46
47
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 DirectoryEntryBase deb;
48
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 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 4 return deb;
55 }
56
57 template <class CatalogMgrT>
58 1 void CatalogBalancer<CatalogMgrT>::AddCatalogMarker(string path) {
59 1 XattrList xattr;
60
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 DirectoryEntry parent;
61 bool retval;
62
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 retval = catalog_mgr_->LookupPath(PathString(path), kLookupDefault, &parent);
63
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 assert(retval);
64
2/4
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
 2 DirectoryEntryBase cvmfscatalog =
65 MakeEmptyDirectoryEntryBase(".cvmfscatalog", parent.uid(),
66 parent.gid());
67
2/4
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
 2 DirectoryEntryBase cvmfsautocatalog =
68 MakeEmptyDirectoryEntryBase(".cvmfsautocatalog", parent.uid(),
69 parent.gid());
70
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 string relative_path = path.substr(1);
71
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 1 catalog_mgr_->AddFile(cvmfscatalog, xattr, relative_path);
72
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 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/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (catalog == NULL) {
78 // obtain a copy of the catalogs
79
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 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/2
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
 1 reverse(catalogs.begin(), catalogs.end());
84
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
 2 for (unsigned i = 0; i < catalogs.size(); ++i)
85
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 Balance(catalogs[i]);
86 1 return;
87 1 }
88
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 string catalog_path = catalog->mountpoint().ToString();
89
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 virtual_node_t root_node(catalog_path, catalog_mgr_);
90
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 root_node.ExtractChildren(catalog_mgr_);
91 // we have just recursively loaded the entire virtual tree!
92
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 PartitionOptimally(&root_node);
93 1 }
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
2/2
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 3 times.
 9 for (unsigned i = 0; i < virtual_node->children.size(); ++i) {
100 virtual_node_t *virtual_child =
101 6 &virtual_node->children[i];
102
6/6
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 2 times.
✓ Branch 4 taken 2 times.
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 2 times.
✓ Branch 7 taken 4 times.
 6 if (virtual_child->IsDirectory() && !virtual_child->IsCatalog())
103 2 PartitionOptimally(virtual_child);
104 }
105 3 virtual_node->FixWeight();
106
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3 times.
 4 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
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 if (heaviest_node != NULL &&
112
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 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/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 AddCatalogMarker(heaviest_node->path);
117 1 AddCatalog(heaviest_node);
118 1 virtual_node->weight -= (max_weight - 1);
119 1 } 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
3/6
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 2 !virtual_node->IsCatalog() &&
139
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 !virtual_node->is_new_nested_catalog) {
140
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
 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
3/6
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 2 !child->IsCatalog() &&
144
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 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/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 assert(child_node != NULL);
156
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 string new_catalog_path = child_node->path.substr(1);
157
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 1 catalog_mgr_->CreateNestedCatalog(new_catalog_path);
158 1 child_node->weight = 1;
159 1 child_node->is_new_nested_catalog = true;
160
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 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
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 catalog_mgr->Listing(path, &direntlist);
169
2/2
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 3 times.
 9 for (unsigned i = 0; i < direntlist.size(); ++i) {
170
4/8
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 6 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 6 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 6 times.
✗ Branch 12 not taken.
 12 string child_path = path + "/" + direntlist[i].name().ToString();
171
2/4
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 6 times.
✗ Branch 6 not taken.
 6 children.push_back(virtual_node_t(
172 child_path, direntlist[i], catalog_mgr));
173 6 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
5/6
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 1 times.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✓ Branch 7 taken 1 times.
 3 if (!IsCatalog() && IsDirectory()) {
194
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 2 times.
 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_
203