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 run_close(&wnd->run); in wnd_close()
130 node = rb_first(&wnd->start_tree); in wnd_close()
134 rb_erase(node, &wnd->start_tree); in wnd_close()
230 static void wnd_add_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len, in wnd_add_free_ext() argument
239 if (wnd->count >= NTFS_MAX_WND_EXTENTS && in wnd_add_free_ext()
240 len <= wnd->extent_min) { in wnd_add_free_ext()
241 wnd->uptodated = -1; in wnd_add_free_ext()
246 n = rb_lookup(&wnd->start_tree, bit); in wnd_add_free_ext()
249 n = rb_first(&wnd->start_tree); in wnd_add_free_ext()
257 rb_erase(&e->start.node, &wnd->start_tree); in wnd_add_free_ext()
258 rb_erase(&e->count.node, &wnd->count_tree); in wnd_add_free_ext()
259 wnd->count -= 1; in wnd_add_free_ext()
276 rb_erase(&e->start.node, &wnd->start_tree); in wnd_add_free_ext()
277 rb_erase(&e->count.node, &wnd->count_tree); in wnd_add_free_ext()
278 wnd->count -= 1; in wnd_add_free_ext()
286 if (wnd->uptodated != 1) { in wnd_add_free_ext()
288 ib = wnd->zone_bit == wnd->zone_end || in wnd_add_free_ext()
289 bit < wnd->zone_end in wnd_add_free_ext()
291 : wnd->zone_end; in wnd_add_free_ext()
293 while (bit > ib && wnd_is_free_hlp(wnd, bit - 1, 1)) { in wnd_add_free_ext()
299 ib = wnd->zone_bit == wnd->zone_end || in wnd_add_free_ext()
300 end_in > wnd->zone_bit in wnd_add_free_ext()
301 ? wnd->nbits in wnd_add_free_ext()
302 : wnd->zone_bit; in wnd_add_free_ext()
304 while (end_in < ib && wnd_is_free_hlp(wnd, end_in, 1)) { in wnd_add_free_ext()
311 if (wnd->count >= NTFS_MAX_WND_EXTENTS) { in wnd_add_free_ext()
315 wnd->uptodated = -1; in wnd_add_free_ext()
318 n = rb_last(&wnd->count_tree); in wnd_add_free_ext()
329 wnd->extent_min = e2->count.key; in wnd_add_free_ext()
333 rb_erase(&e->start.node, &wnd->start_tree); in wnd_add_free_ext()
334 rb_erase(&e->count.node, &wnd->count_tree); in wnd_add_free_ext()
335 wnd->count -= 1; in wnd_add_free_ext()
339 wnd->uptodated = -1; in wnd_add_free_ext()
343 if (build && len <= wnd->extent_min) in wnd_add_free_ext()
344 wnd->extent_min = len; in wnd_add_free_ext()
348 if (len > wnd->extent_max) in wnd_add_free_ext()
349 wnd->extent_max = len; in wnd_add_free_ext()
351 rb_insert_start(&wnd->start_tree, e); in wnd_add_free_ext()
352 rb_insert_count(&wnd->count_tree, e); in wnd_add_free_ext()
353 wnd->count += 1; in wnd_add_free_ext()
361 static void wnd_remove_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len) in wnd_remove_free_ext() argument
369 n = rb_lookup(&wnd->start_tree, bit); in wnd_remove_free_ext()
398 if (e3->count.key == wnd->extent_max) in wnd_remove_free_ext()
404 rb_erase(&e3->count.node, &wnd->count_tree); in wnd_remove_free_ext()
406 rb_insert_count(&wnd->count_tree, e3); in wnd_remove_free_ext()
411 rb_erase(&e3->start.node, &wnd->start_tree); in wnd_remove_free_ext()
412 rb_erase(&e3->count.node, &wnd->count_tree); in wnd_remove_free_ext()
413 wnd->count -= 1; in wnd_remove_free_ext()
418 n3 = rb_first(&wnd->count_tree); in wnd_remove_free_ext()
419 wnd->extent_max = in wnd_remove_free_ext()
425 if (e->count.key != wnd->extent_max) { in wnd_remove_free_ext()
433 wnd->extent_max = max_new_len; in wnd_remove_free_ext()
436 wnd->extent_max = max(e3->count.key, max_new_len); in wnd_remove_free_ext()
443 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
445 rb_insert_count(&wnd->count_tree, e); in wnd_remove_free_ext()
447 rb_erase(&e->start.node, &wnd->start_tree); in wnd_remove_free_ext()
448 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
449 wnd->count -= 1; in wnd_remove_free_ext()
454 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
456 rb_insert_count(&wnd->count_tree, e); in wnd_remove_free_ext()
461 if (wnd->count >= NTFS_MAX_WND_EXTENTS) { in wnd_remove_free_ext()
462 wnd->uptodated = -1; in wnd_remove_free_ext()
465 e = rb_entry(rb_last(&wnd->count_tree), struct e_node, in wnd_remove_free_ext()
471 rb_erase(&e->start.node, &wnd->start_tree); in wnd_remove_free_ext()
472 rb_erase(&e->count.node, &wnd->count_tree); in wnd_remove_free_ext()
473 wnd->count -= 1; in wnd_remove_free_ext()
477 wnd->uptodated = -1; in wnd_remove_free_ext()
483 rb_insert_start(&wnd->start_tree, e); in wnd_remove_free_ext()
484 rb_insert_count(&wnd->count_tree, e); in wnd_remove_free_ext()
485 wnd->count += 1; in wnd_remove_free_ext()
489 if (!wnd->count && 1 != wnd->uptodated) in wnd_remove_free_ext()
490 wnd_rescan(wnd); in wnd_remove_free_ext()
496 static int wnd_rescan(struct wnd_bitmap *wnd) in wnd_rescan() argument
500 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()
566 wnd->free_bits[iw] = frb; in wnd_rescan()
567 wnd->total_zeroes += frb; in wnd_rescan()
573 if (wbit + wbits > wnd->nbits) in wnd_rescan()
574 wbits = wnd->nbits - wbit; in wnd_rescan()
580 wnd_add_free_ext(wnd, wbit + wpos - prev_tail, in wnd_rescan()
600 wnd_add_free_ext(wnd, wbit + wpos - prev_tail, in wnd_rescan()
624 wnd_add_free_ext(wnd, wnd->nbits - prev_tail, prev_tail, true); in wnd_rescan()
632 if (!wnd->uptodated) in wnd_rescan()
633 wnd->uptodated = 1; in wnd_rescan()
635 if (wnd->zone_bit != wnd->zone_end) { in wnd_rescan()
636 size_t zlen = wnd->zone_end - wnd->zone_bit; in wnd_rescan()
638 wnd->zone_end = wnd->zone_bit; in wnd_rescan()
639 wnd_zone_set(wnd, wnd->zone_bit, zlen); in wnd_rescan()
646 int wnd_init(struct wnd_bitmap *wnd, struct super_block *sb, size_t nbits) in wnd_init() argument
652 init_rwsem(&wnd->rw_lock); in wnd_init()
654 wnd->sb = sb; in wnd_init()
655 wnd->nbits = nbits; in wnd_init()
656 wnd->total_zeroes = nbits; in wnd_init()
657 wnd->extent_max = MINUS_ONE_T; in wnd_init()
658 wnd->zone_bit = wnd->zone_end = 0; in wnd_init()
659 wnd->nwnd = bytes_to_block(sb, bitmap_size(nbits)); in wnd_init()
660 wnd->bits_last = nbits & (wbits - 1); in wnd_init()
661 if (!wnd->bits_last) in wnd_init()
662 wnd->bits_last = wbits; in wnd_init()
664 wnd->free_bits = kcalloc(wnd->nwnd, sizeof(u16), GFP_NOFS); 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()
723 if (iw + 1 == wnd->nwnd) in wnd_set_free()
724 wbits = wnd->bits_last; in wnd_set_free()
729 bh = wnd_map(wnd, iw); in wnd_set_free()
741 wnd->free_bits[iw] += op; in wnd_set_free()
748 wnd->total_zeroes += op; in wnd_set_free()
754 wnd_add_free_ext(wnd, bit, bits0, false); in wnd_set_free()
762 int wnd_set_used(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_set_used() argument
765 struct super_block *sb = wnd->sb; in wnd_set_used()
772 while (iw < wnd->nwnd && bits) { in wnd_set_used()
776 if (unlikely(iw + 1 == wnd->nwnd)) in wnd_set_used()
777 wbits = wnd->bits_last; in wnd_set_used()
782 bh = wnd_map(wnd, iw); in wnd_set_used()
792 wnd->free_bits[iw] -= op; in wnd_set_used()
799 wnd->total_zeroes -= op; in wnd_set_used()
805 if (!RB_EMPTY_ROOT(&wnd->start_tree)) in wnd_set_used()
806 wnd_remove_free_ext(wnd, bit, bits0); in wnd_set_used()
816 static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_is_free_hlp() argument
818 struct super_block *sb = wnd->sb; in wnd_is_free_hlp()
823 while (iw < wnd->nwnd && bits) { in wnd_is_free_hlp()
826 if (unlikely(iw + 1 == wnd->nwnd)) in wnd_is_free_hlp()
827 wbits = wnd->bits_last; in wnd_is_free_hlp()
832 if (wbits != wnd->free_bits[iw]) { in wnd_is_free_hlp()
834 struct buffer_head *bh = wnd_map(wnd, iw); in wnd_is_free_hlp()
859 bool wnd_is_free(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_is_free() argument
866 if (RB_EMPTY_ROOT(&wnd->start_tree)) in wnd_is_free()
869 n = rb_lookup(&wnd->start_tree, bit); in wnd_is_free()
881 ret = wnd_is_free_hlp(wnd, bit, bits); in wnd_is_free()
891 bool wnd_is_used(struct wnd_bitmap *wnd, size_t bit, size_t bits) in wnd_is_used() argument
894 struct super_block *sb = wnd->sb; in wnd_is_used()
902 if (RB_EMPTY_ROOT(&wnd->start_tree)) in wnd_is_used()
906 n = rb_lookup(&wnd->start_tree, end - 1); in wnd_is_used()
915 while (iw < wnd->nwnd && bits) { in wnd_is_used()
918 if (unlikely(iw + 1 == wnd->nwnd)) in wnd_is_used()
919 wbits = wnd->bits_last; in wnd_is_used()
924 if (wnd->free_bits[iw]) { in wnd_is_used()
926 struct buffer_head *bh = wnd_map(wnd, iw); in wnd_is_used()
954 size_t wnd_find(struct wnd_bitmap *wnd, size_t to_alloc, size_t hint, in wnd_find() argument
971 size_t zeroes = wnd_zeroes(wnd); in wnd_find()
973 zeroes -= wnd->zone_end - wnd->zone_bit; in wnd_find()
977 if (to_alloc0 > wnd->extent_max) in wnd_find()
980 if (to_alloc > wnd->extent_max) in wnd_find()
981 to_alloc = wnd->extent_max; in wnd_find()
984 if (wnd->zone_bit <= hint && hint < wnd->zone_end) in wnd_find()
985 hint = wnd->zone_end; in wnd_find()
987 max_alloc = wnd->nbits; in wnd_find()
993 if (RB_EMPTY_ROOT(&wnd->start_tree)) { in wnd_find()
994 if (wnd->uptodated == 1) { in wnd_find()
1007 cr = wnd->start_tree.rb_node; in wnd_find()
1056 e = rb_entry(rb_first(&wnd->count_tree), struct e_node, count.node); in wnd_find()
1057 if (e->count.key != wnd->extent_max) in wnd_find()
1058 wnd->extent_max = e->count.key; in wnd_find()
1069 } else if (-1 != wnd->uptodated) { in wnd_find()
1076 memcpy(&start_tree, &wnd->start_tree, in wnd_find()
1078 memset(&wnd->start_tree, 0, sizeof(struct rb_root)); in wnd_find()
1085 if (!wnd_is_free(wnd, op, 1)) in wnd_find()
1088 memcpy(&wnd->start_tree, &start_tree, in wnd_find()
1100 if (wnd->uptodated == 1) { in wnd_find()
1109 sb = wnd->sb; in wnd_find()
1122 if (max_alloc == wnd->nbits) { in wnd_find()
1123 nwnd = wnd->nwnd; in wnd_find()
1127 nwnd = likely(t > max_alloc) ? (t >> log2_bits) : wnd->nwnd; in wnd_find()
1134 if (!wnd->free_bits[iw]) { in wnd_find()
1147 if (max_alloc == wnd->nbits) { in wnd_find()
1148 wbits = wnd->bits_last; in wnd_find()
1159 if (wnd->zone_end > wnd->zone_bit) { in wnd_find()
1161 zbit = max(wnd->zone_bit, wbit); in wnd_find()
1162 zend = min(wnd->zone_end, ebit); in wnd_find()
1172 if (wnd->free_bits[iw] == wzend - wzbit) { in wnd_find()
1179 bh = wnd_map(wnd, iw); in wnd_find()
1223 if (!wpos && fbits_valid && wnd->free_bits[iw] == wbits) { in wnd_find()
1237 bh = wnd_map(wnd, iw); in wnd_find()
1277 wnd->extent_max = b_len; in wnd_find()
1288 if (wnd_set_used(wnd, fnd, to_alloc)) in wnd_find()
1290 } else if (wnd->extent_max != MINUS_ONE_T && in wnd_find()
1291 to_alloc > wnd->extent_max) { in wnd_find()
1292 wnd->extent_max = to_alloc; in wnd_find()
1305 int wnd_extend(struct wnd_bitmap *wnd, size_t new_bits) in wnd_extend() argument
1308 struct super_block *sb = wnd->sb; in wnd_extend()
1314 size_t old_bits = wnd->nbits; in wnd_extend()
1326 if (new_wnd != wnd->nwnd) { in wnd_extend()
1331 memcpy(new_free, wnd->free_bits, wnd->nwnd * sizeof(short)); in wnd_extend()
1332 memset(new_free + wnd->nwnd, 0, in wnd_extend()
1333 (new_wnd - wnd->nwnd) * sizeof(short)); in wnd_extend()
1334 kfree(wnd->free_bits); in wnd_extend()
1335 wnd->free_bits = new_free; in wnd_extend()
1355 err = ntfs_vbo_to_lbo(sbi, &wnd->run, vbo, &lbo, &bytes); in wnd_extend()
1368 wnd->total_zeroes += frb - wnd->free_bits[iw]; in wnd_extend()
1369 wnd->free_bits[iw] = frb; in wnd_extend()
1380 wnd->nbits = new_bits; in wnd_extend()
1381 wnd->nwnd = new_wnd; in wnd_extend()
1382 wnd->bits_last = new_last; in wnd_extend()
1384 wnd_add_free_ext(wnd, old_bits, new_bits - old_bits, false); in wnd_extend()
1389 void wnd_zone_set(struct wnd_bitmap *wnd, size_t lcn, size_t len) in wnd_zone_set() argument
1391 size_t zlen = wnd->zone_end - wnd->zone_bit; in wnd_zone_set()
1394 wnd_add_free_ext(wnd, wnd->zone_bit, zlen, false); in wnd_zone_set()
1396 if (!RB_EMPTY_ROOT(&wnd->start_tree) && len) in wnd_zone_set()
1397 wnd_remove_free_ext(wnd, lcn, len); in wnd_zone_set()
1399 wnd->zone_bit = lcn; in wnd_zone_set()
1400 wnd->zone_end = lcn + len; in wnd_zone_set()
1407 struct wnd_bitmap *wnd = &sbi->used.bitmap; in ntfs_trim_fs() local
1421 lcn_to = wnd->nbits; in ntfs_trim_fs()
1425 down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS); in ntfs_trim_fs()
1427 for (; iw < wnd->nbits; iw++, wbit = 0) { in ntfs_trim_fs()
1434 if (!wnd->free_bits[iw]) in ntfs_trim_fs()
1437 if (iw + 1 == wnd->nwnd) in ntfs_trim_fs()
1438 wbits = wnd->bits_last; in ntfs_trim_fs()
1443 bh = wnd_map(wnd, iw); in ntfs_trim_fs()
1480 up_read(&wnd->rw_lock); in ntfs_trim_fs()