Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0
2 : /*
3 : * Copyright (c) 2017 Christoph Hellwig.
4 : */
5 :
6 : #include "xfs.h"
7 : #include "xfs_shared.h"
8 : #include "xfs_format.h"
9 : #include "xfs_bit.h"
10 : #include "xfs_log_format.h"
11 : #include "xfs_trans_resv.h"
12 : #include "xfs_mount.h"
13 : #include "xfs_inode.h"
14 : #include "xfs_trace.h"
15 :
16 : /*
17 : * In-core extent record layout:
18 : *
19 : * +-------+----------------------------+
20 : * | 00:53 | all 54 bits of startoff |
21 : * | 54:63 | low 10 bits of startblock |
22 : * +-------+----------------------------+
23 : * | 00:20 | all 21 bits of length |
24 : * | 21 | unwritten extent bit |
25 : * | 22:63 | high 42 bits of startblock |
26 : * +-------+----------------------------+
27 : */
28 : #define XFS_IEXT_STARTOFF_MASK xfs_mask64lo(BMBT_STARTOFF_BITLEN)
29 : #define XFS_IEXT_LENGTH_MASK xfs_mask64lo(BMBT_BLOCKCOUNT_BITLEN)
30 : #define XFS_IEXT_STARTBLOCK_MASK xfs_mask64lo(BMBT_STARTBLOCK_BITLEN)
31 :
32 : struct xfs_iext_rec {
33 : uint64_t lo;
34 : uint64_t hi;
35 : };
36 :
37 : /*
38 : * Given that the length can't be a zero, only an empty hi value indicates an
39 : * unused record.
40 : */
41 : static bool xfs_iext_rec_is_empty(struct xfs_iext_rec *rec)
42 : {
43 86796585028 : return rec->hi == 0;
44 : }
45 :
46 : static inline void xfs_iext_rec_clear(struct xfs_iext_rec *rec)
47 : {
48 253367786 : rec->lo = 0;
49 253367786 : rec->hi = 0;
50 : }
51 :
52 : static void
53 2215507152 : xfs_iext_set(
54 : struct xfs_iext_rec *rec,
55 : struct xfs_bmbt_irec *irec)
56 : {
57 2215507152 : ASSERT((irec->br_startoff & ~XFS_IEXT_STARTOFF_MASK) == 0);
58 2215507152 : ASSERT((irec->br_blockcount & ~XFS_IEXT_LENGTH_MASK) == 0);
59 2215507152 : ASSERT((irec->br_startblock & ~XFS_IEXT_STARTBLOCK_MASK) == 0);
60 :
61 2215507152 : rec->lo = irec->br_startoff & XFS_IEXT_STARTOFF_MASK;
62 2215507152 : rec->hi = irec->br_blockcount & XFS_IEXT_LENGTH_MASK;
63 :
64 2215507152 : rec->lo |= (irec->br_startblock << 54);
65 2215507152 : rec->hi |= ((irec->br_startblock & ~xfs_mask64lo(10)) << (22 - 10));
66 :
67 2215507152 : if (irec->br_state == XFS_EXT_UNWRITTEN)
68 329897040 : rec->hi |= (1 << 21);
69 2215507152 : }
70 :
71 : static void
72 27410270850 : xfs_iext_get(
73 : struct xfs_bmbt_irec *irec,
74 : struct xfs_iext_rec *rec)
75 : {
76 27410270850 : irec->br_startoff = rec->lo & XFS_IEXT_STARTOFF_MASK;
77 27410270850 : irec->br_blockcount = rec->hi & XFS_IEXT_LENGTH_MASK;
78 :
79 27410270850 : irec->br_startblock = rec->lo >> 54;
80 27410270850 : irec->br_startblock |= (rec->hi & xfs_mask64hi(42)) >> (22 - 10);
81 :
82 27410270850 : if (rec->hi & (1 << 21))
83 3183796096 : irec->br_state = XFS_EXT_UNWRITTEN;
84 : else
85 24226474754 : irec->br_state = XFS_EXT_NORM;
86 27410270850 : }
87 :
88 : enum {
89 : NODE_SIZE = 256,
90 : KEYS_PER_NODE = NODE_SIZE / (sizeof(uint64_t) + sizeof(void *)),
91 : RECS_PER_LEAF = (NODE_SIZE - (2 * sizeof(struct xfs_iext_leaf *))) /
92 : sizeof(struct xfs_iext_rec),
93 : };
94 :
95 : /*
96 : * In-core extent btree block layout:
97 : *
98 : * There are two types of blocks in the btree: leaf and inner (non-leaf) blocks.
99 : *
100 : * The leaf blocks are made up by %KEYS_PER_NODE extent records, which each
101 : * contain the startoffset, blockcount, startblock and unwritten extent flag.
102 : * See above for the exact format, followed by pointers to the previous and next
103 : * leaf blocks (if there are any).
104 : *
105 : * The inner (non-leaf) blocks first contain KEYS_PER_NODE lookup keys, followed
106 : * by an equal number of pointers to the btree blocks at the next lower level.
107 : *
108 : * +-------+-------+-------+-------+-------+----------+----------+
109 : * Leaf: | rec 1 | rec 2 | rec 3 | rec 4 | rec N | prev-ptr | next-ptr |
110 : * +-------+-------+-------+-------+-------+----------+----------+
111 : *
112 : * +-------+-------+-------+-------+-------+-------+------+-------+
113 : * Inner: | key 1 | key 2 | key 3 | key N | ptr 1 | ptr 2 | ptr3 | ptr N |
114 : * +-------+-------+-------+-------+-------+-------+------+-------+
115 : */
116 : struct xfs_iext_node {
117 : uint64_t keys[KEYS_PER_NODE];
118 : #define XFS_IEXT_KEY_INVALID (1ULL << 63)
119 : void *ptrs[KEYS_PER_NODE];
120 : };
121 :
122 : struct xfs_iext_leaf {
123 : struct xfs_iext_rec recs[RECS_PER_LEAF];
124 : struct xfs_iext_leaf *prev;
125 : struct xfs_iext_leaf *next;
126 : };
127 :
128 894846496 : inline xfs_extnum_t xfs_iext_count(struct xfs_ifork *ifp)
129 : {
130 42688663144 : return ifp->if_bytes / sizeof(struct xfs_iext_rec);
131 : }
132 :
133 : static inline int xfs_iext_max_recs(struct xfs_ifork *ifp)
134 : {
135 21594711172 : if (ifp->if_height == 1)
136 41793816648 : return xfs_iext_count(ifp);
137 : return RECS_PER_LEAF;
138 : }
139 :
140 : static inline struct xfs_iext_rec *cur_rec(struct xfs_iext_cursor *cur)
141 : {
142 >13745*10^7 : return &cur->leaf->recs[cur->pos];
143 : }
144 :
145 22150472142 : static inline bool xfs_iext_valid(struct xfs_ifork *ifp,
146 : struct xfs_iext_cursor *cur)
147 : {
148 22150472142 : if (!cur->leaf)
149 : return false;
150 43359671204 : if (cur->pos < 0 || cur->pos >= xfs_iext_max_recs(ifp))
151 : return false;
152 20264758645 : if (xfs_iext_rec_is_empty(cur_rec(cur)))
153 1609417579 : return false;
154 : return true;
155 : }
156 :
157 : static void *
158 2192429935 : xfs_iext_find_first_leaf(
159 : struct xfs_ifork *ifp)
160 : {
161 2192429935 : struct xfs_iext_node *node = ifp->if_u1.if_root;
162 2192429935 : int height;
163 :
164 2192429935 : if (!ifp->if_height)
165 : return NULL;
166 :
167 1950732559 : for (height = ifp->if_height; height > 1; height--) {
168 28789737 : node = node->ptrs[0];
169 28789737 : ASSERT(node);
170 : }
171 :
172 : return node;
173 : }
174 :
175 : static void *
176 1265689949 : xfs_iext_find_last_leaf(
177 : struct xfs_ifork *ifp)
178 : {
179 1265689949 : struct xfs_iext_node *node = ifp->if_u1.if_root;
180 1265689949 : int height, i;
181 :
182 1265689949 : if (!ifp->if_height)
183 : return NULL;
184 :
185 1706351847 : for (height = ifp->if_height; height > 1; height--) {
186 4001889773 : for (i = 1; i < KEYS_PER_NODE; i++)
187 3985669508 : if (!node->ptrs[i])
188 : break;
189 653414746 : node = node->ptrs[i - 1];
190 653488448 : ASSERT(node);
191 : }
192 :
193 : return node;
194 : }
195 :
196 : void
197 2107480556 : xfs_iext_first(
198 : struct xfs_ifork *ifp,
199 : struct xfs_iext_cursor *cur)
200 : {
201 2192555740 : cur->pos = 0;
202 2107480556 : cur->leaf = xfs_iext_find_first_leaf(ifp);
203 2107498126 : }
204 :
205 : void
206 1266283009 : xfs_iext_last(
207 : struct xfs_ifork *ifp,
208 : struct xfs_iext_cursor *cur)
209 : {
210 1266283009 : int i;
211 :
212 1266283009 : cur->leaf = xfs_iext_find_last_leaf(ifp);
213 1266792581 : if (!cur->leaf) {
214 212820554 : cur->pos = 0;
215 212820554 : return;
216 : }
217 :
218 9334703529 : for (i = 1; i < xfs_iext_max_recs(ifp); i++) {
219 6083595769 : if (xfs_iext_rec_is_empty(&cur->leaf->recs[i]))
220 : break;
221 : }
222 1055751003 : cur->pos = i - 1;
223 : }
224 :
225 : void
226 10695972691 : xfs_iext_next(
227 : struct xfs_ifork *ifp,
228 : struct xfs_iext_cursor *cur)
229 : {
230 10695972691 : if (!cur->leaf) {
231 85075184 : ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF);
232 85075184 : xfs_iext_first(ifp, cur);
233 85028463 : return;
234 : }
235 :
236 10610897507 : ASSERT(cur->pos >= 0);
237 14756588609 : ASSERT(cur->pos < xfs_iext_max_recs(ifp));
238 :
239 10610897507 : cur->pos++;
240 10610897507 : if (ifp->if_height > 1 && !xfs_iext_valid(ifp, cur) &&
241 1563169084 : cur->leaf->next) {
242 425795117 : cur->leaf = cur->leaf->next;
243 425795117 : cur->pos = 0;
244 : }
245 : }
246 :
247 : void
248 1255121320 : xfs_iext_prev(
249 : struct xfs_ifork *ifp,
250 : struct xfs_iext_cursor *cur)
251 : {
252 1255121320 : if (!cur->leaf) {
253 239260345 : ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF);
254 239260345 : xfs_iext_last(ifp, cur);
255 239260345 : return;
256 : }
257 :
258 1015860975 : ASSERT(cur->pos >= 0);
259 1015860975 : ASSERT(cur->pos <= RECS_PER_LEAF);
260 :
261 1015860975 : recurse:
262 1169247414 : do {
263 1169247414 : cur->pos--;
264 1169247414 : if (xfs_iext_valid(ifp, cur))
265 : return;
266 226247703 : } while (cur->pos > 0);
267 :
268 101318977 : if (ifp->if_height > 1 && cur->leaf->prev) {
269 28457713 : cur->leaf = cur->leaf->prev;
270 28457713 : cur->pos = RECS_PER_LEAF;
271 28457713 : goto recurse;
272 : }
273 : }
274 :
275 : static inline int
276 : xfs_iext_key_cmp(
277 : struct xfs_iext_node *node,
278 : int n,
279 : xfs_fileoff_t offset)
280 : {
281 43246710376 : if (node->keys[n] > offset)
282 : return 1;
283 34842055334 : if (node->keys[n] < offset)
284 0 : return -1;
285 : return 0;
286 : }
287 :
288 : static inline int
289 : xfs_iext_rec_cmp(
290 : struct xfs_iext_rec *rec,
291 : xfs_fileoff_t offset)
292 : {
293 57586048020 : uint64_t rec_offset = rec->lo & XFS_IEXT_STARTOFF_MASK;
294 57586048020 : uint32_t rec_len = rec->hi & XFS_IEXT_LENGTH_MASK;
295 :
296 143387679 : if (rec_offset > offset)
297 : return 1;
298 53758208274 : if (rec_offset + rec_len <= offset)
299 0 : return -1;
300 : return 0;
301 : }
302 :
303 : static void *
304 16357278359 : xfs_iext_find_level(
305 : struct xfs_ifork *ifp,
306 : xfs_fileoff_t offset,
307 : int level)
308 : {
309 16357278359 : struct xfs_iext_node *node = ifp->if_u1.if_root;
310 16357278359 : int height, i;
311 :
312 16357278359 : if (!ifp->if_height)
313 : return NULL;
314 :
315 24361073926 : for (height = ifp->if_height; height > level; height--) {
316 42245496984 : for (i = 1; i < KEYS_PER_NODE; i++)
317 42076661166 : if (xfs_iext_key_cmp(node, i, offset) > 0)
318 : break;
319 :
320 8420679095 : node = node->ptrs[i - 1];
321 8420606446 : if (!node)
322 : break;
323 : }
324 :
325 : return node;
326 : }
327 :
328 : static int
329 : xfs_iext_node_pos(
330 : struct xfs_iext_node *node,
331 : xfs_fileoff_t offset)
332 : {
333 8478468 : int i;
334 :
335 50980880 : for (i = 1; i < KEYS_PER_NODE; i++) {
336 50713974 : if (xfs_iext_key_cmp(node, i, offset) > 0)
337 : break;
338 : }
339 :
340 8478477 : return i - 1;
341 : }
342 :
343 : static int
344 : xfs_iext_node_insert_pos(
345 : struct xfs_iext_node *node,
346 : xfs_fileoff_t offset)
347 : {
348 98387150 : int i;
349 :
350 882065776 : for (i = 0; i < KEYS_PER_NODE; i++) {
351 876571130 : if (xfs_iext_key_cmp(node, i, offset) > 0)
352 : return i;
353 : }
354 :
355 : return KEYS_PER_NODE;
356 : }
357 :
358 : static int
359 : xfs_iext_node_nr_entries(
360 : struct xfs_iext_node *node,
361 : int start)
362 : {
363 2850615 : int i;
364 :
365 164587525 : for (i = start; i < KEYS_PER_NODE; i++) {
366 156869128 : if (node->keys[i] == XFS_IEXT_KEY_INVALID)
367 : break;
368 : }
369 :
370 108314367 : return i;
371 : }
372 :
373 : static int
374 : xfs_iext_leaf_nr_entries(
375 : struct xfs_ifork *ifp,
376 : struct xfs_iext_leaf *leaf,
377 : int start)
378 : {
379 1828312202 : int i;
380 :
381 4261097349 : for (i = start; i < xfs_iext_max_recs(ifp); i++) {
382 2575890954 : if (xfs_iext_rec_is_empty(&leaf->recs[i]))
383 : break;
384 : }
385 :
386 2032706401 : return i;
387 : }
388 :
389 : static inline uint64_t
390 : xfs_iext_leaf_key(
391 : struct xfs_iext_leaf *leaf,
392 : int n)
393 : {
394 303175948 : return leaf->recs[n].lo & XFS_IEXT_STARTOFF_MASK;
395 : }
396 :
397 : static void
398 3099439 : xfs_iext_grow(
399 : struct xfs_ifork *ifp)
400 : {
401 3099439 : struct xfs_iext_node *node = kmem_zalloc(NODE_SIZE, KM_NOFS);
402 3099467 : int i;
403 :
404 3099467 : if (ifp->if_height == 1) {
405 2876006 : struct xfs_iext_leaf *prev = ifp->if_u1.if_root;
406 :
407 2876006 : node->keys[0] = xfs_iext_leaf_key(prev, 0);
408 2876006 : node->ptrs[0] = prev;
409 : } else {
410 223461 : struct xfs_iext_node *prev = ifp->if_u1.if_root;
411 :
412 223461 : ASSERT(ifp->if_height > 1);
413 :
414 223461 : node->keys[0] = prev->keys[0];
415 223461 : node->ptrs[0] = prev;
416 : }
417 :
418 49591041 : for (i = 1; i < KEYS_PER_NODE; i++)
419 46491590 : node->keys[i] = XFS_IEXT_KEY_INVALID;
420 :
421 3099451 : ifp->if_u1.if_root = node;
422 3099451 : ifp->if_height++;
423 3099451 : }
424 :
425 : static void
426 34819293 : xfs_iext_update_node(
427 : struct xfs_ifork *ifp,
428 : xfs_fileoff_t old_offset,
429 : xfs_fileoff_t new_offset,
430 : int level,
431 : void *ptr)
432 : {
433 34819293 : struct xfs_iext_node *node = ifp->if_u1.if_root;
434 34819293 : int height, i;
435 :
436 82898942 : for (height = ifp->if_height; height > level; height--) {
437 280280315 : for (i = 0; i < KEYS_PER_NODE; i++) {
438 279450703 : if (i > 0 && xfs_iext_key_cmp(node, i, old_offset) > 0)
439 : break;
440 232200813 : if (node->keys[i] == old_offset)
441 22879254 : node->keys[i] = new_offset;
442 : }
443 48079653 : node = node->ptrs[i - 1];
444 48079649 : ASSERT(node);
445 : }
446 :
447 34819296 : ASSERT(node == ptr);
448 34819296 : }
449 :
450 : static struct xfs_iext_node *
451 6118544 : xfs_iext_split_node(
452 : struct xfs_iext_node **nodep,
453 : int *pos,
454 : int *nr_entries)
455 : {
456 6118544 : struct xfs_iext_node *node = *nodep;
457 6118544 : struct xfs_iext_node *new = kmem_zalloc(NODE_SIZE, KM_NOFS);
458 6118547 : const int nr_move = KEYS_PER_NODE / 2;
459 6118547 : int nr_keep = nr_move + (KEYS_PER_NODE & 1);
460 6118547 : int i = 0;
461 :
462 : /* for sequential append operations just spill over into the new node */
463 6118547 : if (*pos == KEYS_PER_NODE) {
464 5494645 : *nodep = new;
465 5494645 : *pos = 0;
466 5494645 : *nr_entries = 0;
467 5494645 : goto done;
468 : }
469 :
470 :
471 5614955 : for (i = 0; i < nr_move; i++) {
472 4991050 : new->keys[i] = node->keys[nr_keep + i];
473 4991039 : new->ptrs[i] = node->ptrs[nr_keep + i];
474 :
475 4991029 : node->keys[nr_keep + i] = XFS_IEXT_KEY_INVALID;
476 4991021 : node->ptrs[nr_keep + i] = NULL;
477 : }
478 :
479 623905 : if (*pos >= nr_keep) {
480 339549 : *nodep = new;
481 339549 : *pos -= nr_keep;
482 339549 : *nr_entries = nr_move;
483 : } else {
484 284356 : *nr_entries = nr_keep;
485 : }
486 : done:
487 99024002 : for (; i < KEYS_PER_NODE; i++)
488 92905455 : new->keys[i] = XFS_IEXT_KEY_INVALID;
489 6118547 : return new;
490 : }
491 :
492 : static void
493 92268514 : xfs_iext_insert_node(
494 : struct xfs_ifork *ifp,
495 : uint64_t offset,
496 : void *ptr,
497 : int level)
498 : {
499 98387064 : struct xfs_iext_node *node, *new;
500 98387064 : int i, pos, nr_entries;
501 :
502 98387064 : again:
503 98387064 : if (ifp->if_height < level)
504 3099444 : xfs_iext_grow(ifp);
505 :
506 98387070 : new = NULL;
507 98387070 : node = xfs_iext_find_level(ifp, offset, level);
508 98387150 : pos = xfs_iext_node_insert_pos(node, offset);
509 98387221 : nr_entries = xfs_iext_node_nr_entries(node, pos);
510 :
511 102844915 : ASSERT(pos >= nr_entries || xfs_iext_key_cmp(node, pos, offset) != 0);
512 98387184 : ASSERT(nr_entries <= KEYS_PER_NODE);
513 :
514 98387184 : if (nr_entries == KEYS_PER_NODE)
515 6118545 : new = xfs_iext_split_node(&node, &pos, &nr_entries);
516 :
517 : /*
518 : * Update the pointers in higher levels if the first entry changes
519 : * in an existing node.
520 : */
521 98387201 : if (node != new && pos == 0 && nr_entries > 0)
522 0 : xfs_iext_update_node(ifp, node->keys[0], offset, level, node);
523 :
524 115764519 : for (i = nr_entries; i > pos; i--) {
525 17377366 : node->keys[i] = node->keys[i - 1];
526 17377368 : node->ptrs[i] = node->ptrs[i - 1];
527 : }
528 98387153 : node->keys[pos] = offset;
529 98387172 : node->ptrs[pos] = ptr;
530 :
531 98387206 : if (new) {
532 6118550 : offset = new->keys[0];
533 6118550 : ptr = new;
534 6118550 : level++;
535 6118550 : goto again;
536 : }
537 92268656 : }
538 :
539 : static struct xfs_iext_leaf *
540 92268579 : xfs_iext_split_leaf(
541 : struct xfs_iext_cursor *cur,
542 : int *nr_entries)
543 : {
544 92268579 : struct xfs_iext_leaf *leaf = cur->leaf;
545 92268579 : struct xfs_iext_leaf *new = kmem_zalloc(NODE_SIZE, KM_NOFS);
546 92268620 : const int nr_move = RECS_PER_LEAF / 2;
547 92268620 : int nr_keep = nr_move + (RECS_PER_LEAF & 1);
548 92268620 : int i;
549 :
550 : /* for sequential append operations just spill over into the new node */
551 92268620 : if (cur->pos == RECS_PER_LEAF) {
552 81727241 : cur->leaf = new;
553 81727241 : cur->pos = 0;
554 81727241 : *nr_entries = 0;
555 81727241 : goto done;
556 : }
557 :
558 84330558 : for (i = 0; i < nr_move; i++) {
559 73789152 : new->recs[i] = leaf->recs[nr_keep + i];
560 73789137 : xfs_iext_rec_clear(&leaf->recs[nr_keep + i]);
561 : }
562 :
563 10541406 : if (cur->pos >= nr_keep) {
564 7464465 : cur->leaf = new;
565 7464465 : cur->pos -= nr_keep;
566 7464465 : *nr_entries = nr_move;
567 : } else {
568 3076941 : *nr_entries = nr_keep;
569 : }
570 92268647 : done:
571 92268647 : if (leaf->next)
572 4117621 : leaf->next->prev = new;
573 92268647 : new->next = leaf->next;
574 92268647 : new->prev = leaf;
575 92268647 : leaf->next = new;
576 92268647 : return new;
577 : }
578 :
579 : static void
580 170027249 : xfs_iext_alloc_root(
581 : struct xfs_ifork *ifp,
582 : struct xfs_iext_cursor *cur)
583 : {
584 170027249 : ASSERT(ifp->if_bytes == 0);
585 :
586 170027249 : ifp->if_u1.if_root = kmem_zalloc(sizeof(struct xfs_iext_rec), KM_NOFS);
587 170018649 : ifp->if_height = 1;
588 :
589 : /* now that we have a node step into it */
590 170018649 : cur->leaf = ifp->if_u1.if_root;
591 170018649 : cur->pos = 0;
592 170018649 : }
593 :
594 : static void
595 351715468 : xfs_iext_realloc_root(
596 : struct xfs_ifork *ifp,
597 : struct xfs_iext_cursor *cur)
598 : {
599 351715468 : int64_t new_size = ifp->if_bytes + sizeof(struct xfs_iext_rec);
600 351715468 : void *new;
601 :
602 : /* account for the prev/next pointers */
603 351715468 : if (new_size / sizeof(struct xfs_iext_rec) == RECS_PER_LEAF)
604 3624196 : new_size = NODE_SIZE;
605 :
606 351715468 : new = krealloc(ifp->if_u1.if_root, new_size, GFP_NOFS | __GFP_NOFAIL);
607 351717790 : memset(new + ifp->if_bytes, 0, new_size - ifp->if_bytes);
608 351717790 : ifp->if_u1.if_root = new;
609 351717790 : cur->leaf = new;
610 351717790 : }
611 :
612 : /*
613 : * Increment the sequence counter on extent tree changes. If we are on a COW
614 : * fork, this allows the writeback code to skip looking for a COW extent if the
615 : * COW fork hasn't changed. We use WRITE_ONCE here to ensure the update to the
616 : * sequence counter is seen before the modifications to the extent tree itself
617 : * take effect.
618 : */
619 : static inline void xfs_iext_inc_seq(struct xfs_ifork *ifp)
620 : {
621 2395084959 : WRITE_ONCE(ifp->if_seq, READ_ONCE(ifp->if_seq) + 1);
622 : }
623 :
624 : void
625 1828287457 : xfs_iext_insert_raw(
626 : struct xfs_ifork *ifp,
627 : struct xfs_iext_cursor *cur,
628 : struct xfs_bmbt_irec *irec)
629 : {
630 1828287457 : xfs_fileoff_t offset = irec->br_startoff;
631 1828287457 : struct xfs_iext_leaf *new = NULL;
632 1828287457 : int nr_entries, i;
633 :
634 1828287457 : xfs_iext_inc_seq(ifp);
635 :
636 1828287457 : if (ifp->if_height == 0)
637 169993411 : xfs_iext_alloc_root(ifp, cur);
638 1658294046 : else if (ifp->if_height == 1)
639 351715126 : xfs_iext_realloc_root(ifp, cur);
640 :
641 1828312202 : nr_entries = xfs_iext_leaf_nr_entries(ifp, cur->leaf, cur->pos);
642 1828355466 : ASSERT(nr_entries <= RECS_PER_LEAF);
643 1971743145 : ASSERT(cur->pos >= nr_entries ||
644 : xfs_iext_rec_cmp(cur_rec(cur), irec->br_startoff) != 0);
645 :
646 1828354775 : if (nr_entries == RECS_PER_LEAF)
647 92268599 : new = xfs_iext_split_leaf(cur, &nr_entries);
648 :
649 : /*
650 : * Update the pointers in higher levels if the first entry changes
651 : * in an existing node.
652 : */
653 1828354640 : if (cur->leaf != new && cur->pos == 0 && nr_entries > 0) {
654 13846055 : xfs_iext_update_node(ifp, xfs_iext_leaf_key(cur->leaf, 0),
655 : offset, 1, cur->leaf);
656 : }
657 :
658 2358302389 : for (i = nr_entries; i > cur->pos; i--)
659 529970866 : cur->leaf->recs[i] = cur->leaf->recs[i - 1];
660 1828331523 : xfs_iext_set(cur_rec(cur), irec);
661 1828251729 : ifp->if_bytes += sizeof(struct xfs_iext_rec);
662 :
663 1828251729 : if (new)
664 92268546 : xfs_iext_insert_node(ifp, xfs_iext_leaf_key(new, 0), new, 2);
665 1828251831 : }
666 :
667 : void
668 1744649616 : xfs_iext_insert(
669 : struct xfs_inode *ip,
670 : struct xfs_iext_cursor *cur,
671 : struct xfs_bmbt_irec *irec,
672 : int state)
673 : {
674 1744649616 : struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state);
675 :
676 1744561961 : xfs_iext_insert_raw(ifp, cur, irec);
677 1744578658 : trace_xfs_iext_insert(ip, cur, state, _RET_IP_);
678 1744557312 : }
679 :
680 : static struct xfs_iext_node *
681 1652954 : xfs_iext_rebalance_node(
682 : struct xfs_iext_node *parent,
683 : int *pos,
684 : struct xfs_iext_node *node,
685 : int nr_entries)
686 : {
687 : /*
688 : * If the neighbouring nodes are completely full, or have different
689 : * parents, we might never be able to merge our node, and will only
690 : * delete it once the number of entries hits zero.
691 : */
692 1652954 : if (nr_entries == 0)
693 : return node;
694 :
695 1462015 : if (*pos > 0) {
696 1317952 : struct xfs_iext_node *prev = parent->ptrs[*pos - 1];
697 1317952 : int nr_prev = xfs_iext_node_nr_entries(prev, 0), i;
698 :
699 1317952 : if (nr_prev + nr_entries <= KEYS_PER_NODE) {
700 254688 : for (i = 0; i < nr_entries; i++) {
701 218768 : prev->keys[nr_prev + i] = node->keys[i];
702 218768 : prev->ptrs[nr_prev + i] = node->ptrs[i];
703 : }
704 : return node;
705 : }
706 : }
707 :
708 2852190 : if (*pos + 1 < xfs_iext_node_nr_entries(parent, *pos)) {
709 106568 : struct xfs_iext_node *next = parent->ptrs[*pos + 1];
710 106568 : int nr_next = xfs_iext_node_nr_entries(next, 0), i;
711 :
712 106568 : if (nr_entries + nr_next <= KEYS_PER_NODE) {
713 : /*
714 : * Merge the next node into this node so that we don't
715 : * have to do an additional update of the keys in the
716 : * higher levels.
717 : */
718 252434 : for (i = 0; i < nr_next; i++) {
719 228242 : node->keys[nr_entries + i] = next->keys[i];
720 228242 : node->ptrs[nr_entries + i] = next->ptrs[i];
721 : }
722 :
723 24192 : ++*pos;
724 24192 : return next;
725 : }
726 : }
727 :
728 : return NULL;
729 : }
730 :
731 : static void
732 6825514 : xfs_iext_remove_node(
733 : struct xfs_ifork *ifp,
734 : xfs_fileoff_t offset,
735 : void *victim)
736 : {
737 6825514 : struct xfs_iext_node *node, *parent;
738 6825514 : int level = 2, pos, nr_entries, i;
739 :
740 6825514 : ASSERT(level <= ifp->if_height);
741 6825514 : node = xfs_iext_find_level(ifp, offset, level);
742 13651038 : pos = xfs_iext_node_pos(node, offset);
743 7076575 : again:
744 7076575 : ASSERT(node->ptrs[pos]);
745 7076576 : ASSERT(node->ptrs[pos] == victim);
746 7076576 : kmem_free(victim);
747 :
748 7076566 : nr_entries = xfs_iext_node_nr_entries(node, pos) - 1;
749 7076565 : offset = node->keys[0];
750 12316723 : for (i = pos; i < nr_entries; i++) {
751 5240155 : node->keys[i] = node->keys[i + 1];
752 5240155 : node->ptrs[i] = node->ptrs[i + 1];
753 : }
754 7076568 : node->keys[nr_entries] = XFS_IEXT_KEY_INVALID;
755 7076568 : node->ptrs[nr_entries] = NULL;
756 :
757 7076575 : if (pos == 0 && nr_entries > 0) {
758 134215 : xfs_iext_update_node(ifp, offset, node->keys[0], level, node);
759 134215 : offset = node->keys[0];
760 : }
761 :
762 7076575 : if (nr_entries >= KEYS_PER_NODE / 2)
763 2255018 : return;
764 :
765 4821557 : if (level < ifp->if_height) {
766 : /*
767 : * If we aren't at the root yet try to find a neighbour node to
768 : * merge with (or delete the node if it is empty), and then
769 : * recurse up to the next level.
770 : */
771 1652954 : level++;
772 1652954 : parent = xfs_iext_find_level(ifp, offset, level);
773 1652954 : pos = xfs_iext_node_pos(parent, offset);
774 :
775 1652953 : ASSERT(pos != KEYS_PER_NODE);
776 1652953 : ASSERT(parent->ptrs[pos] == node);
777 :
778 1652954 : node = xfs_iext_rebalance_node(parent, &pos, node, nr_entries);
779 1652953 : if (node) {
780 251051 : victim = node;
781 251051 : node = parent;
782 251051 : goto again;
783 : }
784 3168603 : } else if (nr_entries == 1) {
785 : /*
786 : * If we are at the root and only one entry is left we can just
787 : * free this node and update the root pointer.
788 : */
789 1471654 : ASSERT(node == ifp->if_u1.if_root);
790 1471654 : ifp->if_u1.if_root = node->ptrs[0];
791 1471654 : ifp->if_height--;
792 1471654 : kmem_free(node);
793 : }
794 : }
795 :
796 : static void
797 27044924 : xfs_iext_rebalance_leaf(
798 : struct xfs_ifork *ifp,
799 : struct xfs_iext_cursor *cur,
800 : struct xfs_iext_leaf *leaf,
801 : xfs_fileoff_t offset,
802 : int nr_entries)
803 : {
804 : /*
805 : * If the neighbouring nodes are completely full we might never be able
806 : * to merge our node, and will only delete it once the number of
807 : * entries hits zero.
808 : */
809 27044924 : if (nr_entries == 0)
810 3010554 : goto remove_node;
811 :
812 24034370 : if (leaf->prev) {
813 : int nr_prev = xfs_iext_leaf_nr_entries(ifp, leaf->prev, 0), i;
814 :
815 23030666 : if (nr_prev + nr_entries <= RECS_PER_LEAF) {
816 18883160 : for (i = 0; i < nr_entries; i++)
817 15852241 : leaf->prev->recs[nr_prev + i] = leaf->recs[i];
818 :
819 3030919 : if (cur->leaf == leaf) {
820 997675 : cur->leaf = leaf->prev;
821 997675 : cur->pos += nr_prev;
822 : }
823 3030919 : goto remove_node;
824 : }
825 : }
826 :
827 21003471 : if (leaf->next) {
828 : int nr_next = xfs_iext_leaf_nr_entries(ifp, leaf->next, 0), i;
829 :
830 1666316 : if (nr_entries + nr_next <= RECS_PER_LEAF) {
831 : /*
832 : * Merge the next node into this node so that we don't
833 : * have to do an additional update of the keys in the
834 : * higher levels.
835 : */
836 7234310 : for (i = 0; i < nr_next; i++) {
837 6450267 : leaf->recs[nr_entries + i] =
838 6450267 : leaf->next->recs[i];
839 : }
840 :
841 784043 : if (cur->leaf == leaf->next) {
842 131335 : cur->leaf = leaf;
843 131335 : cur->pos += nr_entries;
844 : }
845 :
846 784043 : offset = xfs_iext_leaf_key(leaf->next, 0);
847 784043 : leaf = leaf->next;
848 784043 : goto remove_node;
849 : }
850 : }
851 :
852 : return;
853 6825516 : remove_node:
854 6825516 : if (leaf->prev)
855 6823662 : leaf->prev->next = leaf->next;
856 6825516 : if (leaf->next)
857 1105467 : leaf->next->prev = leaf->prev;
858 6825516 : xfs_iext_remove_node(ifp, offset, leaf);
859 : }
860 :
861 : static void
862 : xfs_iext_free_last_leaf(
863 : struct xfs_ifork *ifp)
864 : {
865 45877055 : ifp->if_height--;
866 45877055 : kmem_free(ifp->if_u1.if_root);
867 46024750 : ifp->if_u1.if_root = NULL;
868 46024750 : }
869 :
870 : void
871 179641395 : xfs_iext_remove(
872 : struct xfs_inode *ip,
873 : struct xfs_iext_cursor *cur,
874 : int state)
875 : {
876 179641395 : struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state);
877 179587747 : struct xfs_iext_leaf *leaf = cur->leaf;
878 179587747 : xfs_fileoff_t offset = xfs_iext_leaf_key(leaf, 0);
879 179587747 : int i, nr_entries;
880 :
881 179587747 : trace_xfs_iext_remove(ip, cur, state, _RET_IP_);
882 :
883 179610010 : ASSERT(ifp->if_height > 0);
884 179610010 : ASSERT(ifp->if_u1.if_root != NULL);
885 179610010 : ASSERT(xfs_iext_valid(ifp, cur));
886 :
887 179547448 : xfs_iext_inc_seq(ifp);
888 :
889 179547448 : nr_entries = xfs_iext_leaf_nr_entries(ifp, leaf, cur->pos) - 1;
890 382497405 : for (i = cur->pos; i < nr_entries; i++)
891 202863779 : leaf->recs[i] = leaf->recs[i + 1];
892 179633626 : xfs_iext_rec_clear(&leaf->recs[nr_entries]);
893 179578607 : ifp->if_bytes -= sizeof(struct xfs_iext_rec);
894 :
895 179578607 : if (cur->pos == 0 && nr_entries > 0) {
896 6906778 : xfs_iext_update_node(ifp, offset, xfs_iext_leaf_key(leaf, 0), 1,
897 : leaf);
898 6906773 : offset = xfs_iext_leaf_key(leaf, 0);
899 172671829 : } else if (cur->pos == nr_entries) {
900 133987934 : if (ifp->if_height > 1 && leaf->next)
901 2013832 : cur->leaf = leaf->next;
902 : else
903 131974102 : cur->leaf = NULL;
904 133987934 : cur->pos = 0;
905 : }
906 :
907 179578602 : if (nr_entries >= RECS_PER_LEAF / 2)
908 : return;
909 :
910 99228768 : if (ifp->if_height > 1)
911 27044925 : xfs_iext_rebalance_leaf(ifp, cur, leaf, offset, nr_entries);
912 72183843 : else if (nr_entries == 0)
913 45877055 : xfs_iext_free_last_leaf(ifp);
914 : }
915 :
916 : /*
917 : * Lookup the extent covering bno.
918 : *
919 : * If there is an extent covering bno return the extent index, and store the
920 : * expanded extent structure in *gotp, and the extent cursor in *cur.
921 : * If there is no extent covering bno, but there is an extent after it (e.g.
922 : * it lies in a hole) return that extent in *gotp and its cursor in *cur
923 : * instead.
924 : * If bno is beyond the last extent return false, and return an invalid
925 : * cursor value.
926 : */
927 : bool
928 16250106881 : xfs_iext_lookup_extent(
929 : struct xfs_inode *ip,
930 : struct xfs_ifork *ifp,
931 : xfs_fileoff_t offset,
932 : struct xfs_iext_cursor *cur,
933 : struct xfs_bmbt_irec *gotp)
934 : {
935 16250106881 : XFS_STATS_INC(ip->i_mount, xs_look_exlist);
936 :
937 16248009557 : cur->leaf = xfs_iext_find_level(ifp, offset, 1);
938 16249742062 : if (!cur->leaf) {
939 416703192 : cur->pos = 0;
940 416703192 : return false;
941 : }
942 :
943 85065751859 : for (cur->pos = 0; cur->pos < xfs_iext_max_recs(ifp); cur->pos++) {
944 57876125536 : struct xfs_iext_rec *rec = cur_rec(cur);
945 :
946 57869708403 : if (xfs_iext_rec_is_empty(rec))
947 : break;
948 57442660341 : if (xfs_iext_rec_cmp(rec, offset) >= 0)
949 14683925840 : goto found;
950 : }
951 :
952 : /* Try looking in the next node for an entry > offset */
953 1142695897 : if (ifp->if_height == 1 || !cur->leaf->next)
954 : return false;
955 97289541 : cur->leaf = cur->leaf->next;
956 97289541 : cur->pos = 0;
957 97289541 : if (!xfs_iext_valid(ifp, cur))
958 : return false;
959 97289288 : found:
960 14781215128 : xfs_iext_get(gotp, cur_rec(cur));
961 14795901127 : return true;
962 : }
963 :
964 : /*
965 : * Returns the last extent before end, and if this extent doesn't cover
966 : * end, update end to the end of the extent.
967 : */
968 : bool
969 210626046 : xfs_iext_lookup_extent_before(
970 : struct xfs_inode *ip,
971 : struct xfs_ifork *ifp,
972 : xfs_fileoff_t *end,
973 : struct xfs_iext_cursor *cur,
974 : struct xfs_bmbt_irec *gotp)
975 : {
976 : /* could be optimized to not even look up the next on a match.. */
977 210626046 : if (xfs_iext_lookup_extent(ip, ifp, *end - 1, cur, gotp) &&
978 127724129 : gotp->br_startoff <= *end - 1)
979 : return true;
980 90329688 : if (!xfs_iext_prev_extent(ifp, cur, gotp))
981 : return false;
982 89349858 : *end = gotp->br_startoff + gotp->br_blockcount;
983 89349858 : return true;
984 : }
985 :
986 : void
987 387263740 : xfs_iext_update_extent(
988 : struct xfs_inode *ip,
989 : int state,
990 : struct xfs_iext_cursor *cur,
991 : struct xfs_bmbt_irec *new)
992 : {
993 387263740 : struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state);
994 :
995 387250054 : xfs_iext_inc_seq(ifp);
996 :
997 387250054 : if (cur->pos == 0) {
998 75547327 : struct xfs_bmbt_irec old;
999 :
1000 75547327 : xfs_iext_get(&old, cur_rec(cur));
1001 75549910 : if (new->br_startoff != old.br_startoff) {
1002 13932314 : xfs_iext_update_node(ifp, old.br_startoff,
1003 : new->br_startoff, 1, cur->leaf);
1004 : }
1005 : }
1006 :
1007 387252639 : trace_xfs_bmap_pre_update(ip, cur, state, _RET_IP_);
1008 387251606 : xfs_iext_set(cur_rec(cur), new);
1009 387256385 : trace_xfs_bmap_post_update(ip, cur, state, _RET_IP_);
1010 387247436 : }
1011 :
1012 : /*
1013 : * Return true if the cursor points at an extent and return the extent structure
1014 : * in gotp. Else return false.
1015 : */
1016 : bool
1017 14249293442 : xfs_iext_get_extent(
1018 : struct xfs_ifork *ifp,
1019 : struct xfs_iext_cursor *cur,
1020 : struct xfs_bmbt_irec *gotp)
1021 : {
1022 14249293442 : if (!xfs_iext_valid(ifp, cur))
1023 : return false;
1024 12543411480 : xfs_iext_get(gotp, cur_rec(cur));
1025 12543800072 : return true;
1026 : }
1027 :
1028 : /*
1029 : * This is a recursive function, because of that we need to be extremely
1030 : * careful with stack usage.
1031 : */
1032 : static void
1033 216899902 : xfs_iext_destroy_node(
1034 : struct xfs_iext_node *node,
1035 : int level)
1036 : {
1037 216899902 : int i;
1038 :
1039 216899902 : if (level > 1) {
1040 100423504 : for (i = 0; i < KEYS_PER_NODE; i++) {
1041 95569108 : if (node->keys[i] == XFS_IEXT_KEY_INVALID)
1042 : break;
1043 92928125 : xfs_iext_destroy_node(node->ptrs[i], level - 1);
1044 : }
1045 : }
1046 :
1047 216900092 : kmem_free(node);
1048 216897387 : }
1049 :
1050 : void
1051 123994940 : xfs_iext_destroy(
1052 : struct xfs_ifork *ifp)
1053 : {
1054 123994940 : xfs_iext_destroy_node(ifp->if_u1.if_root, ifp->if_height);
1055 :
1056 123998410 : ifp->if_bytes = 0;
1057 123998410 : ifp->if_height = 0;
1058 123998410 : ifp->if_u1.if_root = NULL;
1059 123998410 : }
|
