]>
Commit | Line | Data |
---|---|---|
2bd0ea18 | 1 | /* |
da23017d NS |
2 | * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc. |
3 | * All Rights Reserved. | |
dfc130f3 | 4 | * |
da23017d NS |
5 | * This program is free software; you can redistribute it and/or |
6 | * modify it under the terms of the GNU General Public License as | |
2bd0ea18 | 7 | * published by the Free Software Foundation. |
dfc130f3 | 8 | * |
da23017d NS |
9 | * This program is distributed in the hope that it would be useful, |
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
12 | * GNU General Public License for more details. | |
dfc130f3 | 13 | * |
da23017d NS |
14 | * You should have received a copy of the GNU General Public License |
15 | * along with this program; if not, write the Free Software Foundation, | |
16 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |
2bd0ea18 NS |
17 | */ |
18 | ||
19 | #include <libxfs.h> | |
20 | #include "avl.h" | |
21 | #include "globals.h" | |
22 | #include "incore.h" | |
23 | #include "agheader.h" | |
24 | #include "protos.h" | |
25 | #include "err_protos.h" | |
26 | #include "avl64.h" | |
27 | #define ALLOC_NUM_EXTS 100 | |
28 | ||
29 | /* | |
30 | * paranoia -- account for any weird padding, 64/32-bit alignment, etc. | |
31 | */ | |
32 | typedef struct extent_alloc_rec { | |
33 | ba_rec_t alloc_rec; | |
34 | extent_tree_node_t extents[ALLOC_NUM_EXTS]; | |
35 | } extent_alloc_rec_t; | |
36 | ||
37 | typedef struct rt_extent_alloc_rec { | |
38 | ba_rec_t alloc_rec; | |
39 | rt_extent_tree_node_t extents[ALLOC_NUM_EXTS]; | |
40 | } rt_extent_alloc_rec_t; | |
41 | ||
42 | /* | |
43 | * note: there are 4 sets of incore things handled here: | |
44 | * block bitmaps, extent trees, uncertain inode list, | |
45 | * and inode tree. The tree-based code uses the AVL | |
46 | * tree package used by the IRIX kernel VM code | |
47 | * (sys/avl.h). The inode list code uses the same records | |
48 | * as the inode tree code for convenience. The bitmaps | |
49 | * and bitmap operators are mostly macros defined in incore.h. | |
50 | * There are one of everything per AG except for extent | |
51 | * trees. There's one duplicate extent tree, one bno and | |
52 | * one bcnt extent tree per AG. Not all of the above exist | |
53 | * through all phases. The duplicate extent tree gets trashed | |
54 | * at the end of phase 4. The bno/bcnt trees don't appear until | |
55 | * phase 5. The uncertain inode list goes away at the end of | |
56 | * phase 3. The inode tree and bno/bnct trees go away after phase 5. | |
57 | */ | |
58 | typedef struct ext_flist_s { | |
59 | extent_tree_node_t *list; | |
60 | int cnt; | |
61 | } ext_flist_t; | |
62 | ||
63 | static ext_flist_t ext_flist; | |
64 | ||
65 | typedef struct rt_ext_flist_s { | |
66 | rt_extent_tree_node_t *list; | |
67 | int cnt; | |
68 | } rt_ext_flist_t; | |
69 | ||
70 | static rt_ext_flist_t rt_ext_flist; | |
71 | ||
72 | static avl64tree_desc_t *rt_ext_tree_ptr; /* dup extent tree for rt */ | |
73 | ||
1e77098c | 74 | avltree_desc_t **extent_tree_ptrs; /* array of extent tree ptrs */ |
2bd0ea18 NS |
75 | /* one per ag for dups */ |
76 | static avltree_desc_t **extent_bno_ptrs; /* | |
77 | * array of extent tree ptrs | |
78 | * one per ag for free extents | |
79 | * sorted by starting block | |
80 | * number | |
81 | */ | |
82 | static avltree_desc_t **extent_bcnt_ptrs; /* | |
83 | * array of extent tree ptrs | |
84 | * one per ag for free extents | |
85 | * sorted by size | |
86 | */ | |
87 | ||
88 | /* | |
89 | * list of allocated "blocks" for easy freeing later | |
90 | */ | |
91 | static ba_rec_t *ba_list; | |
92 | static ba_rec_t *rt_ba_list; | |
93 | ||
94 | /* | |
95 | * extent tree stuff is avl trees of duplicate extents, | |
96 | * sorted in order by block number. there is one tree per ag. | |
97 | */ | |
98 | ||
99 | static extent_tree_node_t * | |
100 | mk_extent_tree_nodes(xfs_agblock_t new_startblock, | |
101 | xfs_extlen_t new_blockcount, extent_state_t new_state) | |
102 | { | |
103 | int i; | |
104 | extent_tree_node_t *new; | |
105 | extent_alloc_rec_t *rec; | |
106 | ||
107 | if (ext_flist.cnt == 0) { | |
108 | ASSERT(ext_flist.list == NULL); | |
109 | ||
110 | if ((rec = malloc(sizeof(extent_alloc_rec_t))) == NULL) | |
507f4e33 NS |
111 | do_error( |
112 | _("couldn't allocate new extent descriptors.\n")); | |
2bd0ea18 NS |
113 | |
114 | record_allocation(&rec->alloc_rec, ba_list); | |
115 | ||
116 | new = &rec->extents[0]; | |
117 | ||
118 | for (i = 0; i < ALLOC_NUM_EXTS; i++) { | |
119 | new->avl_node.avl_nextino = (avlnode_t *) | |
120 | ext_flist.list; | |
121 | ext_flist.list = new; | |
122 | ext_flist.cnt++; | |
123 | new++; | |
124 | } | |
125 | } | |
126 | ||
127 | ASSERT(ext_flist.list != NULL); | |
128 | ||
129 | new = ext_flist.list; | |
130 | ext_flist.list = (extent_tree_node_t *) new->avl_node.avl_nextino; | |
131 | ext_flist.cnt--; | |
132 | new->avl_node.avl_nextino = NULL; | |
133 | ||
134 | /* initialize node */ | |
135 | ||
136 | new->ex_startblock = new_startblock; | |
137 | new->ex_blockcount = new_blockcount; | |
138 | new->ex_state = new_state; | |
139 | new->next = NULL; | |
140 | ||
141 | return(new); | |
142 | } | |
143 | ||
144 | void | |
145 | release_extent_tree_node(extent_tree_node_t *node) | |
146 | { | |
147 | node->avl_node.avl_nextino = (avlnode_t *) ext_flist.list; | |
148 | ext_flist.list = node; | |
149 | ext_flist.cnt++; | |
150 | ||
151 | return; | |
152 | } | |
153 | ||
154 | /* | |
155 | * routines to recycle all nodes in a tree. it walks the tree | |
156 | * and puts all nodes back on the free list so the nodes can be | |
157 | * reused. the duplicate and bno/bcnt extent trees for each AG | |
158 | * are recycled after they're no longer needed to save memory | |
159 | */ | |
160 | void | |
161 | release_extent_tree(avltree_desc_t *tree) | |
162 | { | |
163 | extent_tree_node_t *ext; | |
164 | extent_tree_node_t *tmp; | |
165 | extent_tree_node_t *lext; | |
166 | extent_tree_node_t *ltmp; | |
167 | ||
168 | if (tree->avl_firstino == NULL) | |
169 | return; | |
170 | ||
171 | ext = (extent_tree_node_t *) tree->avl_firstino; | |
172 | ||
173 | while (ext != NULL) { | |
174 | tmp = (extent_tree_node_t *) ext->avl_node.avl_nextino; | |
175 | ||
176 | /* | |
177 | * ext->next is guaranteed to be set only in bcnt trees | |
178 | */ | |
179 | if (ext->next != NULL) { | |
180 | lext = ext->next; | |
181 | while (lext != NULL) { | |
182 | ltmp = lext->next; | |
183 | release_extent_tree_node(lext); | |
184 | lext = ltmp; | |
185 | } | |
186 | } | |
187 | ||
188 | release_extent_tree_node(ext); | |
189 | ext = tmp; | |
190 | } | |
191 | ||
192 | tree->avl_root = tree->avl_firstino = NULL; | |
193 | ||
194 | return; | |
195 | } | |
196 | ||
197 | /* | |
198 | * top-level (visible) routines | |
199 | */ | |
200 | void | |
201 | release_dup_extent_tree(xfs_agnumber_t agno) | |
202 | { | |
203 | release_extent_tree(extent_tree_ptrs[agno]); | |
204 | ||
205 | return; | |
206 | } | |
207 | ||
208 | void | |
209 | release_agbno_extent_tree(xfs_agnumber_t agno) | |
210 | { | |
211 | release_extent_tree(extent_bno_ptrs[agno]); | |
212 | ||
213 | return; | |
214 | } | |
215 | ||
216 | void | |
217 | release_agbcnt_extent_tree(xfs_agnumber_t agno) | |
218 | { | |
219 | release_extent_tree(extent_bcnt_ptrs[agno]); | |
220 | ||
221 | return; | |
222 | } | |
223 | ||
224 | /* | |
225 | * the next 4 routines manage the trees of free extents -- 2 trees | |
226 | * per AG. The first tree is sorted by block number. The second | |
227 | * tree is sorted by extent size. This is the bno tree. | |
228 | */ | |
229 | void | |
230 | add_bno_extent(xfs_agnumber_t agno, xfs_agblock_t startblock, | |
231 | xfs_extlen_t blockcount) | |
232 | { | |
233 | extent_tree_node_t *ext; | |
234 | ||
235 | ASSERT(extent_bno_ptrs != NULL); | |
236 | ASSERT(extent_bno_ptrs[agno] != NULL); | |
237 | ||
238 | ext = mk_extent_tree_nodes(startblock, blockcount, XR_E_FREE); | |
239 | ||
240 | if (avl_insert(extent_bno_ptrs[agno], (avlnode_t *) ext) == NULL) { | |
507f4e33 | 241 | do_error(_("duplicate bno extent range\n")); |
2bd0ea18 NS |
242 | } |
243 | } | |
244 | ||
245 | extent_tree_node_t * | |
246 | findfirst_bno_extent(xfs_agnumber_t agno) | |
247 | { | |
248 | ASSERT(extent_bno_ptrs != NULL); | |
249 | ASSERT(extent_bno_ptrs[agno] != NULL); | |
250 | ||
251 | return((extent_tree_node_t *) extent_bno_ptrs[agno]->avl_firstino); | |
252 | } | |
253 | ||
254 | extent_tree_node_t * | |
255 | find_bno_extent(xfs_agnumber_t agno, xfs_agblock_t startblock) | |
256 | { | |
257 | ASSERT(extent_bno_ptrs != NULL); | |
258 | ASSERT(extent_bno_ptrs[agno] != NULL); | |
259 | ||
260 | return((extent_tree_node_t *) avl_find(extent_bno_ptrs[agno], | |
261 | startblock)); | |
262 | } | |
263 | ||
264 | /* | |
265 | * delete a node that's in the tree (pointer obtained by a find routine) | |
266 | */ | |
267 | void | |
268 | get_bno_extent(xfs_agnumber_t agno, extent_tree_node_t *ext) | |
269 | { | |
270 | ASSERT(extent_bno_ptrs != NULL); | |
271 | ASSERT(extent_bno_ptrs[agno] != NULL); | |
272 | ||
273 | avl_delete(extent_bno_ptrs[agno], &ext->avl_node); | |
274 | ||
275 | return; | |
276 | } | |
277 | ||
278 | /* | |
279 | * normalizing constant for bcnt size -> address conversion (see avl ops) | |
280 | * used by the AVL tree code to convert sizes and must be used when | |
281 | * doing an AVL search in the tree (e.g. avl_findrange(s)) | |
282 | */ | |
283 | #define MAXBCNT 0xFFFFFFFF | |
284 | #define BCNT_ADDR(cnt) ((unsigned int) MAXBCNT - (cnt)) | |
285 | ||
286 | /* | |
287 | * the next 4 routines manage the trees of free extents -- 2 trees | |
288 | * per AG. The first tree is sorted by block number. The second | |
289 | * tree is sorted by extent size. This is the bcnt tree. | |
290 | */ | |
291 | void | |
292 | add_bcnt_extent(xfs_agnumber_t agno, xfs_agblock_t startblock, | |
293 | xfs_extlen_t blockcount) | |
294 | { | |
295 | extent_tree_node_t *ext, *prev, *current, *top; | |
296 | xfs_agblock_t tmp_startblock; | |
297 | xfs_extlen_t tmp_blockcount; | |
298 | extent_state_t tmp_state; | |
299 | ||
300 | ASSERT(extent_bcnt_ptrs != NULL); | |
301 | ASSERT(extent_bcnt_ptrs[agno] != NULL); | |
302 | ||
303 | ext = mk_extent_tree_nodes(startblock, blockcount, XR_E_FREE); | |
304 | ||
305 | ASSERT(ext->next == NULL); | |
306 | ||
307 | #ifdef XR_BCNT_TRACE | |
308 | fprintf(stderr, "adding bcnt: agno = %d, start = %u, count = %u\n", | |
309 | agno, startblock, blockcount); | |
310 | #endif | |
311 | if ((current = (extent_tree_node_t *) avl_find(extent_bcnt_ptrs[agno], | |
312 | blockcount)) != NULL) { | |
313 | /* | |
314 | * avl tree code doesn't handle dups so insert | |
315 | * onto linked list in increasing startblock order | |
316 | */ | |
317 | top = prev = current; | |
318 | while (current != NULL && | |
319 | startblock > current->ex_startblock) { | |
320 | prev = current; | |
321 | current = current->next; | |
322 | } | |
323 | ||
324 | if (top == current) { | |
325 | ASSERT(top == prev); | |
326 | /* | |
327 | * swap the values of to-be-inserted element | |
328 | * and the values of the head of the list. | |
329 | * then insert as the 2nd element on the list. | |
330 | * | |
331 | * see the comment in get_bcnt_extent() | |
332 | * as to why we have to do this. | |
333 | */ | |
334 | tmp_startblock = top->ex_startblock; | |
335 | tmp_blockcount = top->ex_blockcount; | |
336 | tmp_state = top->ex_state; | |
337 | ||
338 | top->ex_startblock = ext->ex_startblock; | |
339 | top->ex_blockcount = ext->ex_blockcount; | |
340 | top->ex_state = ext->ex_state; | |
341 | ||
342 | ext->ex_startblock = tmp_startblock; | |
343 | ext->ex_blockcount = tmp_blockcount; | |
344 | ext->ex_state = tmp_state; | |
345 | ||
346 | current = top->next; | |
347 | prev = top; | |
348 | } | |
349 | ||
350 | prev->next = ext; | |
351 | ext->next = current; | |
352 | ||
353 | return; | |
354 | } | |
355 | ||
356 | if (avl_insert(extent_bcnt_ptrs[agno], (avlnode_t *) ext) == NULL) { | |
507f4e33 | 357 | do_error(_(": duplicate bno extent range\n")); |
2bd0ea18 NS |
358 | } |
359 | ||
360 | return; | |
361 | } | |
362 | ||
363 | extent_tree_node_t * | |
364 | findfirst_bcnt_extent(xfs_agnumber_t agno) | |
365 | { | |
366 | ASSERT(extent_bcnt_ptrs != NULL); | |
367 | ASSERT(extent_bcnt_ptrs[agno] != NULL); | |
368 | ||
369 | return((extent_tree_node_t *) extent_bcnt_ptrs[agno]->avl_firstino); | |
370 | } | |
371 | ||
372 | extent_tree_node_t * | |
373 | findbiggest_bcnt_extent(xfs_agnumber_t agno) | |
374 | { | |
375 | extern avlnode_t *avl_lastino(avlnode_t *root); | |
376 | ||
377 | ASSERT(extent_bcnt_ptrs != NULL); | |
378 | ASSERT(extent_bcnt_ptrs[agno] != NULL); | |
379 | ||
380 | return((extent_tree_node_t *) avl_lastino(extent_bcnt_ptrs[agno]->avl_root)); | |
381 | } | |
382 | ||
383 | extent_tree_node_t * | |
384 | findnext_bcnt_extent(xfs_agnumber_t agno, extent_tree_node_t *ext) | |
385 | { | |
386 | avlnode_t *nextino; | |
387 | ||
388 | if (ext->next != NULL) { | |
389 | ASSERT(ext->ex_blockcount == ext->next->ex_blockcount); | |
390 | ASSERT(ext->ex_startblock < ext->next->ex_startblock); | |
391 | return(ext->next); | |
392 | } else { | |
393 | /* | |
394 | * have to look at the top of the list to get the | |
395 | * correct avl_nextino pointer since that pointer | |
396 | * is maintained and altered by the AVL code. | |
397 | */ | |
398 | nextino = avl_find(extent_bcnt_ptrs[agno], ext->ex_blockcount); | |
399 | ASSERT(nextino != NULL); | |
400 | if (nextino->avl_nextino != NULL) { | |
401 | ASSERT(ext->ex_blockcount < ((extent_tree_node_t *) | |
402 | nextino->avl_nextino)->ex_blockcount); | |
403 | } | |
404 | return((extent_tree_node_t *) nextino->avl_nextino); | |
405 | } | |
406 | } | |
407 | ||
408 | /* | |
409 | * this is meant to be called after you walk the bno tree to | |
410 | * determine exactly which extent you want (so you'll know the | |
411 | * desired value for startblock when you call this routine). | |
412 | */ | |
413 | extent_tree_node_t * | |
414 | get_bcnt_extent(xfs_agnumber_t agno, xfs_agblock_t startblock, | |
415 | xfs_extlen_t blockcount) | |
416 | { | |
417 | extent_tree_node_t *ext, *prev, *top; | |
418 | xfs_agblock_t tmp_startblock; | |
419 | xfs_extlen_t tmp_blockcount; | |
420 | extent_state_t tmp_state; | |
421 | ||
422 | prev = NULL; | |
423 | ASSERT(extent_bcnt_ptrs != NULL); | |
424 | ASSERT(extent_bcnt_ptrs[agno] != NULL); | |
425 | ||
426 | if ((ext = (extent_tree_node_t *) avl_find(extent_bcnt_ptrs[agno], | |
427 | blockcount)) == NULL) | |
428 | return(NULL); | |
dfc130f3 | 429 | |
2bd0ea18 NS |
430 | top = ext; |
431 | ||
432 | if (ext->next != NULL) { | |
433 | /* | |
434 | * pull it off the list | |
435 | */ | |
436 | while (ext != NULL && startblock != ext->ex_startblock) { | |
437 | prev = ext; | |
438 | ext = ext->next; | |
439 | } | |
440 | ASSERT(ext != NULL); | |
441 | if (ext == top) { | |
442 | /* | |
443 | * this node is linked into the tree so we | |
444 | * swap the core values so we can delete | |
445 | * the next item on the list instead of | |
446 | * the head of the list. This is because | |
447 | * the rest of the tree undoubtedly has | |
448 | * pointers to the piece of memory that | |
449 | * is the head of the list so pulling | |
450 | * the item out of the list and hence | |
451 | * the avl tree would be a bad idea. | |
dfc130f3 | 452 | * |
2bd0ea18 NS |
453 | * (cheaper than the alternative, a tree |
454 | * delete of this node followed by a tree | |
455 | * insert of the next node on the list). | |
456 | */ | |
457 | tmp_startblock = ext->next->ex_startblock; | |
458 | tmp_blockcount = ext->next->ex_blockcount; | |
459 | tmp_state = ext->next->ex_state; | |
460 | ||
461 | ext->next->ex_startblock = ext->ex_startblock; | |
462 | ext->next->ex_blockcount = ext->ex_blockcount; | |
463 | ext->next->ex_state = ext->ex_state; | |
464 | ||
465 | ext->ex_startblock = tmp_startblock; | |
466 | ext->ex_blockcount = tmp_blockcount; | |
467 | ext->ex_state = tmp_state; | |
468 | ||
469 | ext = ext->next; | |
470 | prev = top; | |
471 | } | |
472 | /* | |
473 | * now, a simple list deletion | |
474 | */ | |
475 | prev->next = ext->next; | |
476 | ext->next = NULL; | |
477 | } else { | |
478 | /* | |
479 | * no list, just one node. simply delete | |
480 | */ | |
481 | avl_delete(extent_bcnt_ptrs[agno], &ext->avl_node); | |
482 | } | |
483 | ||
484 | ASSERT(ext->ex_startblock == startblock); | |
485 | ASSERT(ext->ex_blockcount == blockcount); | |
486 | return(ext); | |
487 | } | |
488 | ||
489 | /* | |
490 | * the next 2 routines manage the trees of duplicate extents -- 1 tree | |
491 | * per AG | |
492 | */ | |
493 | void | |
494 | add_dup_extent(xfs_agnumber_t agno, xfs_agblock_t startblock, | |
495 | xfs_extlen_t blockcount) | |
496 | { | |
497 | extent_tree_node_t *first, *last, *ext, *next_ext; | |
498 | xfs_agblock_t new_startblock; | |
499 | xfs_extlen_t new_blockcount; | |
500 | ||
501 | ASSERT(agno < glob_agcount); | |
502 | ||
503 | #ifdef XR_DUP_TRACE | |
504 | fprintf(stderr, "Adding dup extent - %d/%d %d\n", agno, startblock, blockcount); | |
505 | #endif | |
506 | avl_findranges(extent_tree_ptrs[agno], startblock - 1, | |
507 | startblock + blockcount + 1, | |
508 | (avlnode_t **) &first, (avlnode_t **) &last); | |
509 | /* | |
510 | * find adjacent and overlapping extent blocks | |
511 | */ | |
512 | if (first == NULL && last == NULL) { | |
513 | /* nothing, just make and insert new extent */ | |
514 | ||
515 | ext = mk_extent_tree_nodes(startblock, blockcount, XR_E_MULT); | |
516 | ||
517 | if (avl_insert(extent_tree_ptrs[agno], | |
518 | (avlnode_t *) ext) == NULL) { | |
507f4e33 | 519 | do_error(_("duplicate extent range\n")); |
2bd0ea18 NS |
520 | } |
521 | ||
522 | return; | |
523 | } | |
524 | ||
525 | ASSERT(first != NULL && last != NULL); | |
526 | ||
527 | /* | |
528 | * find the new composite range, delete old extent nodes | |
529 | * as we go | |
530 | */ | |
531 | new_startblock = startblock; | |
532 | new_blockcount = blockcount; | |
533 | ||
534 | for (ext = first; | |
535 | ext != (extent_tree_node_t *) last->avl_node.avl_nextino; | |
536 | ext = next_ext) { | |
537 | /* | |
538 | * preserve the next inorder node | |
539 | */ | |
540 | next_ext = (extent_tree_node_t *) ext->avl_node.avl_nextino; | |
541 | /* | |
542 | * just bail if the new extent is contained within an old one | |
543 | */ | |
dfc130f3 | 544 | if (ext->ex_startblock <= startblock && |
2bd0ea18 NS |
545 | ext->ex_blockcount >= blockcount) |
546 | return; | |
547 | /* | |
548 | * now check for overlaps and adjacent extents | |
549 | */ | |
550 | if (ext->ex_startblock + ext->ex_blockcount >= startblock | |
551 | || ext->ex_startblock <= startblock + blockcount) { | |
552 | ||
553 | if (ext->ex_startblock < new_startblock) | |
554 | new_startblock = ext->ex_startblock; | |
555 | ||
556 | if (ext->ex_startblock + ext->ex_blockcount > | |
557 | new_startblock + new_blockcount) | |
558 | new_blockcount = ext->ex_startblock + | |
559 | ext->ex_blockcount - | |
560 | new_startblock; | |
561 | ||
562 | avl_delete(extent_tree_ptrs[agno], (avlnode_t *) ext); | |
563 | continue; | |
564 | } | |
565 | } | |
566 | ||
567 | ext = mk_extent_tree_nodes(new_startblock, new_blockcount, XR_E_MULT); | |
568 | ||
569 | if (avl_insert(extent_tree_ptrs[agno], (avlnode_t *) ext) == NULL) { | |
507f4e33 | 570 | do_error(_("duplicate extent range\n")); |
2bd0ea18 NS |
571 | } |
572 | ||
573 | return; | |
574 | } | |
575 | ||
2bd0ea18 NS |
576 | static __psunsigned_t |
577 | avl_ext_start(avlnode_t *node) | |
578 | { | |
579 | return((__psunsigned_t) | |
580 | ((extent_tree_node_t *) node)->ex_startblock); | |
581 | } | |
582 | ||
583 | static __psunsigned_t | |
584 | avl_ext_end(avlnode_t *node) | |
585 | { | |
586 | return((__psunsigned_t) ( | |
587 | ((extent_tree_node_t *) node)->ex_startblock + | |
588 | ((extent_tree_node_t *) node)->ex_blockcount)); | |
589 | } | |
590 | ||
591 | /* | |
592 | * convert size to an address for the AVL tree code -- the bigger the size, | |
593 | * the lower the address so the biggest extent will be first in the tree | |
594 | */ | |
595 | static __psunsigned_t | |
596 | avl_ext_bcnt_start(avlnode_t *node) | |
597 | { | |
598 | /* | |
599 | return((__psunsigned_t) (BCNT_ADDR(((extent_tree_node_t *) | |
600 | node)->ex_blockcount))); | |
601 | */ | |
602 | return((__psunsigned_t) ((extent_tree_node_t *)node)->ex_blockcount); | |
603 | } | |
604 | ||
605 | static __psunsigned_t | |
606 | avl_ext_bcnt_end(avlnode_t *node) | |
607 | { | |
608 | /* | |
609 | return((__psunsigned_t) (BCNT_ADDR(((extent_tree_node_t *) | |
610 | node)->ex_blockcount))); | |
611 | */ | |
612 | return((__psunsigned_t) ((extent_tree_node_t *)node)->ex_blockcount); | |
613 | } | |
614 | ||
615 | avlops_t avl_extent_bcnt_tree_ops = { | |
616 | avl_ext_bcnt_start, | |
617 | avl_ext_bcnt_end | |
618 | }; | |
619 | ||
620 | avlops_t avl_extent_tree_ops = { | |
621 | avl_ext_start, | |
622 | avl_ext_end | |
623 | }; | |
624 | ||
625 | /* | |
626 | * for real-time extents -- have to dup code since realtime extent | |
627 | * startblocks can be 64-bit values. | |
628 | */ | |
629 | static rt_extent_tree_node_t * | |
630 | mk_rt_extent_tree_nodes(xfs_drtbno_t new_startblock, | |
631 | xfs_extlen_t new_blockcount, extent_state_t new_state) | |
632 | { | |
633 | int i; | |
634 | rt_extent_tree_node_t *new; | |
635 | rt_extent_alloc_rec_t *rec; | |
636 | ||
637 | if (rt_ext_flist.cnt == 0) { | |
638 | ASSERT(rt_ext_flist.list == NULL); | |
639 | ||
640 | if ((rec = malloc(sizeof(rt_extent_alloc_rec_t))) == NULL) | |
507f4e33 NS |
641 | do_error( |
642 | _("couldn't allocate new extent descriptors.\n")); | |
2bd0ea18 NS |
643 | |
644 | record_allocation(&rec->alloc_rec, rt_ba_list); | |
645 | ||
646 | new = &rec->extents[0]; | |
647 | ||
648 | for (i = 0; i < ALLOC_NUM_EXTS; i++) { | |
649 | new->avl_node.avl_nextino = (avlnode_t *) | |
650 | rt_ext_flist.list; | |
651 | rt_ext_flist.list = new; | |
652 | rt_ext_flist.cnt++; | |
653 | new++; | |
654 | } | |
655 | } | |
656 | ||
657 | ASSERT(rt_ext_flist.list != NULL); | |
658 | ||
659 | new = rt_ext_flist.list; | |
660 | rt_ext_flist.list = (rt_extent_tree_node_t *) new->avl_node.avl_nextino; | |
661 | rt_ext_flist.cnt--; | |
662 | new->avl_node.avl_nextino = NULL; | |
663 | ||
664 | /* initialize node */ | |
665 | ||
666 | new->rt_startblock = new_startblock; | |
667 | new->rt_blockcount = new_blockcount; | |
668 | new->rt_state = new_state; | |
669 | ||
670 | return(new); | |
671 | } | |
672 | ||
673 | #if 0 | |
674 | void | |
675 | release_rt_extent_tree_node(rt_extent_tree_node_t *node) | |
676 | { | |
677 | node->avl_node.avl_nextino = (avlnode_t *) rt_ext_flist.list; | |
678 | rt_ext_flist.list = node; | |
679 | rt_ext_flist.cnt++; | |
680 | ||
681 | return; | |
682 | } | |
683 | ||
684 | void | |
685 | release_rt_extent_tree() | |
686 | { | |
687 | extent_tree_node_t *ext; | |
688 | extent_tree_node_t *tmp; | |
689 | extent_tree_node_t *lext; | |
690 | extent_tree_node_t *ltmp; | |
691 | avl64tree_desc_t *tree; | |
692 | ||
693 | tree = rt_extent_tree_ptr; | |
694 | ||
695 | if (tree->avl_firstino == NULL) | |
696 | return; | |
697 | ||
698 | ext = (extent_tree_node_t *) tree->avl_firstino; | |
699 | ||
700 | while (ext != NULL) { | |
701 | tmp = (extent_tree_node_t *) ext->avl_node.avl_nextino; | |
702 | release_rt_extent_tree_node(ext); | |
703 | ext = tmp; | |
704 | } | |
705 | ||
706 | tree->avl_root = tree->avl_firstino = NULL; | |
707 | ||
708 | return; | |
709 | } | |
710 | #endif | |
711 | ||
712 | /* | |
713 | * don't need release functions for realtime tree teardown | |
714 | * since we only have one tree, not one per AG | |
715 | */ | |
716 | /* ARGSUSED */ | |
717 | void | |
718 | free_rt_dup_extent_tree(xfs_mount_t *mp) | |
719 | { | |
720 | ASSERT(mp->m_sb.sb_rblocks != 0); | |
721 | ||
722 | free_allocations(rt_ba_list); | |
723 | free(rt_ext_tree_ptr); | |
724 | ||
725 | rt_ba_list = NULL; | |
726 | rt_ext_tree_ptr = NULL; | |
727 | ||
728 | return; | |
729 | } | |
730 | ||
731 | /* | |
732 | * add a duplicate real-time extent | |
733 | */ | |
734 | void | |
735 | add_rt_dup_extent(xfs_drtbno_t startblock, xfs_extlen_t blockcount) | |
736 | { | |
737 | rt_extent_tree_node_t *first, *last, *ext, *next_ext; | |
738 | xfs_drtbno_t new_startblock; | |
739 | xfs_extlen_t new_blockcount; | |
740 | ||
741 | avl64_findranges(rt_ext_tree_ptr, startblock - 1, | |
742 | startblock + blockcount + 1, | |
743 | (avl64node_t **) &first, (avl64node_t **) &last); | |
744 | /* | |
745 | * find adjacent and overlapping extent blocks | |
746 | */ | |
747 | if (first == NULL && last == NULL) { | |
748 | /* nothing, just make and insert new extent */ | |
749 | ||
750 | ext = mk_rt_extent_tree_nodes(startblock, | |
751 | blockcount, XR_E_MULT); | |
752 | ||
753 | if (avl64_insert(rt_ext_tree_ptr, | |
754 | (avl64node_t *) ext) == NULL) { | |
507f4e33 | 755 | do_error(_("duplicate extent range\n")); |
2bd0ea18 NS |
756 | } |
757 | ||
758 | return; | |
759 | } | |
760 | ||
761 | ASSERT(first != NULL && last != NULL); | |
762 | ||
763 | /* | |
764 | * find the new composite range, delete old extent nodes | |
765 | * as we go | |
766 | */ | |
767 | new_startblock = startblock; | |
768 | new_blockcount = blockcount; | |
769 | ||
770 | for (ext = first; | |
771 | ext != (rt_extent_tree_node_t *) last->avl_node.avl_nextino; | |
772 | ext = next_ext) { | |
773 | /* | |
774 | * preserve the next inorder node | |
775 | */ | |
776 | next_ext = (rt_extent_tree_node_t *) ext->avl_node.avl_nextino; | |
777 | /* | |
778 | * just bail if the new extent is contained within an old one | |
779 | */ | |
dfc130f3 | 780 | if (ext->rt_startblock <= startblock && |
2bd0ea18 NS |
781 | ext->rt_blockcount >= blockcount) |
782 | return; | |
783 | /* | |
784 | * now check for overlaps and adjacent extents | |
785 | */ | |
786 | if (ext->rt_startblock + ext->rt_blockcount >= startblock | |
787 | || ext->rt_startblock <= startblock + blockcount) { | |
788 | ||
789 | if (ext->rt_startblock < new_startblock) | |
790 | new_startblock = ext->rt_startblock; | |
791 | ||
792 | if (ext->rt_startblock + ext->rt_blockcount > | |
793 | new_startblock + new_blockcount) | |
794 | new_blockcount = ext->rt_startblock + | |
795 | ext->rt_blockcount - | |
796 | new_startblock; | |
797 | ||
798 | avl64_delete(rt_ext_tree_ptr, (avl64node_t *) ext); | |
799 | continue; | |
800 | } | |
801 | } | |
802 | ||
803 | ext = mk_rt_extent_tree_nodes(new_startblock, | |
804 | new_blockcount, XR_E_MULT); | |
805 | ||
806 | if (avl64_insert(rt_ext_tree_ptr, (avl64node_t *) ext) == NULL) { | |
507f4e33 | 807 | do_error(_("duplicate extent range\n")); |
2bd0ea18 NS |
808 | } |
809 | ||
810 | return; | |
811 | } | |
812 | ||
813 | /* | |
814 | * returns 1 if block is a dup, 0 if not | |
815 | */ | |
816 | /* ARGSUSED */ | |
817 | int | |
818 | search_rt_dup_extent(xfs_mount_t *mp, xfs_drtbno_t bno) | |
819 | { | |
820 | if (avl64_findrange(rt_ext_tree_ptr, bno) != NULL) | |
821 | return(1); | |
822 | ||
823 | return(0); | |
824 | } | |
825 | ||
826 | static __uint64_t | |
827 | avl64_rt_ext_start(avl64node_t *node) | |
828 | { | |
829 | return(((rt_extent_tree_node_t *) node)->rt_startblock); | |
830 | } | |
831 | ||
832 | static __uint64_t | |
833 | avl64_ext_end(avl64node_t *node) | |
834 | { | |
835 | return(((rt_extent_tree_node_t *) node)->rt_startblock + | |
836 | ((rt_extent_tree_node_t *) node)->rt_blockcount); | |
837 | } | |
838 | ||
839 | avl64ops_t avl64_extent_tree_ops = { | |
840 | avl64_rt_ext_start, | |
841 | avl64_ext_end | |
842 | }; | |
843 | ||
844 | void | |
845 | incore_ext_init(xfs_mount_t *mp) | |
846 | { | |
847 | int i; | |
848 | xfs_agnumber_t agcount = mp->m_sb.sb_agcount; | |
849 | ||
850 | ba_list = NULL; | |
851 | rt_ba_list = NULL; | |
852 | ||
853 | if ((extent_tree_ptrs = malloc(agcount * | |
854 | sizeof(avltree_desc_t *))) == NULL) | |
507f4e33 NS |
855 | do_error( |
856 | _("couldn't malloc dup extent tree descriptor table\n")); | |
2bd0ea18 NS |
857 | |
858 | if ((extent_bno_ptrs = malloc(agcount * | |
859 | sizeof(avltree_desc_t *))) == NULL) | |
507f4e33 NS |
860 | do_error( |
861 | _("couldn't malloc free by-bno extent tree descriptor table\n")); | |
2bd0ea18 NS |
862 | |
863 | if ((extent_bcnt_ptrs = malloc(agcount * | |
864 | sizeof(avltree_desc_t *))) == NULL) | |
507f4e33 NS |
865 | do_error( |
866 | _("couldn't malloc free by-bcnt extent tree descriptor table\n")); | |
2bd0ea18 NS |
867 | |
868 | for (i = 0; i < agcount; i++) { | |
869 | if ((extent_tree_ptrs[i] = | |
870 | malloc(sizeof(avltree_desc_t))) == NULL) | |
507f4e33 NS |
871 | do_error( |
872 | _("couldn't malloc dup extent tree descriptor\n")); | |
2bd0ea18 NS |
873 | if ((extent_bno_ptrs[i] = |
874 | malloc(sizeof(avltree_desc_t))) == NULL) | |
507f4e33 NS |
875 | do_error( |
876 | _("couldn't malloc bno extent tree descriptor\n")); | |
2bd0ea18 NS |
877 | if ((extent_bcnt_ptrs[i] = |
878 | malloc(sizeof(avltree_desc_t))) == NULL) | |
507f4e33 NS |
879 | do_error( |
880 | _("couldn't malloc bcnt extent tree descriptor\n")); | |
2bd0ea18 NS |
881 | } |
882 | ||
883 | for (i = 0; i < agcount; i++) { | |
884 | avl_init_tree(extent_tree_ptrs[i], &avl_extent_tree_ops); | |
885 | avl_init_tree(extent_bno_ptrs[i], &avl_extent_tree_ops); | |
886 | avl_init_tree(extent_bcnt_ptrs[i], &avl_extent_bcnt_tree_ops); | |
887 | } | |
888 | ||
889 | if ((rt_ext_tree_ptr = malloc(sizeof(avltree_desc_t))) == NULL) | |
507f4e33 | 890 | do_error(_("couldn't malloc dup rt extent tree descriptor\n")); |
2bd0ea18 NS |
891 | |
892 | avl64_init_tree(rt_ext_tree_ptr, &avl64_extent_tree_ops); | |
893 | ||
894 | ext_flist.cnt = 0; | |
895 | ext_flist.list = NULL; | |
896 | ||
897 | return; | |
898 | } | |
899 | ||
900 | /* | |
901 | * this routine actually frees all the memory used to track per-AG trees | |
902 | */ | |
903 | void | |
904 | incore_ext_teardown(xfs_mount_t *mp) | |
905 | { | |
906 | xfs_agnumber_t i; | |
907 | ||
908 | free_allocations(ba_list); | |
909 | ||
910 | for (i = 0; i < mp->m_sb.sb_agcount; i++) { | |
911 | free(extent_tree_ptrs[i]); | |
912 | free(extent_bno_ptrs[i]); | |
913 | free(extent_bcnt_ptrs[i]); | |
914 | } | |
915 | ||
916 | free(extent_bcnt_ptrs); | |
917 | free(extent_bno_ptrs); | |
918 | free(extent_tree_ptrs); | |
919 | ||
920 | extent_bcnt_ptrs = extent_bno_ptrs = extent_tree_ptrs = NULL; | |
921 | ||
922 | return; | |
923 | } | |
924 | ||
925 | int | |
926 | count_extents(xfs_agnumber_t agno, avltree_desc_t *tree, int whichtree) | |
927 | { | |
928 | extent_tree_node_t *node; | |
929 | int i = 0; | |
930 | ||
931 | node = (extent_tree_node_t *) tree->avl_firstino; | |
932 | ||
933 | while (node != NULL) { | |
934 | i++; | |
935 | if (whichtree) | |
936 | node = findnext_bcnt_extent(agno, node); | |
937 | else | |
938 | node = findnext_bno_extent(node); | |
939 | } | |
940 | ||
941 | return(i); | |
942 | } | |
943 | ||
944 | int | |
945 | count_bno_extents_blocks(xfs_agnumber_t agno, uint *numblocks) | |
946 | { | |
947 | __uint64_t nblocks; | |
948 | extent_tree_node_t *node; | |
949 | int i = 0; | |
950 | ||
951 | ASSERT(agno < glob_agcount); | |
952 | ||
953 | nblocks = 0; | |
954 | ||
955 | node = (extent_tree_node_t *) extent_bno_ptrs[agno]->avl_firstino; | |
956 | ||
957 | while (node != NULL) { | |
958 | nblocks += node->ex_blockcount; | |
959 | i++; | |
960 | node = findnext_bno_extent(node); | |
961 | } | |
962 | ||
963 | *numblocks = nblocks; | |
964 | return(i); | |
965 | } | |
966 | ||
967 | int | |
968 | count_bno_extents(xfs_agnumber_t agno) | |
969 | { | |
970 | ASSERT(agno < glob_agcount); | |
971 | return(count_extents(agno, extent_bno_ptrs[agno], 0)); | |
972 | } | |
973 | ||
974 | int | |
975 | count_bcnt_extents(xfs_agnumber_t agno) | |
976 | { | |
977 | ASSERT(agno < glob_agcount); | |
978 | return(count_extents(agno, extent_bcnt_ptrs[agno], 1)); | |
979 | } |