]>
Commit | Line | Data |
---|---|---|
959ef981 | 1 | // SPDX-License-Identifier: GPL-2.0 |
2bd0ea18 | 2 | /* |
610f3285 | 3 | * Copyright (c) 2000-2001,2005,2008 Silicon Graphics, Inc. |
da23017d | 4 | * All Rights Reserved. |
2bd0ea18 NS |
5 | */ |
6 | ||
6b803e5a | 7 | #include "libxfs.h" |
2bd0ea18 NS |
8 | #include "err_protos.h" |
9 | #include "bmap.h" | |
10 | ||
11 | /* | |
610f3285 BN |
12 | * Track the logical to physical block mapping for inodes. |
13 | * | |
14 | * Repair only processes one inode at a given time per thread, and the | |
15 | * block map does not have to outlive the processing of a single inode. | |
16 | * | |
17 | * The combination of those factors means we can use pthreads thread-local | |
18 | * storage to store the block map, and we can re-use the allocation over | |
19 | * and over again. | |
2bd0ea18 | 20 | */ |
2bd0ea18 | 21 | |
610f3285 BN |
22 | pthread_key_t dblkmap_key; |
23 | pthread_key_t ablkmap_key; | |
2bd0ea18 | 24 | |
2bd0ea18 NS |
25 | blkmap_t * |
26 | blkmap_alloc( | |
610f3285 BN |
27 | xfs_extnum_t nex, |
28 | int whichfork) | |
2bd0ea18 | 29 | { |
610f3285 | 30 | pthread_key_t key; |
2bd0ea18 NS |
31 | blkmap_t *blkmap; |
32 | ||
610f3285 BN |
33 | ASSERT(whichfork == XFS_DATA_FORK || whichfork == XFS_ATTR_FORK); |
34 | ||
2bd0ea18 NS |
35 | if (nex < 1) |
36 | nex = 1; | |
610f3285 | 37 | |
f8579c03 | 38 | #if (BITS_PER_LONG == 32) /* on 64-bit platforms this is never true */ |
df63c43b | 39 | if (nex > BLKMAP_NEXTS_MAX) { |
df63c43b DC |
40 | do_warn( |
41 | _("Number of extents requested in blkmap_alloc (%d) overflows 32 bits.\n" | |
42 | "If this is not a corruption, then you will need a 64 bit system\n" | |
43 | "to repair this filesystem.\n"), | |
44 | nex); | |
df63c43b DC |
45 | return NULL; |
46 | } | |
f8579c03 | 47 | #endif |
df63c43b | 48 | |
610f3285 BN |
49 | key = whichfork ? ablkmap_key : dblkmap_key; |
50 | blkmap = pthread_getspecific(key); | |
51 | if (!blkmap || blkmap->naexts < nex) { | |
52 | blkmap = realloc(blkmap, BLKMAP_SIZE(nex)); | |
53 | if (!blkmap) { | |
5d1b7f0f | 54 | do_warn(_("malloc failed in blkmap_alloc (%zu bytes)\n"), |
610f3285 BN |
55 | BLKMAP_SIZE(nex)); |
56 | return NULL; | |
57 | } | |
58 | pthread_setspecific(key, blkmap); | |
59 | blkmap->naexts = nex; | |
2bd0ea18 | 60 | } |
610f3285 BN |
61 | |
62 | blkmap->nexts = 0; | |
2bd0ea18 NS |
63 | return blkmap; |
64 | } | |
65 | ||
66 | /* | |
67 | * Free a block map. | |
55d35a39 DC |
68 | * |
69 | * If the map is a large, uncommon size (say for hundreds of thousands of | |
70 | * extents) then free it to release the memory. This prevents us from pinning | |
71 | * large tracts of memory due to corrupted fork values or one-off fragmented | |
72 | * files. Otherwise we have nothing to do but keep the memory around for the | |
bd758142 ES |
73 | * next inode. |
74 | * When the thread is done, it should do an unconditional, final free. | |
2bd0ea18 NS |
75 | */ |
76 | void | |
77 | blkmap_free( | |
78 | blkmap_t *blkmap) | |
79 | { | |
55d35a39 DC |
80 | if (!blkmap) |
81 | return; | |
82 | ||
83 | /* consider more than 100k extents rare */ | |
84 | if (blkmap->naexts < 100 * 1024) | |
85 | return; | |
86 | ||
87 | if (blkmap == pthread_getspecific(dblkmap_key)) | |
88 | pthread_setspecific(dblkmap_key, NULL); | |
89 | else | |
90 | pthread_setspecific(ablkmap_key, NULL); | |
91 | ||
92 | free(blkmap); | |
2bd0ea18 NS |
93 | } |
94 | ||
bd758142 ES |
95 | void |
96 | blkmap_free_final(void) | |
97 | { | |
98 | blkmap_t *blkmap; | |
99 | ||
100 | blkmap = pthread_getspecific(dblkmap_key); | |
101 | pthread_setspecific(dblkmap_key, NULL); | |
102 | free(blkmap); | |
103 | ||
104 | blkmap = pthread_getspecific(ablkmap_key); | |
105 | pthread_setspecific(ablkmap_key, NULL); | |
106 | free(blkmap); | |
107 | } | |
108 | ||
2bd0ea18 NS |
109 | /* |
110 | * Get one entry from a block map. | |
111 | */ | |
5a35bf2c | 112 | xfs_fsblock_t |
2bd0ea18 NS |
113 | blkmap_get( |
114 | blkmap_t *blkmap, | |
5a35bf2c | 115 | xfs_fileoff_t o) |
2bd0ea18 | 116 | { |
610f3285 | 117 | bmap_ext_t *ext = blkmap->exts; |
2bd0ea18 NS |
118 | int i; |
119 | ||
610f3285 BN |
120 | for (i = 0; i < blkmap->nexts; i++, ext++) { |
121 | if (o >= ext->startoff && o < ext->startoff + ext->blockcount) | |
122 | return ext->startblock + (o - ext->startoff); | |
2bd0ea18 | 123 | } |
5a35bf2c | 124 | return NULLFSBLOCK; |
2bd0ea18 NS |
125 | } |
126 | ||
127 | /* | |
610f3285 | 128 | * Get a chunk of entries from a block map - only used for reading dirv2 blocks |
2bd0ea18 NS |
129 | */ |
130 | int | |
131 | blkmap_getn( | |
132 | blkmap_t *blkmap, | |
5a35bf2c DC |
133 | xfs_fileoff_t o, |
134 | xfs_filblks_t nb, | |
1e77098c MV |
135 | bmap_ext_t **bmpp, |
136 | bmap_ext_t *bmpp_single) | |
2bd0ea18 | 137 | { |
610f3285 BN |
138 | bmap_ext_t *bmp = NULL; |
139 | bmap_ext_t *ext; | |
2bd0ea18 NS |
140 | int i; |
141 | int nex; | |
142 | ||
1e77098c | 143 | if (nb == 1) { |
610f3285 | 144 | /* |
1e77098c MV |
145 | * in the common case, when mp->m_dirblkfsbs == 1, |
146 | * avoid additional malloc/free overhead | |
147 | */ | |
148 | bmpp_single->startblock = blkmap_get(blkmap, o); | |
610f3285 | 149 | goto single_ext; |
1e77098c | 150 | } |
610f3285 BN |
151 | ext = blkmap->exts; |
152 | nex = 0; | |
153 | for (i = 0; i < blkmap->nexts; i++, ext++) { | |
154 | ||
155 | if (ext->startoff >= o + nb) | |
2bd0ea18 | 156 | break; |
610f3285 | 157 | if (ext->startoff + ext->blockcount <= o) |
2bd0ea18 | 158 | continue; |
610f3285 BN |
159 | |
160 | /* | |
161 | * if all the requested blocks are in one extent (also common), | |
162 | * use the bmpp_single option as well | |
163 | */ | |
164 | if (!bmp && o >= ext->startoff && | |
165 | o + nb <= ext->startoff + ext->blockcount) { | |
166 | bmpp_single->startblock = | |
167 | ext->startblock + (o - ext->startoff); | |
168 | goto single_ext; | |
2bd0ea18 | 169 | } |
610f3285 BN |
170 | |
171 | /* | |
172 | * rare case - multiple extents for a single dir block | |
173 | */ | |
b220548b ES |
174 | if (!bmp) |
175 | bmp = malloc(nb * sizeof(bmap_ext_t)); | |
610f3285 | 176 | if (!bmp) |
5d1b7f0f | 177 | do_error(_("blkmap_getn malloc failed (%" PRIu64 " bytes)\n"), |
610f3285 BN |
178 | nb * sizeof(bmap_ext_t)); |
179 | ||
180 | bmp[nex].startblock = ext->startblock + (o - ext->startoff); | |
68d16907 | 181 | bmp[nex].blockcount = min(nb, ext->blockcount - |
610f3285 BN |
182 | (bmp[nex].startblock - ext->startblock)); |
183 | o += bmp[nex].blockcount; | |
184 | nb -= bmp[nex].blockcount; | |
185 | nex++; | |
2bd0ea18 NS |
186 | } |
187 | *bmpp = bmp; | |
188 | return nex; | |
2bd0ea18 | 189 | |
610f3285 BN |
190 | single_ext: |
191 | bmpp_single->blockcount = nb; | |
192 | bmpp_single->startoff = 0; /* not even used by caller! */ | |
193 | *bmpp = bmpp_single; | |
5a35bf2c | 194 | return (bmpp_single->startblock != NULLFSBLOCK) ? 1 : 0; |
2bd0ea18 NS |
195 | } |
196 | ||
197 | /* | |
198 | * Return the last offset in a block map. | |
199 | */ | |
5a35bf2c | 200 | xfs_fileoff_t |
2bd0ea18 NS |
201 | blkmap_last_off( |
202 | blkmap_t *blkmap) | |
203 | { | |
610f3285 | 204 | bmap_ext_t *ext; |
2bd0ea18 | 205 | |
610f3285 | 206 | if (!blkmap->nexts) |
5a35bf2c | 207 | return NULLFILEOFF; |
610f3285 BN |
208 | ext = blkmap->exts + blkmap->nexts - 1; |
209 | return ext->startoff + ext->blockcount; | |
2bd0ea18 NS |
210 | } |
211 | ||
22ff57bc ES |
212 | /** |
213 | * blkmap_next_off - Return next logical block offset in a block map. | |
214 | * @blkmap: blockmap to use | |
215 | * @o: current file logical block number | |
216 | * @t: current extent index into blockmap (in/out) | |
217 | * | |
218 | * Given a logical block offset in a file, return the next mapped logical offset | |
219 | * The map index "t" tracks the current extent number in the block map, and | |
220 | * is updated automatically if the returned offset resides within the next | |
221 | * mapped extent. | |
222 | * | |
223 | * If the blockmap contains no extents, or no more logical offsets are mapped, | |
224 | * or the extent index exceeds the number of extents in the map, | |
5a35bf2c | 225 | * return NULLFILEOFF. |
22ff57bc ES |
226 | * |
227 | * If offset o is beyond extent index t, the first offset in the next extent | |
228 | * after extent t will be returned. | |
229 | * | |
230 | * Intended to be called starting with offset 0, index 0, and iterated. | |
2bd0ea18 | 231 | */ |
5a35bf2c | 232 | xfs_fileoff_t |
2bd0ea18 NS |
233 | blkmap_next_off( |
234 | blkmap_t *blkmap, | |
5a35bf2c | 235 | xfs_fileoff_t o, |
2bd0ea18 NS |
236 | int *t) |
237 | { | |
610f3285 | 238 | bmap_ext_t *ext; |
2bd0ea18 | 239 | |
610f3285 | 240 | if (!blkmap->nexts) |
5a35bf2c DC |
241 | return NULLFILEOFF; |
242 | if (o == NULLFILEOFF) { | |
2bd0ea18 | 243 | *t = 0; |
610f3285 | 244 | return blkmap->exts[0].startoff; |
2bd0ea18 | 245 | } |
22ff57bc | 246 | if (*t >= blkmap->nexts) |
5a35bf2c | 247 | return NULLFILEOFF; |
610f3285 BN |
248 | ext = blkmap->exts + *t; |
249 | if (o < ext->startoff + ext->blockcount - 1) | |
2bd0ea18 | 250 | return o + 1; |
22ff57bc | 251 | if (*t == blkmap->nexts - 1) |
5a35bf2c | 252 | return NULLFILEOFF; |
2bd0ea18 | 253 | (*t)++; |
610f3285 | 254 | return ext[1].startoff; |
2bd0ea18 NS |
255 | } |
256 | ||
257 | /* | |
610f3285 | 258 | * Make a block map larger. |
2bd0ea18 | 259 | */ |
610f3285 BN |
260 | static blkmap_t * |
261 | blkmap_grow( | |
75372fed | 262 | blkmap_t *blkmap) |
2bd0ea18 | 263 | { |
610f3285 | 264 | pthread_key_t key = dblkmap_key; |
75372fed | 265 | blkmap_t *new_blkmap; |
bb9ca6c8 DC |
266 | int new_naexts; |
267 | ||
268 | /* reduce the number of reallocations for large files */ | |
269 | if (blkmap->naexts < 1000) | |
270 | new_naexts = blkmap->naexts + 4; | |
271 | else if (blkmap->naexts < 10000) | |
272 | new_naexts = blkmap->naexts + 100; | |
273 | else | |
274 | new_naexts = blkmap->naexts + 1000; | |
2bd0ea18 | 275 | |
610f3285 BN |
276 | if (pthread_getspecific(key) != blkmap) { |
277 | key = ablkmap_key; | |
278 | ASSERT(pthread_getspecific(key) == blkmap); | |
2bd0ea18 | 279 | } |
610f3285 | 280 | |
f8579c03 | 281 | #if (BITS_PER_LONG == 32) /* on 64-bit platforms this is never true */ |
df63c43b | 282 | if (new_naexts > BLKMAP_NEXTS_MAX) { |
df63c43b DC |
283 | do_error( |
284 | _("Number of extents requested in blkmap_grow (%d) overflows 32 bits.\n" | |
285 | "You need a 64 bit system to repair this filesystem.\n"), | |
286 | new_naexts); | |
df63c43b DC |
287 | return NULL; |
288 | } | |
f8579c03 | 289 | #endif |
df63c43b DC |
290 | if (new_naexts <= 0) { |
291 | do_error( | |
292 | _("Number of extents requested in blkmap_grow (%d) overflowed the\n" | |
293 | "maximum number of supported extents (%d).\n"), | |
294 | new_naexts, BLKMAP_NEXTS_MAX); | |
295 | return NULL; | |
296 | } | |
297 | ||
75372fed DC |
298 | new_blkmap = realloc(blkmap, BLKMAP_SIZE(new_naexts)); |
299 | if (!new_blkmap) { | |
610f3285 | 300 | do_error(_("realloc failed in blkmap_grow\n")); |
75372fed DC |
301 | return NULL; |
302 | } | |
303 | new_blkmap->naexts = new_naexts; | |
304 | pthread_setspecific(key, new_blkmap); | |
305 | return new_blkmap; | |
2bd0ea18 NS |
306 | } |
307 | ||
308 | /* | |
309 | * Set an extent into a block map. | |
75372fed DC |
310 | * |
311 | * If this function fails, it leaves the blkmapp untouched so the caller can | |
312 | * handle the error and free the blkmap appropriately. | |
2bd0ea18 | 313 | */ |
75372fed | 314 | int |
2bd0ea18 NS |
315 | blkmap_set_ext( |
316 | blkmap_t **blkmapp, | |
5a35bf2c DC |
317 | xfs_fileoff_t o, |
318 | xfs_fsblock_t b, | |
319 | xfs_filblks_t c) | |
2bd0ea18 | 320 | { |
610f3285 | 321 | blkmap_t *blkmap = *blkmapp; |
2bd0ea18 NS |
322 | xfs_extnum_t i; |
323 | ||
75372fed DC |
324 | if (blkmap->nexts == blkmap->naexts) { |
325 | blkmap = blkmap_grow(blkmap); | |
326 | if (!blkmap) | |
327 | return ENOMEM; | |
328 | *blkmapp = blkmap; | |
329 | } | |
2bd0ea18 | 330 | |
75372fed | 331 | ASSERT(blkmap->nexts < blkmap->naexts); |
bb9ca6c8 DC |
332 | |
333 | if (blkmap->nexts == 0) { | |
334 | i = 0; | |
335 | goto insert; | |
336 | } | |
337 | ||
338 | /* | |
339 | * The most common insert pattern comes from an ascending offset order | |
340 | * bmapbt scan. In this case, the extent being added will end up at the | |
341 | * end of the array. Hence do a reverse order search for the insertion | |
342 | * point so we don't needlessly scan the entire array on every | |
343 | * insertion. | |
344 | * | |
345 | * Also, use "plus 1" indexing for the loop counter so when we break out | |
346 | * of the loop we are at the correct index for insertion. | |
347 | */ | |
348 | for (i = blkmap->nexts; i > 0; i--) { | |
349 | if (blkmap->exts[i - 1].startoff < o) | |
610f3285 | 350 | break; |
610f3285 | 351 | } |
2bd0ea18 | 352 | |
bb9ca6c8 DC |
353 | /* make space for the new extent */ |
354 | memmove(blkmap->exts + i + 1, | |
355 | blkmap->exts + i, | |
356 | sizeof(bmap_ext_t) * (blkmap->nexts - i)); | |
357 | ||
358 | insert: | |
610f3285 BN |
359 | blkmap->exts[i].startoff = o; |
360 | blkmap->exts[i].startblock = b; | |
361 | blkmap->exts[i].blockcount = c; | |
362 | blkmap->nexts++; | |
75372fed | 363 | return 0; |
2bd0ea18 | 364 | } |