net/ceph/striper.c

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2
   3 #include <linux/ceph/ceph_debug.h>
   4
   5 #include <linux/math64.h>
   6 #include <linux/slab.h>
   7
   8 #include <linux/ceph/striper.h>
   9 #include <linux/ceph/types.h>
  10
  11 /*
  12  * Map a file extent to a stripe unit within an object.
  13  * Fill in objno, offset into object, and object extent length (i.e. the
  14  * number of bytes mapped, less than or equal to @l->stripe_unit).
  15  *
  16  * Example for stripe_count = 3, stripes_per_object = 4:
  17  *
  18  * blockno   |  0  3  6  9 |  1  4  7 10 |  2  5  8 11 | 12 15 18 21 | 13 16 19
  19  * stripeno  |  0  1  2  3 |  0  1  2  3 |  0  1  2  3 |  4  5  6  7 |  4  5  6
  20  * stripepos |      0      |      1      |      2      |      0      |      1
  21  * objno     |      0      |      1      |      2      |      3      |      4
  22  * objsetno  |                    0                    |                    1
  23  */
  24 void ceph_calc_file_object_mapping(struct ceph_file_layout *l,
  25                                    u64 off, u64 len,
  26                                    u64 *objno, u64 *objoff, u32 *xlen)
  27 {
  28         u32 stripes_per_object = l->object_size / l->stripe_unit;
  29         u64 blockno;    /* which su in the file (i.e. globally) */
  30         u32 blockoff;   /* offset into su */
  31         u64 stripeno;   /* which stripe */
  32         u32 stripepos;  /* which su in the stripe,
  33                            which object in the object set */
  34         u64 objsetno;   /* which object set */
  35         u32 objsetpos;  /* which stripe in the object set */
  36
  37         blockno = div_u64_rem(off, l->stripe_unit, &blockoff);
  38         stripeno = div_u64_rem(blockno, l->stripe_count, &stripepos);
  39         objsetno = div_u64_rem(stripeno, stripes_per_object, &objsetpos);
  40
  41         *objno = objsetno * l->stripe_count + stripepos;
  42         *objoff = objsetpos * l->stripe_unit + blockoff;
  43         *xlen = min_t(u64, len, l->stripe_unit - blockoff);
  44 }
  45 EXPORT_SYMBOL(ceph_calc_file_object_mapping);
  46
  47 /*
  48  * Return the last extent with given objno (@object_extents is sorted
  49  * by objno).  If not found, return NULL and set @add_pos so that the
  50  * new extent can be added with list_add(add_pos, new_ex).
  51  */
  52 static struct ceph_object_extent *
  53 lookup_last(struct list_head *object_extents, u64 objno,
  54             struct list_head **add_pos)
  55 {
  56         struct list_head *pos;
  57
  58         list_for_each_prev(pos, object_extents) {
  59                 struct ceph_object_extent *ex =
  60                     list_entry(pos, typeof(*ex), oe_item);
  61
  62                 if (ex->oe_objno == objno)
  63                         return ex;
  64
  65                 if (ex->oe_objno < objno)
  66                         break;
  67         }
  68
  69         *add_pos = pos;
  70         return NULL;
  71 }
  72
  73 static struct ceph_object_extent *
  74 lookup_containing(struct list_head *object_extents, u64 objno,
  75                   u64 objoff, u32 xlen)
  76 {
  77         struct ceph_object_extent *ex;
  78
  79         list_for_each_entry(ex, object_extents, oe_item) {
  80                 if (ex->oe_objno == objno &&
  81                     ex->oe_off <= objoff &&
  82                     ex->oe_off + ex->oe_len >= objoff + xlen) /* paranoia */
  83                         return ex;
  84
  85                 if (ex->oe_objno > objno)
  86                         break;
  87         }
  88
  89         return NULL;
  90 }
  91
  92 /*
  93  * Map a file extent to a sorted list of object extents.
  94  *
  95  * We want only one (or as few as possible) object extents per object.
  96  * Adjacent object extents will be merged together, each returned object
  97  * extent may reverse map to multiple different file extents.
  98  *
  99  * Call @alloc_fn for each new object extent and @action_fn for each
 100  * mapped stripe unit, whether it was merged into an already allocated
 101  * object extent or started a new object extent.
 102  *
 103  * Newly allocated object extents are added to @object_extents.
 104  * To keep @object_extents sorted, successive calls to this function
 105  * must map successive file extents (i.e. the list of file extents that
 106  * are mapped using the same @object_extents must be sorted).
 107  *
 108  * The caller is responsible for @object_extents.
 109  */
 110 int ceph_file_to_extents(struct ceph_file_layout *l, u64 off, u64 len,
 111                          struct list_head *object_extents,
 112                          struct ceph_object_extent *alloc_fn(void *arg),
 113                          void *alloc_arg,
 114                          ceph_object_extent_fn_t action_fn,
 115                          void *action_arg)
 116 {
 117         struct ceph_object_extent *last_ex, *ex;
 118
 119         while (len) {
 120                 struct list_head *add_pos = NULL;
 121                 u64 objno, objoff;
 122                 u32 xlen;
 123
 124                 ceph_calc_file_object_mapping(l, off, len, &objno, &objoff,
 125                                               &xlen);
 126
 127                 last_ex = lookup_last(object_extents, objno, &add_pos);
 128                 if (!last_ex || last_ex->oe_off + last_ex->oe_len != objoff) {
 129                         ex = alloc_fn(alloc_arg);
 130                         if (!ex)
 131                                 return -ENOMEM;
 132
 133                         ex->oe_objno = objno;
 134                         ex->oe_off = objoff;
 135                         ex->oe_len = xlen;
 136                         if (action_fn)
 137                                 action_fn(ex, xlen, action_arg);
 138
 139                         if (!last_ex)
 140                                 list_add(&ex->oe_item, add_pos);
 141                         else
 142                                 list_add(&ex->oe_item, &last_ex->oe_item);
 143                 } else {
 144                         last_ex->oe_len += xlen;
 145                         if (action_fn)
 146                                 action_fn(last_ex, xlen, action_arg);
 147                 }
 148
 149                 off += xlen;
 150                 len -= xlen;
 151         }
 152
 153         for (last_ex = list_first_entry(object_extents, typeof(*ex), oe_item),
 154              ex = list_next_entry(last_ex, oe_item);
 155              &ex->oe_item != object_extents;
 156              last_ex = ex, ex = list_next_entry(ex, oe_item)) {
 157                 if (last_ex->oe_objno > ex->oe_objno ||
 158                     (last_ex->oe_objno == ex->oe_objno &&
 159                      last_ex->oe_off + last_ex->oe_len >= ex->oe_off)) {
 160                         WARN(1, "%s: object_extents list not sorted!\n",
 161                              __func__);
 162                         return -EINVAL;
 163                 }
 164         }
 165
 166         return 0;
 167 }
 168 EXPORT_SYMBOL(ceph_file_to_extents);
 169
 170 /*
 171  * A stripped down, non-allocating version of ceph_file_to_extents(),
 172  * for when @object_extents is already populated.
 173  */
 174 int ceph_iterate_extents(struct ceph_file_layout *l, u64 off, u64 len,
 175                          struct list_head *object_extents,
 176                          ceph_object_extent_fn_t action_fn,
 177                          void *action_arg)
 178 {
 179         while (len) {
 180                 struct ceph_object_extent *ex;
 181                 u64 objno, objoff;
 182                 u32 xlen;
 183
 184                 ceph_calc_file_object_mapping(l, off, len, &objno, &objoff,
 185                                               &xlen);
 186
 187                 ex = lookup_containing(object_extents, objno, objoff, xlen);
 188                 if (!ex) {
 189                         WARN(1, "%s: objno %llu %llu~%u not found!\n",
 190                              __func__, objno, objoff, xlen);
 191                         return -EINVAL;
 192                 }
 193
 194                 action_fn(ex, xlen, action_arg);
 195
 196                 off += xlen;
 197                 len -= xlen;
 198         }
 199
 200         return 0;
 201 }
 202 EXPORT_SYMBOL(ceph_iterate_extents);
 203
 204 /*
 205  * Reverse map an object extent to a sorted list of file extents.
 206  *
 207  * On success, the caller is responsible for:
 208  *
 209  *     kfree(file_extents)
 210  */
 211 int ceph_extent_to_file(struct ceph_file_layout *l,
 212                         u64 objno, u64 objoff, u64 objlen,
 213                         struct ceph_file_extent **file_extents,
 214                         u32 *num_file_extents)
 215 {
 216         u32 stripes_per_object = l->object_size / l->stripe_unit;
 217         u64 blockno;    /* which su */
 218         u32 blockoff;   /* offset into su */
 219         u64 stripeno;   /* which stripe */
 220         u32 stripepos;  /* which su in the stripe,
 221                            which object in the object set */
 222         u64 objsetno;   /* which object set */
 223         u32 i = 0;
 224
 225         if (!objlen) {
 226                 *file_extents = NULL;
 227                 *num_file_extents = 0;
 228                 return 0;
 229         }
 230
 231         *num_file_extents = DIV_ROUND_UP_ULL(objoff + objlen, l->stripe_unit) -
 232                                      DIV_ROUND_DOWN_ULL(objoff, l->stripe_unit);
 233         *file_extents = kmalloc_array(*num_file_extents, sizeof(**file_extents),
 234                                       GFP_NOIO);
 235         if (!*file_extents)
 236                 return -ENOMEM;
 237
 238         div_u64_rem(objoff, l->stripe_unit, &blockoff);
 239         while (objlen) {
 240                 u64 off, len;
 241
 242                 objsetno = div_u64_rem(objno, l->stripe_count, &stripepos);
 243                 stripeno = div_u64(objoff, l->stripe_unit) +
 244                                                 objsetno * stripes_per_object;
 245                 blockno = stripeno * l->stripe_count + stripepos;
 246                 off = blockno * l->stripe_unit + blockoff;
 247                 len = min_t(u64, objlen, l->stripe_unit - blockoff);
 248
 249                 (*file_extents)[i].fe_off = off;
 250                 (*file_extents)[i].fe_len = len;
 251
 252                 blockoff = 0;
 253                 objoff += len;
 254                 objlen -= len;
 255                 i++;
 256         }
 257
 258         BUG_ON(i != *num_file_extents);
 259         return 0;
 260 }
 261 EXPORT_SYMBOL(ceph_extent_to_file);
 262
 263 u64 ceph_get_num_objects(struct ceph_file_layout *l, u64 size)
 264 {
 265         u64 period = (u64)l->stripe_count * l->object_size;
 266         u64 num_periods = DIV64_U64_ROUND_UP(size, period);
 267         u64 remainder_bytes;
 268         u64 remainder_objs = 0;
 269
 270         div64_u64_rem(size, period, &remainder_bytes);
 271         if (remainder_bytes > 0 &&
 272             remainder_bytes < (u64)l->stripe_count * l->stripe_unit)
 273                 remainder_objs = l->stripe_count -
 274                             DIV_ROUND_UP_ULL(remainder_bytes, l->stripe_unit);
 275
 276         return num_periods * l->stripe_count - remainder_objs;
 277 }
 278 EXPORT_SYMBOL(ceph_get_num_objects);