GCC Code Coverage Report

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