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(dividend: off, divisor: l->stripe_unit, remainder: &blockoff); |
38 | stripeno = div_u64_rem(dividend: blockno, divisor: l->stripe_count, remainder: &stripepos); |
39 | objsetno = div_u64_rem(dividend: stripeno, divisor: stripes_per_object, remainder: &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: &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(new: &ex->oe_item, head: add_pos); |
141 | else |
142 | list_add(new: &ex->oe_item, head: &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(n: *num_file_extents, size: sizeof(**file_extents), |
234 | GFP_NOIO); |
235 | if (!*file_extents) |
236 | return -ENOMEM; |
237 | |
238 | div_u64_rem(dividend: objoff, divisor: l->stripe_unit, remainder: &blockoff); |
239 | while (objlen) { |
240 | u64 off, len; |
241 | |
242 | objsetno = div_u64_rem(dividend: objno, divisor: l->stripe_count, remainder: &stripepos); |
243 | stripeno = div_u64(dividend: objoff, divisor: 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(dividend: size, divisor: period, remainder: &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); |
279 | |