]>
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" | |
b37d753d CH |
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 | return rec->hi == 0; | |
44 | } | |
45 | ||
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 | |
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 | |
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 | ||
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 | ||
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 | ||
140 | static inline struct xfs_iext_rec *cur_rec(struct xfs_iext_cursor *cur) | |
141 | { | |
142 | return &cur->leaf->recs[cur->pos]; | |
143 | } | |
144 | ||
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 * | |
158 | xfs_iext_find_first_leaf( | |
159 | struct xfs_ifork *ifp) | |
160 | { | |
161 | struct xfs_iext_node *node = ifp->if_u1.if_root; | |
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 * | |
176 | xfs_iext_find_last_leaf( | |
177 | struct xfs_ifork *ifp) | |
178 | { | |
179 | struct xfs_iext_node *node = ifp->if_u1.if_root; | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 * | |
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_u1.if_root; | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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_u1.if_root; | |
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_u1.if_root; | |
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_u1.if_root = node; | |
422 | ifp->if_height++; | |
423 | } | |
424 | ||
425 | static void | |
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_u1.if_root; | |
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 * | |
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 | |
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 | ||
ba0bf2c6 CH |
517 | /* |
518 | * Update the pointers in higher levels if the first entry changes | |
519 | * in an existing node. | |
520 | */ | |
b37d753d CH |
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 * | |
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 */ | |
fd4c3ba5 | 551 | if (cur->pos == RECS_PER_LEAF) { |
b37d753d CH |
552 | cur->leaf = new; |
553 | cur->pos = 0; | |
554 | *nr_entries = 0; | |
555 | goto done; | |
556 | } | |
557 | ||
b37d753d CH |
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 | |
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_u1.if_root = 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_u1.if_root; | |
591 | cur->pos = 0; | |
592 | } | |
593 | ||
594 | static void | |
595 | xfs_iext_realloc_root( | |
596 | struct xfs_ifork *ifp, | |
597 | struct xfs_iext_cursor *cur) | |
598 | { | |
599 | size_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 = kmem_realloc(ifp->if_u1.if_root, new_size, KM_NOFS); | |
607 | memset(new + ifp->if_bytes, 0, new_size - ifp->if_bytes); | |
608 | ifp->if_u1.if_root = new; | |
609 | cur->leaf = new; | |
610 | } | |
611 | ||
c02e0341 | 612 | /* |
a2fa97f1 BF |
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. | |
c02e0341 CH |
618 | */ |
619 | static inline void xfs_iext_inc_seq(struct xfs_ifork *ifp, int state) | |
620 | { | |
a2fa97f1 | 621 | WRITE_ONCE(ifp->if_seq, READ_ONCE(ifp->if_seq) + 1); |
c02e0341 CH |
622 | } |
623 | ||
26a75f67 CH |
624 | void |
625 | xfs_iext_insert( | |
626 | struct xfs_inode *ip, | |
b37d753d | 627 | struct xfs_iext_cursor *cur, |
26a75f67 CH |
628 | struct xfs_bmbt_irec *irec, |
629 | int state) | |
b37d753d | 630 | { |
26a75f67 | 631 | struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state); |
b37d753d CH |
632 | xfs_fileoff_t offset = irec->br_startoff; |
633 | struct xfs_iext_leaf *new = NULL; | |
634 | int nr_entries, i; | |
635 | ||
c02e0341 | 636 | xfs_iext_inc_seq(ifp, state); |
68fc8c43 | 637 | |
b37d753d CH |
638 | if (ifp->if_height == 0) |
639 | xfs_iext_alloc_root(ifp, cur); | |
640 | else if (ifp->if_height == 1) | |
641 | xfs_iext_realloc_root(ifp, cur); | |
642 | ||
643 | nr_entries = xfs_iext_leaf_nr_entries(ifp, cur->leaf, cur->pos); | |
644 | ASSERT(nr_entries <= RECS_PER_LEAF); | |
645 | ASSERT(cur->pos >= nr_entries || | |
646 | xfs_iext_rec_cmp(cur_rec(cur), irec->br_startoff) != 0); | |
647 | ||
648 | if (nr_entries == RECS_PER_LEAF) | |
649 | new = xfs_iext_split_leaf(cur, &nr_entries); | |
650 | ||
ba0bf2c6 CH |
651 | /* |
652 | * Update the pointers in higher levels if the first entry changes | |
653 | * in an existing node. | |
654 | */ | |
b37d753d CH |
655 | if (cur->leaf != new && cur->pos == 0 && nr_entries > 0) { |
656 | xfs_iext_update_node(ifp, xfs_iext_leaf_key(cur->leaf, 0), | |
657 | offset, 1, cur->leaf); | |
658 | } | |
659 | ||
660 | for (i = nr_entries; i > cur->pos; i--) | |
661 | cur->leaf->recs[i] = cur->leaf->recs[i - 1]; | |
662 | xfs_iext_set(cur_rec(cur), irec); | |
663 | ifp->if_bytes += sizeof(struct xfs_iext_rec); | |
664 | ||
6428e6c7 DW |
665 | trace_xfs_iext_insert(ip, cur, state, _RET_IP_); |
666 | ||
b37d753d CH |
667 | if (new) |
668 | xfs_iext_insert_node(ifp, xfs_iext_leaf_key(new, 0), new, 2); | |
669 | } | |
670 | ||
b37d753d CH |
671 | static struct xfs_iext_node * |
672 | xfs_iext_rebalance_node( | |
673 | struct xfs_iext_node *parent, | |
674 | int *pos, | |
675 | struct xfs_iext_node *node, | |
676 | int nr_entries) | |
677 | { | |
373c077a CH |
678 | /* |
679 | * If the neighbouring nodes are completely full, or have different | |
680 | * parents, we might never be able to merge our node, and will only | |
681 | * delete it once the number of entries hits zero. | |
682 | */ | |
b37d753d CH |
683 | if (nr_entries == 0) |
684 | return node; | |
685 | ||
686 | if (*pos > 0) { | |
687 | struct xfs_iext_node *prev = parent->ptrs[*pos - 1]; | |
688 | int nr_prev = xfs_iext_node_nr_entries(prev, 0), i; | |
689 | ||
690 | if (nr_prev + nr_entries <= KEYS_PER_NODE) { | |
691 | for (i = 0; i < nr_entries; i++) { | |
692 | prev->keys[nr_prev + i] = node->keys[i]; | |
693 | prev->ptrs[nr_prev + i] = node->ptrs[i]; | |
694 | } | |
695 | return node; | |
696 | } | |
697 | } | |
698 | ||
699 | if (*pos + 1 < xfs_iext_node_nr_entries(parent, *pos)) { | |
700 | struct xfs_iext_node *next = parent->ptrs[*pos + 1]; | |
701 | int nr_next = xfs_iext_node_nr_entries(next, 0), i; | |
702 | ||
703 | if (nr_entries + nr_next <= KEYS_PER_NODE) { | |
373c077a CH |
704 | /* |
705 | * Merge the next node into this node so that we don't | |
706 | * have to do an additional update of the keys in the | |
707 | * higher levels. | |
708 | */ | |
b37d753d CH |
709 | for (i = 0; i < nr_next; i++) { |
710 | node->keys[nr_entries + i] = next->keys[i]; | |
711 | node->ptrs[nr_entries + i] = next->ptrs[i]; | |
712 | } | |
713 | ||
714 | ++*pos; | |
715 | return next; | |
716 | } | |
717 | } | |
718 | ||
719 | return NULL; | |
720 | } | |
721 | ||
722 | static void | |
723 | xfs_iext_remove_node( | |
724 | struct xfs_ifork *ifp, | |
725 | xfs_fileoff_t offset, | |
726 | void *victim) | |
727 | { | |
728 | struct xfs_iext_node *node, *parent; | |
729 | int level = 2, pos, nr_entries, i; | |
730 | ||
731 | ASSERT(level <= ifp->if_height); | |
732 | node = xfs_iext_find_level(ifp, offset, level); | |
733 | pos = xfs_iext_node_pos(node, offset); | |
734 | again: | |
735 | ASSERT(node->ptrs[pos]); | |
736 | ASSERT(node->ptrs[pos] == victim); | |
737 | kmem_free(victim); | |
738 | ||
739 | nr_entries = xfs_iext_node_nr_entries(node, pos) - 1; | |
740 | offset = node->keys[0]; | |
741 | for (i = pos; i < nr_entries; i++) { | |
742 | node->keys[i] = node->keys[i + 1]; | |
743 | node->ptrs[i] = node->ptrs[i + 1]; | |
744 | } | |
745 | node->keys[nr_entries] = XFS_IEXT_KEY_INVALID; | |
746 | node->ptrs[nr_entries] = NULL; | |
747 | ||
748 | if (pos == 0 && nr_entries > 0) { | |
c45b87cc | 749 | xfs_iext_update_node(ifp, offset, node->keys[0], level, node); |
b37d753d CH |
750 | offset = node->keys[0]; |
751 | } | |
752 | ||
753 | if (nr_entries >= KEYS_PER_NODE / 2) | |
754 | return; | |
755 | ||
756 | if (level < ifp->if_height) { | |
373c077a CH |
757 | /* |
758 | * If we aren't at the root yet try to find a neighbour node to | |
759 | * merge with (or delete the node if it is empty), and then | |
760 | * recurse up to the next level. | |
761 | */ | |
b37d753d CH |
762 | level++; |
763 | parent = xfs_iext_find_level(ifp, offset, level); | |
764 | pos = xfs_iext_node_pos(parent, offset); | |
765 | ||
766 | ASSERT(pos != KEYS_PER_NODE); | |
767 | ASSERT(parent->ptrs[pos] == node); | |
768 | ||
769 | node = xfs_iext_rebalance_node(parent, &pos, node, nr_entries); | |
770 | if (node) { | |
b37d753d CH |
771 | victim = node; |
772 | node = parent; | |
773 | goto again; | |
774 | } | |
775 | } else if (nr_entries == 1) { | |
373c077a CH |
776 | /* |
777 | * If we are at the root and only one entry is left we can just | |
778 | * free this node and update the root pointer. | |
779 | */ | |
b37d753d CH |
780 | ASSERT(node == ifp->if_u1.if_root); |
781 | ifp->if_u1.if_root = node->ptrs[0]; | |
782 | ifp->if_height--; | |
783 | kmem_free(node); | |
784 | } | |
785 | } | |
786 | ||
787 | static void | |
788 | xfs_iext_rebalance_leaf( | |
789 | struct xfs_ifork *ifp, | |
790 | struct xfs_iext_cursor *cur, | |
791 | struct xfs_iext_leaf *leaf, | |
792 | xfs_fileoff_t offset, | |
546f3832 | 793 | int nr_entries) |
b37d753d | 794 | { |
546f3832 CH |
795 | /* |
796 | * If the neighbouring nodes are completely full we might never be able | |
797 | * to merge our node, and will only delete it once the number of | |
798 | * entries hits zero. | |
799 | */ | |
800 | if (nr_entries == 0) | |
801 | goto remove_node; | |
802 | ||
b37d753d CH |
803 | if (leaf->prev) { |
804 | int nr_prev = xfs_iext_leaf_nr_entries(ifp, leaf->prev, 0), i; | |
805 | ||
546f3832 CH |
806 | if (nr_prev + nr_entries <= RECS_PER_LEAF) { |
807 | for (i = 0; i < nr_entries; i++) | |
b37d753d CH |
808 | leaf->prev->recs[nr_prev + i] = leaf->recs[i]; |
809 | ||
810 | if (cur->leaf == leaf) { | |
811 | cur->leaf = leaf->prev; | |
812 | cur->pos += nr_prev; | |
813 | } | |
814 | goto remove_node; | |
815 | } | |
816 | } | |
817 | ||
818 | if (leaf->next) { | |
819 | int nr_next = xfs_iext_leaf_nr_entries(ifp, leaf->next, 0), i; | |
820 | ||
546f3832 | 821 | if (nr_entries + nr_next <= RECS_PER_LEAF) { |
373c077a CH |
822 | /* |
823 | * Merge the next node into this node so that we don't | |
824 | * have to do an additional update of the keys in the | |
825 | * higher levels. | |
826 | */ | |
546f3832 CH |
827 | for (i = 0; i < nr_next; i++) { |
828 | leaf->recs[nr_entries + i] = | |
829 | leaf->next->recs[i]; | |
830 | } | |
b37d753d CH |
831 | |
832 | if (cur->leaf == leaf->next) { | |
833 | cur->leaf = leaf; | |
546f3832 | 834 | cur->pos += nr_entries; |
b37d753d CH |
835 | } |
836 | ||
837 | offset = xfs_iext_leaf_key(leaf->next, 0); | |
838 | leaf = leaf->next; | |
839 | goto remove_node; | |
840 | } | |
841 | } | |
842 | ||
843 | return; | |
844 | remove_node: | |
845 | if (leaf->prev) | |
846 | leaf->prev->next = leaf->next; | |
847 | if (leaf->next) | |
848 | leaf->next->prev = leaf->prev; | |
849 | xfs_iext_remove_node(ifp, offset, leaf); | |
850 | } | |
851 | ||
852 | static void | |
853 | xfs_iext_free_last_leaf( | |
854 | struct xfs_ifork *ifp) | |
855 | { | |
b37d753d CH |
856 | ifp->if_height--; |
857 | kmem_free(ifp->if_u1.if_root); | |
c822b63d | 858 | ifp->if_u1.if_root = NULL; |
b37d753d CH |
859 | } |
860 | ||
cf455a62 CH |
861 | void |
862 | xfs_iext_remove( | |
863 | struct xfs_inode *ip, | |
864 | struct xfs_iext_cursor *cur, | |
865 | int state) | |
b37d753d | 866 | { |
cf455a62 | 867 | struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state); |
b37d753d CH |
868 | struct xfs_iext_leaf *leaf = cur->leaf; |
869 | xfs_fileoff_t offset = xfs_iext_leaf_key(leaf, 0); | |
870 | int i, nr_entries; | |
871 | ||
cf455a62 CH |
872 | trace_xfs_iext_remove(ip, cur, state, _RET_IP_); |
873 | ||
b37d753d CH |
874 | ASSERT(ifp->if_height > 0); |
875 | ASSERT(ifp->if_u1.if_root != NULL); | |
876 | ASSERT(xfs_iext_valid(ifp, cur)); | |
877 | ||
c02e0341 | 878 | xfs_iext_inc_seq(ifp, state); |
68fc8c43 | 879 | |
b37d753d CH |
880 | nr_entries = xfs_iext_leaf_nr_entries(ifp, leaf, cur->pos) - 1; |
881 | for (i = cur->pos; i < nr_entries; i++) | |
882 | leaf->recs[i] = leaf->recs[i + 1]; | |
883 | xfs_iext_rec_clear(&leaf->recs[nr_entries]); | |
884 | ifp->if_bytes -= sizeof(struct xfs_iext_rec); | |
885 | ||
886 | if (cur->pos == 0 && nr_entries > 0) { | |
887 | xfs_iext_update_node(ifp, offset, xfs_iext_leaf_key(leaf, 0), 1, | |
888 | leaf); | |
889 | offset = xfs_iext_leaf_key(leaf, 0); | |
890 | } else if (cur->pos == nr_entries) { | |
891 | if (ifp->if_height > 1 && leaf->next) | |
892 | cur->leaf = leaf->next; | |
893 | else | |
894 | cur->leaf = NULL; | |
895 | cur->pos = 0; | |
896 | } | |
897 | ||
898 | if (nr_entries >= RECS_PER_LEAF / 2) | |
899 | return; | |
900 | ||
901 | if (ifp->if_height > 1) | |
902 | xfs_iext_rebalance_leaf(ifp, cur, leaf, offset, nr_entries); | |
903 | else if (nr_entries == 0) | |
904 | xfs_iext_free_last_leaf(ifp); | |
905 | } | |
906 | ||
b37d753d CH |
907 | /* |
908 | * Lookup the extent covering bno. | |
909 | * | |
910 | * If there is an extent covering bno return the extent index, and store the | |
911 | * expanded extent structure in *gotp, and the extent cursor in *cur. | |
912 | * If there is no extent covering bno, but there is an extent after it (e.g. | |
913 | * it lies in a hole) return that extent in *gotp and its cursor in *cur | |
914 | * instead. | |
915 | * If bno is beyond the last extent return false, and return an invalid | |
916 | * cursor value. | |
917 | */ | |
918 | bool | |
919 | xfs_iext_lookup_extent( | |
920 | struct xfs_inode *ip, | |
921 | struct xfs_ifork *ifp, | |
922 | xfs_fileoff_t offset, | |
923 | struct xfs_iext_cursor *cur, | |
924 | struct xfs_bmbt_irec *gotp) | |
925 | { | |
926 | XFS_STATS_INC(ip->i_mount, xs_look_exlist); | |
927 | ||
928 | cur->leaf = xfs_iext_find_level(ifp, offset, 1); | |
929 | if (!cur->leaf) { | |
930 | cur->pos = 0; | |
931 | return false; | |
932 | } | |
933 | ||
934 | for (cur->pos = 0; cur->pos < xfs_iext_max_recs(ifp); cur->pos++) { | |
935 | struct xfs_iext_rec *rec = cur_rec(cur); | |
936 | ||
937 | if (xfs_iext_rec_is_empty(rec)) | |
938 | break; | |
939 | if (xfs_iext_rec_cmp(rec, offset) >= 0) | |
940 | goto found; | |
941 | } | |
942 | ||
943 | /* Try looking in the next node for an entry > offset */ | |
944 | if (ifp->if_height == 1 || !cur->leaf->next) | |
945 | return false; | |
946 | cur->leaf = cur->leaf->next; | |
947 | cur->pos = 0; | |
948 | if (!xfs_iext_valid(ifp, cur)) | |
949 | return false; | |
950 | found: | |
951 | xfs_iext_get(gotp, cur_rec(cur)); | |
952 | return true; | |
953 | } | |
954 | ||
955 | /* | |
956 | * Returns the last extent before end, and if this extent doesn't cover | |
957 | * end, update end to the end of the extent. | |
958 | */ | |
959 | bool | |
960 | xfs_iext_lookup_extent_before( | |
961 | struct xfs_inode *ip, | |
962 | struct xfs_ifork *ifp, | |
963 | xfs_fileoff_t *end, | |
964 | struct xfs_iext_cursor *cur, | |
965 | struct xfs_bmbt_irec *gotp) | |
966 | { | |
967 | /* could be optimized to not even look up the next on a match.. */ | |
968 | if (xfs_iext_lookup_extent(ip, ifp, *end - 1, cur, gotp) && | |
969 | gotp->br_startoff <= *end - 1) | |
970 | return true; | |
971 | if (!xfs_iext_prev_extent(ifp, cur, gotp)) | |
972 | return false; | |
973 | *end = gotp->br_startoff + gotp->br_blockcount; | |
974 | return true; | |
975 | } | |
976 | ||
977 | void | |
978 | xfs_iext_update_extent( | |
979 | struct xfs_inode *ip, | |
980 | int state, | |
981 | struct xfs_iext_cursor *cur, | |
982 | struct xfs_bmbt_irec *new) | |
983 | { | |
984 | struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state); | |
985 | ||
c02e0341 | 986 | xfs_iext_inc_seq(ifp, state); |
68fc8c43 | 987 | |
b37d753d CH |
988 | if (cur->pos == 0) { |
989 | struct xfs_bmbt_irec old; | |
990 | ||
991 | xfs_iext_get(&old, cur_rec(cur)); | |
992 | if (new->br_startoff != old.br_startoff) { | |
993 | xfs_iext_update_node(ifp, old.br_startoff, | |
994 | new->br_startoff, 1, cur->leaf); | |
995 | } | |
996 | } | |
997 | ||
998 | trace_xfs_bmap_pre_update(ip, cur, state, _RET_IP_); | |
999 | xfs_iext_set(cur_rec(cur), new); | |
1000 | trace_xfs_bmap_post_update(ip, cur, state, _RET_IP_); | |
1001 | } | |
1002 | ||
1003 | /* | |
1004 | * Return true if the cursor points at an extent and return the extent structure | |
1005 | * in gotp. Else return false. | |
1006 | */ | |
1007 | bool | |
1008 | xfs_iext_get_extent( | |
1009 | struct xfs_ifork *ifp, | |
1010 | struct xfs_iext_cursor *cur, | |
1011 | struct xfs_bmbt_irec *gotp) | |
1012 | { | |
1013 | if (!xfs_iext_valid(ifp, cur)) | |
1014 | return false; | |
1015 | xfs_iext_get(gotp, cur_rec(cur)); | |
1016 | return true; | |
1017 | } | |
1018 | ||
1019 | /* | |
1020 | * This is a recursive function, because of that we need to be extremely | |
1021 | * careful with stack usage. | |
1022 | */ | |
1023 | static void | |
1024 | xfs_iext_destroy_node( | |
1025 | struct xfs_iext_node *node, | |
1026 | int level) | |
1027 | { | |
1028 | int i; | |
1029 | ||
1030 | if (level > 1) { | |
1031 | for (i = 0; i < KEYS_PER_NODE; i++) { | |
1032 | if (node->keys[i] == XFS_IEXT_KEY_INVALID) | |
1033 | break; | |
1034 | xfs_iext_destroy_node(node->ptrs[i], level - 1); | |
1035 | } | |
1036 | } | |
1037 | ||
1038 | kmem_free(node); | |
1039 | } | |
1040 | ||
1041 | void | |
1042 | xfs_iext_destroy( | |
1043 | struct xfs_ifork *ifp) | |
1044 | { | |
1045 | xfs_iext_destroy_node(ifp->if_u1.if_root, ifp->if_height); | |
1046 | ||
1047 | ifp->if_bytes = 0; | |
1048 | ifp->if_height = 0; | |
1049 | ifp->if_u1.if_root = NULL; | |
1050 | } |