Line data Source code
1 : #include "clusterautoconfig.h"
2 :
3 : #include <inttypes.h>
4 : #include <limits.h>
5 : #include <stdio.h>
6 : #include <stdlib.h>
7 : #include <string.h>
8 : #include <unistd.h>
9 :
10 : #include "libgfs2.h"
11 : #include "rgrp.h"
12 :
13 : #define ROUND_UP(N, S) ((((N) + (S) - 1) / (S)) * (S))
14 :
15 2137594 : static void compute_bitmaps(lgfs2_rgrp_t rg, const unsigned bsize)
16 : {
17 : int x;
18 :
19 2137594 : rg->rt_bits[0].bi_offset = sizeof(struct gfs2_rgrp);
20 2137594 : rg->rt_bits[0].bi_start = 0;
21 2137594 : rg->rt_bits[0].bi_len = bsize - sizeof(struct gfs2_rgrp);
22 :
23 2861766 : for (x = 1; x < rg->rt_length; x++) {
24 724172 : rg->rt_bits[x].bi_offset = sizeof(struct gfs2_meta_header);
25 724172 : rg->rt_bits[x].bi_start = rg->rt_bits[x - 1].bi_start + rg->rt_bits[x - 1].bi_len;
26 724172 : rg->rt_bits[x].bi_len = bsize - sizeof(struct gfs2_meta_header);
27 : }
28 2137594 : x--;
29 2137594 : rg->rt_bits[x].bi_len = rg->rt_bitbytes - rg->rt_bits[x].bi_start;
30 2137594 : }
31 :
32 : /**
33 : * lgfs2_compute_bitstructs - Compute the bitmap sizes
34 : * bsize: Block size
35 : * rgd: The resource group descriptor
36 : * Returns: 0 on success, -1 on error
37 : */
38 2130495 : int lgfs2_compute_bitstructs(const uint32_t bsize, struct lgfs2_rgrp_tree *rgd)
39 : {
40 2130495 : uint32_t length = rgd->rt_length;
41 : uint32_t bytes_left;
42 2130495 : int ownbits = 0;
43 :
44 : /* Max size of an rg is 2GB. A 2GB RG with (minimum) 512-byte blocks
45 : has 4194304 blocks. We can represent 4 blocks in one bitmap byte.
46 : Therefore, all 4194304 blocks can be represented in 1048576 bytes.
47 : Subtract a metadata header for each 512-byte block and we get
48 : 488 bytes of bitmap per block. Divide 1048576 by 488 and we can
49 : be assured we should never have more than 2149 of them. */
50 2130495 : errno = EINVAL;
51 2130495 : if (length > 2149 || length == 0)
52 3 : return -1;
53 :
54 2130492 : if(rgd->rt_bits == NULL) {
55 2130492 : rgd->rt_bits = calloc(length, sizeof(struct lgfs2_bitmap));
56 2130492 : if(rgd->rt_bits == NULL)
57 0 : return -1;
58 2130492 : ownbits = 1;
59 : }
60 :
61 2130492 : compute_bitmaps(rgd, bsize);
62 2130492 : bytes_left = rgd->rt_bitbytes - (rgd->rt_bits[rgd->rt_length - 1].bi_start +
63 2130492 : rgd->rt_bits[rgd->rt_length - 1].bi_len);
64 2130492 : errno = EINVAL;
65 2130492 : if(bytes_left)
66 0 : goto errbits;
67 :
68 2130492 : if((rgd->rt_bits[length - 1].bi_start +
69 2130492 : rgd->rt_bits[length - 1].bi_len) * GFS2_NBBY != rgd->rt_data)
70 0 : goto errbits;
71 :
72 2130492 : return 0;
73 0 : errbits:
74 0 : if (ownbits) {
75 0 : free(rgd->rt_bits);
76 0 : rgd->rt_bits = NULL;
77 : }
78 0 : return -1;
79 : }
80 :
81 :
82 : /**
83 : * blk2rgrpd - Find resource group for a given data block number
84 : * @sdp: The GFS superblock
85 : * @n: The data block number
86 : *
87 : * Returns: Ths resource group, or NULL if not found
88 : */
89 4022755 : struct lgfs2_rgrp_tree *lgfs2_blk2rgrpd(struct lgfs2_sbd *sdp, uint64_t blk)
90 : {
91 4022755 : struct lgfs2_rgrp_tree *rgd = (struct lgfs2_rgrp_tree *)sdp->rgtree.osi_node;
92 22065805 : while (rgd) {
93 22065805 : if (blk < rgd->rt_addr)
94 17993462 : rgd = (struct lgfs2_rgrp_tree *) rgd->rt_node.osi_left;
95 4072343 : else if (blk >= rgd->rt_data0 + rgd->rt_data)
96 49588 : rgd = (struct lgfs2_rgrp_tree *) rgd->rt_node.osi_right;
97 : else
98 4022755 : return rgd;
99 : }
100 0 : return NULL;
101 : }
102 :
103 : /**
104 : * Allocate a multi-block buffer for a resource group's bitmaps. This is done
105 : * as one chunk and should be freed using lgfs2_rgrp_bitbuf_free().
106 : * Returns 0 on success with the bitmap buffer allocated in the resource group,
107 : * or non-zero on failure with errno set.
108 : */
109 6827 : int lgfs2_rgrp_bitbuf_alloc(lgfs2_rgrp_t rg)
110 : {
111 6827 : struct lgfs2_sbd *sdp = rg->rt_rgrps->rgs_sdp;
112 6827 : size_t len = rg->rt_length * sdp->sd_bsize;
113 6827 : unsigned long io_align = sdp->sd_bsize;
114 : unsigned i;
115 : void *bufs;
116 :
117 6827 : if (rg->rt_rgrps->rgs_align > 0) {
118 408 : len = ROUND_UP(len, rg->rt_rgrps->rgs_align * sdp->sd_bsize);
119 408 : io_align = rg->rt_rgrps->rgs_align_off * sdp->sd_bsize;
120 : }
121 6827 : if (posix_memalign(&bufs, io_align, len) != 0) {
122 0 : errno = ENOMEM;
123 0 : return 1;
124 : }
125 6827 : memset(bufs, 0, len);
126 :
127 163026 : for (i = 0; i < rg->rt_length; i++) {
128 156199 : rg->rt_bits[i].bi_data = (char *)bufs + (i * sdp->sd_bsize);
129 156199 : rg->rt_bits[i].bi_modified = 0;
130 : }
131 : /* coverity[leaked_storage:SUPPRESS] */
132 6827 : return 0;
133 : }
134 :
135 : /**
136 : * Free the multi-block bitmap buffer from a resource group. The buffer should
137 : * have been allocated as a single chunk as in lgfs2_rgrp_bitbuf_alloc().
138 : * This does not implicitly write the bitmaps to disk. Use lgfs2_rgrp_write()
139 : * for that.
140 : * rg: The resource groups whose bitmap buffer should be freed.
141 : */
142 6585 : void lgfs2_rgrp_bitbuf_free(lgfs2_rgrp_t rg)
143 : {
144 : unsigned i;
145 :
146 6585 : free(rg->rt_bits[0].bi_data);
147 154072 : for (i = 0; i < rg->rt_length; i++) {
148 147487 : rg->rt_bits[i].bi_data = NULL;
149 147487 : rg->rt_bits[i].bi_modified = 0;
150 : }
151 6585 : }
152 :
153 : /**
154 : * Check a resource group's crc
155 : * Returns 0 on success, non-zero if crc is bad
156 : */
157 42995 : int lgfs2_rgrp_crc_check(char *buf)
158 : {
159 42995 : int ret = 0;
160 42995 : struct gfs2_rgrp *rg = (struct gfs2_rgrp *)buf;
161 42995 : __be32 crc = rg->rg_crc;
162 :
163 42995 : if (crc == 0)
164 0 : return 0;
165 :
166 42995 : rg->rg_crc = 0;
167 42995 : if (be32_to_cpu(crc) != lgfs2_disk_hash(buf, sizeof(struct gfs2_rgrp)))
168 0 : ret = 1;
169 42995 : rg->rg_crc = crc;
170 42995 : return ret;
171 : }
172 :
173 : /**
174 : * Set the crc of an on-disk resource group
175 : */
176 77642 : void lgfs2_rgrp_crc_set(char *buf)
177 : {
178 77642 : struct gfs2_rgrp *rg = (struct gfs2_rgrp *)buf;
179 : uint32_t crc;
180 :
181 77642 : rg->rg_crc = 0;
182 77642 : crc = lgfs2_disk_hash(buf, sizeof(struct gfs2_rgrp));
183 77642 : rg->rg_crc = cpu_to_be32(crc);
184 77642 : }
185 :
186 : /**
187 : * lgfs2_rgrp_read - read in the resource group information from disk.
188 : * @rgd - resource group structure
189 : * returns: 0 if no error, otherwise the block number that failed
190 : */
191 43003 : uint64_t lgfs2_rgrp_read(struct lgfs2_sbd *sdp, struct lgfs2_rgrp_tree *rgd)
192 : {
193 43003 : unsigned length = rgd->rt_length * sdp->sd_bsize;
194 43003 : off_t offset = rgd->rt_addr * sdp->sd_bsize;
195 : char *buf;
196 :
197 43003 : if (length == 0 || lgfs2_check_range(sdp, rgd->rt_addr))
198 0 : return -1;
199 :
200 43003 : buf = calloc(1, length);
201 43003 : if (buf == NULL)
202 0 : return -1;
203 :
204 43003 : if (pread(sdp->device_fd, buf, length, offset) != length) {
205 0 : free(buf);
206 0 : return -1;
207 : }
208 :
209 8916922 : for (unsigned i = 0; i < rgd->rt_length; i++) {
210 8873927 : int mtype = (i ? GFS2_METATYPE_RB : GFS2_METATYPE_RG);
211 :
212 8873927 : rgd->rt_bits[i].bi_data = buf + (i * sdp->sd_bsize);
213 8873927 : if (lgfs2_check_meta(rgd->rt_bits[i].bi_data, mtype)) {
214 8 : free(buf);
215 8 : rgd->rt_bits[0].bi_data = NULL;
216 8 : return rgd->rt_addr + i;
217 : }
218 : }
219 42995 : if (lgfs2_rgrp_crc_check(buf)) {
220 0 : free(buf);
221 0 : return rgd->rt_addr;
222 : }
223 42995 : lgfs2_rgrp_in(rgd, buf);
224 : /* coverity[leaked_storage:SUPPRESS] */
225 42995 : return 0;
226 : }
227 :
228 2168469 : void lgfs2_rgrp_relse(struct lgfs2_sbd *sdp, struct lgfs2_rgrp_tree *rgd)
229 : {
230 2168469 : if (rgd->rt_bits == NULL)
231 178 : return;
232 13612097 : for (unsigned i = 0; i < rgd->rt_length; i++) {
233 11443806 : off_t offset = sdp->sd_bsize * (rgd->rt_addr + i);
234 : ssize_t ret;
235 :
236 11443806 : if (rgd->rt_bits[i].bi_data == NULL || !rgd->rt_bits[i].bi_modified)
237 11394724 : continue;
238 :
239 49082 : ret = pwrite(sdp->device_fd, rgd->rt_bits[i].bi_data,
240 49082 : sdp->sd_bsize, offset);
241 49082 : if (ret != sdp->sd_bsize) {
242 0 : fprintf(stderr, "Failed to write modified resource group at block %"PRIu64": %s\n",
243 0 : rgd->rt_addr, strerror(errno));
244 : }
245 49082 : rgd->rt_bits[i].bi_modified = 0;
246 : }
247 2168291 : free(rgd->rt_bits[0].bi_data);
248 13612097 : for (unsigned i = 0; i < rgd->rt_length; i++)
249 11443806 : rgd->rt_bits[i].bi_data = NULL;
250 : }
251 :
252 2130670 : struct lgfs2_rgrp_tree *lgfs2_rgrp_insert(struct osi_root *rgtree, uint64_t rgblock)
253 : {
254 2130670 : struct osi_node **newn = &rgtree->osi_node, *parent = NULL;
255 : struct lgfs2_rgrp_tree *data;
256 :
257 : /* Figure out where to put new node */
258 29805606 : while (*newn) {
259 27674936 : struct lgfs2_rgrp_tree *cur = (struct lgfs2_rgrp_tree *)*newn;
260 :
261 27674936 : parent = *newn;
262 27674936 : if (rgblock < cur->rt_addr)
263 6 : newn = &((*newn)->osi_left);
264 27674930 : else if (rgblock > cur->rt_addr)
265 27674930 : newn = &((*newn)->osi_right);
266 : else
267 0 : return cur;
268 : }
269 :
270 2130670 : data = calloc(1, sizeof(struct lgfs2_rgrp_tree));
271 2130670 : if (!data)
272 0 : return NULL;
273 : /* Add new node and rebalance tree. */
274 2130670 : data->rt_addr = rgblock;
275 2130670 : osi_link_node(&data->rt_node, parent, newn);
276 2130670 : osi_insert_color(&data->rt_node, rgtree);
277 :
278 2130670 : return data;
279 : }
280 :
281 4547 : void lgfs2_rgrp_free(struct lgfs2_sbd *sdp, struct osi_root *rgrp_tree)
282 : {
283 : struct lgfs2_rgrp_tree *rgd;
284 : struct osi_node *n;
285 :
286 4547 : if (OSI_EMPTY_ROOT(rgrp_tree))
287 4 : return;
288 2134459 : while ((n = osi_first(rgrp_tree))) {
289 2129916 : rgd = (struct lgfs2_rgrp_tree *)n;
290 :
291 2129916 : lgfs2_rgrp_relse(sdp, rgd);
292 2129916 : free(rgd->rt_bits);
293 2129916 : rgd->rt_bits = NULL;
294 2129916 : osi_erase(&rgd->rt_node, rgrp_tree);
295 2129916 : free(rgd);
296 : }
297 : }
298 :
299 290 : static uint64_t align_block(const uint64_t base, const uint64_t align)
300 : {
301 290 : if ((align > 0) && ((base % align) > 0))
302 19 : return (base - (base % align)) + align;
303 271 : return base;
304 : }
305 :
306 : /**
307 : * Calculate the aligned block address of a resource group.
308 : * rgs: The resource groups handle
309 : * base: The base address of the first resource group address, in blocks
310 : * Returns the aligned address of the first resource group.
311 : */
312 142 : uint64_t lgfs2_rgrp_align_addr(const lgfs2_rgrps_t rgs, uint64_t addr)
313 : {
314 142 : return align_block(addr, rgs->rgs_align_off);
315 : }
316 :
317 : /**
318 : * Calculate the aligned relative address of the next resource group (and thus
319 : * the aligned length of this one).
320 : * rgs: The resource groups handle
321 : * base: The base length of the current resource group, in blocks
322 : * Returns the length of the resource group (the aligned relative address of
323 : * the next one)
324 : */
325 148 : uint32_t lgfs2_rgrp_align_len(const lgfs2_rgrps_t rgs, uint32_t len)
326 : {
327 148 : return align_block(len, rgs->rgs_align) + rgs->rgs_align_off;
328 : }
329 :
330 : /**
331 : * Plan the sizes of resource groups for remaining free space, based on a
332 : * target maximum size. In order to make best use of the space while keeping
333 : * the resource groups aligned appropriately we need to either reduce the
334 : * length of every resource group or of a subset of the resource groups, so
335 : * we're left with either one or two resource group sizes. We keep track of
336 : * both of these and the numbers of each size of resource group inside the
337 : * resource groups descriptor.
338 : * rgs: The resource groups descriptor
339 : * space: The number of remaining blocks to be allocated
340 : * tgtsize: The target resource group size in blocks
341 : * Returns the number of resource groups planned to fit in the given space, or
342 : * 0 if the smallest resource group would be smaller than GFS2_MIN_RGSIZE.
343 : */
344 77 : uint32_t lgfs2_rgrps_plan(const lgfs2_rgrps_t rgs, uint64_t space, uint32_t tgtsize)
345 : {
346 77 : uint32_t maxlen = (LGFS2_MAX_RGSIZE << 20) / rgs->rgs_sdp->sd_bsize;
347 77 : uint32_t minlen = (LGFS2_MIN_RGSIZE << 20) / rgs->rgs_sdp->sd_bsize;
348 77 : struct rg_spec *spec = rgs->rgs_plan->rg_specs;
349 :
350 : /* Apps should already have checked that the rg size is <=
351 : GFS2_MAX_RGSIZE but just in case alignment pushes it over we clamp
352 : it back down while calculating the initial rgrp length. */
353 : do {
354 77 : spec[0].len = lgfs2_rgrp_align_len(rgs, tgtsize);
355 77 : tgtsize -= (rgs->rgs_align + 1);
356 77 : } while (spec[0].len > maxlen);
357 :
358 77 : spec[0].num = space / spec[0].len;
359 :
360 77 : if ((space - (spec[0].num * spec[0].len)) > rgs->rgs_align) {
361 77 : unsigned adj = (rgs->rgs_align > 0) ? rgs->rgs_align : 1;
362 :
363 : /* Spread the adjustment required to fit a new rgrp at the end
364 : over all of the rgrps so that we don't end with a single
365 : tiny one. */
366 77 : spec[0].num++;
367 174609 : while (((spec[0].len - adj) * (uint64_t)spec[0].num) >= space)
368 174532 : spec[0].len -= adj;
369 :
370 : /* We've adjusted the size of the rgrps down as far as we can
371 : without leaving a large gap at the end of the device now,
372 : but we still need to reduce the size of some rgrps in order
373 : to make everything fit, so we use the second rgplan to
374 : specify a second length for a subset of the resource groups.
375 : If plan[0].len already divides the space with no remainder,
376 : plan[1].num will stay 0 and it won't be used. */
377 77 : spec[1].len = spec[0].len - adj;
378 77 : spec[1].num = 0;
379 :
380 77 : while ((((uint64_t)spec[0].len * spec[0].num) +
381 3403 : ((uint64_t)spec[1].len * spec[1].num)) >= space) {
382 : /* Total number of rgrps stays constant now. We just
383 : need to shift some weight around */
384 3326 : spec[0].num--;
385 3326 : spec[1].num++;
386 : }
387 : }
388 :
389 : /* Once we've reached this point,
390 : (spec[0].num * spec[0].len) + (spec[1].num * spec[1].len)
391 : will be less than one adjustment smaller than 'space'. */
392 77 : if (spec[0].len < minlen)
393 1 : return 0;
394 :
395 76 : return spec[0].num + spec[1].num;
396 : }
397 :
398 : /**
399 : * Create and initialise an empty set of resource groups
400 : * bsize: The block size of the fs
401 : * devlen: The length of the device, in fs blocks
402 : * align: The required stripe alignment of the resource groups. Must be a multiple of 'offset'.
403 : * offset: The required stripe offset of the resource groups
404 : * Returns an initialised lgfs2_rgrps_t or NULL if unsuccessful with errno set
405 : */
406 83 : lgfs2_rgrps_t lgfs2_rgrps_init(struct lgfs2_sbd *sdp, uint64_t align, uint64_t offset)
407 : {
408 : lgfs2_rgrps_t rgs;
409 :
410 83 : errno = EINVAL;
411 83 : if (offset != 0 && (align % offset) != 0)
412 0 : return NULL;
413 :
414 83 : rgs = calloc(1, sizeof(*rgs));
415 83 : if (rgs == NULL)
416 0 : return NULL;
417 :
418 83 : rgs->rgs_plan = calloc(1, sizeof(struct rgs_plan) + (5 * sizeof(struct rg_spec)));
419 83 : if (rgs->rgs_plan == NULL) {
420 0 : free(rgs);
421 0 : return NULL;
422 : }
423 83 : rgs->rgs_plan->length = 0;
424 83 : rgs->rgs_plan->capacity = 5;
425 83 : rgs->rgs_sdp = sdp;
426 83 : rgs->rgs_align = align;
427 83 : rgs->rgs_align_off = offset;
428 83 : memset(&rgs->rgs_root, 0, sizeof(rgs->rgs_root));
429 :
430 83 : return rgs;
431 : }
432 :
433 : /**
434 : * Populate a set of resource groups from a gfs2 rindex file.
435 : * fd: An open file descriptor for the rindex file.
436 : * rgs: The set of resource groups.
437 : * Returns the number of resource groups added to the set or 0 on error with
438 : * errno set.
439 : */
440 0 : unsigned lgfs2_rindex_read_fd(int fd, lgfs2_rgrps_t rgs)
441 : {
442 0 : unsigned count = 0;
443 :
444 0 : errno = EINVAL;
445 0 : if (fd < 0 || rgs == NULL)
446 0 : return 0;
447 :
448 0 : while (1) {
449 : lgfs2_rgrp_t rg;
450 : struct gfs2_rindex ri;
451 0 : ssize_t ret = read(fd, &ri, sizeof(ri));
452 0 : if (ret == 0)
453 0 : break;
454 :
455 0 : if (ret != sizeof(ri))
456 0 : return 0;
457 :
458 0 : rg = lgfs2_rgrps_append(rgs, &ri, 0);
459 0 : if (rg == NULL)
460 0 : return 0;
461 0 : count++;
462 : }
463 0 : return count;
464 : }
465 :
466 : /**
467 : * Read a rindex entry into a set of resource groups
468 : * rip: The inode of the rindex file
469 : * rgs: The set of resource groups.
470 : * i: The index of the entry to read from the rindex file
471 : * Returns the new rindex entry added to the set or NULL on error with errno
472 : * set.
473 : */
474 346 : lgfs2_rgrp_t lgfs2_rindex_read_one(struct lgfs2_inode *rip, lgfs2_rgrps_t rgs, unsigned i)
475 : {
476 346 : uint64_t off = i * sizeof(struct gfs2_rindex);
477 : struct gfs2_rindex ri;
478 : lgfs2_rgrp_t rg;
479 : int ret;
480 :
481 346 : errno = EINVAL;
482 346 : if (rip == NULL || rgs == NULL)
483 0 : return NULL;
484 :
485 346 : ret = lgfs2_readi(rip, &ri, off, sizeof(struct gfs2_rindex));
486 346 : if (ret != sizeof(struct gfs2_rindex))
487 0 : return NULL;
488 :
489 346 : rg = lgfs2_rgrps_append(rgs, &ri, 0);
490 346 : if (rg == NULL)
491 0 : return NULL;
492 :
493 346 : return rg;
494 : }
495 :
496 : /**
497 : * Free a set of resource groups created with lgfs2_rgrps_append() etc. This
498 : * does not write any dirty buffers to disk. See lgfs2_rgrp_write().
499 : * rgs: A pointer to the set of resource groups to be freed.
500 : */
501 83 : void lgfs2_rgrps_free(lgfs2_rgrps_t *rgs)
502 : {
503 : lgfs2_rgrp_t rg;
504 83 : struct osi_root *tree = &(*rgs)->rgs_root;
505 :
506 7185 : while ((rg = (struct lgfs2_rgrp_tree *)osi_first(tree))) {
507 : int i;
508 7102 : free(rg->rt_bits[0].bi_data);
509 161685 : for (i = 0; i < rg->rt_length; i++) {
510 154583 : rg->rt_bits[i].bi_data = NULL;
511 : }
512 7102 : osi_erase(&rg->rt_node, tree);
513 7102 : free(rg);
514 : }
515 83 : free((*rgs)->rgs_plan);
516 83 : free(*rgs);
517 83 : *rgs = NULL;
518 83 : }
519 :
520 : /**
521 : * Given a number of blocks in a resource group, return the number of blocks
522 : * needed for bitmaps. Also calculate the adjusted number of free data blocks
523 : * in the resource group and store it in *ri_data.
524 : */
525 9508 : uint32_t lgfs2_rgblocks2bitblocks(const unsigned int bsize, const uint32_t rgblocks, uint32_t *ri_data)
526 : {
527 9508 : uint32_t mappable = 0;
528 9508 : uint32_t bitblocks = 0;
529 : /* Number of blocks mappable by bitmap blocks with these header types */
530 9508 : const uint32_t blks_rgrp = GFS2_NBBY * (bsize - sizeof(struct gfs2_rgrp));
531 9508 : const uint32_t blks_meta = GFS2_NBBY * (bsize - sizeof(struct gfs2_meta_header));
532 :
533 155749 : while (blks_rgrp + (blks_meta * bitblocks) < ((rgblocks - bitblocks) & ~(uint32_t)3))
534 146241 : bitblocks++;
535 :
536 9508 : if (bitblocks > 0)
537 5022 : mappable = blks_rgrp + (blks_meta * (bitblocks - 1));
538 :
539 9508 : *ri_data = (rgblocks - (bitblocks + 1)) & ~(uint32_t)3;
540 9508 : if (mappable < *ri_data)
541 9508 : bitblocks++;
542 :
543 9508 : return bitblocks;
544 : }
545 :
546 : /**
547 : * Calculate the fields for a new entry in the resource group index.
548 : * ri: A pointer to the resource group index entry to be calculated.
549 : * addr: The address at which to place this resource group
550 : * len: The required length of the resource group, in fs blocks.
551 : * If rglen is 0, geometry previously calculated by lgfs2_rgrps_plan() will be used.
552 : * Returns the calculated address of the next resource group or 0 with errno set:
553 : * EINVAL - The entry pointer is NULL
554 : * ENOSPC - This rgrp would extend past the end of the device
555 : */
556 6829 : uint64_t lgfs2_rindex_entry_new(lgfs2_rgrps_t rgs, struct gfs2_rindex *ri, uint64_t addr, uint32_t len)
557 : {
558 6829 : struct rg_spec *spec = rgs->rgs_plan->rg_specs;
559 : uint32_t ri_length, ri_data;
560 6829 : int plan = -1;
561 6829 : errno = EINVAL;
562 6829 : if (!ri)
563 0 : return 0;
564 :
565 6829 : errno = ENOSPC;
566 6829 : if (spec[0].num > 0)
567 3364 : plan = 0;
568 3465 : else if (spec[1].num > 0)
569 3314 : plan = 1;
570 151 : else if (len == 0)
571 73 : return 0;
572 :
573 6756 : if (plan >= 0 && (len == 0 || len == spec[plan].len)) {
574 6674 : len = spec[plan].len;
575 6674 : spec[plan].num--;
576 : }
577 :
578 6756 : if (addr + len > rgs->rgs_sdp->device.length)
579 0 : return 0;
580 :
581 6756 : ri_length = lgfs2_rgblocks2bitblocks(rgs->rgs_sdp->sd_bsize, len, &ri_data);
582 6756 : ri->ri_addr = cpu_to_be64(addr);
583 6756 : ri->ri_length = cpu_to_be32(ri_length);
584 6756 : ri->ri_data = cpu_to_be32(ri_data);
585 6756 : ri->__pad = 0;
586 6756 : ri->ri_data0 = cpu_to_be64(addr + ri_length);
587 6756 : ri->ri_bitbytes = cpu_to_be32(ri_data / GFS2_NBBY);
588 6756 : memset(&ri->ri_reserved, 0, sizeof(ri->ri_reserved));
589 :
590 6756 : return addr + len;
591 : }
592 :
593 : /**
594 : * Returns the total resource group size, in blocks, required to give blksreq data blocks
595 : */
596 71 : unsigned lgfs2_rgsize_for_data(uint64_t blksreq, unsigned bsize)
597 : {
598 71 : const uint32_t blks_rgrp = GFS2_NBBY * (bsize - sizeof(struct gfs2_rgrp));
599 71 : const uint32_t blks_meta = GFS2_NBBY * (bsize - sizeof(struct gfs2_meta_header));
600 71 : unsigned bitblocks = 1;
601 71 : blksreq = (blksreq + 3) & ~3;
602 71 : if (blksreq > blks_rgrp)
603 67 : bitblocks += ((blksreq - blks_rgrp) + blks_meta - 1) / blks_meta;
604 71 : return bitblocks + blksreq;
605 : }
606 :
607 : // Temporary function to aid in API migration
608 73 : void lgfs2_attach_rgrps(struct lgfs2_sbd *sdp, lgfs2_rgrps_t rgs)
609 : {
610 73 : sdp->rgtree.osi_node = rgs->rgs_root.osi_node;
611 73 : }
612 :
613 : /**
614 : * Insert a new resource group after the last resource group in a set.
615 : * rgs: The set of resource groups
616 : * entry: The entry to be added
617 : * rg_skip: The value to be used for this resource group's rg_skip field
618 : * Returns the new resource group on success or NULL on failure with errno set.
619 : */
620 7102 : lgfs2_rgrp_t lgfs2_rgrps_append(lgfs2_rgrps_t rgs, struct gfs2_rindex *entry, uint32_t rg_skip)
621 : {
622 : lgfs2_rgrp_t rg;
623 7102 : struct osi_node **link = &rgs->rgs_root.osi_node;
624 7102 : struct osi_node *parent = osi_last(&rgs->rgs_root);
625 7102 : lgfs2_rgrp_t lastrg = (lgfs2_rgrp_t)parent;
626 :
627 7102 : errno = EINVAL;
628 7102 : if (entry == NULL)
629 0 : return NULL;
630 :
631 7102 : if (lastrg != NULL) { /* Tree is not empty */
632 7019 : if (be64_to_cpu(entry->ri_addr) <= lastrg->rt_addr)
633 0 : return NULL; /* Appending with a lower address doesn't make sense */
634 7019 : link = &lastrg->rt_node.osi_right;
635 : }
636 :
637 7102 : rg = calloc(1, sizeof(*rg) + (be32_to_cpu(entry->ri_length) * sizeof(struct lgfs2_bitmap)));
638 7102 : if (rg == NULL)
639 0 : return NULL;
640 :
641 7102 : rg->rt_bits = (struct lgfs2_bitmap *)(rg + 1);
642 :
643 7102 : osi_link_node(&rg->rt_node, parent, link);
644 7102 : osi_insert_color(&rg->rt_node, &rgs->rgs_root);
645 :
646 7102 : rg->rt_addr = be64_to_cpu(entry->ri_addr);
647 7102 : rg->rt_length = be32_to_cpu(entry->ri_length);
648 7102 : rg->rt_data0 = rg->rt_rg_data0 = be64_to_cpu(entry->ri_data0);
649 7102 : rg->rt_data = rg->rt_rg_data = be32_to_cpu(entry->ri_data);
650 7102 : rg->rt_bitbytes = rg->rt_rg_bitbytes = be32_to_cpu(entry->ri_bitbytes);
651 7102 : rg->rt_flags = 0;
652 7102 : rg->rt_free = be32_to_cpu(entry->ri_data);
653 7102 : rg->rt_dinodes = 0;
654 7102 : rg->rt_skip = rg_skip;
655 7102 : rg->rt_igeneration = 0;
656 7102 : compute_bitmaps(rg, rgs->rgs_sdp->sd_bsize);
657 7102 : rg->rt_rgrps = rgs;
658 7102 : return rg;
659 : }
660 :
661 : /**
662 : * Write a resource group to a file descriptor.
663 : * Returns 0 on success or non-zero on failure with errno set
664 : */
665 6583 : int lgfs2_rgrp_write(int fd, const lgfs2_rgrp_t rg)
666 : {
667 6583 : struct lgfs2_sbd *sdp = rg->rt_rgrps->rgs_sdp;
668 : unsigned int i;
669 6583 : int freebufs = 0;
670 : ssize_t ret;
671 : size_t len;
672 :
673 6583 : if (rg->rt_bits[0].bi_data == NULL) {
674 6503 : freebufs = 1;
675 6503 : if (lgfs2_rgrp_bitbuf_alloc(rg) != 0)
676 0 : return -1;
677 : }
678 6583 : lgfs2_rgrp_out(rg, rg->rt_bits[0].bi_data);
679 147483 : for (i = 1; i < rg->rt_length; i++) {
680 140900 : struct gfs2_meta_header *mh = (void *) rg->rt_bits[i].bi_data;
681 :
682 140900 : mh->mh_magic = cpu_to_be32(GFS2_MAGIC);
683 140900 : mh->mh_type = cpu_to_be32(GFS2_METATYPE_RB);
684 140900 : mh->mh_format = cpu_to_be32(GFS2_FORMAT_RB);
685 : }
686 :
687 6583 : len = sdp->sd_bsize * rg->rt_length;
688 6583 : if (rg->rt_rgrps->rgs_align > 0)
689 408 : len = ROUND_UP(len, rg->rt_rgrps->rgs_align * sdp->sd_bsize);
690 :
691 6583 : ret = pwrite(fd, rg->rt_bits[0].bi_data, len,
692 6583 : rg->rt_addr * sdp->sd_bsize);
693 :
694 6583 : if (freebufs)
695 6503 : lgfs2_rgrp_bitbuf_free(rg);
696 :
697 6583 : return ret == len ? 0 : -1;
698 : }
699 :
700 : /**
701 : * Write the final resource group with rg_skip == 0.
702 : * If there is no bitmap data attached to the rg then the block after the
703 : * header will be zeroed.
704 : * fd: The file descriptor to write to
705 : * rgs: The set of resource groups
706 : */
707 73 : int lgfs2_rgrps_write_final(int fd, lgfs2_rgrps_t rgs)
708 : {
709 73 : lgfs2_rgrp_t rg = lgfs2_rgrp_last(rgs);
710 :
711 73 : rg->rt_skip = 0;
712 73 : if (lgfs2_rgrp_write(fd, rg) != 0)
713 1 : return -1;
714 72 : return 0;
715 : }
716 :
717 13 : lgfs2_rgrp_t lgfs2_rgrp_first(lgfs2_rgrps_t rgs)
718 : {
719 13 : return (lgfs2_rgrp_t)osi_first(&rgs->rgs_root);
720 : }
721 :
722 346 : lgfs2_rgrp_t lgfs2_rgrp_next(lgfs2_rgrp_t rg)
723 : {
724 346 : return (lgfs2_rgrp_t)osi_next(&rg->rt_node);
725 : }
726 :
727 6510 : lgfs2_rgrp_t lgfs2_rgrp_prev(lgfs2_rgrp_t rg)
728 : {
729 6510 : return (lgfs2_rgrp_t)osi_prev(&rg->rt_node);
730 : }
731 :
732 74 : lgfs2_rgrp_t lgfs2_rgrp_last(lgfs2_rgrps_t rgs)
733 : {
734 74 : return (lgfs2_rgrp_t)osi_last(&rgs->rgs_root);
735 : }
736 :
737 : /**
738 : * gfs2_rbm_from_block - Set the rbm based upon rgd and block number
739 : * @rbm: The rbm with rgd already set correctly
740 : * @block: The block number (filesystem relative)
741 : *
742 : * This sets the bi and offset members of an rbm based on a
743 : * resource group and a filesystem relative block number. The
744 : * resource group must be set in the rbm on entry, the bi and
745 : * offset members will be set by this function.
746 : *
747 : * Returns: 0 on success, or non-zero with errno set
748 : */
749 2460243 : int lgfs2_rbm_from_block(struct lgfs2_rbm *rbm, uint64_t block)
750 : {
751 2460243 : uint64_t rblock = block - rbm->rgd->rt_data0;
752 2460243 : struct lgfs2_sbd *sdp = rbm->rgd->rt_rgrps->rgs_sdp;
753 :
754 2460243 : if (rblock > UINT_MAX) {
755 0 : errno = EINVAL;
756 0 : return 1;
757 : }
758 2460243 : if (block >= rbm->rgd->rt_data0 + rbm->rgd->rt_data) {
759 1 : errno = E2BIG;
760 1 : return 1;
761 : }
762 :
763 2460242 : rbm->bii = 0;
764 2460242 : rbm->offset = (uint32_t)(rblock);
765 : /* Check if the block is within the first block */
766 2460242 : if (rbm->offset < (rbm_bi(rbm)->bi_len * GFS2_NBBY))
767 983596 : return 0;
768 :
769 : /* Adjust for the size diff between gfs2_meta_header and gfs2_rgrp */
770 1476646 : rbm->offset += (sizeof(struct gfs2_rgrp) -
771 : sizeof(struct gfs2_meta_header)) * GFS2_NBBY;
772 1476646 : rbm->bii = rbm->offset / sdp->sd_blocks_per_bitmap;
773 1476646 : rbm->offset -= rbm->bii * sdp->sd_blocks_per_bitmap;
774 1476646 : return 0;
775 : }
776 :
777 : /**
778 : * lgfs2_rbm_incr - increment an rbm structure
779 : * @rbm: The rbm with rgd already set correctly
780 : *
781 : * This function takes an existing rbm structure and increments it to the next
782 : * viable block offset.
783 : *
784 : * Returns: If incrementing the offset would cause the rbm to go past the
785 : * end of the rgrp, true is returned, otherwise false.
786 : *
787 : */
788 19197 : static int lgfs2_rbm_incr(struct lgfs2_rbm *rbm)
789 : {
790 19197 : if (rbm->offset + 1 < (rbm_bi(rbm)->bi_len * GFS2_NBBY)) { /* in the same bitmap */
791 19197 : rbm->offset++;
792 19197 : return 0;
793 : }
794 0 : if (rbm->bii == rbm->rgd->rt_length - 1) /* at the last bitmap */
795 0 : return 1;
796 :
797 0 : rbm->offset = 0;
798 0 : rbm->bii++;
799 0 : return 0;
800 : }
801 :
802 : /**
803 : * lgfs2_testbit - test a bit in the bitmaps
804 : * @rbm: The bit to test
805 : *
806 : * Returns: The two bit block state of the requested bit
807 : */
808 2463246 : static inline uint8_t lgfs2_testbit(const struct lgfs2_rbm *rbm)
809 : {
810 2463246 : struct lgfs2_bitmap *bi = rbm_bi(rbm);
811 2463246 : const uint8_t *buffer = (uint8_t *)bi->bi_data + bi->bi_offset;
812 : const uint8_t *byte;
813 : unsigned int bit;
814 :
815 2463246 : byte = buffer + (rbm->offset / GFS2_NBBY);
816 2463246 : bit = (rbm->offset % GFS2_NBBY) * GFS2_BIT_SIZE;
817 :
818 2463246 : return (*byte >> bit) & GFS2_BIT_MASK;
819 : }
820 :
821 : /**
822 : * lgfs2_unaligned_extlen - Look for free blocks which are not byte aligned
823 : * @rbm: Position to search (value/result)
824 : * @n_unaligned: Number of unaligned blocks to check
825 : * @len: Decremented for each block found (terminate on zero)
826 : *
827 : * Returns: true if a non-free block is encountered
828 : */
829 19198 : static int lgfs2_unaligned_extlen(struct lgfs2_rbm *rbm, uint32_t n_unaligned, uint32_t *len)
830 : {
831 : uint32_t n;
832 : uint8_t res;
833 :
834 38395 : for (n = 0; n < n_unaligned; n++) {
835 38395 : res = lgfs2_testbit(rbm);
836 38395 : if (res != GFS2_BLKST_FREE)
837 0 : return 1;
838 38395 : (*len)--;
839 38395 : if (*len == 0)
840 19198 : return 1;
841 19197 : if (lgfs2_rbm_incr(rbm))
842 0 : return 1;
843 : }
844 :
845 0 : return 0;
846 : }
847 :
848 35314 : static uint8_t *check_bytes8(const uint8_t *start, uint8_t value, unsigned bytes)
849 : {
850 81923317 : while (bytes) {
851 81888003 : if (*start != value)
852 0 : return (void *)start;
853 81888003 : start++;
854 81888003 : bytes--;
855 : }
856 35314 : return NULL;
857 : }
858 :
859 : /**
860 : * lgfs2_free_extlen - Return extent length of free blocks
861 : * @rbm: Starting position
862 : * @len: Max length to check
863 : *
864 : * Starting at the block specified by the rbm, see how many free blocks
865 : * there are, not reading more than len blocks ahead. This can be done
866 : * using check_bytes8 when the blocks are byte aligned, but has to be done
867 : * on a block by block basis in case of unaligned blocks. Also this
868 : * function can cope with bitmap boundaries (although it must stop on
869 : * a resource group boundary)
870 : *
871 : * Returns: Number of free blocks in the extent
872 : */
873 25597 : static uint32_t lgfs2_free_extlen(const struct lgfs2_rbm *rrbm, uint32_t len)
874 : {
875 25597 : struct lgfs2_rbm rbm = *rrbm;
876 25597 : uint32_t n_unaligned = rbm.offset & 3;
877 25597 : uint32_t size = len;
878 : uint32_t bytes;
879 : uint32_t chunk_size;
880 : uint8_t *ptr, *start, *end;
881 : uint64_t block;
882 : struct lgfs2_bitmap *bi;
883 25597 : struct lgfs2_sbd *sdp = rbm.rgd->rt_rgrps->rgs_sdp;
884 :
885 25598 : if (n_unaligned &&
886 1 : lgfs2_unaligned_extlen(&rbm, 4 - n_unaligned, &len))
887 1 : goto out;
888 :
889 25596 : n_unaligned = len & 3;
890 : /* Start is now byte aligned */
891 60909 : while (len > 3) {
892 35314 : bi = rbm_bi(&rbm);
893 35314 : start = (uint8_t *)bi->bi_data;
894 35314 : end = start + sdp->sd_bsize;
895 35314 : start += bi->bi_offset;
896 35314 : start += (rbm.offset / GFS2_NBBY);
897 35314 : bytes = (len / GFS2_NBBY) < (end - start) ? (len / GFS2_NBBY):(end - start);
898 35314 : ptr = check_bytes8(start, 0, bytes);
899 35314 : chunk_size = ((ptr == NULL) ? bytes : (ptr - start));
900 35314 : chunk_size *= GFS2_NBBY;
901 35314 : len -= chunk_size;
902 35314 : block = lgfs2_rbm_to_block(&rbm);
903 35314 : if (lgfs2_rbm_from_block(&rbm, block + chunk_size)) {
904 1 : n_unaligned = 0;
905 1 : break;
906 : }
907 35313 : if (ptr) {
908 0 : n_unaligned = 3;
909 0 : break;
910 : }
911 35313 : n_unaligned = len & 3;
912 : }
913 :
914 : /* Deal with any bits left over at the end */
915 25596 : if (n_unaligned)
916 19197 : lgfs2_unaligned_extlen(&rbm, n_unaligned, &len);
917 6399 : out:
918 25597 : return size - len;
919 : }
920 :
921 : /**
922 : * gfs2_rbm_find - Look for blocks of a particular state
923 : * @rbm: Value/result starting position and final position
924 : * @state: The state which we want to find
925 : * @minext: Pointer to the requested extent length (NULL for a single block)
926 : * This is updated to be the actual reservation size.
927 : *
928 : * Returns: 0 on success, non-zero with errno == ENOSPC if there is no block of the requested state
929 : */
930 25598 : int lgfs2_rbm_find(struct lgfs2_rbm *rbm, uint8_t state, uint32_t *minext)
931 : {
932 : int initial_bii;
933 : uint32_t offset;
934 25598 : int n = 0;
935 25598 : int iters = rbm->rgd->rt_length;
936 : uint32_t extlen;
937 :
938 : /* If we are not starting at the beginning of a bitmap, then we
939 : * need to add one to the bitmap count to ensure that we search
940 : * the starting bitmap twice.
941 : */
942 25598 : if (rbm->offset != 0)
943 0 : iters++;
944 :
945 25600 : for (n = 0; n < iters; n++) {
946 25600 : struct lgfs2_bitmap *bi = rbm_bi(rbm);
947 25600 : uint8_t *buf = (uint8_t *)bi->bi_data + bi->bi_offset;
948 : uint64_t block;
949 : int ret;
950 :
951 25600 : if ((rbm->rgd->rt_free < *minext) && (state == GFS2_BLKST_FREE))
952 2 : goto next_bitmap;
953 :
954 25598 : offset = lgfs2_bitfit(buf, bi->bi_len, rbm->offset, state);
955 25598 : if (offset == LGFS2_BFITNOENT)
956 1 : goto next_bitmap;
957 :
958 25597 : rbm->offset = offset;
959 25597 : initial_bii = rbm->bii;
960 25597 : block = lgfs2_rbm_to_block(rbm);
961 25597 : extlen = 1;
962 :
963 25597 : if (*minext != 0)
964 25597 : extlen = lgfs2_free_extlen(rbm, *minext);
965 :
966 25597 : if (extlen >= *minext)
967 25597 : return 0;
968 :
969 0 : ret = lgfs2_rbm_from_block(rbm, block + extlen);
970 0 : if (ret == 0) {
971 0 : n += (rbm->bii - initial_bii);
972 0 : continue;
973 : }
974 :
975 0 : if (errno == E2BIG) {
976 0 : rbm->bii = 0;
977 0 : rbm->offset = 0;
978 0 : n += (rbm->bii - initial_bii);
979 0 : goto res_covered_end_of_rgrp;
980 : }
981 :
982 0 : return ret;
983 :
984 3 : next_bitmap: /* Find next bitmap in the rgrp */
985 3 : rbm->offset = 0;
986 3 : rbm->bii++;
987 3 : if (rbm->bii == rbm->rgd->rt_length)
988 1 : rbm->bii = 0;
989 :
990 2 : res_covered_end_of_rgrp:
991 3 : if (rbm->bii == 0)
992 1 : break;
993 : }
994 :
995 1 : errno = ENOSPC;
996 1 : return 1;
997 : }
998 :
999 : /**
1000 : * lgfs2_alloc_extent - allocate an extent from a given bitmap
1001 : * @rbm: the resource group information
1002 : * @state: The state of the first block, GFS2_BLKST_DINODE or GFS2_BLKST_USED
1003 : * @elen: The requested extent length
1004 : * Returns the length of the extent allocated.
1005 : */
1006 78 : unsigned lgfs2_alloc_extent(const struct lgfs2_rbm *rbm, int state, const unsigned elen)
1007 : {
1008 78 : struct lgfs2_rbm pos = { .rgd = rbm->rgd, };
1009 78 : const uint64_t block = lgfs2_rbm_to_block(rbm);
1010 : unsigned len;
1011 :
1012 78 : lgfs2_set_bitmap(rbm->rgd, block, state);
1013 :
1014 2424929 : for (len = 1; len < elen; len++) {
1015 2424851 : int ret = lgfs2_rbm_from_block(&pos, block + len);
1016 2424851 : if (ret || lgfs2_testbit(&pos) != GFS2_BLKST_FREE)
1017 : break;
1018 2424851 : lgfs2_set_bitmap(pos.rgd, block + len, GFS2_BLKST_USED);
1019 : }
1020 78 : return len;
1021 : }
|
