net/ceph/striper.c

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002
0003 #include <linux/ceph/ceph_debug.h>
0004
0005 #include <linux/math64.h>
0006 #include <linux/slab.h>
0007
0008 #include <linux/ceph/striper.h>
0009 #include <linux/ceph/types.h>
0010
0011 /*
0012  * Map a file extent to a stripe unit within an object.
0013  * Fill in objno, offset into object, and object extent length (i.e. the
0014  * number of bytes mapped, less than or equal to @l->stripe_unit).
0015  *
0016  * Example for stripe_count = 3, stripes_per_object = 4:
0017  *
0018  * blockno   |  0  3  6  9 |  1  4  7 10 |  2  5  8 11 | 12 15 18 21 | 13 16 19
0019  * stripeno  |  0  1  2  3 |  0  1  2  3 |  0  1  2  3 |  4  5  6  7 |  4  5  6
0020  * stripepos |      0      |      1      |      2      |      0      |      1
0021  * objno     |      0      |      1      |      2      |      3      |      4
0022  * objsetno  |                    0                    |                    1
0023  */
0024 void ceph_calc_file_object_mapping(struct ceph_file_layout *l,
0025                    u64 off, u64 len,
0026                    u64 *objno, u64 *objoff, u32 *xlen)
0027 {
0028     u32 stripes_per_object = l->object_size / l->stripe_unit;
0029     u64 blockno;    /* which su in the file (i.e. globally) */
0030     u32 blockoff;   /* offset into su */
0031     u64 stripeno;   /* which stripe */
0032     u32 stripepos;  /* which su in the stripe,
0033                which object in the object set */
0034     u64 objsetno;   /* which object set */
0035     u32 objsetpos;  /* which stripe in the object set */
0036
0037     blockno = div_u64_rem(off, l->stripe_unit, &blockoff);
0038     stripeno = div_u64_rem(blockno, l->stripe_count, &stripepos);
0039     objsetno = div_u64_rem(stripeno, stripes_per_object, &objsetpos);
0040
0041     *objno = objsetno * l->stripe_count + stripepos;
0042     *objoff = objsetpos * l->stripe_unit + blockoff;
0043     *xlen = min_t(u64, len, l->stripe_unit - blockoff);
0044 }
0045 EXPORT_SYMBOL(ceph_calc_file_object_mapping);
0046
0047 /*
0048  * Return the last extent with given objno (@object_extents is sorted
0049  * by objno).  If not found, return NULL and set @add_pos so that the
0050  * new extent can be added with list_add(add_pos, new_ex).
0051  */
0052 static struct ceph_object_extent *
0053 lookup_last(struct list_head *object_extents, u64 objno,
0054         struct list_head **add_pos)
0055 {
0056     struct list_head *pos;
0057
0058     list_for_each_prev(pos, object_extents) {
0059         struct ceph_object_extent *ex =
0060             list_entry(pos, typeof(*ex), oe_item);
0061
0062         if (ex->oe_objno == objno)
0063             return ex;
0064
0065         if (ex->oe_objno < objno)
0066             break;
0067     }
0068
0069     *add_pos = pos;
0070     return NULL;
0071 }
0072
0073 static struct ceph_object_extent *
0074 lookup_containing(struct list_head *object_extents, u64 objno,
0075           u64 objoff, u32 xlen)
0076 {
0077     struct ceph_object_extent *ex;
0078
0079     list_for_each_entry(ex, object_extents, oe_item) {
0080         if (ex->oe_objno == objno &&
0081             ex->oe_off <= objoff &&
0082             ex->oe_off + ex->oe_len >= objoff + xlen) /* paranoia */
0083             return ex;
0084
0085         if (ex->oe_objno > objno)
0086             break;
0087     }
0088
0089     return NULL;
0090 }
0091
0092 /*
0093  * Map a file extent to a sorted list of object extents.
0094  *
0095  * We want only one (or as few as possible) object extents per object.
0096  * Adjacent object extents will be merged together, each returned object
0097  * extent may reverse map to multiple different file extents.
0098  *
0099  * Call @alloc_fn for each new object extent and @action_fn for each
0100  * mapped stripe unit, whether it was merged into an already allocated
0101  * object extent or started a new object extent.
0102  *
0103  * Newly allocated object extents are added to @object_extents.
0104  * To keep @object_extents sorted, successive calls to this function
0105  * must map successive file extents (i.e. the list of file extents that
0106  * are mapped using the same @object_extents must be sorted).
0107  *
0108  * The caller is responsible for @object_extents.
0109  */
0110 int ceph_file_to_extents(struct ceph_file_layout *l, u64 off, u64 len,
0111              struct list_head *object_extents,
0112              struct ceph_object_extent *alloc_fn(void *arg),
0113              void *alloc_arg,
0114              ceph_object_extent_fn_t action_fn,
0115              void *action_arg)
0116 {
0117     struct ceph_object_extent *last_ex, *ex;
0118
0119     while (len) {
0120         struct list_head *add_pos = NULL;
0121         u64 objno, objoff;
0122         u32 xlen;
0123
0124         ceph_calc_file_object_mapping(l, off, len, &objno, &objoff,
0125                           &xlen);
0126
0127         last_ex = lookup_last(object_extents, objno, &add_pos);
0128         if (!last_ex || last_ex->oe_off + last_ex->oe_len != objoff) {
0129             ex = alloc_fn(alloc_arg);
0130             if (!ex)
0131                 return -ENOMEM;
0132
0133             ex->oe_objno = objno;
0134             ex->oe_off = objoff;
0135             ex->oe_len = xlen;
0136             if (action_fn)
0137                 action_fn(ex, xlen, action_arg);
0138
0139             if (!last_ex)
0140                 list_add(&ex->oe_item, add_pos);
0141             else
0142                 list_add(&ex->oe_item, &last_ex->oe_item);
0143         } else {
0144             last_ex->oe_len += xlen;
0145             if (action_fn)
0146                 action_fn(last_ex, xlen, action_arg);
0147         }
0148
0149         off += xlen;
0150         len -= xlen;
0151     }
0152
0153     for (last_ex = list_first_entry(object_extents, typeof(*ex), oe_item),
0154          ex = list_next_entry(last_ex, oe_item);
0155          &ex->oe_item != object_extents;
0156          last_ex = ex, ex = list_next_entry(ex, oe_item)) {
0157         if (last_ex->oe_objno > ex->oe_objno ||
0158             (last_ex->oe_objno == ex->oe_objno &&
0159              last_ex->oe_off + last_ex->oe_len >= ex->oe_off)) {
0160             WARN(1, "%s: object_extents list not sorted!\n",
0161                  __func__);
0162             return -EINVAL;
0163         }
0164     }
0165
0166     return 0;
0167 }
0168 EXPORT_SYMBOL(ceph_file_to_extents);
0169
0170 /*
0171  * A stripped down, non-allocating version of ceph_file_to_extents(),
0172  * for when @object_extents is already populated.
0173  */
0174 int ceph_iterate_extents(struct ceph_file_layout *l, u64 off, u64 len,
0175              struct list_head *object_extents,
0176              ceph_object_extent_fn_t action_fn,
0177              void *action_arg)
0178 {
0179     while (len) {
0180         struct ceph_object_extent *ex;
0181         u64 objno, objoff;
0182         u32 xlen;
0183
0184         ceph_calc_file_object_mapping(l, off, len, &objno, &objoff,
0185                           &xlen);
0186
0187         ex = lookup_containing(object_extents, objno, objoff, xlen);
0188         if (!ex) {
0189             WARN(1, "%s: objno %llu %llu~%u not found!\n",
0190                  __func__, objno, objoff, xlen);
0191             return -EINVAL;
0192         }
0193
0194         action_fn(ex, xlen, action_arg);
0195
0196         off += xlen;
0197         len -= xlen;
0198     }
0199
0200     return 0;
0201 }
0202 EXPORT_SYMBOL(ceph_iterate_extents);
0203
0204 /*
0205  * Reverse map an object extent to a sorted list of file extents.
0206  *
0207  * On success, the caller is responsible for:
0208  *
0209  *     kfree(file_extents)
0210  */
0211 int ceph_extent_to_file(struct ceph_file_layout *l,
0212             u64 objno, u64 objoff, u64 objlen,
0213             struct ceph_file_extent **file_extents,
0214             u32 *num_file_extents)
0215 {
0216     u32 stripes_per_object = l->object_size / l->stripe_unit;
0217     u64 blockno;    /* which su */
0218     u32 blockoff;   /* offset into su */
0219     u64 stripeno;   /* which stripe */
0220     u32 stripepos;  /* which su in the stripe,
0221                which object in the object set */
0222     u64 objsetno;   /* which object set */
0223     u32 i = 0;
0224
0225     if (!objlen) {
0226         *file_extents = NULL;
0227         *num_file_extents = 0;
0228         return 0;
0229     }
0230
0231     *num_file_extents = DIV_ROUND_UP_ULL(objoff + objlen, l->stripe_unit) -
0232                      DIV_ROUND_DOWN_ULL(objoff, l->stripe_unit);
0233     *file_extents = kmalloc_array(*num_file_extents, sizeof(**file_extents),
0234                       GFP_NOIO);
0235     if (!*file_extents)
0236         return -ENOMEM;
0237
0238     div_u64_rem(objoff, l->stripe_unit, &blockoff);
0239     while (objlen) {
0240         u64 off, len;
0241
0242         objsetno = div_u64_rem(objno, l->stripe_count, &stripepos);
0243         stripeno = div_u64(objoff, l->stripe_unit) +
0244                         objsetno * stripes_per_object;
0245         blockno = stripeno * l->stripe_count + stripepos;
0246         off = blockno * l->stripe_unit + blockoff;
0247         len = min_t(u64, objlen, l->stripe_unit - blockoff);
0248
0249         (*file_extents)[i].fe_off = off;
0250         (*file_extents)[i].fe_len = len;
0251
0252         blockoff = 0;
0253         objoff += len;
0254         objlen -= len;
0255         i++;
0256     }
0257
0258     BUG_ON(i != *num_file_extents);
0259     return 0;
0260 }
0261 EXPORT_SYMBOL(ceph_extent_to_file);
0262
0263 u64 ceph_get_num_objects(struct ceph_file_layout *l, u64 size)
0264 {
0265     u64 period = (u64)l->stripe_count * l->object_size;
0266     u64 num_periods = DIV64_U64_ROUND_UP(size, period);
0267     u64 remainder_bytes;
0268     u64 remainder_objs = 0;
0269
0270     div64_u64_rem(size, period, &remainder_bytes);
0271     if (remainder_bytes > 0 &&
0272         remainder_bytes < (u64)l->stripe_count * l->stripe_unit)
0273         remainder_objs = l->stripe_count -
0274                 DIV_ROUND_UP_ULL(remainder_bytes, l->stripe_unit);
0275
0276     return num_periods * l->stripe_count - remainder_objs;
0277 }
0278 EXPORT_SYMBOL(ceph_get_num_objects);