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 */
xfs_iext_rec_is_empty(struct xfs_iext_rec * rec)41 static bool xfs_iext_rec_is_empty(struct xfs_iext_rec *rec)
42 {
43 return rec->hi == 0;
44 }
45
xfs_iext_rec_clear(struct xfs_iext_rec * rec)46 static inline void xfs_iext_rec_clear(struct xfs_iext_rec *rec)
47 {
48 rec->lo = 0;
49 rec->hi = 0;
50 }
51
52 static void
xfs_iext_set(struct xfs_iext_rec * rec,struct xfs_bmbt_irec * irec)53 xfs_iext_set(
54 struct xfs_iext_rec *rec,
55 struct xfs_bmbt_irec *irec)
56 {
57 ASSERT((irec->br_startoff & ~XFS_IEXT_STARTOFF_MASK) == 0);
58 ASSERT((irec->br_blockcount & ~XFS_IEXT_LENGTH_MASK) == 0);
59 ASSERT((irec->br_startblock & ~XFS_IEXT_STARTBLOCK_MASK) == 0);
60
61 rec->lo = irec->br_startoff & XFS_IEXT_STARTOFF_MASK;
62 rec->hi = irec->br_blockcount & XFS_IEXT_LENGTH_MASK;
63
64 rec->lo |= (irec->br_startblock << 54);
65 rec->hi |= ((irec->br_startblock & ~xfs_mask64lo(10)) << (22 - 10));
66
67 if (irec->br_state == XFS_EXT_UNWRITTEN)
68 rec->hi |= (1 << 21);
69 }
70
71 static void
xfs_iext_get(struct xfs_bmbt_irec * irec,struct xfs_iext_rec * rec)72 xfs_iext_get(
73 struct xfs_bmbt_irec *irec,
74 struct xfs_iext_rec *rec)
75 {
76 irec->br_startoff = rec->lo & XFS_IEXT_STARTOFF_MASK;
77 irec->br_blockcount = rec->hi & XFS_IEXT_LENGTH_MASK;
78
79 irec->br_startblock = rec->lo >> 54;
80 irec->br_startblock |= (rec->hi & xfs_mask64hi(42)) >> (22 - 10);
81
82 if (rec->hi & (1 << 21))
83 irec->br_state = XFS_EXT_UNWRITTEN;
84 else
85 irec->br_state = XFS_EXT_NORM;
86 }
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
xfs_iext_count(struct xfs_ifork * ifp)128 inline xfs_extnum_t xfs_iext_count(struct xfs_ifork *ifp)
129 {
130 return ifp->if_bytes / sizeof(struct xfs_iext_rec);
131 }
132
xfs_iext_max_recs(struct xfs_ifork * ifp)133 static inline int xfs_iext_max_recs(struct xfs_ifork *ifp)
134 {
135 if (ifp->if_height == 1)
136 return xfs_iext_count(ifp);
137 return RECS_PER_LEAF;
138 }
139
cur_rec(struct xfs_iext_cursor * cur)140 static inline struct xfs_iext_rec *cur_rec(struct xfs_iext_cursor *cur)
141 {
142 return &cur->leaf->recs[cur->pos];
143 }
144
xfs_iext_valid(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)145 static inline bool xfs_iext_valid(struct xfs_ifork *ifp,
146 struct xfs_iext_cursor *cur)
147 {
148 if (!cur->leaf)
149 return false;
150 if (cur->pos < 0 || cur->pos >= xfs_iext_max_recs(ifp))
151 return false;
152 if (xfs_iext_rec_is_empty(cur_rec(cur)))
153 return false;
154 return true;
155 }
156
157 static void *
xfs_iext_find_first_leaf(struct xfs_ifork * ifp)158 xfs_iext_find_first_leaf(
159 struct xfs_ifork *ifp)
160 {
161 struct xfs_iext_node *node = ifp->if_data;
162 int height;
163
164 if (!ifp->if_height)
165 return NULL;
166
167 for (height = ifp->if_height; height > 1; height--) {
168 node = node->ptrs[0];
169 ASSERT(node);
170 }
171
172 return node;
173 }
174
175 static void *
xfs_iext_find_last_leaf(struct xfs_ifork * ifp)176 xfs_iext_find_last_leaf(
177 struct xfs_ifork *ifp)
178 {
179 struct xfs_iext_node *node = ifp->if_data;
180 int height, i;
181
182 if (!ifp->if_height)
183 return NULL;
184
185 for (height = ifp->if_height; height > 1; height--) {
186 for (i = 1; i < KEYS_PER_NODE; i++)
187 if (!node->ptrs[i])
188 break;
189 node = node->ptrs[i - 1];
190 ASSERT(node);
191 }
192
193 return node;
194 }
195
196 void
xfs_iext_first(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)197 xfs_iext_first(
198 struct xfs_ifork *ifp,
199 struct xfs_iext_cursor *cur)
200 {
201 cur->pos = 0;
202 cur->leaf = xfs_iext_find_first_leaf(ifp);
203 }
204
205 void
xfs_iext_last(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)206 xfs_iext_last(
207 struct xfs_ifork *ifp,
208 struct xfs_iext_cursor *cur)
209 {
210 int i;
211
212 cur->leaf = xfs_iext_find_last_leaf(ifp);
213 if (!cur->leaf) {
214 cur->pos = 0;
215 return;
216 }
217
218 for (i = 1; i < xfs_iext_max_recs(ifp); i++) {
219 if (xfs_iext_rec_is_empty(&cur->leaf->recs[i]))
220 break;
221 }
222 cur->pos = i - 1;
223 }
224
225 void
xfs_iext_next(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)226 xfs_iext_next(
227 struct xfs_ifork *ifp,
228 struct xfs_iext_cursor *cur)
229 {
230 if (!cur->leaf) {
231 ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF);
232 xfs_iext_first(ifp, cur);
233 return;
234 }
235
236 ASSERT(cur->pos >= 0);
237 ASSERT(cur->pos < xfs_iext_max_recs(ifp));
238
239 cur->pos++;
240 if (ifp->if_height > 1 && !xfs_iext_valid(ifp, cur) &&
241 cur->leaf->next) {
242 cur->leaf = cur->leaf->next;
243 cur->pos = 0;
244 }
245 }
246
247 void
xfs_iext_prev(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)248 xfs_iext_prev(
249 struct xfs_ifork *ifp,
250 struct xfs_iext_cursor *cur)
251 {
252 if (!cur->leaf) {
253 ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF);
254 xfs_iext_last(ifp, cur);
255 return;
256 }
257
258 ASSERT(cur->pos >= 0);
259 ASSERT(cur->pos <= RECS_PER_LEAF);
260
261 recurse:
262 do {
263 cur->pos--;
264 if (xfs_iext_valid(ifp, cur))
265 return;
266 } while (cur->pos > 0);
267
268 if (ifp->if_height > 1 && cur->leaf->prev) {
269 cur->leaf = cur->leaf->prev;
270 cur->pos = RECS_PER_LEAF;
271 goto recurse;
272 }
273 }
274
275 static inline int
xfs_iext_key_cmp(struct xfs_iext_node * node,int n,xfs_fileoff_t offset)276 xfs_iext_key_cmp(
277 struct xfs_iext_node *node,
278 int n,
279 xfs_fileoff_t offset)
280 {
281 if (node->keys[n] > offset)
282 return 1;
283 if (node->keys[n] < offset)
284 return -1;
285 return 0;
286 }
287
288 static inline int
xfs_iext_rec_cmp(struct xfs_iext_rec * rec,xfs_fileoff_t offset)289 xfs_iext_rec_cmp(
290 struct xfs_iext_rec *rec,
291 xfs_fileoff_t offset)
292 {
293 uint64_t rec_offset = rec->lo & XFS_IEXT_STARTOFF_MASK;
294 uint32_t rec_len = rec->hi & XFS_IEXT_LENGTH_MASK;
295
296 if (rec_offset > offset)
297 return 1;
298 if (rec_offset + rec_len <= offset)
299 return -1;
300 return 0;
301 }
302
303 static void *
xfs_iext_find_level(struct xfs_ifork * ifp,xfs_fileoff_t offset,int level)304 xfs_iext_find_level(
305 struct xfs_ifork *ifp,
306 xfs_fileoff_t offset,
307 int level)
308 {
309 struct xfs_iext_node *node = ifp->if_data;
310 int height, i;
311
312 if (!ifp->if_height)
313 return NULL;
314
315 for (height = ifp->if_height; height > level; height--) {
316 for (i = 1; i < KEYS_PER_NODE; i++)
317 if (xfs_iext_key_cmp(node, i, offset) > 0)
318 break;
319
320 node = node->ptrs[i - 1];
321 if (!node)
322 break;
323 }
324
325 return node;
326 }
327
328 static int
xfs_iext_node_pos(struct xfs_iext_node * node,xfs_fileoff_t offset)329 xfs_iext_node_pos(
330 struct xfs_iext_node *node,
331 xfs_fileoff_t offset)
332 {
333 int i;
334
335 for (i = 1; i < KEYS_PER_NODE; i++) {
336 if (xfs_iext_key_cmp(node, i, offset) > 0)
337 break;
338 }
339
340 return i - 1;
341 }
342
343 static int
xfs_iext_node_insert_pos(struct xfs_iext_node * node,xfs_fileoff_t offset)344 xfs_iext_node_insert_pos(
345 struct xfs_iext_node *node,
346 xfs_fileoff_t offset)
347 {
348 int i;
349
350 for (i = 0; i < KEYS_PER_NODE; i++) {
351 if (xfs_iext_key_cmp(node, i, offset) > 0)
352 return i;
353 }
354
355 return KEYS_PER_NODE;
356 }
357
358 static int
xfs_iext_node_nr_entries(struct xfs_iext_node * node,int start)359 xfs_iext_node_nr_entries(
360 struct xfs_iext_node *node,
361 int start)
362 {
363 int i;
364
365 for (i = start; i < KEYS_PER_NODE; i++) {
366 if (node->keys[i] == XFS_IEXT_KEY_INVALID)
367 break;
368 }
369
370 return i;
371 }
372
373 static int
xfs_iext_leaf_nr_entries(struct xfs_ifork * ifp,struct xfs_iext_leaf * leaf,int start)374 xfs_iext_leaf_nr_entries(
375 struct xfs_ifork *ifp,
376 struct xfs_iext_leaf *leaf,
377 int start)
378 {
379 int i;
380
381 for (i = start; i < xfs_iext_max_recs(ifp); i++) {
382 if (xfs_iext_rec_is_empty(&leaf->recs[i]))
383 break;
384 }
385
386 return i;
387 }
388
389 static inline uint64_t
xfs_iext_leaf_key(struct xfs_iext_leaf * leaf,int n)390 xfs_iext_leaf_key(
391 struct xfs_iext_leaf *leaf,
392 int n)
393 {
394 return leaf->recs[n].lo & XFS_IEXT_STARTOFF_MASK;
395 }
396
397 static void
xfs_iext_grow(struct xfs_ifork * ifp)398 xfs_iext_grow(
399 struct xfs_ifork *ifp)
400 {
401 struct xfs_iext_node *node = kmem_zalloc(NODE_SIZE, KM_NOFS);
402 int i;
403
404 if (ifp->if_height == 1) {
405 struct xfs_iext_leaf *prev = ifp->if_data;
406
407 node->keys[0] = xfs_iext_leaf_key(prev, 0);
408 node->ptrs[0] = prev;
409 } else {
410 struct xfs_iext_node *prev = ifp->if_data;
411
412 ASSERT(ifp->if_height > 1);
413
414 node->keys[0] = prev->keys[0];
415 node->ptrs[0] = prev;
416 }
417
418 for (i = 1; i < KEYS_PER_NODE; i++)
419 node->keys[i] = XFS_IEXT_KEY_INVALID;
420
421 ifp->if_data = node;
422 ifp->if_height++;
423 }
424
425 static void
xfs_iext_update_node(struct xfs_ifork * ifp,xfs_fileoff_t old_offset,xfs_fileoff_t new_offset,int level,void * ptr)426 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 struct xfs_iext_node *node = ifp->if_data;
434 int height, i;
435
436 for (height = ifp->if_height; height > level; height--) {
437 for (i = 0; i < KEYS_PER_NODE; i++) {
438 if (i > 0 && xfs_iext_key_cmp(node, i, old_offset) > 0)
439 break;
440 if (node->keys[i] == old_offset)
441 node->keys[i] = new_offset;
442 }
443 node = node->ptrs[i - 1];
444 ASSERT(node);
445 }
446
447 ASSERT(node == ptr);
448 }
449
450 static struct xfs_iext_node *
xfs_iext_split_node(struct xfs_iext_node ** nodep,int * pos,int * nr_entries)451 xfs_iext_split_node(
452 struct xfs_iext_node **nodep,
453 int *pos,
454 int *nr_entries)
455 {
456 struct xfs_iext_node *node = *nodep;
457 struct xfs_iext_node *new = kmem_zalloc(NODE_SIZE, KM_NOFS);
458 const int nr_move = KEYS_PER_NODE / 2;
459 int nr_keep = nr_move + (KEYS_PER_NODE & 1);
460 int i = 0;
461
462 /* for sequential append operations just spill over into the new node */
463 if (*pos == KEYS_PER_NODE) {
464 *nodep = new;
465 *pos = 0;
466 *nr_entries = 0;
467 goto done;
468 }
469
470
471 for (i = 0; i < nr_move; i++) {
472 new->keys[i] = node->keys[nr_keep + i];
473 new->ptrs[i] = node->ptrs[nr_keep + i];
474
475 node->keys[nr_keep + i] = XFS_IEXT_KEY_INVALID;
476 node->ptrs[nr_keep + i] = NULL;
477 }
478
479 if (*pos >= nr_keep) {
480 *nodep = new;
481 *pos -= nr_keep;
482 *nr_entries = nr_move;
483 } else {
484 *nr_entries = nr_keep;
485 }
486 done:
487 for (; i < KEYS_PER_NODE; i++)
488 new->keys[i] = XFS_IEXT_KEY_INVALID;
489 return new;
490 }
491
492 static void
xfs_iext_insert_node(struct xfs_ifork * ifp,uint64_t offset,void * ptr,int level)493 xfs_iext_insert_node(
494 struct xfs_ifork *ifp,
495 uint64_t offset,
496 void *ptr,
497 int level)
498 {
499 struct xfs_iext_node *node, *new;
500 int i, pos, nr_entries;
501
502 again:
503 if (ifp->if_height < level)
504 xfs_iext_grow(ifp);
505
506 new = NULL;
507 node = xfs_iext_find_level(ifp, offset, level);
508 pos = xfs_iext_node_insert_pos(node, offset);
509 nr_entries = xfs_iext_node_nr_entries(node, pos);
510
511 ASSERT(pos >= nr_entries || xfs_iext_key_cmp(node, pos, offset) != 0);
512 ASSERT(nr_entries <= KEYS_PER_NODE);
513
514 if (nr_entries == KEYS_PER_NODE)
515 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 if (node != new && pos == 0 && nr_entries > 0)
522 xfs_iext_update_node(ifp, node->keys[0], offset, level, node);
523
524 for (i = nr_entries; i > pos; i--) {
525 node->keys[i] = node->keys[i - 1];
526 node->ptrs[i] = node->ptrs[i - 1];
527 }
528 node->keys[pos] = offset;
529 node->ptrs[pos] = ptr;
530
531 if (new) {
532 offset = new->keys[0];
533 ptr = new;
534 level++;
535 goto again;
536 }
537 }
538
539 static struct xfs_iext_leaf *
xfs_iext_split_leaf(struct xfs_iext_cursor * cur,int * nr_entries)540 xfs_iext_split_leaf(
541 struct xfs_iext_cursor *cur,
542 int *nr_entries)
543 {
544 struct xfs_iext_leaf *leaf = cur->leaf;
545 struct xfs_iext_leaf *new = kmem_zalloc(NODE_SIZE, KM_NOFS);
546 const int nr_move = RECS_PER_LEAF / 2;
547 int nr_keep = nr_move + (RECS_PER_LEAF & 1);
548 int i;
549
550 /* for sequential append operations just spill over into the new node */
551 if (cur->pos == RECS_PER_LEAF) {
552 cur->leaf = new;
553 cur->pos = 0;
554 *nr_entries = 0;
555 goto done;
556 }
557
558 for (i = 0; i < nr_move; i++) {
559 new->recs[i] = leaf->recs[nr_keep + i];
560 xfs_iext_rec_clear(&leaf->recs[nr_keep + i]);
561 }
562
563 if (cur->pos >= nr_keep) {
564 cur->leaf = new;
565 cur->pos -= nr_keep;
566 *nr_entries = nr_move;
567 } else {
568 *nr_entries = nr_keep;
569 }
570 done:
571 if (leaf->next)
572 leaf->next->prev = new;
573 new->next = leaf->next;
574 new->prev = leaf;
575 leaf->next = new;
576 return new;
577 }
578
579 static void
xfs_iext_alloc_root(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)580 xfs_iext_alloc_root(
581 struct xfs_ifork *ifp,
582 struct xfs_iext_cursor *cur)
583 {
584 ASSERT(ifp->if_bytes == 0);
585
586 ifp->if_data = kmem_zalloc(sizeof(struct xfs_iext_rec), KM_NOFS);
587 ifp->if_height = 1;
588
589 /* now that we have a node step into it */
590 cur->leaf = ifp->if_data;
591 cur->pos = 0;
592 }
593
594 static void
xfs_iext_realloc_root(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)595 xfs_iext_realloc_root(
596 struct xfs_ifork *ifp,
597 struct xfs_iext_cursor *cur)
598 {
599 int64_t new_size = ifp->if_bytes + sizeof(struct xfs_iext_rec);
600 void *new;
601
602 /* account for the prev/next pointers */
603 if (new_size / sizeof(struct xfs_iext_rec) == RECS_PER_LEAF)
604 new_size = NODE_SIZE;
605
606 new = krealloc(ifp->if_data, new_size, GFP_NOFS | __GFP_NOFAIL);
607 memset(new + ifp->if_bytes, 0, new_size - ifp->if_bytes);
608 ifp->if_data = new;
609 cur->leaf = new;
610 }
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 */
xfs_iext_inc_seq(struct xfs_ifork * ifp)619 static inline void xfs_iext_inc_seq(struct xfs_ifork *ifp)
620 {
621 WRITE_ONCE(ifp->if_seq, READ_ONCE(ifp->if_seq) + 1);
622 }
623
624 void
xfs_iext_insert_raw(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur,struct xfs_bmbt_irec * irec)625 xfs_iext_insert_raw(
626 struct xfs_ifork *ifp,
627 struct xfs_iext_cursor *cur,
628 struct xfs_bmbt_irec *irec)
629 {
630 xfs_fileoff_t offset = irec->br_startoff;
631 struct xfs_iext_leaf *new = NULL;
632 int nr_entries, i;
633
634 xfs_iext_inc_seq(ifp);
635
636 if (ifp->if_height == 0)
637 xfs_iext_alloc_root(ifp, cur);
638 else if (ifp->if_height == 1)
639 xfs_iext_realloc_root(ifp, cur);
640
641 nr_entries = xfs_iext_leaf_nr_entries(ifp, cur->leaf, cur->pos);
642 ASSERT(nr_entries <= RECS_PER_LEAF);
643 ASSERT(cur->pos >= nr_entries ||
644 xfs_iext_rec_cmp(cur_rec(cur), irec->br_startoff) != 0);
645
646 if (nr_entries == RECS_PER_LEAF)
647 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 if (cur->leaf != new && cur->pos == 0 && nr_entries > 0) {
654 xfs_iext_update_node(ifp, xfs_iext_leaf_key(cur->leaf, 0),
655 offset, 1, cur->leaf);
656 }
657
658 for (i = nr_entries; i > cur->pos; i--)
659 cur->leaf->recs[i] = cur->leaf->recs[i - 1];
660 xfs_iext_set(cur_rec(cur), irec);
661 ifp->if_bytes += sizeof(struct xfs_iext_rec);
662
663 if (new)
664 xfs_iext_insert_node(ifp, xfs_iext_leaf_key(new, 0), new, 2);
665 }
666
667 void
xfs_iext_insert(struct xfs_inode * ip,struct xfs_iext_cursor * cur,struct xfs_bmbt_irec * irec,int state)668 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 struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state);
675
676 xfs_iext_insert_raw(ifp, cur, irec);
677 trace_xfs_iext_insert(ip, cur, state, _RET_IP_);
678 }
679
680 static struct xfs_iext_node *
xfs_iext_rebalance_node(struct xfs_iext_node * parent,int * pos,struct xfs_iext_node * node,int nr_entries)681 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 if (nr_entries == 0)
693 return node;
694
695 if (*pos > 0) {
696 struct xfs_iext_node *prev = parent->ptrs[*pos - 1];
697 int nr_prev = xfs_iext_node_nr_entries(prev, 0), i;
698
699 if (nr_prev + nr_entries <= KEYS_PER_NODE) {
700 for (i = 0; i < nr_entries; i++) {
701 prev->keys[nr_prev + i] = node->keys[i];
702 prev->ptrs[nr_prev + i] = node->ptrs[i];
703 }
704 return node;
705 }
706 }
707
708 if (*pos + 1 < xfs_iext_node_nr_entries(parent, *pos)) {
709 struct xfs_iext_node *next = parent->ptrs[*pos + 1];
710 int nr_next = xfs_iext_node_nr_entries(next, 0), i;
711
712 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 for (i = 0; i < nr_next; i++) {
719 node->keys[nr_entries + i] = next->keys[i];
720 node->ptrs[nr_entries + i] = next->ptrs[i];
721 }
722
723 ++*pos;
724 return next;
725 }
726 }
727
728 return NULL;
729 }
730
731 static void
xfs_iext_remove_node(struct xfs_ifork * ifp,xfs_fileoff_t offset,void * victim)732 xfs_iext_remove_node(
733 struct xfs_ifork *ifp,
734 xfs_fileoff_t offset,
735 void *victim)
736 {
737 struct xfs_iext_node *node, *parent;
738 int level = 2, pos, nr_entries, i;
739
740 ASSERT(level <= ifp->if_height);
741 node = xfs_iext_find_level(ifp, offset, level);
742 pos = xfs_iext_node_pos(node, offset);
743 again:
744 ASSERT(node->ptrs[pos]);
745 ASSERT(node->ptrs[pos] == victim);
746 kmem_free(victim);
747
748 nr_entries = xfs_iext_node_nr_entries(node, pos) - 1;
749 offset = node->keys[0];
750 for (i = pos; i < nr_entries; i++) {
751 node->keys[i] = node->keys[i + 1];
752 node->ptrs[i] = node->ptrs[i + 1];
753 }
754 node->keys[nr_entries] = XFS_IEXT_KEY_INVALID;
755 node->ptrs[nr_entries] = NULL;
756
757 if (pos == 0 && nr_entries > 0) {
758 xfs_iext_update_node(ifp, offset, node->keys[0], level, node);
759 offset = node->keys[0];
760 }
761
762 if (nr_entries >= KEYS_PER_NODE / 2)
763 return;
764
765 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 level++;
772 parent = xfs_iext_find_level(ifp, offset, level);
773 pos = xfs_iext_node_pos(parent, offset);
774
775 ASSERT(pos != KEYS_PER_NODE);
776 ASSERT(parent->ptrs[pos] == node);
777
778 node = xfs_iext_rebalance_node(parent, &pos, node, nr_entries);
779 if (node) {
780 victim = node;
781 node = parent;
782 goto again;
783 }
784 } 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 ASSERT(node == ifp->if_data);
790 ifp->if_data = node->ptrs[0];
791 ifp->if_height--;
792 kmem_free(node);
793 }
794 }
795
796 static void
xfs_iext_rebalance_leaf(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur,struct xfs_iext_leaf * leaf,xfs_fileoff_t offset,int nr_entries)797 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 if (nr_entries == 0)
810 goto remove_node;
811
812 if (leaf->prev) {
813 int nr_prev = xfs_iext_leaf_nr_entries(ifp, leaf->prev, 0), i;
814
815 if (nr_prev + nr_entries <= RECS_PER_LEAF) {
816 for (i = 0; i < nr_entries; i++)
817 leaf->prev->recs[nr_prev + i] = leaf->recs[i];
818
819 if (cur->leaf == leaf) {
820 cur->leaf = leaf->prev;
821 cur->pos += nr_prev;
822 }
823 goto remove_node;
824 }
825 }
826
827 if (leaf->next) {
828 int nr_next = xfs_iext_leaf_nr_entries(ifp, leaf->next, 0), i;
829
830 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 for (i = 0; i < nr_next; i++) {
837 leaf->recs[nr_entries + i] =
838 leaf->next->recs[i];
839 }
840
841 if (cur->leaf == leaf->next) {
842 cur->leaf = leaf;
843 cur->pos += nr_entries;
844 }
845
846 offset = xfs_iext_leaf_key(leaf->next, 0);
847 leaf = leaf->next;
848 goto remove_node;
849 }
850 }
851
852 return;
853 remove_node:
854 if (leaf->prev)
855 leaf->prev->next = leaf->next;
856 if (leaf->next)
857 leaf->next->prev = leaf->prev;
858 xfs_iext_remove_node(ifp, offset, leaf);
859 }
860
861 static void
xfs_iext_free_last_leaf(struct xfs_ifork * ifp)862 xfs_iext_free_last_leaf(
863 struct xfs_ifork *ifp)
864 {
865 ifp->if_height--;
866 kmem_free(ifp->if_data);
867 ifp->if_data = NULL;
868 }
869
870 void
xfs_iext_remove(struct xfs_inode * ip,struct xfs_iext_cursor * cur,int state)871 xfs_iext_remove(
872 struct xfs_inode *ip,
873 struct xfs_iext_cursor *cur,
874 int state)
875 {
876 struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state);
877 struct xfs_iext_leaf *leaf = cur->leaf;
878 xfs_fileoff_t offset = xfs_iext_leaf_key(leaf, 0);
879 int i, nr_entries;
880
881 trace_xfs_iext_remove(ip, cur, state, _RET_IP_);
882
883 ASSERT(ifp->if_height > 0);
884 ASSERT(ifp->if_data != NULL);
885 ASSERT(xfs_iext_valid(ifp, cur));
886
887 xfs_iext_inc_seq(ifp);
888
889 nr_entries = xfs_iext_leaf_nr_entries(ifp, leaf, cur->pos) - 1;
890 for (i = cur->pos; i < nr_entries; i++)
891 leaf->recs[i] = leaf->recs[i + 1];
892 xfs_iext_rec_clear(&leaf->recs[nr_entries]);
893 ifp->if_bytes -= sizeof(struct xfs_iext_rec);
894
895 if (cur->pos == 0 && nr_entries > 0) {
896 xfs_iext_update_node(ifp, offset, xfs_iext_leaf_key(leaf, 0), 1,
897 leaf);
898 offset = xfs_iext_leaf_key(leaf, 0);
899 } else if (cur->pos == nr_entries) {
900 if (ifp->if_height > 1 && leaf->next)
901 cur->leaf = leaf->next;
902 else
903 cur->leaf = NULL;
904 cur->pos = 0;
905 }
906
907 if (nr_entries >= RECS_PER_LEAF / 2)
908 return;
909
910 if (ifp->if_height > 1)
911 xfs_iext_rebalance_leaf(ifp, cur, leaf, offset, nr_entries);
912 else if (nr_entries == 0)
913 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
xfs_iext_lookup_extent(struct xfs_inode * ip,struct xfs_ifork * ifp,xfs_fileoff_t offset,struct xfs_iext_cursor * cur,struct xfs_bmbt_irec * gotp)928 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 XFS_STATS_INC(ip->i_mount, xs_look_exlist);
936
937 cur->leaf = xfs_iext_find_level(ifp, offset, 1);
938 if (!cur->leaf) {
939 cur->pos = 0;
940 return false;
941 }
942
943 for (cur->pos = 0; cur->pos < xfs_iext_max_recs(ifp); cur->pos++) {
944 struct xfs_iext_rec *rec = cur_rec(cur);
945
946 if (xfs_iext_rec_is_empty(rec))
947 break;
948 if (xfs_iext_rec_cmp(rec, offset) >= 0)
949 goto found;
950 }
951
952 /* Try looking in the next node for an entry > offset */
953 if (ifp->if_height == 1 || !cur->leaf->next)
954 return false;
955 cur->leaf = cur->leaf->next;
956 cur->pos = 0;
957 if (!xfs_iext_valid(ifp, cur))
958 return false;
959 found:
960 xfs_iext_get(gotp, cur_rec(cur));
961 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
xfs_iext_lookup_extent_before(struct xfs_inode * ip,struct xfs_ifork * ifp,xfs_fileoff_t * end,struct xfs_iext_cursor * cur,struct xfs_bmbt_irec * gotp)969 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 if (xfs_iext_lookup_extent(ip, ifp, *end - 1, cur, gotp) &&
978 gotp->br_startoff <= *end - 1)
979 return true;
980 if (!xfs_iext_prev_extent(ifp, cur, gotp))
981 return false;
982 *end = gotp->br_startoff + gotp->br_blockcount;
983 return true;
984 }
985
986 void
xfs_iext_update_extent(struct xfs_inode * ip,int state,struct xfs_iext_cursor * cur,struct xfs_bmbt_irec * new)987 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 struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state);
994
995 xfs_iext_inc_seq(ifp);
996
997 if (cur->pos == 0) {
998 struct xfs_bmbt_irec old;
999
1000 xfs_iext_get(&old, cur_rec(cur));
1001 if (new->br_startoff != old.br_startoff) {
1002 xfs_iext_update_node(ifp, old.br_startoff,
1003 new->br_startoff, 1, cur->leaf);
1004 }
1005 }
1006
1007 trace_xfs_bmap_pre_update(ip, cur, state, _RET_IP_);
1008 xfs_iext_set(cur_rec(cur), new);
1009 trace_xfs_bmap_post_update(ip, cur, state, _RET_IP_);
1010 }
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
xfs_iext_get_extent(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur,struct xfs_bmbt_irec * gotp)1017 xfs_iext_get_extent(
1018 struct xfs_ifork *ifp,
1019 struct xfs_iext_cursor *cur,
1020 struct xfs_bmbt_irec *gotp)
1021 {
1022 if (!xfs_iext_valid(ifp, cur))
1023 return false;
1024 xfs_iext_get(gotp, cur_rec(cur));
1025 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
xfs_iext_destroy_node(struct xfs_iext_node * node,int level)1033 xfs_iext_destroy_node(
1034 struct xfs_iext_node *node,
1035 int level)
1036 {
1037 int i;
1038
1039 if (level > 1) {
1040 for (i = 0; i < KEYS_PER_NODE; i++) {
1041 if (node->keys[i] == XFS_IEXT_KEY_INVALID)
1042 break;
1043 xfs_iext_destroy_node(node->ptrs[i], level - 1);
1044 }
1045 }
1046
1047 kmem_free(node);
1048 }
1049
1050 void
xfs_iext_destroy(struct xfs_ifork * ifp)1051 xfs_iext_destroy(
1052 struct xfs_ifork *ifp)
1053 {
1054 xfs_iext_destroy_node(ifp->if_data, ifp->if_height);
1055
1056 ifp->if_bytes = 0;
1057 ifp->if_height = 0;
1058 ifp->if_data = NULL;
1059 }
1060