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