1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
14 #include "err_protos.h"
17 * array of inode tree ptrs, one per ag
19 avltree_desc_t
**inode_tree_ptrs
;
22 * ditto for uncertain inodes
24 static avltree_desc_t
**inode_uncertain_tree_ptrs
;
26 /* memory optimised nlink counting for all inodes */
29 alloc_nlink_array(uint8_t nlink_size
)
33 ptr
= calloc(XFS_INODES_PER_CHUNK
, nlink_size
);
35 do_error(_("could not allocate nlink array\n"));
40 nlink_grow_8_to_16(ino_tree_node_t
*irec
)
45 irec
->nlink_size
= sizeof(uint16_t);
47 new_nlinks
= alloc_nlink_array(irec
->nlink_size
);
48 for (i
= 0; i
< XFS_INODES_PER_CHUNK
; i
++)
49 new_nlinks
[i
] = irec
->disk_nlinks
.un8
[i
];
50 free(irec
->disk_nlinks
.un8
);
51 irec
->disk_nlinks
.un16
= new_nlinks
;
53 if (full_ino_ex_data
) {
54 new_nlinks
= alloc_nlink_array(irec
->nlink_size
);
55 for (i
= 0; i
< XFS_INODES_PER_CHUNK
; i
++) {
57 irec
->ino_un
.ex_data
->counted_nlinks
.un8
[i
];
59 free(irec
->ino_un
.ex_data
->counted_nlinks
.un8
);
60 irec
->ino_un
.ex_data
->counted_nlinks
.un16
= new_nlinks
;
65 nlink_grow_16_to_32(ino_tree_node_t
*irec
)
70 irec
->nlink_size
= sizeof(uint32_t);
72 new_nlinks
= alloc_nlink_array(irec
->nlink_size
);
73 for (i
= 0; i
< XFS_INODES_PER_CHUNK
; i
++)
74 new_nlinks
[i
] = irec
->disk_nlinks
.un16
[i
];
75 free(irec
->disk_nlinks
.un16
);
76 irec
->disk_nlinks
.un32
= new_nlinks
;
78 if (full_ino_ex_data
) {
79 new_nlinks
= alloc_nlink_array(irec
->nlink_size
);
81 for (i
= 0; i
< XFS_INODES_PER_CHUNK
; i
++) {
83 irec
->ino_un
.ex_data
->counted_nlinks
.un16
[i
];
85 free(irec
->ino_un
.ex_data
->counted_nlinks
.un16
);
86 irec
->ino_un
.ex_data
->counted_nlinks
.un32
= new_nlinks
;
90 void add_inode_ref(struct ino_tree_node
*irec
, int ino_offset
)
92 ASSERT(irec
->ino_un
.ex_data
!= NULL
);
94 switch (irec
->nlink_size
) {
96 if (irec
->ino_un
.ex_data
->counted_nlinks
.un8
[ino_offset
] < 0xff) {
97 irec
->ino_un
.ex_data
->counted_nlinks
.un8
[ino_offset
]++;
100 nlink_grow_8_to_16(irec
);
102 case sizeof(uint16_t):
103 if (irec
->ino_un
.ex_data
->counted_nlinks
.un16
[ino_offset
] < 0xffff) {
104 irec
->ino_un
.ex_data
->counted_nlinks
.un16
[ino_offset
]++;
107 nlink_grow_16_to_32(irec
);
109 case sizeof(uint32_t):
110 irec
->ino_un
.ex_data
->counted_nlinks
.un32
[ino_offset
]++;
117 void drop_inode_ref(struct ino_tree_node
*irec
, int ino_offset
)
121 ASSERT(irec
->ino_un
.ex_data
!= NULL
);
123 switch (irec
->nlink_size
) {
124 case sizeof(uint8_t):
125 ASSERT(irec
->ino_un
.ex_data
->counted_nlinks
.un8
[ino_offset
] > 0);
126 refs
= --irec
->ino_un
.ex_data
->counted_nlinks
.un8
[ino_offset
];
128 case sizeof(uint16_t):
129 ASSERT(irec
->ino_un
.ex_data
->counted_nlinks
.un16
[ino_offset
] > 0);
130 refs
= --irec
->ino_un
.ex_data
->counted_nlinks
.un16
[ino_offset
];
132 case sizeof(uint32_t):
133 ASSERT(irec
->ino_un
.ex_data
->counted_nlinks
.un32
[ino_offset
] > 0);
134 refs
= --irec
->ino_un
.ex_data
->counted_nlinks
.un32
[ino_offset
];
141 irec
->ino_un
.ex_data
->ino_reached
&= ~IREC_MASK(ino_offset
);
144 uint32_t num_inode_references(struct ino_tree_node
*irec
, int ino_offset
)
146 ASSERT(irec
->ino_un
.ex_data
!= NULL
);
148 switch (irec
->nlink_size
) {
149 case sizeof(uint8_t):
150 return irec
->ino_un
.ex_data
->counted_nlinks
.un8
[ino_offset
];
151 case sizeof(uint16_t):
152 return irec
->ino_un
.ex_data
->counted_nlinks
.un16
[ino_offset
];
153 case sizeof(uint32_t):
154 return irec
->ino_un
.ex_data
->counted_nlinks
.un32
[ino_offset
];
161 void set_inode_disk_nlinks(struct ino_tree_node
*irec
, int ino_offset
,
164 switch (irec
->nlink_size
) {
165 case sizeof(uint8_t):
167 irec
->disk_nlinks
.un8
[ino_offset
] = nlinks
;
170 nlink_grow_8_to_16(irec
);
172 case sizeof(uint16_t):
173 if (nlinks
< 0xffff) {
174 irec
->disk_nlinks
.un16
[ino_offset
] = nlinks
;
177 nlink_grow_16_to_32(irec
);
179 case sizeof(uint32_t):
180 irec
->disk_nlinks
.un32
[ino_offset
] = nlinks
;
187 uint32_t get_inode_disk_nlinks(struct ino_tree_node
*irec
, int ino_offset
)
189 switch (irec
->nlink_size
) {
190 case sizeof(uint8_t):
191 return irec
->disk_nlinks
.un8
[ino_offset
];
192 case sizeof(uint16_t):
193 return irec
->disk_nlinks
.un16
[ino_offset
];
194 case sizeof(uint32_t):
195 return irec
->disk_nlinks
.un32
[ino_offset
];
204 struct xfs_mount
*mp
)
208 if (!xfs_sb_version_hasftype(&mp
->m_sb
))
211 ptr
= calloc(XFS_INODES_PER_CHUNK
, sizeof(*ptr
));
213 do_error(_("could not allocate ftypes array\n"));
218 * Next is the uncertain inode list -- a sorted (in ascending order)
219 * list of inode records sorted on the starting inode number. There
220 * is one list per ag.
224 * Common code for creating inode records for use by trees and lists.
225 * called only from add_inodes and add_inodes_uncertain
227 * IMPORTANT: all inodes (inode records) start off as free and
230 static struct ino_tree_node
*
232 struct xfs_mount
*mp
,
233 xfs_agino_t starting_ino
)
235 struct ino_tree_node
*irec
;
237 irec
= malloc(sizeof(*irec
));
239 do_error(_("inode map malloc failed\n"));
241 irec
->avl_node
.avl_nextino
= NULL
;
242 irec
->avl_node
.avl_forw
= NULL
;
243 irec
->avl_node
.avl_back
= NULL
;
245 irec
->ino_startnum
= starting_ino
;
246 irec
->ino_confirmed
= 0;
247 irec
->ino_isa_dir
= 0;
248 irec
->ino_was_rl
= 0;
250 irec
->ir_free
= (xfs_inofree_t
) - 1;
252 irec
->ino_un
.ex_data
= NULL
;
253 irec
->nlink_size
= sizeof(uint8_t);
254 irec
->disk_nlinks
.un8
= alloc_nlink_array(irec
->nlink_size
);
255 irec
->ftypes
= alloc_ftypes_array(mp
);
260 free_nlink_array(union ino_nlink nlinks
, uint8_t nlink_size
)
262 switch (nlink_size
) {
263 case sizeof(uint8_t):
266 case sizeof(uint16_t):
269 case sizeof(uint32_t):
279 struct ino_tree_node
*irec
)
281 irec
->avl_node
.avl_nextino
= NULL
;
282 irec
->avl_node
.avl_forw
= NULL
;
283 irec
->avl_node
.avl_back
= NULL
;
285 free_nlink_array(irec
->disk_nlinks
, irec
->nlink_size
);
286 if (irec
->ino_un
.ex_data
!= NULL
) {
287 if (full_ino_ex_data
) {
288 free(irec
->ino_un
.ex_data
->parents
);
289 free_nlink_array(irec
->ino_un
.ex_data
->counted_nlinks
,
292 free(irec
->ino_un
.ex_data
);
301 * last referenced cache for uncertain inodes
303 static ino_tree_node_t
**last_rec
;
306 * ok, the uncertain inodes are a set of trees just like the
307 * good inodes but all starting inode records are (arbitrarily)
308 * aligned on XFS_CHUNK_PER_INODE boundaries to prevent overlaps.
309 * this means we may have partials records in the tree (e.g. records
310 * without 64 confirmed uncertain inodes). Tough.
312 * free is set to 1 if the inode is thought to be free, 0 if used
315 add_aginode_uncertain(
316 struct xfs_mount
*mp
,
321 ino_tree_node_t
*ino_rec
;
325 ASSERT(agno
< glob_agcount
);
326 ASSERT(last_rec
!= NULL
);
328 s_ino
= rounddown(ino
, XFS_INODES_PER_CHUNK
);
331 * check for a cache hit
333 if (last_rec
[agno
] != NULL
&& last_rec
[agno
]->ino_startnum
== s_ino
) {
334 offset
= ino
- s_ino
;
336 set_inode_free(last_rec
[agno
], offset
);
338 set_inode_used(last_rec
[agno
], offset
);
344 * check to see if record containing inode is already in the tree.
347 ino_rec
= (ino_tree_node_t
*)
348 avl_findrange(inode_uncertain_tree_ptrs
[agno
], s_ino
);
350 ino_rec
= alloc_ino_node(mp
, s_ino
);
352 if (!avl_insert(inode_uncertain_tree_ptrs
[agno
],
355 _("add_aginode_uncertain - duplicate inode range\n"));
359 set_inode_free(ino_rec
, ino
- s_ino
);
361 set_inode_used(ino_rec
, ino
- s_ino
);
366 last_rec
[agno
] = ino_rec
;
370 * like add_aginode_uncertain() only it needs an xfs_mount_t *
371 * to perform the inode number conversion.
374 add_inode_uncertain(xfs_mount_t
*mp
, xfs_ino_t ino
, int free
)
376 add_aginode_uncertain(mp
, XFS_INO_TO_AGNO(mp
, ino
),
377 XFS_INO_TO_AGINO(mp
, ino
), free
);
381 * pull the indicated inode record out of the uncertain inode tree
384 get_uncertain_inode_rec(struct xfs_mount
*mp
, xfs_agnumber_t agno
,
385 ino_tree_node_t
*ino_rec
)
387 ASSERT(inode_tree_ptrs
!= NULL
);
388 ASSERT(agno
< mp
->m_sb
.sb_agcount
);
389 ASSERT(inode_tree_ptrs
[agno
] != NULL
);
391 avl_delete(inode_uncertain_tree_ptrs
[agno
], &ino_rec
->avl_node
);
393 ino_rec
->avl_node
.avl_nextino
= NULL
;
394 ino_rec
->avl_node
.avl_forw
= NULL
;
395 ino_rec
->avl_node
.avl_back
= NULL
;
399 findfirst_uncertain_inode_rec(xfs_agnumber_t agno
)
401 return((ino_tree_node_t
*)
402 inode_uncertain_tree_ptrs
[agno
]->avl_firstino
);
406 find_uncertain_inode_rec(xfs_agnumber_t agno
, xfs_agino_t ino
)
408 return((ino_tree_node_t
*)
409 avl_findrange(inode_uncertain_tree_ptrs
[agno
], ino
));
413 clear_uncertain_ino_cache(xfs_agnumber_t agno
)
415 last_rec
[agno
] = NULL
;
420 * Next comes the inode trees. One per AG, AVL trees of inode records, each
421 * inode record tracking 64 inodes
425 * Set up an inode tree record for a group of inodes that will include the
428 * This does NOT do error-check for duplicate records. The caller is
429 * responsible for checking that. Ino must be the start of an
430 * XFS_INODES_PER_CHUNK (64) inode chunk
432 * Each inode resides in a 64-inode chunk which can be part one or more chunks
433 * (max(64, inodes-per-block). The fs allocates in chunks (as opposed to 1
434 * chunk) when a block can hold more than one chunk (inodes per block > 64).
435 * Allocating in one chunk pieces causes us problems when it takes more than
436 * one fs block to contain an inode chunk because the chunks can start on
437 * *any* block boundary. So we assume that the caller has a clue because at
438 * this level, we don't.
440 static struct ino_tree_node
*
442 struct xfs_mount
*mp
,
446 struct ino_tree_node
*irec
;
448 irec
= alloc_ino_node(mp
, agino
);
449 if (!avl_insert(inode_tree_ptrs
[agno
], &irec
->avl_node
))
450 do_warn(_("add_inode - duplicate inode range\n"));
455 * pull the indicated inode record out of the inode tree
458 get_inode_rec(struct xfs_mount
*mp
, xfs_agnumber_t agno
, ino_tree_node_t
*ino_rec
)
460 ASSERT(inode_tree_ptrs
!= NULL
);
461 ASSERT(agno
< mp
->m_sb
.sb_agcount
);
462 ASSERT(inode_tree_ptrs
[agno
] != NULL
);
464 avl_delete(inode_tree_ptrs
[agno
], &ino_rec
->avl_node
);
466 ino_rec
->avl_node
.avl_nextino
= NULL
;
467 ino_rec
->avl_node
.avl_forw
= NULL
;
468 ino_rec
->avl_node
.avl_back
= NULL
;
472 * free the designated inode record (return it to the free pool)
476 free_inode_rec(xfs_agnumber_t agno
, ino_tree_node_t
*ino_rec
)
478 free_ino_tree_node(ino_rec
);
482 find_inode_rec_range(struct xfs_mount
*mp
, xfs_agnumber_t agno
,
483 xfs_agino_t start_ino
, xfs_agino_t end_ino
,
484 ino_tree_node_t
**first
, ino_tree_node_t
**last
)
486 *first
= *last
= NULL
;
489 * Is the AG inside the file system ?
491 if (agno
< mp
->m_sb
.sb_agcount
)
492 avl_findranges(inode_tree_ptrs
[agno
], start_ino
,
493 end_ino
, (avlnode_t
**) first
, (avlnode_t
**) last
);
497 * if ino doesn't exist, it must be properly aligned -- on a
498 * filesystem block boundary or XFS_INODES_PER_CHUNK boundary,
499 * whichever alignment is larger.
502 set_inode_used_alloc(struct xfs_mount
*mp
, xfs_agnumber_t agno
, xfs_agino_t ino
)
504 ino_tree_node_t
*ino_rec
;
507 * check alignment -- the only way to detect this
508 * is too see if the chunk overlaps another chunk
509 * already in the tree
511 ino_rec
= add_inode(mp
, agno
, ino
);
513 ASSERT(ino_rec
!= NULL
);
514 ASSERT(ino
>= ino_rec
->ino_startnum
&&
515 ino
- ino_rec
->ino_startnum
< XFS_INODES_PER_CHUNK
);
517 set_inode_used(ino_rec
, ino
- ino_rec
->ino_startnum
);
523 set_inode_free_alloc(struct xfs_mount
*mp
, xfs_agnumber_t agno
, xfs_agino_t ino
)
525 ino_tree_node_t
*ino_rec
;
527 ino_rec
= add_inode(mp
, agno
, ino
);
529 ASSERT(ino_rec
!= NULL
);
530 ASSERT(ino
>= ino_rec
->ino_startnum
&&
531 ino
- ino_rec
->ino_startnum
< XFS_INODES_PER_CHUNK
);
533 set_inode_free(ino_rec
, ino
- ino_rec
->ino_startnum
);
539 print_inode_list_int(xfs_agnumber_t agno
, int uncertain
)
541 ino_tree_node_t
*ino_rec
;
544 fprintf(stderr
, _("good inode list is --\n"));
545 ino_rec
= findfirst_inode_rec(agno
);
547 fprintf(stderr
, _("uncertain inode list is --\n"));
548 ino_rec
= findfirst_uncertain_inode_rec(agno
);
551 if (ino_rec
== NULL
) {
552 fprintf(stderr
, _("agno %d -- no inodes\n"), agno
);
556 printf(_("agno %d\n"), agno
);
558 while(ino_rec
!= NULL
) {
560 _("\tptr = %lx, start = 0x%x, free = 0x%llx, confirmed = 0x%llx\n"),
561 (unsigned long)ino_rec
,
562 ino_rec
->ino_startnum
,
563 (unsigned long long)ino_rec
->ir_free
,
564 (unsigned long long)ino_rec
->ino_confirmed
);
565 if (ino_rec
->ino_startnum
== 0)
567 ino_rec
= next_ino_rec(ino_rec
);
572 print_inode_list(xfs_agnumber_t agno
)
574 print_inode_list_int(agno
, 0);
578 print_uncertain_inode_list(xfs_agnumber_t agno
)
580 print_inode_list_int(agno
, 1);
584 * set parent -- use a bitmask and a packed array. The bitmask
585 * indicate which inodes have an entry in the array. An inode that
586 * is the Nth bit set in the mask is stored in the Nth location in
587 * the array where N starts at 0.
592 ino_tree_node_t
*irec
,
603 if (full_ino_ex_data
)
604 ptbl
= irec
->ino_un
.ex_data
->parents
;
606 ptbl
= irec
->ino_un
.plist
;
609 ptbl
= (parent_list_t
*)malloc(sizeof(parent_list_t
));
611 do_error(_("couldn't malloc parent list table\n"));
613 if (full_ino_ex_data
)
614 irec
->ino_un
.ex_data
->parents
= ptbl
;
616 irec
->ino_un
.plist
= ptbl
;
618 ptbl
->pmask
= 1ULL << offset
;
619 ptbl
->pentries
= (xfs_ino_t
*)memalign(sizeof(xfs_ino_t
),
622 do_error(_("couldn't memalign pentries table\n"));
626 ptbl
->pentries
[0] = parent
;
631 if (ptbl
->pmask
& (1ULL << offset
)) {
635 for (i
= 0; i
< offset
; i
++) {
636 if (ptbl
->pmask
& bitmask
)
641 ASSERT(target
< ptbl
->cnt
);
643 ptbl
->pentries
[target
] = parent
;
651 for (i
= 0; i
< XFS_INODES_PER_CHUNK
; i
++) {
652 if (ptbl
->pmask
& bitmask
) {
662 ASSERT(cnt
== ptbl
->cnt
);
664 ASSERT(cnt
>= target
);
666 tmp
= (xfs_ino_t
*)memalign(sizeof(xfs_ino_t
), (cnt
+ 1) * sizeof(xfs_ino_t
));
668 do_error(_("couldn't memalign pentries table\n"));
670 memmove(tmp
, ptbl
->pentries
, target
* sizeof(parent_entry_t
));
673 memmove(tmp
+ target
+ 1, ptbl
->pentries
+ target
,
674 (cnt
- target
) * sizeof(parent_entry_t
));
676 free(ptbl
->pentries
);
678 ptbl
->pentries
= tmp
;
683 ptbl
->pentries
[target
] = parent
;
684 ptbl
->pmask
|= (1ULL << offset
);
688 get_inode_parent(ino_tree_node_t
*irec
, int offset
)
695 if (full_ino_ex_data
)
696 ptbl
= irec
->ino_un
.ex_data
->parents
;
698 ptbl
= irec
->ino_un
.plist
;
700 if (ptbl
->pmask
& (1ULL << offset
)) {
704 for (i
= 0; i
< offset
; i
++) {
705 if (ptbl
->pmask
& bitmask
)
710 ASSERT(target
< ptbl
->cnt
);
712 return(ptbl
->pentries
[target
]);
719 alloc_ex_data(ino_tree_node_t
*irec
)
723 ptbl
= irec
->ino_un
.plist
;
724 irec
->ino_un
.ex_data
= (ino_ex_data_t
*)calloc(1, sizeof(ino_ex_data_t
));
725 if (irec
->ino_un
.ex_data
== NULL
)
726 do_error(_("could not malloc inode extra data\n"));
728 irec
->ino_un
.ex_data
->parents
= ptbl
;
730 switch (irec
->nlink_size
) {
731 case sizeof(uint8_t):
732 irec
->ino_un
.ex_data
->counted_nlinks
.un8
=
733 alloc_nlink_array(irec
->nlink_size
);
735 case sizeof(uint16_t):
736 irec
->ino_un
.ex_data
->counted_nlinks
.un16
=
737 alloc_nlink_array(irec
->nlink_size
);
739 case sizeof(uint32_t):
740 irec
->ino_un
.ex_data
->counted_nlinks
.un32
=
741 alloc_nlink_array(irec
->nlink_size
);
749 add_ino_ex_data(xfs_mount_t
*mp
)
751 ino_tree_node_t
*ino_rec
;
754 for (i
= 0; i
< mp
->m_sb
.sb_agcount
; i
++) {
755 ino_rec
= findfirst_inode_rec(i
);
757 while (ino_rec
!= NULL
) {
758 alloc_ex_data(ino_rec
);
759 ino_rec
= next_ino_rec(ino_rec
);
762 full_ino_ex_data
= 1;
766 avl_ino_start(avlnode_t
*node
)
768 return((uintptr_t) ((ino_tree_node_t
*) node
)->ino_startnum
);
772 avl_ino_end(avlnode_t
*node
)
775 ((ino_tree_node_t
*) node
)->ino_startnum
+
776 XFS_INODES_PER_CHUNK
));
779 avlops_t avl_ino_tree_ops
= {
785 incore_ino_init(xfs_mount_t
*mp
)
788 int agcount
= mp
->m_sb
.sb_agcount
;
790 if ((inode_tree_ptrs
= malloc(agcount
*
791 sizeof(avltree_desc_t
*))) == NULL
)
792 do_error(_("couldn't malloc inode tree descriptor table\n"));
793 if ((inode_uncertain_tree_ptrs
= malloc(agcount
*
794 sizeof(avltree_desc_t
*))) == NULL
)
796 _("couldn't malloc uncertain ino tree descriptor table\n"));
798 for (i
= 0; i
< agcount
; i
++) {
799 if ((inode_tree_ptrs
[i
] =
800 malloc(sizeof(avltree_desc_t
))) == NULL
)
801 do_error(_("couldn't malloc inode tree descriptor\n"));
802 if ((inode_uncertain_tree_ptrs
[i
] =
803 malloc(sizeof(avltree_desc_t
))) == NULL
)
805 _("couldn't malloc uncertain ino tree descriptor\n"));
807 for (i
= 0; i
< agcount
; i
++) {
808 avl_init_tree(inode_tree_ptrs
[i
], &avl_ino_tree_ops
);
809 avl_init_tree(inode_uncertain_tree_ptrs
[i
], &avl_ino_tree_ops
);
812 if ((last_rec
= malloc(sizeof(ino_tree_node_t
*) * agcount
)) == NULL
)
813 do_error(_("couldn't malloc uncertain inode cache area\n"));
815 memset(last_rec
, 0, sizeof(ino_tree_node_t
*) * agcount
);
817 full_ino_ex_data
= 0;