Lines Matching refs:wnd
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);
54 static inline u32 wnd_bits(const struct wnd_bitmap *wnd, size_t i) in wnd_bits() argument
56 return i + 1 == wnd->nwnd ? wnd->bits_last : wnd->sb->s_blocksize * 8; in wnd_bits()
128 void wnd_close(struct wnd_bitmap *wnd) in wnd_close() argument
132 kfree(wnd->free_bits); in wnd_close()
133 run_close(&wnd->run); in wnd_close()
135 node = rb_first(&wnd->start_tree); in wnd_close()
139 rb_erase(node, &wnd->start_tree); in wnd_close()
235 static void wnd_add_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len, in wnd_add_free_ext() argument
244 if (wnd->count >= NTFS_MAX_WND_EXTENTS && in wnd_add_free_ext()
245 len <= wnd->extent_min) { in wnd_add_free_ext()
246 wnd->uptodated = -1; in wnd_add_free_ext()
251 n = rb_lookup(&wnd->start_tree, bit); in wnd_add_free_ext()
254 n = rb_first(&wnd->start_tree); in wnd_add_free_ext()
262 rb_erase(&e->start.node, &wnd->start_tree); in wnd_add_free_ext()
263 rb_erase(&e->count.node, &wnd->count_tree); in wnd_add_free_ext()
264 wnd->count -= 1; in wnd_add_free_ext()
281 rb_erase(&e->start.node, &wnd->start_tree); in wnd_add_free_ext()
282 rb_erase(&e->count.node, &wnd->count_tree); in wnd_add_free_ext()
283 wnd->count -= 1; in wnd_add_free_ext()
291 if (wnd->uptodated != 1) { in wnd_add_free_ext()
293 ib = wnd->zone_bit == wnd->zone_end || in wnd_add_free_ext()
294 bit < wnd->zone_end in wnd_add_free_ext()
296 : wnd->zone_end; in wnd_add_free_ext()
298 while (bit > ib && wnd_is_free_hlp(wnd, bit - 1, 1)) { in wnd_add_free_ext()
304 ib = wnd->zone_bit == wnd->zone_end || in wnd_add_free_ext()
305 end_in > wnd->zone_bit in wnd_add_free_ext()
306 ? wnd->nbits in wnd_add_free_ext()
307 : wnd->zone_bit; in wnd_add_free_ext()
309 while (end_in < ib && wnd_is_free_hlp(wnd, end_in, 1)) { in wnd_add_free_ext()
316 if (wnd->count >= NTFS_MAX_WND_EXTENTS) { in wnd_add_free_ext()
320 wnd->uptodated = -1; in wnd_add_free_ext()
323 n = rb_last(&wnd->count_tree); in wnd_add_free_ext()
334 wnd->extent_min = e2->count.key; in wnd_add_free_ext()
338 rb_erase(&e->start.node, &wnd->start_tree); in wnd_add_free_ext()
339 rb_erase(&e->count.node, &wnd->count_tree); in wnd_add_free_ext()
340 wnd->count -= 1; in wnd_add_free_ext()
344 wnd->uptodated = -1; in wnd_add_free_ext()
348 if (build && len <= wnd->extent_min) in wnd_add_free_ext()
349 wnd->extent_min = len; in wnd_add_free_ext()
353 if (len > wnd->extent_max) in wnd_add_free_ext()
354 wnd->extent_max = len; in wnd_add_free_ext()
356 rb_insert_start(&wnd->start_tree, e); in wnd_add_free_ext()
357 rb_insert_count(&wnd->count_tree, e); in wnd_add_free_ext()
358 wnd->count += 1; in wnd_add_free_ext()
366 static void wnd_remove_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len) in wnd_remove_free_ext() argument
374 n = rb_lookup(&wnd->start_tree, bit); in wnd_remove_free_ext()
403 if (e3->count.key == wnd->extent_max) in wnd_remove_free_ext()
409 rb_erase(&e3->count.node, &wnd->count_tree); in wnd_remove_free_ext()
411 rb_insert_count(&wnd->count_tree, e3); in wnd_remove_free_ext()
416 rb_erase(&e3->start.node, &wnd->start_tree); in wnd_remove_free_ext()
417 rb_erase(&e3->count.node, &wnd->count_tree); in wnd_remove_free_ext()
418 wnd->count -= 1; in wnd_remove_free_ext()
423 n3 = rb_first(&wnd->count_tree); in wnd_remove_free_ext()
424 wnd->extent_max = in wnd_remove_free_ext()
430 if (e->count.key != wnd->extent_max) { in wnd_remove_free_ext()
438 wnd->extent_max = max_new_len; in wnd_remove_free_ext()
441 wnd->extent_max = max(e3->count.key, max_new_len); in wnd_remove_free_ext()
448 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
450 rb_insert_count(&wnd->count_tree, e); in wnd_remove_free_ext()
452 rb_erase(&e->start.node, &wnd->start_tree); in wnd_remove_free_ext()
453 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
454 wnd->count -= 1; in wnd_remove_free_ext()
459 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
461 rb_insert_count(&wnd->count_tree, e); in wnd_remove_free_ext()
466 if (wnd->count >= NTFS_MAX_WND_EXTENTS) { in wnd_remove_free_ext()
467 wnd->uptodated = -1; in wnd_remove_free_ext()
470 e = rb_entry(rb_last(&wnd->count_tree), struct e_node, in wnd_remove_free_ext()
476 rb_erase(&e->start.node, &wnd->start_tree); in wnd_remove_free_ext()
477 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
478 wnd->count -= 1; in wnd_remove_free_ext()
482 wnd->uptodated = -1; in wnd_remove_free_ext()
488 rb_insert_start(&wnd->start_tree, e); in wnd_remove_free_ext()
489 rb_insert_count(&wnd->count_tree, e); in wnd_remove_free_ext()
490 wnd->count += 1; in wnd_remove_free_ext()
494 if (!wnd->count && 1 != wnd->uptodated) in wnd_remove_free_ext()
495 wnd_rescan(wnd); in wnd_remove_free_ext()
501 static int wnd_rescan(struct wnd_bitmap *wnd) in wnd_rescan() argument
505 struct super_block *sb = wnd->sb; in wnd_rescan()
517 wnd->uptodated = 0; in wnd_rescan()
518 wnd->extent_max = 0; in wnd_rescan()
519 wnd->extent_min = MINUS_ONE_T; in wnd_rescan()
520 wnd->total_zeroes = 0; in wnd_rescan()
524 for (iw = 0; iw < wnd->nwnd; iw++) { in wnd_rescan()
525 if (iw + 1 == wnd->nwnd) in wnd_rescan()
526 wbits = wnd->bits_last; in wnd_rescan()
528 if (wnd->inited) { in wnd_rescan()
529 if (!wnd->free_bits[iw]) { in wnd_rescan()
532 wnd_add_free_ext(wnd, in wnd_rescan()
539 if (wbits == wnd->free_bits[iw]) { in wnd_rescan()
542 wnd->total_zeroes += wbits; in wnd_rescan()
550 if (!run_lookup_entry(&wnd->run, vbo >> cluster_bits, in wnd_rescan()
571 wnd->free_bits[iw] = frb; in wnd_rescan()
572 wnd->total_zeroes += frb; in wnd_rescan()
578 if (wbit + wbits > wnd->nbits) in wnd_rescan()
579 wbits = wnd->nbits - wbit; in wnd_rescan()
585 wnd_add_free_ext(wnd, wbit + wpos - prev_tail, in wnd_rescan()
605 wnd_add_free_ext(wnd, wbit + wpos - prev_tail, in wnd_rescan()
629 wnd_add_free_ext(wnd, wnd->nbits - prev_tail, prev_tail, true); in wnd_rescan()
637 if (!wnd->uptodated) in wnd_rescan()
638 wnd->uptodated = 1; in wnd_rescan()
640 if (wnd->zone_bit != wnd->zone_end) { in wnd_rescan()
641 size_t zlen = wnd->zone_end - wnd->zone_bit; in wnd_rescan()
643 wnd->zone_end = wnd->zone_bit; in wnd_rescan()
644 wnd_zone_set(wnd, wnd->zone_bit, zlen); in wnd_rescan()
651 int wnd_init(struct wnd_bitmap *wnd, struct super_block *sb, size_t nbits) in wnd_init() argument
657 init_rwsem(&wnd->rw_lock); in wnd_init()
659 wnd->sb = sb; in wnd_init()
660 wnd->nbits = nbits; in wnd_init()
661 wnd->total_zeroes = nbits; in wnd_init()
662 wnd->extent_max = MINUS_ONE_T; in wnd_init()
663 wnd->zone_bit = wnd->zone_end = 0; in wnd_init()
664 wnd->nwnd = bytes_to_block(sb, bitmap_size(nbits)); in wnd_init()
665 wnd->bits_last = nbits & (wbits - 1); in wnd_init()
666 if (!wnd->bits_last) in wnd_init()
667 wnd->bits_last = wbits; in wnd_init()
669 wnd->free_bits = kcalloc(wnd->nwnd, sizeof(u16), GFP_NOFS); in wnd_init()
670 if (!wnd->free_bits) in wnd_init()
673 err = wnd_rescan(wnd); in wnd_init()
677 wnd->inited = true; in wnd_init()
685 static struct buffer_head *wnd_map(struct wnd_bitmap *wnd, size_t iw) in wnd_map() argument
689 struct super_block *sb = wnd->sb; in wnd_map()
697 if (!run_lookup_entry(&wnd->run, vbo >> sbi->cluster_bits, &lcn, &clen, in wnd_map()
704 bh = ntfs_bread(wnd->sb, lbo >> sb->s_blocksize_bits); in wnd_map()
714 int wnd_set_free(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_set_free() argument
717 struct super_block *sb = wnd->sb; in wnd_set_free()
724 while (iw < wnd->nwnd && bits) { in wnd_set_free()
728 if (iw + 1 == wnd->nwnd) in wnd_set_free()
729 wbits = wnd->bits_last; in wnd_set_free()
734 bh = wnd_map(wnd, iw); in wnd_set_free()
746 wnd->free_bits[iw] += op; in wnd_set_free()
753 wnd->total_zeroes += op; in wnd_set_free()
759 wnd_add_free_ext(wnd, bit, bits0, false); in wnd_set_free()
767 int wnd_set_used(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_set_used() argument
770 struct super_block *sb = wnd->sb; in wnd_set_used()
777 while (iw < wnd->nwnd && bits) { in wnd_set_used()
781 if (unlikely(iw + 1 == wnd->nwnd)) in wnd_set_used()
782 wbits = wnd->bits_last; in wnd_set_used()
787 bh = wnd_map(wnd, iw); in wnd_set_used()
797 wnd->free_bits[iw] -= op; in wnd_set_used()
804 wnd->total_zeroes -= op; in wnd_set_used()
810 if (!RB_EMPTY_ROOT(&wnd->start_tree)) in wnd_set_used()
811 wnd_remove_free_ext(wnd, bit, bits0); in wnd_set_used()
821 static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_is_free_hlp() argument
823 struct super_block *sb = wnd->sb; in wnd_is_free_hlp()
828 while (iw < wnd->nwnd && bits) { in wnd_is_free_hlp()
831 if (unlikely(iw + 1 == wnd->nwnd)) in wnd_is_free_hlp()
832 wbits = wnd->bits_last; in wnd_is_free_hlp()
837 if (wbits != wnd->free_bits[iw]) { in wnd_is_free_hlp()
839 struct buffer_head *bh = wnd_map(wnd, iw); in wnd_is_free_hlp()
864 bool wnd_is_free(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_is_free() argument
871 if (RB_EMPTY_ROOT(&wnd->start_tree)) in wnd_is_free()
874 n = rb_lookup(&wnd->start_tree, bit); in wnd_is_free()
886 ret = wnd_is_free_hlp(wnd, bit, bits); in wnd_is_free()
896 bool wnd_is_used(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_is_used() argument
899 struct super_block *sb = wnd->sb; in wnd_is_used()
907 if (RB_EMPTY_ROOT(&wnd->start_tree)) in wnd_is_used()
911 n = rb_lookup(&wnd->start_tree, end - 1); in wnd_is_used()
920 while (iw < wnd->nwnd && bits) { in wnd_is_used()
923 if (unlikely(iw + 1 == wnd->nwnd)) in wnd_is_used()
924 wbits = wnd->bits_last; in wnd_is_used()
929 if (wnd->free_bits[iw]) { in wnd_is_used()
931 struct buffer_head *bh = wnd_map(wnd, iw); in wnd_is_used()
959 size_t wnd_find(struct wnd_bitmap *wnd, size_t to_alloc, size_t hint, in wnd_find() argument
976 size_t zeroes = wnd_zeroes(wnd); in wnd_find()
978 zeroes -= wnd->zone_end - wnd->zone_bit; in wnd_find()
982 if (to_alloc0 > wnd->extent_max) in wnd_find()
985 if (to_alloc > wnd->extent_max) in wnd_find()
986 to_alloc = wnd->extent_max; in wnd_find()
989 if (wnd->zone_bit <= hint && hint < wnd->zone_end) in wnd_find()
990 hint = wnd->zone_end; in wnd_find()
992 max_alloc = wnd->nbits; in wnd_find()
998 if (RB_EMPTY_ROOT(&wnd->start_tree)) { in wnd_find()
999 if (wnd->uptodated == 1) { in wnd_find()
1012 cr = wnd->start_tree.rb_node; in wnd_find()
1061 e = rb_entry(rb_first(&wnd->count_tree), struct e_node, count.node); in wnd_find()
1062 if (e->count.key != wnd->extent_max) in wnd_find()
1063 wnd->extent_max = e->count.key; in wnd_find()
1074 } else if (-1 != wnd->uptodated) { in wnd_find()
1081 memcpy(&start_tree, &wnd->start_tree, in wnd_find()
1083 memset(&wnd->start_tree, 0, sizeof(struct rb_root)); in wnd_find()
1090 if (!wnd_is_free(wnd, op, 1)) in wnd_find()
1093 memcpy(&wnd->start_tree, &start_tree, in wnd_find()
1105 if (wnd->uptodated == 1) { in wnd_find()
1114 sb = wnd->sb; in wnd_find()
1127 if (max_alloc == wnd->nbits) { in wnd_find()
1128 nwnd = wnd->nwnd; in wnd_find()
1132 nwnd = likely(t > max_alloc) ? (t >> log2_bits) : wnd->nwnd; in wnd_find()
1139 if (!wnd->free_bits[iw]) { in wnd_find()
1152 if (max_alloc == wnd->nbits) { in wnd_find()
1153 wbits = wnd->bits_last; in wnd_find()
1164 if (wnd->zone_end > wnd->zone_bit) { in wnd_find()
1166 zbit = max(wnd->zone_bit, wbit); in wnd_find()
1167 zend = min(wnd->zone_end, ebit); in wnd_find()
1177 if (wnd->free_bits[iw] == wzend - wzbit) { in wnd_find()
1184 bh = wnd_map(wnd, iw); in wnd_find()
1228 if (!wpos && fbits_valid && wnd->free_bits[iw] == wbits) { in wnd_find()
1242 bh = wnd_map(wnd, iw); in wnd_find()
1282 wnd->extent_max = b_len; in wnd_find()
1293 if (wnd_set_used(wnd, fnd, to_alloc)) in wnd_find()
1295 } else if (wnd->extent_max != MINUS_ONE_T && in wnd_find()
1296 to_alloc > wnd->extent_max) { in wnd_find()
1297 wnd->extent_max = to_alloc; in wnd_find()
1310 int wnd_extend(struct wnd_bitmap *wnd, size_t new_bits) in wnd_extend() argument
1313 struct super_block *sb = wnd->sb; in wnd_extend()
1319 size_t old_bits = wnd->nbits; in wnd_extend()
1331 if (new_wnd != wnd->nwnd) { in wnd_extend()
1336 if (new_free != wnd->free_bits) in wnd_extend()
1337 memcpy(new_free, wnd->free_bits, in wnd_extend()
1338 wnd->nwnd * sizeof(short)); in wnd_extend()
1339 memset(new_free + wnd->nwnd, 0, in wnd_extend()
1340 (new_wnd - wnd->nwnd) * sizeof(short)); in wnd_extend()
1341 kfree(wnd->free_bits); in wnd_extend()
1342 wnd->free_bits = new_free; in wnd_extend()
1362 err = ntfs_vbo_to_lbo(sbi, &wnd->run, vbo, &lbo, &bytes); in wnd_extend()
1375 wnd->total_zeroes += frb - wnd->free_bits[iw]; in wnd_extend()
1376 wnd->free_bits[iw] = frb; in wnd_extend()
1387 wnd->nbits = new_bits; in wnd_extend()
1388 wnd->nwnd = new_wnd; in wnd_extend()
1389 wnd->bits_last = new_last; in wnd_extend()
1391 wnd_add_free_ext(wnd, old_bits, new_bits - old_bits, false); in wnd_extend()
1396 void wnd_zone_set(struct wnd_bitmap *wnd, size_t lcn, size_t len) in wnd_zone_set() argument
1400 zlen = wnd->zone_end - wnd->zone_bit; in wnd_zone_set()
1402 wnd_add_free_ext(wnd, wnd->zone_bit, zlen, false); in wnd_zone_set()
1404 if (!RB_EMPTY_ROOT(&wnd->start_tree) && len) in wnd_zone_set()
1405 wnd_remove_free_ext(wnd, lcn, len); in wnd_zone_set()
1407 wnd->zone_bit = lcn; in wnd_zone_set()
1408 wnd->zone_end = lcn + len; in wnd_zone_set()
1415 struct wnd_bitmap *wnd = &sbi->used.bitmap; in ntfs_trim_fs() local
1429 lcn_to = wnd->nbits; in ntfs_trim_fs()
1433 down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS); in ntfs_trim_fs()
1435 for (; iw < wnd->nbits; iw++, wbit = 0) { in ntfs_trim_fs()
1442 if (!wnd->free_bits[iw]) in ntfs_trim_fs()
1445 if (iw + 1 == wnd->nwnd) in ntfs_trim_fs()
1446 wbits = wnd->bits_last; in ntfs_trim_fs()
1451 bh = wnd_map(wnd, iw); in ntfs_trim_fs()
1488 up_read(&wnd->rw_lock); in ntfs_trim_fs()