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