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