1 /*
2    Copyright 2005-2010 Jakub Kruszona-Zawadzki, Gemius SA, 2013-2014 EditShare, 2013-2016
3    Skytechnology sp. z o.o..
4 
5    This file was part of MooseFS and is part of LizardFS.
6 
7    LizardFS is free software: you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation, version 3.
10 
11    LizardFS is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14    GNU General Public License for more details.
15 
16    You should have received a copy of the GNU General Public License
17    along with LizardFS  If not, see <http://www.gnu.org/licenses/>.
18  */
19 
20 #pragma once
21 
22 #include "common/platform.h"
23 
24 #include <array>
25 #include <cstdint>
26 #include <unordered_map>
27 #include <memory>
28 
29 #include "common/access_control_list.h"
30 #include "common/acl_type.h"
31 #include "common/attributes.h"
32 #include "common/goal.h"
33 #include "common/compact_vector.h"
34 
35 #ifdef LIZARDFS_HAVE_64BIT_JUDY
36 #  include "common/judy_map.h"
37 #else
38 #  include <map>
39 #  include "common/flat_map.h"
40 #endif
41 
42 #include "master/fs_context.h"
43 #include "master/hstring_storage.h"
44 
45 #define NODEHASHBITS (22)
46 #define NODEHASHSIZE (1 << NODEHASHBITS)
47 #define NODEHASHPOS(nodeid) ((nodeid) & (NODEHASHSIZE - 1))
48 #define NODECHECKSUMSEED 12345
49 
50 #define EDGEHASHBITS (22)
51 #define EDGEHASHSIZE (1 << EDGEHASHBITS)
52 #define EDGEHASHPOS(hash) ((hash) & (EDGEHASHSIZE - 1))
53 #define EDGECHECKSUMSEED 1231241261
54 
55 #define MAX_INDEX 0x7FFFFFFF
56 
57 enum class AclInheritance { kInheritAcl, kDontInheritAcl };
58 
59 // Arguments for verify_session
60 enum class SessionType { kNotMeta, kOnlyMeta, kAny };
61 enum class OperationMode { kReadWrite, kReadOnly };
62 enum class ExpectedNodeType { kFile, kDirectory, kNotDirectory, kFileOrDirectory, kAny };
63 
64 typedef std::unordered_map<uint32_t, uint32_t> TrashtimeMap;
65 typedef std::array<uint32_t, GoalId::kMax + 1> GoalStatistics;
66 
67 struct statsrecord {
68 	uint32_t inodes;
69 	uint32_t dirs;
70 	uint32_t files;
71 	uint32_t chunks;
72 	uint64_t length;
73 	uint64_t size;
74 	uint64_t realsize;
75 };
76 
77 /*! \brief Node containing common meta data for each file system object (file or directory).
78  *
79  * Node size = 64B
80  *
81  * Estimating (taking into account directory and file node size) 150B per file.
82  *
83  * 10K files will occupy 1.5MB
84  * 10M files will occupy 1.5GB
85  * 1G files will occupy 150GB
86  * 4G files will occupy 600GB
87  */
88 struct FSNode {
89 	enum {
90 		kFile = TYPE_FILE,
91 		kDirectory = TYPE_DIRECTORY,
92 		kSymlink = TYPE_SYMLINK,
93 		kFifo = TYPE_FIFO,
94 		kBlockDev = TYPE_BLOCKDEV,
95 		kCharDev = TYPE_CHARDEV,
96 		kSocket = TYPE_SOCKET,
97 		kTrash = TYPE_TRASH,
98 		kReserved = TYPE_RESERVED,
99 		kUnknown = TYPE_UNKNOWN
100 	};
101 
102 	uint32_t id; /*!< Unique number identifying node. */
103 	uint32_t ctime; /*!< Change time. */
104 	uint32_t mtime; /*!< Modification time. */
105 	uint32_t atime; /*!< Access time. */
106 	uint8_t type; /*!< Node type. (file, directory, symlink, ...) */
107 	uint8_t goal; /*!< Goal id. */
108 	uint16_t mode;  /*!< Only 12 lowest bits are used for mode, in unix standard upper 4 are used
109 	                 for object type, but since there is field "type" this bits can be used as
110 	                 extra flags. */
111 	uint32_t uid; /*!< User id. */
112 	uint32_t gid; /*!< Group id. */
113 	uint32_t trashtime; /*!< Trash time. */
114 
115 	compact_vector<uint32_t, uint32_t> parent; /*!< Parent nodes ids. To reduce memory usage ids
116 	                                                are stored instead of pointers to FSNode. */
117 
118 	FSNode   *next; /*!< Next field used for storing FSNode in hash map. */
119 	uint64_t checksum; /*!< Node checksum. */
120 
FSNodeFSNode121 	FSNode(uint8_t t) {
122 		type = t;
123 		next = nullptr;
124 		checksum = 0;
125 	}
126 
127 	/*! \brief Static function used for creating proper node for given type.
128 	 * \param type Type of node to create.
129 	 * \return Pointer to created node.
130 	 */
131 	static FSNode *create(uint8_t type);
132 
133 	/*! \brief Static function used for erasing node (uses node's type
134 	 * for correct invocation of destructors).
135 	 *
136 	 * \param node Pointer to node that should be erased.
137 	 */
138 	static void destroy(FSNode *node);
139 };
140 
141 /*! \brief Node used for storing file object.
142  *
143  * Node size = 64B + 40B + 8 * chunks_count + 4 * session_count
144  * Avg size (assuming 1 chunk and session id) = 104 + 8 + 4 ~ 120B
145  */
146 struct FSNodeFile : public FSNode {
147 	uint64_t length;
148 	compact_vector<uint32_t> sessionid;
149 	compact_vector<uint64_t, uint32_t> chunks;
150 
FSNodeFileFSNodeFile151 	FSNodeFile(uint8_t t) : FSNode(t), length(), sessionid(), chunks() {
152 		assert(t == kFile || t == kTrash || t == kReserved);
153 	}
154 
chunkCountFSNodeFile155 	uint32_t chunkCount() const {
156 		for(uint32_t i = chunks.size(); i > 0; --i) {
157 			if (chunks[i-1] != 0) {
158 				return i;
159 			}
160 		}
161 
162 		return 0;
163 	}
164 };
165 
166 /*! \brief Node used for storing symbolic link.
167  *
168  * Node size = 64 + 16 = 80B
169  */
170 struct FSNodeSymlink : public FSNode {
171 	hstorage::Handle path;
172 	uint16_t path_length;
173 
FSNodeSymlinkFSNodeSymlink174 	FSNodeSymlink() : FSNode(kSymlink), path_length() {
175 	}
176 };
177 
178 /*! \brief Node used for storing device object.
179  *
180  * Node size = 64 + 8 = 72B
181  */
182 struct FSNodeDevice : public FSNode {
183 	uint32_t rdev;
184 
FSNodeDeviceFSNodeDevice185 	FSNodeDevice(uint8_t device_type) : FSNode(device_type), rdev() {
186 	}
187 };
188 
189 /*! \brief Node used for storing directory.
190  *
191  * Node size = 64 + 56 + 16 * entries_count
192  * Avg size (10 files) ~ 280B (28B per file)
193  */
194 struct FSNodeDirectory : public FSNode {
195 #ifdef LIZARDFS_HAVE_64BIT_JUDY
196 	typedef judy_map<hstorage::Handle, FSNode *> EntriesContainer;
197 #else
198 	struct HandleCompare {
199 		bool operator()(const hstorage::Handle &a, const hstorage::Handle &b) const {
200 			return a.data() < b.data();
201 		}
202 	};
203 	typedef flat_map<hstorage::Handle, FSNode *, std::vector<std::pair<hstorage::Handle, FSNode *>>,
204 	HandleCompare> EntriesContainer;
205 #endif
206 
207 	typedef EntriesContainer::iterator iterator;
208 	typedef EntriesContainer::const_iterator const_iterator;
209 
210 	EntriesContainer entries; /*!< Directory entries (entry: name + pointer to child node). */
211 	statsrecord stats; /*!< Directory statistics (including subdirectories). */
212 	uint32_t nlink; /*!< Number of directories linking to this directory. */
213 	uint16_t entries_hash;
214 
FSNodeDirectoryFSNodeDirectory215 	FSNodeDirectory() : FSNode(kDirectory) {
216 		memset(&stats, 0, sizeof(stats));
217 		nlink = 2;
218 		entries_hash = 0;
219 	}
220 
~FSNodeDirectoryFSNodeDirectory221 	~FSNodeDirectory() {
222 	}
223 
224 
225 	/*! \brief Find directory entry with given name.
226 	 *
227 	 * \param name Name of entry to find.
228 	 * \return If node is found returns iterator pointing to directory entry containing node,
229 	 *         otherwise entries.end().
230 	 */
findFSNodeDirectory231 	iterator find(const HString& name) {
232 		uint64_t name_hash = (hstorage::Handle::HashType)name.hash();
233 
234 		auto it = entries.lower_bound(hstorage::Handle(name_hash << hstorage::Handle::kHashShift));
235 		for (; it != entries.end(); ++it) {
236 			if (((*it).first.data() >> hstorage::Handle::kHashShift) != name_hash) {
237 				break;
238 			}
239 			if ((*it).first == name) {
240 				return it;
241 			}
242 		}
243 
244 		return entries.end();
245 	}
246 
247 	/*! \brief Find directory entry with given node.
248 	 *
249 	 * \param node Node to find.
250 	 * \return If node is found returns iterator pointing to directory entry containing node,
251 	 *         otherwise entries.end().
252 	 */
findFSNodeDirectory253 	iterator find(const FSNode *node) {
254 		auto it = entries.begin();
255 		for (; it != entries.end(); ++it) {
256 			if ((*it).second == node) {
257 				break;
258 			}
259 		}
260 
261 		return it;
262 	}
263 
264 	/*! \brief Find directory entry with given node.
265 	 *
266 	 * \param node Node to find.
267 	 * \return If node is found returns iterator pointing to directory entry containing node,
268 	 *         otherwise entries.end().
269 	 */
findFSNodeDirectory270 	const_iterator find(const FSNode *node) const {
271 		auto it = entries.begin();
272 		for (; it != entries.end(); ++it) {
273 			if ((*it).second == node) {
274 				break;
275 			}
276 		}
277 
278 		return it;
279 	}
280 
find_nthFSNodeDirectory281 	iterator find_nth(EntriesContainer::size_type nth) {
282 		return entries.find_nth(nth);
283 	}
284 
find_nthFSNodeDirectory285 	const_iterator find_nth(EntriesContainer::size_type nth) const {
286 		return entries.find_nth(nth);
287 	}
288 
289 	/*! \brief Returns name for specified node.
290 	 *
291 	 * \param node Pointer to node.
292 	 * \return If node is found returns name associated with this node,
293 	 *         otherwise returns empty string.
294 	 */
getChildNameFSNodeDirectory295 	std::string getChildName(const FSNode *node) const {
296 		auto it = find(node);
297 		if (it != entries.end()) {
298 			return (std::string)(*it).first;
299 		}
300 		return std::string();
301 	}
302 
beginFSNodeDirectory303 	iterator begin() {
304 		return entries.begin();
305 	}
306 
endFSNodeDirectory307 	iterator end() {
308 		return entries.end();
309 	}
310 
beginFSNodeDirectory311 	const_iterator begin() const {
312 		return entries.begin();
313 	}
314 
endFSNodeDirectory315 	const_iterator end() const {
316 		return entries.end();
317 	}
318 };
319 
320 struct TrashPathKey {
TrashPathKeyTrashPathKey321 	explicit TrashPathKey(const FSNode *node) :
322 #ifdef WORDS_BIGENDIAN
323 	    timestamp(std::min((uint64_t)node->ctime + node->trashtime, (uint64_t)UINT32_MAX)),
324 	    id(node->id)
325 #else
326 	    id(node->id),
327 	    timestamp(std::min((uint64_t)node->ctime + node->trashtime, (uint64_t)UINT32_MAX))
328 #endif
329 	{}
330 
331 	bool operator<(const TrashPathKey &other) const {
332 		return std::make_pair(timestamp, id) < std::make_pair(other.timestamp, other.id);
333 	}
334 
335 #ifdef WORDS_BIGENDIAN
336 	uint32_t timestamp;
337 	uint32_t id;
338 #else
339 	uint32_t id;
340 	uint32_t timestamp;
341 #endif
342 };
343 
344 #ifdef LIZARDFS_HAVE_64BIT_JUDY
345 typedef judy_map<TrashPathKey, hstorage::Handle> TrashPathContainer;
346 typedef judy_map<uint32_t, hstorage::Handle> ReservedPathContainer;
347 #else
348 typedef std::map<TrashPathKey, hstorage::Handle> TrashPathContainer;
349 typedef std::map<uint32_t, hstorage::Handle> ReservedPathContainer;
350 #endif
351