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