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);
123 void wnd_close(struct wnd_bitmap *wnd) in wnd_close() argument
127 kfree(wnd->free_bits); in wnd_close()
128 wnd->free_bits = NULL; in wnd_close()
129 run_close(&wnd->run); in wnd_close()
131 node = rb_first(&wnd->start_tree); in wnd_close()
135 rb_erase(node, &wnd->start_tree); in wnd_close()
231 static void wnd_add_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len, in wnd_add_free_ext() argument
240 if (wnd->count >= NTFS_MAX_WND_EXTENTS && in wnd_add_free_ext()
241 len <= wnd->extent_min) { in wnd_add_free_ext()
242 wnd->uptodated = -1; in wnd_add_free_ext()
247 n = rb_lookup(&wnd->start_tree, bit); in wnd_add_free_ext()
250 n = rb_first(&wnd->start_tree); in wnd_add_free_ext()
258 rb_erase(&e->start.node, &wnd->start_tree); in wnd_add_free_ext()
259 rb_erase(&e->count.node, &wnd->count_tree); in wnd_add_free_ext()
260 wnd->count -= 1; in wnd_add_free_ext()
277 rb_erase(&e->start.node, &wnd->start_tree); in wnd_add_free_ext()
278 rb_erase(&e->count.node, &wnd->count_tree); in wnd_add_free_ext()
279 wnd->count -= 1; in wnd_add_free_ext()
287 if (wnd->uptodated != 1) { in wnd_add_free_ext()
289 ib = wnd->zone_bit == wnd->zone_end || in wnd_add_free_ext()
290 bit < wnd->zone_end ? in wnd_add_free_ext()
292 wnd->zone_end; in wnd_add_free_ext()
294 while (bit > ib && wnd_is_free_hlp(wnd, bit - 1, 1)) { in wnd_add_free_ext()
300 ib = wnd->zone_bit == wnd->zone_end || in wnd_add_free_ext()
301 end_in > wnd->zone_bit ? in wnd_add_free_ext()
302 wnd->nbits : in wnd_add_free_ext()
303 wnd->zone_bit; in wnd_add_free_ext()
305 while (end_in < ib && wnd_is_free_hlp(wnd, end_in, 1)) { in wnd_add_free_ext()
312 if (wnd->count >= NTFS_MAX_WND_EXTENTS) { in wnd_add_free_ext()
316 wnd->uptodated = -1; in wnd_add_free_ext()
319 n = rb_last(&wnd->count_tree); in wnd_add_free_ext()
330 wnd->extent_min = e2->count.key; in wnd_add_free_ext()
334 rb_erase(&e->start.node, &wnd->start_tree); in wnd_add_free_ext()
335 rb_erase(&e->count.node, &wnd->count_tree); in wnd_add_free_ext()
336 wnd->count -= 1; in wnd_add_free_ext()
340 wnd->uptodated = -1; in wnd_add_free_ext()
344 if (build && len <= wnd->extent_min) in wnd_add_free_ext()
345 wnd->extent_min = len; in wnd_add_free_ext()
349 if (len > wnd->extent_max) in wnd_add_free_ext()
350 wnd->extent_max = len; in wnd_add_free_ext()
352 rb_insert_start(&wnd->start_tree, e); in wnd_add_free_ext()
353 rb_insert_count(&wnd->count_tree, e); in wnd_add_free_ext()
354 wnd->count += 1; in wnd_add_free_ext()
362 static void wnd_remove_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len) in wnd_remove_free_ext() argument
370 n = rb_lookup(&wnd->start_tree, bit); in wnd_remove_free_ext()
399 if (e3->count.key == wnd->extent_max) in wnd_remove_free_ext()
405 rb_erase(&e3->count.node, &wnd->count_tree); in wnd_remove_free_ext()
407 rb_insert_count(&wnd->count_tree, e3); in wnd_remove_free_ext()
412 rb_erase(&e3->start.node, &wnd->start_tree); in wnd_remove_free_ext()
413 rb_erase(&e3->count.node, &wnd->count_tree); in wnd_remove_free_ext()
414 wnd->count -= 1; in wnd_remove_free_ext()
419 n3 = rb_first(&wnd->count_tree); in wnd_remove_free_ext()
420 wnd->extent_max = in wnd_remove_free_ext()
426 if (e->count.key != wnd->extent_max) { in wnd_remove_free_ext()
434 wnd->extent_max = max_new_len; in wnd_remove_free_ext()
437 wnd->extent_max = max(e3->count.key, max_new_len); in wnd_remove_free_ext()
444 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
446 rb_insert_count(&wnd->count_tree, e); in wnd_remove_free_ext()
448 rb_erase(&e->start.node, &wnd->start_tree); in wnd_remove_free_ext()
449 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
450 wnd->count -= 1; in wnd_remove_free_ext()
455 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
457 rb_insert_count(&wnd->count_tree, e); in wnd_remove_free_ext()
462 if (wnd->count >= NTFS_MAX_WND_EXTENTS) { in wnd_remove_free_ext()
463 wnd->uptodated = -1; in wnd_remove_free_ext()
466 e = rb_entry(rb_last(&wnd->count_tree), struct e_node, in wnd_remove_free_ext()
472 rb_erase(&e->start.node, &wnd->start_tree); in wnd_remove_free_ext()
473 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
474 wnd->count -= 1; in wnd_remove_free_ext()
478 wnd->uptodated = -1; in wnd_remove_free_ext()
484 rb_insert_start(&wnd->start_tree, e); in wnd_remove_free_ext()
485 rb_insert_count(&wnd->count_tree, e); in wnd_remove_free_ext()
486 wnd->count += 1; in wnd_remove_free_ext()
490 if (!wnd->count && 1 != wnd->uptodated) in wnd_remove_free_ext()
491 wnd_rescan(wnd); in wnd_remove_free_ext()
497 static int wnd_rescan(struct wnd_bitmap *wnd) in wnd_rescan() argument
501 struct super_block *sb = wnd->sb; in wnd_rescan()
512 wnd->uptodated = 0; in wnd_rescan()
513 wnd->extent_max = 0; in wnd_rescan()
514 wnd->extent_min = MINUS_ONE_T; in wnd_rescan()
515 wnd->total_zeroes = 0; in wnd_rescan()
519 for (iw = 0; iw < wnd->nwnd; iw++) { in wnd_rescan()
520 if (iw + 1 == wnd->nwnd) in wnd_rescan()
521 wbits = wnd->bits_last; in wnd_rescan()
523 if (wnd->inited) { in wnd_rescan()
524 if (!wnd->free_bits[iw]) { in wnd_rescan()
527 wnd_add_free_ext(wnd, in wnd_rescan()
534 if (wbits == wnd->free_bits[iw]) { in wnd_rescan()
537 wnd->total_zeroes += wbits; in wnd_rescan()
545 if (!run_lookup_entry(&wnd->run, vbo >> cluster_bits, in wnd_rescan()
564 wnd->free_bits[iw] = frb; in wnd_rescan()
565 wnd->total_zeroes += frb; in wnd_rescan()
571 if (wbit + wbits > wnd->nbits) in wnd_rescan()
572 wbits = wnd->nbits - wbit; in wnd_rescan()
578 wnd_add_free_ext(wnd, wbit + wpos - prev_tail, in wnd_rescan()
598 wnd_add_free_ext(wnd, wbit + wpos - prev_tail, in wnd_rescan()
622 wnd_add_free_ext(wnd, wnd->nbits - prev_tail, prev_tail, true); in wnd_rescan()
630 if (!wnd->uptodated) in wnd_rescan()
631 wnd->uptodated = 1; in wnd_rescan()
633 if (wnd->zone_bit != wnd->zone_end) { in wnd_rescan()
634 size_t zlen = wnd->zone_end - wnd->zone_bit; in wnd_rescan()
636 wnd->zone_end = wnd->zone_bit; in wnd_rescan()
637 wnd_zone_set(wnd, wnd->zone_bit, zlen); in wnd_rescan()
644 int wnd_init(struct wnd_bitmap *wnd, struct super_block *sb, size_t nbits) in wnd_init() argument
650 init_rwsem(&wnd->rw_lock); in wnd_init()
652 wnd->sb = sb; in wnd_init()
653 wnd->nbits = nbits; in wnd_init()
654 wnd->total_zeroes = nbits; in wnd_init()
655 wnd->extent_max = MINUS_ONE_T; in wnd_init()
656 wnd->zone_bit = wnd->zone_end = 0; in wnd_init()
657 wnd->nwnd = bytes_to_block(sb, bitmap_size(nbits)); in wnd_init()
658 wnd->bits_last = nbits & (wbits - 1); in wnd_init()
659 if (!wnd->bits_last) in wnd_init()
660 wnd->bits_last = wbits; in wnd_init()
662 wnd->free_bits = in wnd_init()
663 kvmalloc_array(wnd->nwnd, sizeof(u16), GFP_KERNEL | __GFP_ZERO); in wnd_init()
665 if (!wnd->free_bits) in wnd_init()
668 err = wnd_rescan(wnd); in wnd_init()
672 wnd->inited = true; in wnd_init()
680 static struct buffer_head *wnd_map(struct wnd_bitmap *wnd, size_t iw) in wnd_map() argument
684 struct super_block *sb = wnd->sb; in wnd_map()
692 if (!run_lookup_entry(&wnd->run, vbo >> sbi->cluster_bits, &lcn, &clen, in wnd_map()
699 bh = ntfs_bread(wnd->sb, lbo >> sb->s_blocksize_bits); in wnd_map()
709 int wnd_set_free(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_set_free() argument
712 struct super_block *sb = wnd->sb; in wnd_set_free()
719 while (iw < wnd->nwnd && bits) { in wnd_set_free()
722 if (iw + 1 == wnd->nwnd) in wnd_set_free()
723 wbits = wnd->bits_last; in wnd_set_free()
728 bh = wnd_map(wnd, iw); in wnd_set_free()
738 wnd->free_bits[iw] += op; in wnd_set_free()
745 wnd->total_zeroes += op; in wnd_set_free()
751 wnd_add_free_ext(wnd, bit, bits0, false); in wnd_set_free()
759 int wnd_set_used(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_set_used() argument
762 struct super_block *sb = wnd->sb; in wnd_set_used()
769 while (iw < wnd->nwnd && bits) { in wnd_set_used()
772 if (unlikely(iw + 1 == wnd->nwnd)) in wnd_set_used()
773 wbits = wnd->bits_last; in wnd_set_used()
778 bh = wnd_map(wnd, iw); in wnd_set_used()
787 wnd->free_bits[iw] -= op; in wnd_set_used()
794 wnd->total_zeroes -= op; in wnd_set_used()
800 if (!RB_EMPTY_ROOT(&wnd->start_tree)) in wnd_set_used()
801 wnd_remove_free_ext(wnd, bit, bits0); in wnd_set_used()
815 int wnd_set_used_safe(struct wnd_bitmap *wnd, size_t bit, size_t bits, in wnd_set_used_safe() argument
823 if (wnd_is_free(wnd, bit + i, 1)) { in wnd_set_used_safe()
828 err = wnd_set_used(wnd, from, len); in wnd_set_used_safe()
838 err = wnd_set_used(wnd, from, len); in wnd_set_used_safe()
849 static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_is_free_hlp() argument
851 struct super_block *sb = wnd->sb; in wnd_is_free_hlp()
856 while (iw < wnd->nwnd && bits) { in wnd_is_free_hlp()
859 if (unlikely(iw + 1 == wnd->nwnd)) in wnd_is_free_hlp()
860 wbits = wnd->bits_last; in wnd_is_free_hlp()
865 if (wbits != wnd->free_bits[iw]) { in wnd_is_free_hlp()
867 struct buffer_head *bh = wnd_map(wnd, iw); in wnd_is_free_hlp()
892 bool wnd_is_free(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_is_free() argument
899 if (RB_EMPTY_ROOT(&wnd->start_tree)) in wnd_is_free()
902 n = rb_lookup(&wnd->start_tree, bit); in wnd_is_free()
914 ret = wnd_is_free_hlp(wnd, bit, bits); in wnd_is_free()
924 bool wnd_is_used(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_is_used() argument
927 struct super_block *sb = wnd->sb; in wnd_is_used()
935 if (RB_EMPTY_ROOT(&wnd->start_tree)) in wnd_is_used()
939 n = rb_lookup(&wnd->start_tree, end - 1); in wnd_is_used()
948 while (iw < wnd->nwnd && bits) { in wnd_is_used()
951 if (unlikely(iw + 1 == wnd->nwnd)) in wnd_is_used()
952 wbits = wnd->bits_last; in wnd_is_used()
957 if (wnd->free_bits[iw]) { in wnd_is_used()
959 struct buffer_head *bh = wnd_map(wnd, iw); in wnd_is_used()
987 size_t wnd_find(struct wnd_bitmap *wnd, size_t to_alloc, size_t hint, in wnd_find() argument
1003 size_t zeroes = wnd_zeroes(wnd); in wnd_find()
1005 zeroes -= wnd->zone_end - wnd->zone_bit; in wnd_find()
1009 if (to_alloc0 > wnd->extent_max) in wnd_find()
1012 if (to_alloc > wnd->extent_max) in wnd_find()
1013 to_alloc = wnd->extent_max; in wnd_find()
1016 if (wnd->zone_bit <= hint && hint < wnd->zone_end) in wnd_find()
1017 hint = wnd->zone_end; in wnd_find()
1019 max_alloc = wnd->nbits; in wnd_find()
1025 if (RB_EMPTY_ROOT(&wnd->start_tree)) { in wnd_find()
1026 if (wnd->uptodated == 1) { in wnd_find()
1039 cr = wnd->start_tree.rb_node; in wnd_find()
1088 e = rb_entry(rb_first(&wnd->count_tree), struct e_node, count.node); in wnd_find()
1089 if (e->count.key != wnd->extent_max) in wnd_find()
1090 wnd->extent_max = e->count.key; in wnd_find()
1101 } else if (-1 != wnd->uptodated) { in wnd_find()
1108 memcpy(&start_tree, &wnd->start_tree, in wnd_find()
1110 memset(&wnd->start_tree, 0, sizeof(struct rb_root)); in wnd_find()
1117 if (!wnd_is_free(wnd, op, 1)) in wnd_find()
1120 memcpy(&wnd->start_tree, &start_tree, in wnd_find()
1132 if (wnd->uptodated == 1) { in wnd_find()
1141 sb = wnd->sb; in wnd_find()
1154 if (max_alloc == wnd->nbits) { in wnd_find()
1155 nwnd = wnd->nwnd; in wnd_find()
1159 nwnd = likely(t > max_alloc) ? (t >> log2_bits) : wnd->nwnd; in wnd_find()
1166 if (!wnd->free_bits[iw]) { in wnd_find()
1179 if (max_alloc == wnd->nbits) { in wnd_find()
1180 wbits = wnd->bits_last; in wnd_find()
1191 if (wnd->zone_end > wnd->zone_bit) { in wnd_find()
1193 zbit = max(wnd->zone_bit, wbit); in wnd_find()
1194 zend = min(wnd->zone_end, ebit); in wnd_find()
1204 if (wnd->free_bits[iw] == wzend - wzbit) { in wnd_find()
1211 bh = wnd_map(wnd, iw); in wnd_find()
1254 if (!wpos && fbits_valid && wnd->free_bits[iw] == wbits) { in wnd_find()
1268 bh = wnd_map(wnd, iw); in wnd_find()
1306 wnd->extent_max = b_len; in wnd_find()
1317 if (wnd_set_used(wnd, fnd, to_alloc)) in wnd_find()
1319 } else if (wnd->extent_max != MINUS_ONE_T && in wnd_find()
1320 to_alloc > wnd->extent_max) { in wnd_find()
1321 wnd->extent_max = to_alloc; in wnd_find()
1334 int wnd_extend(struct wnd_bitmap *wnd, size_t new_bits) in wnd_extend() argument
1337 struct super_block *sb = wnd->sb; in wnd_extend()
1343 size_t old_bits = wnd->nbits; in wnd_extend()
1355 if (new_wnd != wnd->nwnd) { in wnd_extend()
1360 memcpy(new_free, wnd->free_bits, wnd->nwnd * sizeof(short)); in wnd_extend()
1361 memset(new_free + wnd->nwnd, 0, in wnd_extend()
1362 (new_wnd - wnd->nwnd) * sizeof(short)); in wnd_extend()
1363 kfree(wnd->free_bits); in wnd_extend()
1364 wnd->free_bits = new_free; in wnd_extend()
1383 err = ntfs_vbo_to_lbo(sbi, &wnd->run, vbo, &lbo, &bytes); in wnd_extend()
1395 wnd->total_zeroes += frb - wnd->free_bits[iw]; in wnd_extend()
1396 wnd->free_bits[iw] = frb; in wnd_extend()
1407 wnd->nbits = new_bits; in wnd_extend()
1408 wnd->nwnd = new_wnd; in wnd_extend()
1409 wnd->bits_last = new_last; in wnd_extend()
1411 wnd_add_free_ext(wnd, old_bits, new_bits - old_bits, false); in wnd_extend()
1416 void wnd_zone_set(struct wnd_bitmap *wnd, size_t lcn, size_t len) in wnd_zone_set() argument
1418 size_t zlen = wnd->zone_end - wnd->zone_bit; in wnd_zone_set()
1421 wnd_add_free_ext(wnd, wnd->zone_bit, zlen, false); in wnd_zone_set()
1423 if (!RB_EMPTY_ROOT(&wnd->start_tree) && len) in wnd_zone_set()
1424 wnd_remove_free_ext(wnd, lcn, len); in wnd_zone_set()
1426 wnd->zone_bit = lcn; in wnd_zone_set()
1427 wnd->zone_end = lcn + len; in wnd_zone_set()
1434 struct wnd_bitmap *wnd = &sbi->used.bitmap; in ntfs_trim_fs() local
1447 lcn_to = wnd->nbits; in ntfs_trim_fs()
1451 down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS); in ntfs_trim_fs()
1453 for (; iw < wnd->nwnd; iw++, wbit = 0) { in ntfs_trim_fs()
1460 if (!wnd->free_bits[iw]) in ntfs_trim_fs()
1463 if (iw + 1 == wnd->nwnd) in ntfs_trim_fs()
1464 wbits = wnd->bits_last; in ntfs_trim_fs()
1469 bh = wnd_map(wnd, iw); in ntfs_trim_fs()
1504 up_read(&wnd->rw_lock); in ntfs_trim_fs()