xref: /openbmc/linux/net/ceph/striper.c (revision 22e8bd51)
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  */
ceph_calc_file_object_mapping(struct ceph_file_layout * l,u64 off,u64 len,u64 * objno,u64 * objoff,u32 * xlen)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 *
lookup_last(struct list_head * object_extents,u64 objno,struct list_head ** add_pos)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 *
lookup_containing(struct list_head * object_extents,u64 objno,u64 objoff,u32 xlen)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  */
ceph_file_to_extents(struct ceph_file_layout * l,u64 off,u64 len,struct list_head * object_extents,struct ceph_object_extent * alloc_fn (void * arg),void * alloc_arg,ceph_object_extent_fn_t action_fn,void * action_arg)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  */
ceph_iterate_extents(struct ceph_file_layout * l,u64 off,u64 len,struct list_head * object_extents,ceph_object_extent_fn_t action_fn,void * action_arg)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  */
ceph_extent_to_file(struct ceph_file_layout * l,u64 objno,u64 objoff,u64 objlen,struct ceph_file_extent ** file_extents,u32 * num_file_extents)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 
ceph_get_num_objects(struct ceph_file_layout * l,u64 size)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);
279