Whamcloud - gitweb
e33cdc1a71677aec803073c572d8c7864d6501f8
[fs/lustre-release.git] / lustre / include / lustre_lmv.h
1 /*
2  * GPL HEADER START
3  *
4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License version 2 only,
8  * as published by the Free Software Foundation.
9
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License version 2 for more details.  A copy is
14  * included in the COPYING file that accompanied this code.
15
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19  *
20  * GPL HEADER END
21  */
22 /*
23  * Copyright (c) 2014, 2016, Intel Corporation.
24  */
25 /*
26  * lustre/include/lustre_lmv.h
27  *
28  * Lustre LMV structures and functions.
29  *
30  * Author: Di Wang <di.wang@intel.com>
31  */
32
33 #ifndef _LUSTRE_LMV_H
34 #define _LUSTRE_LMV_H
35 #include <uapi/linux/lustre/lustre_idl.h>
36
37 struct lmv_oinfo {
38         struct lu_fid   lmo_fid;
39         u32             lmo_mds;
40         struct inode    *lmo_root;
41 };
42
43 struct lmv_stripe_md {
44         __u32   lsm_md_magic;
45         __u32   lsm_md_stripe_count;
46         __u32   lsm_md_master_mdt_index;
47         __u32   lsm_md_hash_type;
48         __u32   lsm_md_layout_version;
49         __u32   lsm_md_migrate_offset;
50         __u32   lsm_md_migrate_hash;
51         __u32   lsm_md_default_count;
52         __u32   lsm_md_default_index;
53         char    lsm_md_pool_name[LOV_MAXPOOLNAME + 1];
54         struct lmv_oinfo lsm_md_oinfo[0];
55 };
56
57 static inline bool lmv_dir_striped(const struct lmv_stripe_md *lsm)
58 {
59         return lsm && lsm->lsm_md_magic == LMV_MAGIC;
60 }
61
62 static inline bool lmv_dir_foreign(const struct lmv_stripe_md *lsm)
63 {
64         return lsm && lsm->lsm_md_magic == LMV_MAGIC_FOREIGN;
65 }
66
67 static inline bool lmv_dir_layout_changing(const struct lmv_stripe_md *lsm)
68 {
69         return lmv_dir_striped(lsm) &&
70                lmv_hash_is_layout_changing(lsm->lsm_md_hash_type);
71 }
72
73 static inline bool lmv_dir_bad_hash(const struct lmv_stripe_md *lsm)
74 {
75         if (!lmv_dir_striped(lsm))
76                 return false;
77
78         if (lsm->lsm_md_hash_type & LMV_HASH_FLAG_BAD_TYPE)
79                 return true;
80
81         return !lmv_is_known_hash_type(lsm->lsm_md_hash_type);
82 }
83
84 static inline bool
85 lsm_md_eq(const struct lmv_stripe_md *lsm1, const struct lmv_stripe_md *lsm2)
86 {
87         __u32 idx;
88
89         if (lsm1->lsm_md_magic != lsm2->lsm_md_magic ||
90             lsm1->lsm_md_stripe_count != lsm2->lsm_md_stripe_count ||
91             lsm1->lsm_md_master_mdt_index !=
92                                 lsm2->lsm_md_master_mdt_index ||
93             lsm1->lsm_md_hash_type != lsm2->lsm_md_hash_type ||
94             lsm1->lsm_md_layout_version !=
95                                 lsm2->lsm_md_layout_version ||
96             lsm1->lsm_md_migrate_offset !=
97                                 lsm2->lsm_md_migrate_offset ||
98             lsm1->lsm_md_migrate_hash !=
99                                 lsm2->lsm_md_migrate_hash ||
100             strncmp(lsm1->lsm_md_pool_name, lsm2->lsm_md_pool_name,
101                     sizeof(lsm1->lsm_md_pool_name)) != 0)
102                 return false;
103
104         if (lmv_dir_striped(lsm1)) {
105                 for (idx = 0; idx < lsm1->lsm_md_stripe_count; idx++) {
106                         if (!lu_fid_eq(&lsm1->lsm_md_oinfo[idx].lmo_fid,
107                                        &lsm2->lsm_md_oinfo[idx].lmo_fid))
108                                 return false;
109                 }
110         }
111
112         return true;
113 }
114
115 static inline void lsm_md_dump(int mask, const struct lmv_stripe_md *lsm)
116 {
117         int i;
118
119         /* If lsm_md_magic == LMV_MAGIC_FOREIGN pool_name may not be a null
120          * terminated string so only print LOV_MAXPOOLNAME bytes.
121          */
122         CDEBUG(mask,
123                "magic %#x stripe count %d master mdt %d hash type %#x version %d migrate offset %d migrate hash %#x pool %.*s\n",
124                lsm->lsm_md_magic, lsm->lsm_md_stripe_count,
125                lsm->lsm_md_master_mdt_index, lsm->lsm_md_hash_type,
126                lsm->lsm_md_layout_version, lsm->lsm_md_migrate_offset,
127                lsm->lsm_md_migrate_hash,
128                LOV_MAXPOOLNAME, lsm->lsm_md_pool_name);
129
130         if (!lmv_dir_striped(lsm))
131                 return;
132
133         for (i = 0; i < lsm->lsm_md_stripe_count; i++)
134                 CDEBUG(mask, "stripe[%d] "DFID"\n",
135                        i, PFID(&lsm->lsm_md_oinfo[i].lmo_fid));
136 }
137
138 union lmv_mds_md;
139
140 void lmv_free_memmd(struct lmv_stripe_md *lsm);
141
142 static inline void lmv1_le_to_cpu(struct lmv_mds_md_v1 *lmv_dst,
143                                   const struct lmv_mds_md_v1 *lmv_src)
144 {
145         __u32 i;
146
147         lmv_dst->lmv_magic = le32_to_cpu(lmv_src->lmv_magic);
148         lmv_dst->lmv_stripe_count = le32_to_cpu(lmv_src->lmv_stripe_count);
149         lmv_dst->lmv_master_mdt_index =
150                                 le32_to_cpu(lmv_src->lmv_master_mdt_index);
151         lmv_dst->lmv_hash_type = le32_to_cpu(lmv_src->lmv_hash_type);
152         lmv_dst->lmv_layout_version = le32_to_cpu(lmv_src->lmv_layout_version);
153         for (i = 0; i < lmv_src->lmv_stripe_count; i++)
154                 fid_le_to_cpu(&lmv_dst->lmv_stripe_fids[i],
155                               &lmv_src->lmv_stripe_fids[i]);
156 }
157
158 static inline void lmv_le_to_cpu(union lmv_mds_md *lmv_dst,
159                                  const union lmv_mds_md *lmv_src)
160 {
161         switch (le32_to_cpu(lmv_src->lmv_magic)) {
162         case LMV_MAGIC_V1:
163                 lmv1_le_to_cpu(&lmv_dst->lmv_md_v1, &lmv_src->lmv_md_v1);
164                 break;
165         default:
166                 break;
167         }
168 }
169
170 /* This hash is only for testing purpose */
171 static inline unsigned int
172 lmv_hash_all_chars(unsigned int count, const char *name, int namelen)
173 {
174         unsigned int c = 0;
175         const unsigned char *p = (const unsigned char *)name;
176
177         while (--namelen >= 0)
178                 c += p[namelen];
179
180         c = c % count;
181
182         return c;
183 }
184
185 static inline unsigned int
186 lmv_hash_fnv1a(unsigned int count, const char *name, int namelen)
187 {
188         __u64 hash;
189
190         hash = lustre_hash_fnv_1a_64(name, namelen);
191
192         return do_div(hash, count);
193 }
194
195 /*
196  * Robert Jenkins' function for mixing 32-bit values
197  * http://burtleburtle.net/bob/hash/evahash.html
198  * a, b = random bits, c = input and output
199  *
200  * Mixing inputs to generate an evenly distributed hash.
201  */
202 #define crush_hashmix(a, b, c)                          \
203 do {                                                    \
204         a = a - b;  a = a - c;  a = a ^ (c >> 13);      \
205         b = b - c;  b = b - a;  b = b ^ (a << 8);       \
206         c = c - a;  c = c - b;  c = c ^ (b >> 13);      \
207         a = a - b;  a = a - c;  a = a ^ (c >> 12);      \
208         b = b - c;  b = b - a;  b = b ^ (a << 16);      \
209         c = c - a;  c = c - b;  c = c ^ (b >> 5);       \
210         a = a - b;  a = a - c;  a = a ^ (c >> 3);       \
211         b = b - c;  b = b - a;  b = b ^ (a << 10);      \
212         c = c - a;  c = c - b;  c = c ^ (b >> 15);      \
213 } while (0)
214
215 #define crush_hash_seed 1315423911
216
217 static inline __u32 crush_hash(__u32 a, __u32 b)
218 {
219         __u32 hash = crush_hash_seed ^ a ^ b;
220         __u32 x = 231232;
221         __u32 y = 1232;
222
223         crush_hashmix(a, b, hash);
224         crush_hashmix(x, a, hash);
225         crush_hashmix(b, y, hash);
226
227         return hash;
228 }
229
230 /* refer to https://github.com/ceph/ceph/blob/master/src/crush/hash.c and
231  * https://www.ssrc.ucsc.edu/Papers/weil-sc06.pdf for details of CRUSH
232  * algorithm.
233  */
234 static inline unsigned int
235 lmv_hash_crush(unsigned int count, const char *name, int namelen)
236 {
237         unsigned long long straw;
238         unsigned long long highest_straw = 0;
239         unsigned int pg_id;
240         unsigned int idx = 0;
241         int i;
242
243         /* put temp and backup file on the same MDT where target is located.
244          * temporary file naming rule:
245          * 1. rsync: .<target>.XXXXXX
246          * 2. dstripe: <target>.XXXXXXXX
247          */
248         if (lu_name_is_temp_file(name, namelen, true, 6)) {
249                 name++;
250                 namelen -= 8;
251         } else if (lu_name_is_temp_file(name, namelen, false, 8)) {
252                 namelen -= 9;
253         } else if (lu_name_is_backup_file(name, namelen, &i)) {
254                 LASSERT(i < namelen);
255                 namelen -= i;
256         }
257
258         pg_id = lmv_hash_fnv1a(LMV_CRUSH_PG_COUNT, name, namelen);
259
260         /* distribute PG among all stripes pseudo-randomly, so they are almost
261          * evenly distributed, and when stripe count changes, only (delta /
262          * total) sub files need to be moved, herein 'delta' is added or removed
263          * stripe count, 'total' is total stripe count before change for
264          * removal, or count after change for addition.
265          */
266         for (i = 0; i < count; i++) {
267                 straw = crush_hash(pg_id, i);
268                 if (straw > highest_straw) {
269                         highest_straw = straw;
270                         idx = i;
271                 }
272         }
273         LASSERT(idx < count);
274
275         return idx;
276 }
277
278 /* directory layout may change in three ways:
279  * 1. directory migration, in its LMV source stripes are appended after
280  *    target stripes, \a migrate_hash is source hash type, \a migrate_offset is
281  *    target stripe count,
282  * 2. directory split, \a migrate_hash is hash type before split,
283  *    \a migrate_offset is stripe count before split.
284  * 3. directory merge, \a migrate_hash is hash type after merge,
285  *    \a migrate_offset is stripe count after merge.
286  */
287 static inline int
288 __lmv_name_to_stripe_index(__u32 hash_type, __u32 stripe_count,
289                            __u32 migrate_hash, __u32 migrate_offset,
290                            const char *name, int namelen, bool new_layout)
291 {
292         __u32 saved_hash = hash_type;
293         __u32 saved_count = stripe_count;
294         int stripe_index = 0;
295
296         LASSERT(namelen > 0);
297         LASSERT(stripe_count > 0);
298
299         if (lmv_hash_is_splitting(hash_type)) {
300                 if (!new_layout) {
301                         hash_type = migrate_hash;
302                         stripe_count = migrate_offset;
303                 }
304         } else if (lmv_hash_is_merging(hash_type)) {
305                 if (new_layout) {
306                         hash_type = migrate_hash;
307                         stripe_count = migrate_offset;
308                 }
309         } else if (lmv_hash_is_migrating(hash_type)) {
310                 if (new_layout) {
311                         stripe_count = migrate_offset;
312                 } else {
313                         hash_type = migrate_hash;
314                         stripe_count -= migrate_offset;
315                 }
316         }
317
318         if (stripe_count > 1) {
319                 switch (hash_type & LMV_HASH_TYPE_MASK) {
320                 case LMV_HASH_TYPE_ALL_CHARS:
321                         stripe_index = lmv_hash_all_chars(stripe_count, name,
322                                                           namelen);
323                         break;
324                 case LMV_HASH_TYPE_FNV_1A_64:
325                         stripe_index = lmv_hash_fnv1a(stripe_count, name,
326                                                       namelen);
327                         break;
328                 case LMV_HASH_TYPE_CRUSH:
329                         stripe_index = lmv_hash_crush(stripe_count, name,
330                                                       namelen);
331                         break;
332                 default:
333                         return -EBADFD;
334                 }
335         }
336
337         LASSERT(stripe_index < stripe_count);
338
339         if (!new_layout && lmv_hash_is_migrating(saved_hash))
340                 stripe_index += migrate_offset;
341
342         LASSERT(stripe_index < saved_count);
343
344         CDEBUG(D_INFO, "name %.*s hash=%#x/%#x idx=%d/%u/%u under %s layout\n",
345                namelen, name, saved_hash, migrate_hash, stripe_index,
346                saved_count, migrate_offset, new_layout ? "new" : "old");
347
348         return stripe_index;
349 }
350
351 static inline int lmv_name_to_stripe_index(struct lmv_mds_md_v1 *lmv,
352                                            const char *name, int namelen)
353 {
354         if (lmv->lmv_magic == LMV_MAGIC_V1)
355                 return __lmv_name_to_stripe_index(lmv->lmv_hash_type,
356                                                   lmv->lmv_stripe_count,
357                                                   lmv->lmv_migrate_hash,
358                                                   lmv->lmv_migrate_offset,
359                                                   name, namelen, true);
360
361         if (lmv->lmv_magic == cpu_to_le32(LMV_MAGIC_V1))
362                 return __lmv_name_to_stripe_index(
363                                         le32_to_cpu(lmv->lmv_hash_type),
364                                         le32_to_cpu(lmv->lmv_stripe_count),
365                                         le32_to_cpu(lmv->lmv_migrate_hash),
366                                         le32_to_cpu(lmv->lmv_migrate_offset),
367                                         name, namelen, true);
368
369         return -EINVAL;
370 }
371
372 static inline int lmv_name_to_stripe_index_old(struct lmv_mds_md_v1 *lmv,
373                                                const char *name, int namelen)
374 {
375         if (lmv->lmv_magic == LMV_MAGIC_V1 ||
376             lmv->lmv_magic == LMV_MAGIC_STRIPE)
377                 return __lmv_name_to_stripe_index(lmv->lmv_hash_type,
378                                                   lmv->lmv_stripe_count,
379                                                   lmv->lmv_migrate_hash,
380                                                   lmv->lmv_migrate_offset,
381                                                   name, namelen, false);
382
383         if (lmv->lmv_magic == cpu_to_le32(LMV_MAGIC_V1) ||
384             lmv->lmv_magic == cpu_to_le32(LMV_MAGIC_STRIPE))
385                 return __lmv_name_to_stripe_index(
386                                         le32_to_cpu(lmv->lmv_hash_type),
387                                         le32_to_cpu(lmv->lmv_stripe_count),
388                                         le32_to_cpu(lmv->lmv_migrate_hash),
389                                         le32_to_cpu(lmv->lmv_migrate_offset),
390                                         name, namelen, false);
391
392         return -EINVAL;
393 }
394
395 static inline bool lmv_user_magic_supported(__u32 lum_magic)
396 {
397         return lum_magic == LMV_USER_MAGIC ||
398                lum_magic == LMV_USER_MAGIC_SPECIFIC ||
399                lum_magic == LMV_MAGIC_FOREIGN;
400 }
401
402 /* master LMV is sane */
403 static inline bool lmv_is_sane(const struct lmv_mds_md_v1 *lmv)
404 {
405         if (!lmv)
406                 return false;
407
408         if (le32_to_cpu(lmv->lmv_magic) != LMV_MAGIC_V1)
409                 goto insane;
410
411         if (le32_to_cpu(lmv->lmv_stripe_count) == 0)
412                 goto insane;
413
414         if (!lmv_is_known_hash_type(le32_to_cpu(lmv->lmv_hash_type)))
415                 goto insane;
416
417         return true;
418 insane:
419         LMV_DEBUG(D_ERROR, lmv, "insane");
420         return false;
421 }
422
423 /* LMV can be either master or stripe LMV */
424 static inline bool lmv_is_sane2(const struct lmv_mds_md_v1 *lmv)
425 {
426         if (!lmv)
427                 return false;
428
429         if (le32_to_cpu(lmv->lmv_magic) != LMV_MAGIC_V1 &&
430             le32_to_cpu(lmv->lmv_magic) != LMV_MAGIC_STRIPE)
431                 goto insane;
432
433         if (le32_to_cpu(lmv->lmv_stripe_count) == 0)
434                 goto insane;
435
436         if (!lmv_is_known_hash_type(le32_to_cpu(lmv->lmv_hash_type)))
437                 goto insane;
438
439         return true;
440 insane:
441         LMV_DEBUG(D_ERROR, lmv, "insane");
442         return false;
443 }
444
445 static inline bool lmv_is_splitting(const struct lmv_mds_md_v1 *lmv)
446 {
447         LASSERT(lmv_is_sane2(lmv));
448         return lmv_hash_is_splitting(cpu_to_le32(lmv->lmv_hash_type));
449 }
450
451 static inline bool lmv_is_merging(const struct lmv_mds_md_v1 *lmv)
452 {
453         LASSERT(lmv_is_sane2(lmv));
454         return lmv_hash_is_merging(cpu_to_le32(lmv->lmv_hash_type));
455 }
456
457 static inline bool lmv_is_migrating(const struct lmv_mds_md_v1 *lmv)
458 {
459         LASSERT(lmv_is_sane(lmv));
460         return lmv_hash_is_migrating(cpu_to_le32(lmv->lmv_hash_type));
461 }
462
463 static inline bool lmv_is_restriping(const struct lmv_mds_md_v1 *lmv)
464 {
465         LASSERT(lmv_is_sane2(lmv));
466         return lmv_hash_is_splitting(cpu_to_le32(lmv->lmv_hash_type)) ||
467                lmv_hash_is_merging(cpu_to_le32(lmv->lmv_hash_type));
468 }
469
470 static inline bool lmv_is_layout_changing(const struct lmv_mds_md_v1 *lmv)
471 {
472         LASSERT(lmv_is_sane2(lmv));
473         return lmv_hash_is_splitting(cpu_to_le32(lmv->lmv_hash_type)) ||
474                lmv_hash_is_merging(cpu_to_le32(lmv->lmv_hash_type)) ||
475                lmv_hash_is_migrating(cpu_to_le32(lmv->lmv_hash_type));
476 }
477
478 #endif