~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/net/ceph/striper.c

Version: ~ [ linux-5.1-rc5 ] ~ [ linux-5.0.7 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.34 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.111 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.168 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.178 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.138 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.65 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp