Commit | Line | Data |
---|---|---|
3f3b442b KK |
1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* | |
3 | * | |
4 | * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved. | |
5 | * | |
6 | * This code builds two trees of free clusters extents. | |
7 | * Trees are sorted by start of extent and by length of extent. | |
8 | * NTFS_MAX_WND_EXTENTS defines the maximum number of elements in trees. | |
e8b8e97f | 9 | * In extreme case code reads on-disk bitmap to find free clusters. |
3f3b442b KK |
10 | * |
11 | */ | |
12 | ||
3f3b442b KK |
13 | #include <linux/buffer_head.h> |
14 | #include <linux/fs.h> | |
6e3331ee | 15 | #include <linux/kernel.h> |
3f3b442b | 16 | |
3f3b442b KK |
17 | #include "ntfs.h" |
18 | #include "ntfs_fs.h" | |
19 | ||
20 | /* | |
21 | * Maximum number of extents in tree. | |
22 | */ | |
23 | #define NTFS_MAX_WND_EXTENTS (32u * 1024u) | |
24 | ||
25 | struct rb_node_key { | |
26 | struct rb_node node; | |
27 | size_t key; | |
28 | }; | |
29 | ||
3f3b442b | 30 | struct e_node { |
e8b8e97f KA |
31 | struct rb_node_key start; /* Tree sorted by start. */ |
32 | struct rb_node_key count; /* Tree sorted by len. */ | |
3f3b442b KK |
33 | }; |
34 | ||
35 | static int wnd_rescan(struct wnd_bitmap *wnd); | |
36 | static struct buffer_head *wnd_map(struct wnd_bitmap *wnd, size_t iw); | |
37 | static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits); | |
38 | ||
39 | static struct kmem_cache *ntfs_enode_cachep; | |
40 | ||
41 | int __init ntfs3_init_bitmap(void) | |
42 | { | |
43 | ntfs_enode_cachep = | |
44 | kmem_cache_create("ntfs3_enode_cache", sizeof(struct e_node), 0, | |
45 | SLAB_RECLAIM_ACCOUNT, NULL); | |
46 | return ntfs_enode_cachep ? 0 : -ENOMEM; | |
47 | } | |
48 | ||
49 | void ntfs3_exit_bitmap(void) | |
50 | { | |
51 | kmem_cache_destroy(ntfs_enode_cachep); | |
52 | } | |
53 | ||
3f3b442b | 54 | /* |
e8b8e97f KA |
55 | * wnd_scan |
56 | * | |
57 | * b_pos + b_len - biggest fragment. | |
58 | * Scan range [wpos wbits) window @buf. | |
59 | * | |
60 | * Return: -1 if not found. | |
3f3b442b | 61 | */ |
08811ba5 | 62 | static size_t wnd_scan(const void *buf, size_t wbit, u32 wpos, u32 wend, |
3f3b442b KK |
63 | size_t to_alloc, size_t *prev_tail, size_t *b_pos, |
64 | size_t *b_len) | |
65 | { | |
66 | while (wpos < wend) { | |
67 | size_t free_len; | |
68 | u32 free_bits, end; | |
095d8ce6 | 69 | u32 used = find_next_zero_bit_le(buf, wend, wpos); |
3f3b442b KK |
70 | |
71 | if (used >= wend) { | |
72 | if (*b_len < *prev_tail) { | |
73 | *b_pos = wbit - *prev_tail; | |
74 | *b_len = *prev_tail; | |
75 | } | |
76 | ||
77 | *prev_tail = 0; | |
78 | return -1; | |
79 | } | |
80 | ||
81 | if (used > wpos) { | |
82 | wpos = used; | |
83 | if (*b_len < *prev_tail) { | |
84 | *b_pos = wbit - *prev_tail; | |
85 | *b_len = *prev_tail; | |
86 | } | |
87 | ||
88 | *prev_tail = 0; | |
89 | } | |
90 | ||
91 | /* | |
e8b8e97f | 92 | * Now we have a fragment [wpos, wend) staring with 0. |
3f3b442b KK |
93 | */ |
94 | end = wpos + to_alloc - *prev_tail; | |
095d8ce6 | 95 | free_bits = find_next_bit_le(buf, min(end, wend), wpos); |
3f3b442b KK |
96 | |
97 | free_len = *prev_tail + free_bits - wpos; | |
98 | ||
99 | if (*b_len < free_len) { | |
100 | *b_pos = wbit + wpos - *prev_tail; | |
101 | *b_len = free_len; | |
102 | } | |
103 | ||
104 | if (free_len >= to_alloc) | |
105 | return wbit + wpos - *prev_tail; | |
106 | ||
107 | if (free_bits >= wend) { | |
108 | *prev_tail += free_bits - wpos; | |
109 | return -1; | |
110 | } | |
111 | ||
112 | wpos = free_bits + 1; | |
113 | ||
114 | *prev_tail = 0; | |
115 | } | |
116 | ||
117 | return -1; | |
118 | } | |
119 | ||
120 | /* | |
e8b8e97f | 121 | * wnd_close - Frees all resources. |
3f3b442b KK |
122 | */ |
123 | void wnd_close(struct wnd_bitmap *wnd) | |
124 | { | |
125 | struct rb_node *node, *next; | |
126 | ||
195c52bd | 127 | kfree(wnd->free_bits); |
3f3b442b KK |
128 | run_close(&wnd->run); |
129 | ||
130 | node = rb_first(&wnd->start_tree); | |
131 | ||
132 | while (node) { | |
133 | next = rb_next(node); | |
134 | rb_erase(node, &wnd->start_tree); | |
135 | kmem_cache_free(ntfs_enode_cachep, | |
136 | rb_entry(node, struct e_node, start.node)); | |
137 | node = next; | |
138 | } | |
139 | } | |
140 | ||
141 | static struct rb_node *rb_lookup(struct rb_root *root, size_t v) | |
142 | { | |
143 | struct rb_node **p = &root->rb_node; | |
144 | struct rb_node *r = NULL; | |
145 | ||
146 | while (*p) { | |
147 | struct rb_node_key *k; | |
148 | ||
149 | k = rb_entry(*p, struct rb_node_key, node); | |
150 | if (v < k->key) { | |
151 | p = &(*p)->rb_left; | |
152 | } else if (v > k->key) { | |
153 | r = &k->node; | |
154 | p = &(*p)->rb_right; | |
155 | } else { | |
156 | return &k->node; | |
157 | } | |
158 | } | |
159 | ||
160 | return r; | |
161 | } | |
162 | ||
163 | /* | |
e8b8e97f | 164 | * rb_insert_count - Helper function to insert special kind of 'count' tree. |
3f3b442b KK |
165 | */ |
166 | static inline bool rb_insert_count(struct rb_root *root, struct e_node *e) | |
167 | { | |
168 | struct rb_node **p = &root->rb_node; | |
169 | struct rb_node *parent = NULL; | |
170 | size_t e_ckey = e->count.key; | |
171 | size_t e_skey = e->start.key; | |
172 | ||
173 | while (*p) { | |
174 | struct e_node *k = | |
175 | rb_entry(parent = *p, struct e_node, count.node); | |
176 | ||
177 | if (e_ckey > k->count.key) { | |
178 | p = &(*p)->rb_left; | |
179 | } else if (e_ckey < k->count.key) { | |
180 | p = &(*p)->rb_right; | |
181 | } else if (e_skey < k->start.key) { | |
182 | p = &(*p)->rb_left; | |
183 | } else if (e_skey > k->start.key) { | |
184 | p = &(*p)->rb_right; | |
185 | } else { | |
186 | WARN_ON(1); | |
187 | return false; | |
188 | } | |
189 | } | |
190 | ||
191 | rb_link_node(&e->count.node, parent, p); | |
192 | rb_insert_color(&e->count.node, root); | |
193 | return true; | |
194 | } | |
195 | ||
196 | /* | |
e8b8e97f | 197 | * rb_insert_start - Helper function to insert special kind of 'count' tree. |
3f3b442b KK |
198 | */ |
199 | static inline bool rb_insert_start(struct rb_root *root, struct e_node *e) | |
200 | { | |
201 | struct rb_node **p = &root->rb_node; | |
202 | struct rb_node *parent = NULL; | |
203 | size_t e_skey = e->start.key; | |
204 | ||
205 | while (*p) { | |
206 | struct e_node *k; | |
207 | ||
208 | parent = *p; | |
209 | ||
210 | k = rb_entry(parent, struct e_node, start.node); | |
211 | if (e_skey < k->start.key) { | |
212 | p = &(*p)->rb_left; | |
213 | } else if (e_skey > k->start.key) { | |
214 | p = &(*p)->rb_right; | |
215 | } else { | |
216 | WARN_ON(1); | |
217 | return false; | |
218 | } | |
219 | } | |
220 | ||
221 | rb_link_node(&e->start.node, parent, p); | |
222 | rb_insert_color(&e->start.node, root); | |
223 | return true; | |
224 | } | |
225 | ||
226 | /* | |
e8b8e97f KA |
227 | * wnd_add_free_ext - Adds a new extent of free space. |
228 | * @build: 1 when building tree. | |
3f3b442b KK |
229 | */ |
230 | static void wnd_add_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len, | |
231 | bool build) | |
232 | { | |
233 | struct e_node *e, *e0 = NULL; | |
234 | size_t ib, end_in = bit + len; | |
235 | struct rb_node *n; | |
236 | ||
237 | if (build) { | |
e8b8e97f | 238 | /* Use extent_min to filter too short extents. */ |
3f3b442b KK |
239 | if (wnd->count >= NTFS_MAX_WND_EXTENTS && |
240 | len <= wnd->extent_min) { | |
241 | wnd->uptodated = -1; | |
242 | return; | |
243 | } | |
244 | } else { | |
e8b8e97f | 245 | /* Try to find extent before 'bit'. */ |
3f3b442b KK |
246 | n = rb_lookup(&wnd->start_tree, bit); |
247 | ||
248 | if (!n) { | |
249 | n = rb_first(&wnd->start_tree); | |
250 | } else { | |
251 | e = rb_entry(n, struct e_node, start.node); | |
252 | n = rb_next(n); | |
253 | if (e->start.key + e->count.key == bit) { | |
e8b8e97f | 254 | /* Remove left. */ |
3f3b442b KK |
255 | bit = e->start.key; |
256 | len += e->count.key; | |
257 | rb_erase(&e->start.node, &wnd->start_tree); | |
258 | rb_erase(&e->count.node, &wnd->count_tree); | |
259 | wnd->count -= 1; | |
260 | e0 = e; | |
261 | } | |
262 | } | |
263 | ||
264 | while (n) { | |
265 | size_t next_end; | |
266 | ||
267 | e = rb_entry(n, struct e_node, start.node); | |
268 | next_end = e->start.key + e->count.key; | |
269 | if (e->start.key > end_in) | |
270 | break; | |
271 | ||
e8b8e97f | 272 | /* Remove right. */ |
3f3b442b KK |
273 | n = rb_next(n); |
274 | len += next_end - end_in; | |
275 | end_in = next_end; | |
276 | rb_erase(&e->start.node, &wnd->start_tree); | |
277 | rb_erase(&e->count.node, &wnd->count_tree); | |
278 | wnd->count -= 1; | |
279 | ||
280 | if (!e0) | |
281 | e0 = e; | |
282 | else | |
283 | kmem_cache_free(ntfs_enode_cachep, e); | |
284 | } | |
285 | ||
286 | if (wnd->uptodated != 1) { | |
e8b8e97f | 287 | /* Check bits before 'bit'. */ |
3f3b442b KK |
288 | ib = wnd->zone_bit == wnd->zone_end || |
289 | bit < wnd->zone_end | |
290 | ? 0 | |
291 | : wnd->zone_end; | |
292 | ||
293 | while (bit > ib && wnd_is_free_hlp(wnd, bit - 1, 1)) { | |
294 | bit -= 1; | |
295 | len += 1; | |
296 | } | |
297 | ||
e8b8e97f | 298 | /* Check bits after 'end_in'. */ |
3f3b442b KK |
299 | ib = wnd->zone_bit == wnd->zone_end || |
300 | end_in > wnd->zone_bit | |
301 | ? wnd->nbits | |
302 | : wnd->zone_bit; | |
303 | ||
304 | while (end_in < ib && wnd_is_free_hlp(wnd, end_in, 1)) { | |
305 | end_in += 1; | |
306 | len += 1; | |
307 | } | |
308 | } | |
309 | } | |
e8b8e97f | 310 | /* Insert new fragment. */ |
3f3b442b KK |
311 | if (wnd->count >= NTFS_MAX_WND_EXTENTS) { |
312 | if (e0) | |
313 | kmem_cache_free(ntfs_enode_cachep, e0); | |
314 | ||
315 | wnd->uptodated = -1; | |
316 | ||
e8b8e97f | 317 | /* Compare with smallest fragment. */ |
3f3b442b KK |
318 | n = rb_last(&wnd->count_tree); |
319 | e = rb_entry(n, struct e_node, count.node); | |
320 | if (len <= e->count.key) | |
e8b8e97f | 321 | goto out; /* Do not insert small fragments. */ |
3f3b442b KK |
322 | |
323 | if (build) { | |
324 | struct e_node *e2; | |
325 | ||
326 | n = rb_prev(n); | |
327 | e2 = rb_entry(n, struct e_node, count.node); | |
e8b8e97f | 328 | /* Smallest fragment will be 'e2->count.key'. */ |
3f3b442b KK |
329 | wnd->extent_min = e2->count.key; |
330 | } | |
331 | ||
e8b8e97f | 332 | /* Replace smallest fragment by new one. */ |
3f3b442b KK |
333 | rb_erase(&e->start.node, &wnd->start_tree); |
334 | rb_erase(&e->count.node, &wnd->count_tree); | |
335 | wnd->count -= 1; | |
336 | } else { | |
337 | e = e0 ? e0 : kmem_cache_alloc(ntfs_enode_cachep, GFP_ATOMIC); | |
338 | if (!e) { | |
339 | wnd->uptodated = -1; | |
340 | goto out; | |
341 | } | |
342 | ||
343 | if (build && len <= wnd->extent_min) | |
344 | wnd->extent_min = len; | |
345 | } | |
346 | e->start.key = bit; | |
347 | e->count.key = len; | |
348 | if (len > wnd->extent_max) | |
349 | wnd->extent_max = len; | |
350 | ||
351 | rb_insert_start(&wnd->start_tree, e); | |
352 | rb_insert_count(&wnd->count_tree, e); | |
353 | wnd->count += 1; | |
354 | ||
355 | out:; | |
356 | } | |
357 | ||
358 | /* | |
e8b8e97f | 359 | * wnd_remove_free_ext - Remove a run from the cached free space. |
3f3b442b KK |
360 | */ |
361 | static void wnd_remove_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len) | |
362 | { | |
363 | struct rb_node *n, *n3; | |
364 | struct e_node *e, *e3; | |
365 | size_t end_in = bit + len; | |
366 | size_t end3, end, new_key, new_len, max_new_len; | |
367 | ||
e8b8e97f | 368 | /* Try to find extent before 'bit'. */ |
3f3b442b KK |
369 | n = rb_lookup(&wnd->start_tree, bit); |
370 | ||
371 | if (!n) | |
372 | return; | |
373 | ||
374 | e = rb_entry(n, struct e_node, start.node); | |
375 | end = e->start.key + e->count.key; | |
376 | ||
377 | new_key = new_len = 0; | |
378 | len = e->count.key; | |
379 | ||
e8b8e97f | 380 | /* Range [bit,end_in) must be inside 'e' or outside 'e' and 'n'. */ |
3f3b442b KK |
381 | if (e->start.key > bit) |
382 | ; | |
383 | else if (end_in <= end) { | |
e8b8e97f | 384 | /* Range [bit,end_in) inside 'e'. */ |
3f3b442b KK |
385 | new_key = end_in; |
386 | new_len = end - end_in; | |
387 | len = bit - e->start.key; | |
388 | } else if (bit > end) { | |
389 | bool bmax = false; | |
390 | ||
391 | n3 = rb_next(n); | |
392 | ||
393 | while (n3) { | |
394 | e3 = rb_entry(n3, struct e_node, start.node); | |
395 | if (e3->start.key >= end_in) | |
396 | break; | |
397 | ||
398 | if (e3->count.key == wnd->extent_max) | |
399 | bmax = true; | |
400 | ||
401 | end3 = e3->start.key + e3->count.key; | |
402 | if (end3 > end_in) { | |
403 | e3->start.key = end_in; | |
404 | rb_erase(&e3->count.node, &wnd->count_tree); | |
405 | e3->count.key = end3 - end_in; | |
406 | rb_insert_count(&wnd->count_tree, e3); | |
407 | break; | |
408 | } | |
409 | ||
410 | n3 = rb_next(n3); | |
411 | rb_erase(&e3->start.node, &wnd->start_tree); | |
412 | rb_erase(&e3->count.node, &wnd->count_tree); | |
413 | wnd->count -= 1; | |
414 | kmem_cache_free(ntfs_enode_cachep, e3); | |
415 | } | |
416 | if (!bmax) | |
417 | return; | |
418 | n3 = rb_first(&wnd->count_tree); | |
419 | wnd->extent_max = | |
420 | n3 ? rb_entry(n3, struct e_node, count.node)->count.key | |
421 | : 0; | |
422 | return; | |
423 | } | |
424 | ||
425 | if (e->count.key != wnd->extent_max) { | |
426 | ; | |
427 | } else if (rb_prev(&e->count.node)) { | |
428 | ; | |
429 | } else { | |
430 | n3 = rb_next(&e->count.node); | |
6e3331ee | 431 | max_new_len = max(len, new_len); |
3f3b442b KK |
432 | if (!n3) { |
433 | wnd->extent_max = max_new_len; | |
434 | } else { | |
435 | e3 = rb_entry(n3, struct e_node, count.node); | |
436 | wnd->extent_max = max(e3->count.key, max_new_len); | |
437 | } | |
438 | } | |
439 | ||
440 | if (!len) { | |
441 | if (new_len) { | |
442 | e->start.key = new_key; | |
443 | rb_erase(&e->count.node, &wnd->count_tree); | |
444 | e->count.key = new_len; | |
445 | rb_insert_count(&wnd->count_tree, e); | |
446 | } else { | |
447 | rb_erase(&e->start.node, &wnd->start_tree); | |
448 | rb_erase(&e->count.node, &wnd->count_tree); | |
449 | wnd->count -= 1; | |
450 | kmem_cache_free(ntfs_enode_cachep, e); | |
451 | } | |
452 | goto out; | |
453 | } | |
454 | rb_erase(&e->count.node, &wnd->count_tree); | |
455 | e->count.key = len; | |
456 | rb_insert_count(&wnd->count_tree, e); | |
457 | ||
458 | if (!new_len) | |
459 | goto out; | |
460 | ||
461 | if (wnd->count >= NTFS_MAX_WND_EXTENTS) { | |
462 | wnd->uptodated = -1; | |
463 | ||
e8b8e97f | 464 | /* Get minimal extent. */ |
3f3b442b KK |
465 | e = rb_entry(rb_last(&wnd->count_tree), struct e_node, |
466 | count.node); | |
467 | if (e->count.key > new_len) | |
468 | goto out; | |
469 | ||
e8b8e97f | 470 | /* Replace minimum. */ |
3f3b442b KK |
471 | rb_erase(&e->start.node, &wnd->start_tree); |
472 | rb_erase(&e->count.node, &wnd->count_tree); | |
473 | wnd->count -= 1; | |
474 | } else { | |
475 | e = kmem_cache_alloc(ntfs_enode_cachep, GFP_ATOMIC); | |
476 | if (!e) | |
477 | wnd->uptodated = -1; | |
478 | } | |
479 | ||
480 | if (e) { | |
481 | e->start.key = new_key; | |
482 | e->count.key = new_len; | |
483 | rb_insert_start(&wnd->start_tree, e); | |
484 | rb_insert_count(&wnd->count_tree, e); | |
485 | wnd->count += 1; | |
486 | } | |
487 | ||
488 | out: | |
489 | if (!wnd->count && 1 != wnd->uptodated) | |
490 | wnd_rescan(wnd); | |
491 | } | |
492 | ||
493 | /* | |
e8b8e97f | 494 | * wnd_rescan - Scan all bitmap. Used while initialization. |
3f3b442b KK |
495 | */ |
496 | static int wnd_rescan(struct wnd_bitmap *wnd) | |
497 | { | |
498 | int err = 0; | |
499 | size_t prev_tail = 0; | |
500 | struct super_block *sb = wnd->sb; | |
501 | struct ntfs_sb_info *sbi = sb->s_fs_info; | |
502 | u64 lbo, len = 0; | |
503 | u32 blocksize = sb->s_blocksize; | |
504 | u8 cluster_bits = sbi->cluster_bits; | |
505 | u32 wbits = 8 * sb->s_blocksize; | |
506 | u32 used, frb; | |
3f3b442b KK |
507 | size_t wpos, wbit, iw, vbo; |
508 | struct buffer_head *bh = NULL; | |
509 | CLST lcn, clen; | |
510 | ||
511 | wnd->uptodated = 0; | |
512 | wnd->extent_max = 0; | |
513 | wnd->extent_min = MINUS_ONE_T; | |
514 | wnd->total_zeroes = 0; | |
515 | ||
516 | vbo = 0; | |
517 | ||
518 | for (iw = 0; iw < wnd->nwnd; iw++) { | |
519 | if (iw + 1 == wnd->nwnd) | |
520 | wbits = wnd->bits_last; | |
521 | ||
522 | if (wnd->inited) { | |
523 | if (!wnd->free_bits[iw]) { | |
e8b8e97f | 524 | /* All ones. */ |
3f3b442b KK |
525 | if (prev_tail) { |
526 | wnd_add_free_ext(wnd, | |
527 | vbo * 8 - prev_tail, | |
528 | prev_tail, true); | |
529 | prev_tail = 0; | |
530 | } | |
531 | goto next_wnd; | |
532 | } | |
533 | if (wbits == wnd->free_bits[iw]) { | |
e8b8e97f | 534 | /* All zeroes. */ |
3f3b442b KK |
535 | prev_tail += wbits; |
536 | wnd->total_zeroes += wbits; | |
537 | goto next_wnd; | |
538 | } | |
539 | } | |
540 | ||
541 | if (!len) { | |
542 | u32 off = vbo & sbi->cluster_mask; | |
543 | ||
544 | if (!run_lookup_entry(&wnd->run, vbo >> cluster_bits, | |
545 | &lcn, &clen, NULL)) { | |
546 | err = -ENOENT; | |
547 | goto out; | |
548 | } | |
549 | ||
550 | lbo = ((u64)lcn << cluster_bits) + off; | |
551 | len = ((u64)clen << cluster_bits) - off; | |
552 | } | |
553 | ||
554 | bh = ntfs_bread(sb, lbo >> sb->s_blocksize_bits); | |
555 | if (!bh) { | |
556 | err = -EIO; | |
557 | goto out; | |
558 | } | |
559 | ||
08811ba5 | 560 | used = ntfs_bitmap_weight_le(bh->b_data, wbits); |
3f3b442b KK |
561 | if (used < wbits) { |
562 | frb = wbits - used; | |
563 | wnd->free_bits[iw] = frb; | |
564 | wnd->total_zeroes += frb; | |
565 | } | |
566 | ||
567 | wpos = 0; | |
568 | wbit = vbo * 8; | |
569 | ||
570 | if (wbit + wbits > wnd->nbits) | |
571 | wbits = wnd->nbits - wbit; | |
572 | ||
573 | do { | |
08811ba5 | 574 | used = find_next_zero_bit_le(bh->b_data, wbits, wpos); |
3f3b442b KK |
575 | |
576 | if (used > wpos && prev_tail) { | |
577 | wnd_add_free_ext(wnd, wbit + wpos - prev_tail, | |
578 | prev_tail, true); | |
579 | prev_tail = 0; | |
580 | } | |
581 | ||
582 | wpos = used; | |
583 | ||
584 | if (wpos >= wbits) { | |
e8b8e97f | 585 | /* No free blocks. */ |
3f3b442b KK |
586 | prev_tail = 0; |
587 | break; | |
588 | } | |
589 | ||
08811ba5 | 590 | frb = find_next_bit_le(bh->b_data, wbits, wpos); |
3f3b442b | 591 | if (frb >= wbits) { |
e8b8e97f | 592 | /* Keep last free block. */ |
3f3b442b KK |
593 | prev_tail += frb - wpos; |
594 | break; | |
595 | } | |
596 | ||
597 | wnd_add_free_ext(wnd, wbit + wpos - prev_tail, | |
598 | frb + prev_tail - wpos, true); | |
599 | ||
e8b8e97f | 600 | /* Skip free block and first '1'. */ |
3f3b442b | 601 | wpos = frb + 1; |
e8b8e97f | 602 | /* Reset previous tail. */ |
3f3b442b KK |
603 | prev_tail = 0; |
604 | } while (wpos < wbits); | |
605 | ||
606 | next_wnd: | |
607 | ||
608 | if (bh) | |
609 | put_bh(bh); | |
610 | bh = NULL; | |
611 | ||
612 | vbo += blocksize; | |
613 | if (len) { | |
614 | len -= blocksize; | |
615 | lbo += blocksize; | |
616 | } | |
617 | } | |
618 | ||
e8b8e97f | 619 | /* Add last block. */ |
3f3b442b KK |
620 | if (prev_tail) |
621 | wnd_add_free_ext(wnd, wnd->nbits - prev_tail, prev_tail, true); | |
622 | ||
623 | /* | |
e8b8e97f | 624 | * Before init cycle wnd->uptodated was 0. |
3f3b442b | 625 | * If any errors or limits occurs while initialization then |
e8b8e97f KA |
626 | * wnd->uptodated will be -1. |
627 | * If 'uptodated' is still 0 then Tree is really updated. | |
3f3b442b KK |
628 | */ |
629 | if (!wnd->uptodated) | |
630 | wnd->uptodated = 1; | |
631 | ||
632 | if (wnd->zone_bit != wnd->zone_end) { | |
633 | size_t zlen = wnd->zone_end - wnd->zone_bit; | |
634 | ||
635 | wnd->zone_end = wnd->zone_bit; | |
636 | wnd_zone_set(wnd, wnd->zone_bit, zlen); | |
637 | } | |
638 | ||
639 | out: | |
640 | return err; | |
641 | } | |
642 | ||
3f3b442b KK |
643 | int wnd_init(struct wnd_bitmap *wnd, struct super_block *sb, size_t nbits) |
644 | { | |
645 | int err; | |
646 | u32 blocksize = sb->s_blocksize; | |
647 | u32 wbits = blocksize * 8; | |
648 | ||
649 | init_rwsem(&wnd->rw_lock); | |
650 | ||
651 | wnd->sb = sb; | |
652 | wnd->nbits = nbits; | |
653 | wnd->total_zeroes = nbits; | |
654 | wnd->extent_max = MINUS_ONE_T; | |
655 | wnd->zone_bit = wnd->zone_end = 0; | |
656 | wnd->nwnd = bytes_to_block(sb, bitmap_size(nbits)); | |
657 | wnd->bits_last = nbits & (wbits - 1); | |
658 | if (!wnd->bits_last) | |
659 | wnd->bits_last = wbits; | |
660 | ||
0d0f659b | 661 | wnd->free_bits = kcalloc(wnd->nwnd, sizeof(u16), GFP_NOFS | __GFP_NOWARN); |
3f3b442b KK |
662 | if (!wnd->free_bits) |
663 | return -ENOMEM; | |
664 | ||
665 | err = wnd_rescan(wnd); | |
666 | if (err) | |
667 | return err; | |
668 | ||
669 | wnd->inited = true; | |
670 | ||
671 | return 0; | |
672 | } | |
673 | ||
674 | /* | |
e8b8e97f | 675 | * wnd_map - Call sb_bread for requested window. |
3f3b442b KK |
676 | */ |
677 | static struct buffer_head *wnd_map(struct wnd_bitmap *wnd, size_t iw) | |
678 | { | |
679 | size_t vbo; | |
680 | CLST lcn, clen; | |
681 | struct super_block *sb = wnd->sb; | |
682 | struct ntfs_sb_info *sbi; | |
683 | struct buffer_head *bh; | |
684 | u64 lbo; | |
685 | ||
686 | sbi = sb->s_fs_info; | |
687 | vbo = (u64)iw << sb->s_blocksize_bits; | |
688 | ||
689 | if (!run_lookup_entry(&wnd->run, vbo >> sbi->cluster_bits, &lcn, &clen, | |
690 | NULL)) { | |
691 | return ERR_PTR(-ENOENT); | |
692 | } | |
693 | ||
694 | lbo = ((u64)lcn << sbi->cluster_bits) + (vbo & sbi->cluster_mask); | |
695 | ||
696 | bh = ntfs_bread(wnd->sb, lbo >> sb->s_blocksize_bits); | |
697 | if (!bh) | |
698 | return ERR_PTR(-EIO); | |
699 | ||
700 | return bh; | |
701 | } | |
702 | ||
703 | /* | |
e8b8e97f | 704 | * wnd_set_free - Mark the bits range from bit to bit + bits as free. |
3f3b442b KK |
705 | */ |
706 | int wnd_set_free(struct wnd_bitmap *wnd, size_t bit, size_t bits) | |
707 | { | |
708 | int err = 0; | |
709 | struct super_block *sb = wnd->sb; | |
710 | size_t bits0 = bits; | |
711 | u32 wbits = 8 * sb->s_blocksize; | |
712 | size_t iw = bit >> (sb->s_blocksize_bits + 3); | |
713 | u32 wbit = bit & (wbits - 1); | |
714 | struct buffer_head *bh; | |
715 | ||
716 | while (iw < wnd->nwnd && bits) { | |
717 | u32 tail, op; | |
3f3b442b KK |
718 | |
719 | if (iw + 1 == wnd->nwnd) | |
720 | wbits = wnd->bits_last; | |
721 | ||
722 | tail = wbits - wbit; | |
6e3331ee | 723 | op = min_t(u32, tail, bits); |
3f3b442b KK |
724 | |
725 | bh = wnd_map(wnd, iw); | |
726 | if (IS_ERR(bh)) { | |
727 | err = PTR_ERR(bh); | |
728 | break; | |
729 | } | |
730 | ||
3f3b442b KK |
731 | lock_buffer(bh); |
732 | ||
08811ba5 | 733 | ntfs_bitmap_clear_le(bh->b_data, wbit, op); |
3f3b442b KK |
734 | |
735 | wnd->free_bits[iw] += op; | |
736 | ||
737 | set_buffer_uptodate(bh); | |
738 | mark_buffer_dirty(bh); | |
739 | unlock_buffer(bh); | |
740 | put_bh(bh); | |
741 | ||
742 | wnd->total_zeroes += op; | |
743 | bits -= op; | |
744 | wbit = 0; | |
745 | iw += 1; | |
746 | } | |
747 | ||
748 | wnd_add_free_ext(wnd, bit, bits0, false); | |
749 | ||
750 | return err; | |
751 | } | |
752 | ||
753 | /* | |
e8b8e97f | 754 | * wnd_set_used - Mark the bits range from bit to bit + bits as used. |
3f3b442b KK |
755 | */ |
756 | int wnd_set_used(struct wnd_bitmap *wnd, size_t bit, size_t bits) | |
757 | { | |
758 | int err = 0; | |
759 | struct super_block *sb = wnd->sb; | |
760 | size_t bits0 = bits; | |
761 | size_t iw = bit >> (sb->s_blocksize_bits + 3); | |
762 | u32 wbits = 8 * sb->s_blocksize; | |
763 | u32 wbit = bit & (wbits - 1); | |
764 | struct buffer_head *bh; | |
765 | ||
766 | while (iw < wnd->nwnd && bits) { | |
767 | u32 tail, op; | |
3f3b442b KK |
768 | |
769 | if (unlikely(iw + 1 == wnd->nwnd)) | |
770 | wbits = wnd->bits_last; | |
771 | ||
772 | tail = wbits - wbit; | |
6e3331ee | 773 | op = min_t(u32, tail, bits); |
3f3b442b KK |
774 | |
775 | bh = wnd_map(wnd, iw); | |
776 | if (IS_ERR(bh)) { | |
777 | err = PTR_ERR(bh); | |
778 | break; | |
779 | } | |
3f3b442b KK |
780 | |
781 | lock_buffer(bh); | |
782 | ||
08811ba5 | 783 | ntfs_bitmap_set_le(bh->b_data, wbit, op); |
3f3b442b KK |
784 | wnd->free_bits[iw] -= op; |
785 | ||
786 | set_buffer_uptodate(bh); | |
787 | mark_buffer_dirty(bh); | |
788 | unlock_buffer(bh); | |
789 | put_bh(bh); | |
790 | ||
791 | wnd->total_zeroes -= op; | |
792 | bits -= op; | |
793 | wbit = 0; | |
794 | iw += 1; | |
795 | } | |
796 | ||
797 | if (!RB_EMPTY_ROOT(&wnd->start_tree)) | |
798 | wnd_remove_free_ext(wnd, bit, bits0); | |
799 | ||
800 | return err; | |
801 | } | |
802 | ||
ec5fc720 KK |
803 | /* |
804 | * wnd_set_used_safe - Mark the bits range from bit to bit + bits as used. | |
805 | * | |
806 | * Unlikely wnd_set_used/wnd_set_free this function is not full trusted. | |
807 | * It scans every bit in bitmap and marks free bit as used. | |
808 | * @done - how many bits were marked as used. | |
809 | * | |
810 | * NOTE: normally *done should be 0. | |
811 | */ | |
812 | int wnd_set_used_safe(struct wnd_bitmap *wnd, size_t bit, size_t bits, | |
813 | size_t *done) | |
814 | { | |
815 | size_t i, from = 0, len = 0; | |
816 | int err = 0; | |
817 | ||
818 | *done = 0; | |
819 | for (i = 0; i < bits; i++) { | |
820 | if (wnd_is_free(wnd, bit + i, 1)) { | |
821 | if (!len) | |
822 | from = bit + i; | |
823 | len += 1; | |
824 | } else if (len) { | |
825 | err = wnd_set_used(wnd, from, len); | |
826 | *done += len; | |
827 | len = 0; | |
828 | if (err) | |
829 | break; | |
830 | } | |
831 | } | |
832 | ||
833 | if (len) { | |
834 | /* last fragment. */ | |
835 | err = wnd_set_used(wnd, from, len); | |
836 | *done += len; | |
837 | } | |
838 | return err; | |
839 | } | |
840 | ||
3f3b442b KK |
841 | /* |
842 | * wnd_is_free_hlp | |
843 | * | |
e8b8e97f | 844 | * Return: True if all clusters [bit, bit+bits) are free (bitmap only). |
3f3b442b KK |
845 | */ |
846 | static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits) | |
847 | { | |
848 | struct super_block *sb = wnd->sb; | |
849 | size_t iw = bit >> (sb->s_blocksize_bits + 3); | |
850 | u32 wbits = 8 * sb->s_blocksize; | |
851 | u32 wbit = bit & (wbits - 1); | |
852 | ||
853 | while (iw < wnd->nwnd && bits) { | |
854 | u32 tail, op; | |
855 | ||
856 | if (unlikely(iw + 1 == wnd->nwnd)) | |
857 | wbits = wnd->bits_last; | |
858 | ||
859 | tail = wbits - wbit; | |
6e3331ee | 860 | op = min_t(u32, tail, bits); |
3f3b442b KK |
861 | |
862 | if (wbits != wnd->free_bits[iw]) { | |
863 | bool ret; | |
864 | struct buffer_head *bh = wnd_map(wnd, iw); | |
865 | ||
866 | if (IS_ERR(bh)) | |
867 | return false; | |
868 | ||
08811ba5 | 869 | ret = are_bits_clear(bh->b_data, wbit, op); |
3f3b442b KK |
870 | |
871 | put_bh(bh); | |
872 | if (!ret) | |
873 | return false; | |
874 | } | |
875 | ||
876 | bits -= op; | |
877 | wbit = 0; | |
878 | iw += 1; | |
879 | } | |
880 | ||
881 | return true; | |
882 | } | |
883 | ||
884 | /* | |
885 | * wnd_is_free | |
886 | * | |
e8b8e97f | 887 | * Return: True if all clusters [bit, bit+bits) are free. |
3f3b442b KK |
888 | */ |
889 | bool wnd_is_free(struct wnd_bitmap *wnd, size_t bit, size_t bits) | |
890 | { | |
891 | bool ret; | |
892 | struct rb_node *n; | |
893 | size_t end; | |
894 | struct e_node *e; | |
895 | ||
896 | if (RB_EMPTY_ROOT(&wnd->start_tree)) | |
897 | goto use_wnd; | |
898 | ||
899 | n = rb_lookup(&wnd->start_tree, bit); | |
900 | if (!n) | |
901 | goto use_wnd; | |
902 | ||
903 | e = rb_entry(n, struct e_node, start.node); | |
904 | ||
905 | end = e->start.key + e->count.key; | |
906 | ||
907 | if (bit < end && bit + bits <= end) | |
908 | return true; | |
909 | ||
910 | use_wnd: | |
911 | ret = wnd_is_free_hlp(wnd, bit, bits); | |
912 | ||
913 | return ret; | |
914 | } | |
915 | ||
916 | /* | |
917 | * wnd_is_used | |
918 | * | |
e8b8e97f | 919 | * Return: True if all clusters [bit, bit+bits) are used. |
3f3b442b KK |
920 | */ |
921 | bool wnd_is_used(struct wnd_bitmap *wnd, size_t bit, size_t bits) | |
922 | { | |
923 | bool ret = false; | |
924 | struct super_block *sb = wnd->sb; | |
925 | size_t iw = bit >> (sb->s_blocksize_bits + 3); | |
926 | u32 wbits = 8 * sb->s_blocksize; | |
927 | u32 wbit = bit & (wbits - 1); | |
928 | size_t end; | |
929 | struct rb_node *n; | |
930 | struct e_node *e; | |
931 | ||
932 | if (RB_EMPTY_ROOT(&wnd->start_tree)) | |
933 | goto use_wnd; | |
934 | ||
935 | end = bit + bits; | |
936 | n = rb_lookup(&wnd->start_tree, end - 1); | |
937 | if (!n) | |
938 | goto use_wnd; | |
939 | ||
940 | e = rb_entry(n, struct e_node, start.node); | |
941 | if (e->start.key + e->count.key > bit) | |
942 | return false; | |
943 | ||
944 | use_wnd: | |
945 | while (iw < wnd->nwnd && bits) { | |
946 | u32 tail, op; | |
947 | ||
948 | if (unlikely(iw + 1 == wnd->nwnd)) | |
949 | wbits = wnd->bits_last; | |
950 | ||
951 | tail = wbits - wbit; | |
6e3331ee | 952 | op = min_t(u32, tail, bits); |
3f3b442b KK |
953 | |
954 | if (wnd->free_bits[iw]) { | |
955 | bool ret; | |
956 | struct buffer_head *bh = wnd_map(wnd, iw); | |
957 | ||
958 | if (IS_ERR(bh)) | |
959 | goto out; | |
960 | ||
08811ba5 | 961 | ret = are_bits_set(bh->b_data, wbit, op); |
3f3b442b KK |
962 | put_bh(bh); |
963 | if (!ret) | |
964 | goto out; | |
965 | } | |
966 | ||
967 | bits -= op; | |
968 | wbit = 0; | |
969 | iw += 1; | |
970 | } | |
971 | ret = true; | |
972 | ||
973 | out: | |
974 | return ret; | |
975 | } | |
976 | ||
977 | /* | |
e8b8e97f KA |
978 | * wnd_find - Look for free space. |
979 | * | |
3f3b442b KK |
980 | * - flags - BITMAP_FIND_XXX flags |
981 | * | |
e8b8e97f | 982 | * Return: 0 if not found. |
3f3b442b KK |
983 | */ |
984 | size_t wnd_find(struct wnd_bitmap *wnd, size_t to_alloc, size_t hint, | |
985 | size_t flags, size_t *allocated) | |
986 | { | |
987 | struct super_block *sb; | |
988 | u32 wbits, wpos, wzbit, wzend; | |
989 | size_t fnd, max_alloc, b_len, b_pos; | |
990 | size_t iw, prev_tail, nwnd, wbit, ebit, zbit, zend; | |
991 | size_t to_alloc0 = to_alloc; | |
3f3b442b KK |
992 | const struct e_node *e; |
993 | const struct rb_node *pr, *cr; | |
994 | u8 log2_bits; | |
995 | bool fbits_valid; | |
996 | struct buffer_head *bh; | |
997 | ||
e8b8e97f | 998 | /* Fast checking for available free space. */ |
3f3b442b KK |
999 | if (flags & BITMAP_FIND_FULL) { |
1000 | size_t zeroes = wnd_zeroes(wnd); | |
1001 | ||
1002 | zeroes -= wnd->zone_end - wnd->zone_bit; | |
1003 | if (zeroes < to_alloc0) | |
1004 | goto no_space; | |
1005 | ||
1006 | if (to_alloc0 > wnd->extent_max) | |
1007 | goto no_space; | |
1008 | } else { | |
1009 | if (to_alloc > wnd->extent_max) | |
1010 | to_alloc = wnd->extent_max; | |
1011 | } | |
1012 | ||
1013 | if (wnd->zone_bit <= hint && hint < wnd->zone_end) | |
1014 | hint = wnd->zone_end; | |
1015 | ||
1016 | max_alloc = wnd->nbits; | |
1017 | b_len = b_pos = 0; | |
1018 | ||
1019 | if (hint >= max_alloc) | |
1020 | hint = 0; | |
1021 | ||
1022 | if (RB_EMPTY_ROOT(&wnd->start_tree)) { | |
1023 | if (wnd->uptodated == 1) { | |
e8b8e97f | 1024 | /* Extents tree is updated -> No free space. */ |
3f3b442b KK |
1025 | goto no_space; |
1026 | } | |
1027 | goto scan_bitmap; | |
1028 | } | |
1029 | ||
1030 | e = NULL; | |
1031 | if (!hint) | |
1032 | goto allocate_biggest; | |
1033 | ||
e8b8e97f | 1034 | /* Use hint: Enumerate extents by start >= hint. */ |
3f3b442b KK |
1035 | pr = NULL; |
1036 | cr = wnd->start_tree.rb_node; | |
1037 | ||
1038 | for (;;) { | |
1039 | e = rb_entry(cr, struct e_node, start.node); | |
1040 | ||
1041 | if (e->start.key == hint) | |
1042 | break; | |
1043 | ||
1044 | if (e->start.key < hint) { | |
1045 | pr = cr; | |
1046 | cr = cr->rb_right; | |
1047 | if (!cr) | |
1048 | break; | |
1049 | continue; | |
1050 | } | |
1051 | ||
1052 | cr = cr->rb_left; | |
1053 | if (!cr) { | |
1054 | e = pr ? rb_entry(pr, struct e_node, start.node) : NULL; | |
1055 | break; | |
1056 | } | |
1057 | } | |
1058 | ||
1059 | if (!e) | |
1060 | goto allocate_biggest; | |
1061 | ||
1062 | if (e->start.key + e->count.key > hint) { | |
e8b8e97f | 1063 | /* We have found extension with 'hint' inside. */ |
3f3b442b KK |
1064 | size_t len = e->start.key + e->count.key - hint; |
1065 | ||
1066 | if (len >= to_alloc && hint + to_alloc <= max_alloc) { | |
1067 | fnd = hint; | |
1068 | goto found; | |
1069 | } | |
1070 | ||
1071 | if (!(flags & BITMAP_FIND_FULL)) { | |
1072 | if (len > to_alloc) | |
1073 | len = to_alloc; | |
1074 | ||
1075 | if (hint + len <= max_alloc) { | |
1076 | fnd = hint; | |
1077 | to_alloc = len; | |
1078 | goto found; | |
1079 | } | |
1080 | } | |
1081 | } | |
1082 | ||
1083 | allocate_biggest: | |
e8b8e97f | 1084 | /* Allocate from biggest free extent. */ |
3f3b442b KK |
1085 | e = rb_entry(rb_first(&wnd->count_tree), struct e_node, count.node); |
1086 | if (e->count.key != wnd->extent_max) | |
1087 | wnd->extent_max = e->count.key; | |
1088 | ||
1089 | if (e->count.key < max_alloc) { | |
1090 | if (e->count.key >= to_alloc) { | |
1091 | ; | |
1092 | } else if (flags & BITMAP_FIND_FULL) { | |
1093 | if (e->count.key < to_alloc0) { | |
e8b8e97f | 1094 | /* Biggest free block is less then requested. */ |
3f3b442b KK |
1095 | goto no_space; |
1096 | } | |
1097 | to_alloc = e->count.key; | |
1098 | } else if (-1 != wnd->uptodated) { | |
1099 | to_alloc = e->count.key; | |
1100 | } else { | |
e8b8e97f | 1101 | /* Check if we can use more bits. */ |
3f3b442b KK |
1102 | size_t op, max_check; |
1103 | struct rb_root start_tree; | |
1104 | ||
1105 | memcpy(&start_tree, &wnd->start_tree, | |
1106 | sizeof(struct rb_root)); | |
1107 | memset(&wnd->start_tree, 0, sizeof(struct rb_root)); | |
1108 | ||
1109 | max_check = e->start.key + to_alloc; | |
1110 | if (max_check > max_alloc) | |
1111 | max_check = max_alloc; | |
1112 | for (op = e->start.key + e->count.key; op < max_check; | |
1113 | op++) { | |
1114 | if (!wnd_is_free(wnd, op, 1)) | |
1115 | break; | |
1116 | } | |
1117 | memcpy(&wnd->start_tree, &start_tree, | |
1118 | sizeof(struct rb_root)); | |
1119 | to_alloc = op - e->start.key; | |
1120 | } | |
1121 | ||
e8b8e97f | 1122 | /* Prepare to return. */ |
3f3b442b KK |
1123 | fnd = e->start.key; |
1124 | if (e->start.key + to_alloc > max_alloc) | |
1125 | to_alloc = max_alloc - e->start.key; | |
1126 | goto found; | |
1127 | } | |
1128 | ||
1129 | if (wnd->uptodated == 1) { | |
e8b8e97f | 1130 | /* Extents tree is updated -> no free space. */ |
3f3b442b KK |
1131 | goto no_space; |
1132 | } | |
1133 | ||
1134 | b_len = e->count.key; | |
1135 | b_pos = e->start.key; | |
1136 | ||
1137 | scan_bitmap: | |
1138 | sb = wnd->sb; | |
1139 | log2_bits = sb->s_blocksize_bits + 3; | |
1140 | ||
d3624466 | 1141 | /* At most two ranges [hint, max_alloc) + [0, hint). */ |
3f3b442b KK |
1142 | Again: |
1143 | ||
e8b8e97f | 1144 | /* TODO: Optimize request for case nbits > wbits. */ |
3f3b442b KK |
1145 | iw = hint >> log2_bits; |
1146 | wbits = sb->s_blocksize * 8; | |
1147 | wpos = hint & (wbits - 1); | |
1148 | prev_tail = 0; | |
1149 | fbits_valid = true; | |
1150 | ||
1151 | if (max_alloc == wnd->nbits) { | |
1152 | nwnd = wnd->nwnd; | |
1153 | } else { | |
1154 | size_t t = max_alloc + wbits - 1; | |
1155 | ||
1156 | nwnd = likely(t > max_alloc) ? (t >> log2_bits) : wnd->nwnd; | |
1157 | } | |
1158 | ||
e8b8e97f | 1159 | /* Enumerate all windows. */ |
3f3b442b KK |
1160 | for (; iw < nwnd; iw++) { |
1161 | wbit = iw << log2_bits; | |
1162 | ||
1163 | if (!wnd->free_bits[iw]) { | |
1164 | if (prev_tail > b_len) { | |
1165 | b_pos = wbit - prev_tail; | |
1166 | b_len = prev_tail; | |
1167 | } | |
1168 | ||
e8b8e97f | 1169 | /* Skip full used window. */ |
3f3b442b KK |
1170 | prev_tail = 0; |
1171 | wpos = 0; | |
1172 | continue; | |
1173 | } | |
1174 | ||
1175 | if (unlikely(iw + 1 == nwnd)) { | |
1176 | if (max_alloc == wnd->nbits) { | |
1177 | wbits = wnd->bits_last; | |
1178 | } else { | |
1179 | size_t t = max_alloc & (wbits - 1); | |
1180 | ||
1181 | if (t) { | |
1182 | wbits = t; | |
1183 | fbits_valid = false; | |
1184 | } | |
1185 | } | |
1186 | } | |
1187 | ||
1188 | if (wnd->zone_end > wnd->zone_bit) { | |
1189 | ebit = wbit + wbits; | |
1190 | zbit = max(wnd->zone_bit, wbit); | |
1191 | zend = min(wnd->zone_end, ebit); | |
1192 | ||
e8b8e97f | 1193 | /* Here we have a window [wbit, ebit) and zone [zbit, zend). */ |
3f3b442b | 1194 | if (zend <= zbit) { |
e8b8e97f | 1195 | /* Zone does not overlap window. */ |
3f3b442b KK |
1196 | } else { |
1197 | wzbit = zbit - wbit; | |
1198 | wzend = zend - wbit; | |
1199 | ||
e8b8e97f | 1200 | /* Zone overlaps window. */ |
3f3b442b KK |
1201 | if (wnd->free_bits[iw] == wzend - wzbit) { |
1202 | prev_tail = 0; | |
1203 | wpos = 0; | |
1204 | continue; | |
1205 | } | |
1206 | ||
e8b8e97f | 1207 | /* Scan two ranges window: [wbit, zbit) and [zend, ebit). */ |
3f3b442b KK |
1208 | bh = wnd_map(wnd, iw); |
1209 | ||
1210 | if (IS_ERR(bh)) { | |
e8b8e97f | 1211 | /* TODO: Error */ |
3f3b442b KK |
1212 | prev_tail = 0; |
1213 | wpos = 0; | |
1214 | continue; | |
1215 | } | |
1216 | ||
e8b8e97f | 1217 | /* Scan range [wbit, zbit). */ |
3f3b442b | 1218 | if (wpos < wzbit) { |
e8b8e97f | 1219 | /* Scan range [wpos, zbit). */ |
08811ba5 KK |
1220 | fnd = wnd_scan(bh->b_data, wbit, wpos, |
1221 | wzbit, to_alloc, | |
1222 | &prev_tail, &b_pos, | |
1223 | &b_len); | |
3f3b442b KK |
1224 | if (fnd != MINUS_ONE_T) { |
1225 | put_bh(bh); | |
1226 | goto found; | |
1227 | } | |
1228 | } | |
1229 | ||
1230 | prev_tail = 0; | |
1231 | ||
e8b8e97f | 1232 | /* Scan range [zend, ebit). */ |
3f3b442b | 1233 | if (wzend < wbits) { |
08811ba5 | 1234 | fnd = wnd_scan(bh->b_data, wbit, |
3f3b442b KK |
1235 | max(wzend, wpos), wbits, |
1236 | to_alloc, &prev_tail, | |
1237 | &b_pos, &b_len); | |
1238 | if (fnd != MINUS_ONE_T) { | |
1239 | put_bh(bh); | |
1240 | goto found; | |
1241 | } | |
1242 | } | |
1243 | ||
1244 | wpos = 0; | |
1245 | put_bh(bh); | |
1246 | continue; | |
1247 | } | |
1248 | } | |
1249 | ||
e8b8e97f | 1250 | /* Current window does not overlap zone. */ |
3f3b442b | 1251 | if (!wpos && fbits_valid && wnd->free_bits[iw] == wbits) { |
e8b8e97f | 1252 | /* Window is empty. */ |
3f3b442b KK |
1253 | if (prev_tail + wbits >= to_alloc) { |
1254 | fnd = wbit + wpos - prev_tail; | |
1255 | goto found; | |
1256 | } | |
1257 | ||
e8b8e97f | 1258 | /* Increase 'prev_tail' and process next window. */ |
3f3b442b KK |
1259 | prev_tail += wbits; |
1260 | wpos = 0; | |
1261 | continue; | |
1262 | } | |
1263 | ||
d3624466 | 1264 | /* Read window. */ |
3f3b442b KK |
1265 | bh = wnd_map(wnd, iw); |
1266 | if (IS_ERR(bh)) { | |
e8b8e97f | 1267 | // TODO: Error. |
3f3b442b KK |
1268 | prev_tail = 0; |
1269 | wpos = 0; | |
1270 | continue; | |
1271 | } | |
1272 | ||
e8b8e97f | 1273 | /* Scan range [wpos, eBits). */ |
08811ba5 KK |
1274 | fnd = wnd_scan(bh->b_data, wbit, wpos, wbits, to_alloc, |
1275 | &prev_tail, &b_pos, &b_len); | |
3f3b442b KK |
1276 | put_bh(bh); |
1277 | if (fnd != MINUS_ONE_T) | |
1278 | goto found; | |
1279 | } | |
1280 | ||
1281 | if (b_len < prev_tail) { | |
e8b8e97f | 1282 | /* The last fragment. */ |
3f3b442b KK |
1283 | b_len = prev_tail; |
1284 | b_pos = max_alloc - prev_tail; | |
1285 | } | |
1286 | ||
1287 | if (hint) { | |
1288 | /* | |
e8b8e97f KA |
1289 | * We have scanned range [hint max_alloc). |
1290 | * Prepare to scan range [0 hint + to_alloc). | |
3f3b442b KK |
1291 | */ |
1292 | size_t nextmax = hint + to_alloc; | |
1293 | ||
1294 | if (likely(nextmax >= hint) && nextmax < max_alloc) | |
1295 | max_alloc = nextmax; | |
1296 | hint = 0; | |
1297 | goto Again; | |
1298 | } | |
1299 | ||
1300 | if (!b_len) | |
1301 | goto no_space; | |
1302 | ||
1303 | wnd->extent_max = b_len; | |
1304 | ||
1305 | if (flags & BITMAP_FIND_FULL) | |
1306 | goto no_space; | |
1307 | ||
1308 | fnd = b_pos; | |
1309 | to_alloc = b_len; | |
1310 | ||
1311 | found: | |
1312 | if (flags & BITMAP_FIND_MARK_AS_USED) { | |
e8b8e97f | 1313 | /* TODO: Optimize remove extent (pass 'e'?). */ |
3f3b442b KK |
1314 | if (wnd_set_used(wnd, fnd, to_alloc)) |
1315 | goto no_space; | |
1316 | } else if (wnd->extent_max != MINUS_ONE_T && | |
1317 | to_alloc > wnd->extent_max) { | |
1318 | wnd->extent_max = to_alloc; | |
1319 | } | |
1320 | ||
1321 | *allocated = fnd; | |
1322 | return to_alloc; | |
1323 | ||
1324 | no_space: | |
1325 | return 0; | |
1326 | } | |
1327 | ||
1328 | /* | |
e8b8e97f | 1329 | * wnd_extend - Extend bitmap ($MFT bitmap). |
3f3b442b KK |
1330 | */ |
1331 | int wnd_extend(struct wnd_bitmap *wnd, size_t new_bits) | |
1332 | { | |
1333 | int err; | |
1334 | struct super_block *sb = wnd->sb; | |
1335 | struct ntfs_sb_info *sbi = sb->s_fs_info; | |
1336 | u32 blocksize = sb->s_blocksize; | |
1337 | u32 wbits = blocksize * 8; | |
1338 | u32 b0, new_last; | |
1339 | size_t bits, iw, new_wnd; | |
1340 | size_t old_bits = wnd->nbits; | |
1341 | u16 *new_free; | |
1342 | ||
1343 | if (new_bits <= old_bits) | |
1344 | return -EINVAL; | |
1345 | ||
e8b8e97f | 1346 | /* Align to 8 byte boundary. */ |
3f3b442b KK |
1347 | new_wnd = bytes_to_block(sb, bitmap_size(new_bits)); |
1348 | new_last = new_bits & (wbits - 1); | |
1349 | if (!new_last) | |
1350 | new_last = wbits; | |
1351 | ||
1352 | if (new_wnd != wnd->nwnd) { | |
92f017c4 | 1353 | new_free = kmalloc_array(new_wnd, sizeof(u16), GFP_NOFS); |
3f3b442b KK |
1354 | if (!new_free) |
1355 | return -ENOMEM; | |
1356 | ||
548744f8 | 1357 | memcpy(new_free, wnd->free_bits, wnd->nwnd * sizeof(short)); |
3f3b442b KK |
1358 | memset(new_free + wnd->nwnd, 0, |
1359 | (new_wnd - wnd->nwnd) * sizeof(short)); | |
195c52bd | 1360 | kfree(wnd->free_bits); |
3f3b442b KK |
1361 | wnd->free_bits = new_free; |
1362 | } | |
1363 | ||
e8b8e97f | 1364 | /* Zero bits [old_bits,new_bits). */ |
3f3b442b KK |
1365 | bits = new_bits - old_bits; |
1366 | b0 = old_bits & (wbits - 1); | |
1367 | ||
1368 | for (iw = old_bits >> (sb->s_blocksize_bits + 3); bits; iw += 1) { | |
1369 | u32 op; | |
1370 | size_t frb; | |
1371 | u64 vbo, lbo, bytes; | |
1372 | struct buffer_head *bh; | |
3f3b442b KK |
1373 | |
1374 | if (iw + 1 == new_wnd) | |
1375 | wbits = new_last; | |
1376 | ||
1377 | op = b0 + bits > wbits ? wbits - b0 : bits; | |
1378 | vbo = (u64)iw * blocksize; | |
1379 | ||
1380 | err = ntfs_vbo_to_lbo(sbi, &wnd->run, vbo, &lbo, &bytes); | |
1381 | if (err) | |
1382 | break; | |
1383 | ||
1384 | bh = ntfs_bread(sb, lbo >> sb->s_blocksize_bits); | |
1385 | if (!bh) | |
1386 | return -EIO; | |
1387 | ||
1388 | lock_buffer(bh); | |
3f3b442b | 1389 | |
08811ba5 KK |
1390 | ntfs_bitmap_clear_le(bh->b_data, b0, blocksize * 8 - b0); |
1391 | frb = wbits - ntfs_bitmap_weight_le(bh->b_data, wbits); | |
3f3b442b KK |
1392 | wnd->total_zeroes += frb - wnd->free_bits[iw]; |
1393 | wnd->free_bits[iw] = frb; | |
1394 | ||
1395 | set_buffer_uptodate(bh); | |
1396 | mark_buffer_dirty(bh); | |
1397 | unlock_buffer(bh); | |
e8b8e97f | 1398 | /* err = sync_dirty_buffer(bh); */ |
3f3b442b KK |
1399 | |
1400 | b0 = 0; | |
1401 | bits -= op; | |
1402 | } | |
1403 | ||
1404 | wnd->nbits = new_bits; | |
1405 | wnd->nwnd = new_wnd; | |
1406 | wnd->bits_last = new_last; | |
1407 | ||
1408 | wnd_add_free_ext(wnd, old_bits, new_bits - old_bits, false); | |
1409 | ||
1410 | return 0; | |
1411 | } | |
1412 | ||
3f3b442b KK |
1413 | void wnd_zone_set(struct wnd_bitmap *wnd, size_t lcn, size_t len) |
1414 | { | |
54033c13 | 1415 | size_t zlen = wnd->zone_end - wnd->zone_bit; |
3f3b442b | 1416 | |
3f3b442b KK |
1417 | if (zlen) |
1418 | wnd_add_free_ext(wnd, wnd->zone_bit, zlen, false); | |
1419 | ||
1420 | if (!RB_EMPTY_ROOT(&wnd->start_tree) && len) | |
1421 | wnd_remove_free_ext(wnd, lcn, len); | |
1422 | ||
1423 | wnd->zone_bit = lcn; | |
1424 | wnd->zone_end = lcn + len; | |
1425 | } | |
1426 | ||
1427 | int ntfs_trim_fs(struct ntfs_sb_info *sbi, struct fstrim_range *range) | |
1428 | { | |
1429 | int err = 0; | |
1430 | struct super_block *sb = sbi->sb; | |
1431 | struct wnd_bitmap *wnd = &sbi->used.bitmap; | |
1432 | u32 wbits = 8 * sb->s_blocksize; | |
1433 | CLST len = 0, lcn = 0, done = 0; | |
1434 | CLST minlen = bytes_to_cluster(sbi, range->minlen); | |
1435 | CLST lcn_from = bytes_to_cluster(sbi, range->start); | |
1436 | size_t iw = lcn_from >> (sb->s_blocksize_bits + 3); | |
1437 | u32 wbit = lcn_from & (wbits - 1); | |
3f3b442b KK |
1438 | CLST lcn_to; |
1439 | ||
1440 | if (!minlen) | |
1441 | minlen = 1; | |
1442 | ||
1443 | if (range->len == (u64)-1) | |
1444 | lcn_to = wnd->nbits; | |
1445 | else | |
1446 | lcn_to = bytes_to_cluster(sbi, range->start + range->len); | |
1447 | ||
1448 | down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS); | |
1449 | ||
557d1967 | 1450 | for (; iw < wnd->nwnd; iw++, wbit = 0) { |
3f3b442b KK |
1451 | CLST lcn_wnd = iw * wbits; |
1452 | struct buffer_head *bh; | |
1453 | ||
1454 | if (lcn_wnd > lcn_to) | |
1455 | break; | |
1456 | ||
1457 | if (!wnd->free_bits[iw]) | |
1458 | continue; | |
1459 | ||
1460 | if (iw + 1 == wnd->nwnd) | |
1461 | wbits = wnd->bits_last; | |
1462 | ||
1463 | if (lcn_wnd + wbits > lcn_to) | |
1464 | wbits = lcn_to - lcn_wnd; | |
1465 | ||
1466 | bh = wnd_map(wnd, iw); | |
1467 | if (IS_ERR(bh)) { | |
1468 | err = PTR_ERR(bh); | |
1469 | break; | |
1470 | } | |
1471 | ||
3f3b442b | 1472 | for (; wbit < wbits; wbit++) { |
08811ba5 | 1473 | if (!test_bit_le(wbit, bh->b_data)) { |
3f3b442b KK |
1474 | if (!len) |
1475 | lcn = lcn_wnd + wbit; | |
1476 | len += 1; | |
1477 | continue; | |
1478 | } | |
1479 | if (len >= minlen) { | |
1480 | err = ntfs_discard(sbi, lcn, len); | |
1481 | if (err) | |
1482 | goto out; | |
1483 | done += len; | |
1484 | } | |
1485 | len = 0; | |
1486 | } | |
1487 | put_bh(bh); | |
1488 | } | |
1489 | ||
e8b8e97f | 1490 | /* Process the last fragment. */ |
3f3b442b KK |
1491 | if (len >= minlen) { |
1492 | err = ntfs_discard(sbi, lcn, len); | |
1493 | if (err) | |
1494 | goto out; | |
1495 | done += len; | |
1496 | } | |
1497 | ||
1498 | out: | |
1499 | range->len = (u64)done << sbi->cluster_bits; | |
1500 | ||
1501 | up_read(&wnd->rw_lock); | |
1502 | ||
1503 | return err; | |
1504 | } | |
88a8d0d2 | 1505 | |
08811ba5 KK |
1506 | #if BITS_PER_LONG == 64 |
1507 | typedef __le64 bitmap_ulong; | |
1508 | #define cpu_to_ul(x) cpu_to_le64(x) | |
1509 | #define ul_to_cpu(x) le64_to_cpu(x) | |
1510 | #else | |
1511 | typedef __le32 bitmap_ulong; | |
1512 | #define cpu_to_ul(x) cpu_to_le32(x) | |
1513 | #define ul_to_cpu(x) le32_to_cpu(x) | |
1514 | #endif | |
1515 | ||
1516 | void ntfs_bitmap_set_le(void *map, unsigned int start, int len) | |
88a8d0d2 | 1517 | { |
08811ba5 | 1518 | bitmap_ulong *p = (bitmap_ulong *)map + BIT_WORD(start); |
88a8d0d2 TK |
1519 | const unsigned int size = start + len; |
1520 | int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); | |
08811ba5 | 1521 | bitmap_ulong mask_to_set = cpu_to_ul(BITMAP_FIRST_WORD_MASK(start)); |
88a8d0d2 TK |
1522 | |
1523 | while (len - bits_to_set >= 0) { | |
1524 | *p |= mask_to_set; | |
1525 | len -= bits_to_set; | |
1526 | bits_to_set = BITS_PER_LONG; | |
08811ba5 | 1527 | mask_to_set = cpu_to_ul(~0UL); |
88a8d0d2 TK |
1528 | p++; |
1529 | } | |
1530 | if (len) { | |
08811ba5 | 1531 | mask_to_set &= cpu_to_ul(BITMAP_LAST_WORD_MASK(size)); |
88a8d0d2 TK |
1532 | *p |= mask_to_set; |
1533 | } | |
1534 | } | |
1535 | ||
08811ba5 | 1536 | void ntfs_bitmap_clear_le(void *map, unsigned int start, int len) |
88a8d0d2 | 1537 | { |
08811ba5 | 1538 | bitmap_ulong *p = (bitmap_ulong *)map + BIT_WORD(start); |
88a8d0d2 TK |
1539 | const unsigned int size = start + len; |
1540 | int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); | |
08811ba5 | 1541 | bitmap_ulong mask_to_clear = cpu_to_ul(BITMAP_FIRST_WORD_MASK(start)); |
88a8d0d2 TK |
1542 | |
1543 | while (len - bits_to_clear >= 0) { | |
1544 | *p &= ~mask_to_clear; | |
1545 | len -= bits_to_clear; | |
1546 | bits_to_clear = BITS_PER_LONG; | |
08811ba5 | 1547 | mask_to_clear = cpu_to_ul(~0UL); |
88a8d0d2 TK |
1548 | p++; |
1549 | } | |
1550 | if (len) { | |
08811ba5 | 1551 | mask_to_clear &= cpu_to_ul(BITMAP_LAST_WORD_MASK(size)); |
88a8d0d2 TK |
1552 | *p &= ~mask_to_clear; |
1553 | } | |
1554 | } | |
08811ba5 KK |
1555 | |
1556 | unsigned int ntfs_bitmap_weight_le(const void *bitmap, int bits) | |
1557 | { | |
1558 | const ulong *bmp = bitmap; | |
1559 | unsigned int k, lim = bits / BITS_PER_LONG; | |
1560 | unsigned int w = 0; | |
1561 | ||
1562 | for (k = 0; k < lim; k++) | |
1563 | w += hweight_long(bmp[k]); | |
1564 | ||
1565 | if (bits % BITS_PER_LONG) { | |
1566 | w += hweight_long(ul_to_cpu(((bitmap_ulong *)bitmap)[k]) & | |
1567 | BITMAP_LAST_WORD_MASK(bits)); | |
1568 | } | |
1569 | ||
1570 | return w; | |
1571 | } |